Ab heute habe ich bis einschließlich zum 4. Oktober Semesterferien, bevor die Vorlesungen wieder beginnen. Zwischenzeitlich werde ich für eine Woche im Urlaub sein, sowie nebenbei Arbeiten gehen, so dass mit nicht all zu vielen Einträgen zu rechnen ist. 
Vorab schon einmal die Information, dass es einen kleinen Bericht Ende August auf jedenfall über die ICE in Lingen geben wird.
Die Semesterferien stehen kurz vor der Tür. Nächste Woche steht die Klausurphase noch an und dann beginnen endlich die Ferien. Daher ist es Zeit einen Rückblick auf das 2. Semester zu werfen:
Algorithmen und Programmierung 2:
AP2 war im 2. Semester das interessanteste Fach überhaupt, vermutlich lag es auch an unserem Dozenten, der sich nicht nur während der Vorlesung alle Mühe gab, sondern dazu eine sehr gute Betreuung während den Praktika leistete.
Hauptsächlich drehte sich in AP2 alles um Java und die objektorientierte Programmierung. Dabei ging es um polymorphe Algorithmen und Datenstrukturen, sowie um abstrakte Klassen und verkettete Listen. Hinzu kamen die Themen rund um die Iteratoren, Stacks und Queues. Das Ganze wurde zum Semesterende mit dem Themen Bereich Such- und Sortieralgorithmen abgerundet und beendet. Hier lernte man neben einfachen Suchen, auch die Implementierung der Breiten-, Tiefen-, und Binärsuche kennen. Komplexer wurde es dann bei der Implementierung von den Suchalgorithmen. Hier kannte man bisher hauptsächlich die Bubblesort-Methode, welche mit einer Laufzeit von O(n²) nicht wirklich schnell ist im Vergleich zu Quick- und Mergesort. Die beiden zuletzt genannten Suchalgorithmen sind in ihrer Ausführung sehr effizient und erreichen fast immer eine Laufzeit von O(n*log n).
Paradigmen der Programmierung:
In PP hatten wir denselben Dozenten wie in AP2. Daher braucht man an dieser Stelle nicht mehr viel zur Durchführung der Vorlesung zu sagen.
Die PP Vorlesung war durch die Einführung in funktionale sowie logische Programmiersprachen geprägt. Hierfür wurden Scheme und Prolog verwendet. Hinzu kamen noch die Themen Prädikatenlogik und die Einführung in generische Datentypen. Zum Abschluss lernten wir die Implementierung des Backtracking-Verfahrens in Prolog und Java auf Basis des Damenproblems kennen.
BWL 2:
Auch hier hatten wir einen guten Dozenten, der es immer wieder mit Witzen und Anekdoten schaffte die Aufmerksamkeit der Studenten bei dem trockenen Thema Rechnungswesen zu wecken. Die folgende kurze Auflistung soll einen Überblick über die behandelten Themen geben:
Mathematik 2:
Mathematik 2 beinhaltete sehr interessante Themenblöcke für das 2. Semester. Besonders gefallen haben mir „Funktionen mehrerer Verändlicher“ mit den untergeordneten Themen: Totales Differential, LS-Methode und Lagrange. Sehr großes Interesse hat der Themenblock Graphentheorie bei mir geweckt. Einige der in diesem Block behandelten Themen waren der Euler-Zug, der Shannon-Fano & Huffman-Code, der Algorithmus von Kruskal und der Algorithmus von Dijkstra. Leider wurde während des Semesters mit Beginn des Themas Statistik der Dozent gewechselt, da sich unser bisheriger Dozent stärker der Forschung widmen wollte. In diesen Sinne kam es wie es kommen musste und was ich schon befürchtet hatte, die Qualität der Vorlesung nahm deutlich ab und die recht interessanten Themen der Statistik, der Komplexen Zahlen sowie der Differentialgleichung wurden mit, so schien es mir zu mindestens, weniger Einsatz gelehrt. Daher saß ich in den folgenden Vorlesungen auch weniger interessiert im Hörsaal.
Theoretische Informatik:
Nachdem das 1. Semester noch relativ uninteressant für mich war, da ich die Themen schon kannte, zog der Schwierigkeitsgrad im 2. Semester doch schon ordentlich an. Zu den großen Themenblöcken zählten Reguläre Sprachen, kontextfreie Sprachen (Stapel-Kellerautomaten, Parser, nicht deterministische und deterministische Kellerautomaten) und kontextsensitive Sprachen (Typ-1 und Typ-0 Grammatiken, Turingautomaten). Leider konnte der Dozent auch hier nicht die Themen interessant genug vermitteln.
Die Aufgabenblätter sind hier zu finden: http://www.gm.fh-koeln.de/~ehses/ap/index.html
Aufgabe 1:
Node.java:
package search.util;
public class Node {
public Object value;
public Node next;
Node (Object value, Node next) {
this.value = value;
this.next = next;
}
}
ConcatenateList.java:
package search.util;
import java.util.Comparator;
public class ConcatenateList {
private Node first = null;
public boolean isEmpty() {
return first == null;
}
public Object removeFirst() {
Object retValue = first.value;
first = first.next;
return retValue;
}
public void addLast(Object o) {
Node newNode = new Node(o, null);
if (first == null) {
first = newNode;
}
else {
Node temp = first;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
}
public void clear() {
first = null;
}
public void add(Object o, Comparator cmp) {
if ( isEmpty() ) {
first = new Node(o, null);
}
else {
Node temp = first;
Node temp_prev = null;
while ( temp != null && cmp.compare(o, temp.value) > 0 ) {
temp_prev = temp;
temp = temp.next;
}
if (temp == null) {
temp_prev.next = new Node (o, null);
}
else if (temp == first){
first = new Node (o, temp);
}
else{
temp_prev.next = new Node (o, temp);
}
}
}
public Object removeLast() {
Node temp = first;
Node temp_prev = null;
while (temp.next != null) {
temp_prev = temp;
temp = temp.next;
}
if (temp == first) {
first = null;
return temp.value;
}
else {
temp_prev.next = null;
return temp.value;
}
}
}
FIFOQueue.java:
package search.util;
import java.util.NoSuchElementException;
public final class FIFOQueue implements IQueue {
private ConcatenateList snake = new ConcatenateList();
public void clear() {
snake.clear();
}
public Object get() {
if (this.isEmpty()) throw new NoSuchElementException(“Queue is empty”);
return snake.removeFirst();
}
public boolean isEmpty() {
return snake.isEmpty();
}
public void put(Object p) {
snake.addLast(p);
}
}
LIFOQueue.java:
package search.util;
import java.util.NoSuchElementException;
public final class LIFOQueue implements IQueue {
private ConcatenateList stack = new ConcatenateList();
public void clear() {
stack.clear();
}
public Object get() {
if (this.isEmpty()) throw new NoSuchElementException(“Queue is empty”);
return stack.removeLast();
}
public boolean isEmpty() {
return stack.isEmpty();
}
public void put(Object p) {
stack.addLast(p);
}
}
PriorityQueue.java:
package search.util;
import java.util.Comparator;
import java.util.NoSuchElementException;
public final class PriorityQueue implements IQueue {
private ConcatenateList prio = new ConcatenateList();
private Comparator cmp;
public PriorityQueue(Comparator cmp) {
this.cmp = cmp;
}
public void clear() {
prio.clear();
}
public Object get() {
if (this.isEmpty()) throw new NoSuchElementException(“Queue is empty”);
return prio.removeFirst();
}
public boolean isEmpty() {
return prio.isEmpty();
}
public void put(Object p) {
prio.add(p, this.cmp);
}
}
Aufgabe 3:
numberOfNodes():
public static int numberOfNodes(ITreeNode root) {
if(root==null){
return 0;
}
else{
int countNodes = 1;
for (Iterator iter = root.getChildren().iterator(); iter.hasNext();) {
ITreeNode child = (ITreeNode) iter.next();
countNodes += numberOfNodes(child);
}
return countNodes;
}
}
Aufgabe 4:
getPathToGoal():
public static List getPathToGoal(ITreeNode root, Object goalNode) {
List pathList = null;
if (root == null) {
return pathList;
}
if (goalNode.equals(root.getValue())) {
pathList = new ArrayList();
pathList.add(goalNode.toString());
return pathList;
}
for (Iterator iter = root.getChildren().iterator(); iter.hasNext();) {
ITreeNode child = (ITreeNode) iter.next();
pathList = getPathToGoal(child, goalNode);
if (pathList != null) {
pathList.add(0, root.getValue().toString());
return pathList;
}
}
return pathList;
}
Hier folgt nun meine Implementierung des Shannon-Fano Algorithmus für Maple, die wir bezüglich unseres Mathematik-Praktikums “Tag7″ programmieren sollten!
Aufgabe 1 (Shannon-Fano)
Implementieren Sie einen Algorithmus zur Shannon-Fano Kodierung und berechnen Sie eine Kodierung für das Beispiel 21.1.
Beispiel 21.1: [[a,41],[b,33],[c,23],[d,25],[e,100]]
Prozedur:
restart:
with(GraphTheory):
with(Logic):
with(networks):
##Aus dem Mapleskript zum Sortieren von Listen!
comp2 :=proc(a::list,b::list)
if a[2] < b[2] then true else false fi;
end:
##Der Graph muss vor der Prozedur initialisiert werden!
global G2:
G2:=Digraph():
########################################################################
##Prozedur Shannon-Fano!
ShaFa:=proc(L::listlist)
global prev, ECKE, KANTE, G2;
local i,j,k,l,v,S,Sl,Sr,hauf1,hauf2,hauf3,hauf4,hauf5;
##Sortierung der Liste!
S := sort( L , comp2);
##Lokale Variablen initialisieren!
hauf1:=0;
hauf2:=0;
hauf3:=0;
hauf4:=0;
hauf5:=0;
Sl:={};
Sr:={};
ECKE:={};
KANTE:={};
##Gesamthäufigkeit von S!
i:=1;
while(i<=nops(S)) do
hauf1:=hauf1+S[i][2];
i:=i+1;
od:
##Festlegen einer Grenze für die Häufigkeit, damit Sl und Sr ungefähr die gleiche Häufigkeit haben!
hauf3:=((hauf1/2))+(S[nops(S)][2]/nops(S));
##Algorithmus der S in Sl und Sr überführt!
j:=1;
while(j<=nops(S)) do
hauf2:=hauf2+S[j][2];
if(hauf2<=hauf3) then
Sl:=[op(Sl),S[j]];
fi;
if(hauf2>hauf3)then
Sr:=[op(Sr),S[j]];
fi;
j:=j+1;
od:
##Kontrolle ob auch alles funktioniert!
print(S);
print(“linkerTeilbaum:”, Sl);
print(“rechterTeilbaum:”, Sr);
##Gesamthäufigkeit von Sl! Wird beim Erstellen der Ecken und Kanten gebraucht!
k:=1;
while(k<=nops(Sl)) do
hauf4:=hauf4+Sl[k][2];
k:=k+1;
od:
##Gesamthäufigkeit von Sr! Wird beim Erstellen der Ecken und Kanten gebraucht!
l:=1;
while(l<=nops(Sr)) do
hauf5:=hauf5+Sr[l][2];
l:=l+1;
od:
##Welche Ecken sind in G2 vorhanden!
v:=Vertices(G2);
##Wenn nicht in G2, dann initialisiere die Wurzel!
if not member(hauf1, v) then
ECKE:=[op(ECKE),hauf1];
fi;
##rechter Teilbaum: Fügt entweder eine endgültige Ecke oder eine weitere Ecke hinzu, an der weitere Ecken folgen können!
if(nops(Sr)=1) then
ECKE:=[op(ECKE),Sr[1][1]];
KANTE:=[op(KANTE),[hauf1,Sr[1][1]]];
else
ECKE:=[op(ECKE), hauf5];
KANTE:=[op(KANTE),[hauf1,hauf5]];
fi;
##linker Teilbaum: Fügt entweder eine endgültige Ecke oder eine weitere Ecke hinzu, an der weitere Ecken folgen können!
if(nops(Sl)=1) then
ECKE:=[op(ECKE),Sl[1][1]];
KANTE:=[op(KANTE),[hauf1,Sl[1][1]]];
else
ECKE:=[op(ECKE),hauf4];
KANTE:=[op(KANTE),[hauf1,hauf4]];
fi;
##Kontrolle ob auch alles funktioniert!
print(“Ecken:”,ECKE);
print(“Kanten:”,KANTE);
##Die Ecken und Kanten werden dem Graphen G2 hinzugefügt!
G2:=AddVertex(G2,ECKE);
G2:=AddArc(G2, KANTE);
##rekursiver Aufruf bis Sl und Sr =1 sind!
if(nops(Sr)>1) then ShaFa(Sr); fi;
if(nops(Sl)>1) then ShaFa(Sl); fi;
##Rückgabe des Graphen G2 zum Zeichnen!
return G2;
end:
########################################################################
Aufruf:
S:=ShaFa([[a,41],[b,33],[c,23],[d,25],[e,100]]);
Graphzeichnen:
DrawGraph(S);
Die Aufgabenblätter sind hier zu finden: http://www.gm.fh-koeln.de/~ehses/ap/index.html
Bevor ihr euch die Lösungen anschaut eines vorweg: Die Lösungen dieses Praktikums dienen wirklich nur zum Vergleich oder als Hilfestellung, wenn irgendwo etwas noch hapern sollte im Programmcode.
Ihr müsst, um das Praktikum bestehen zu können, den Zusammenhang der einzelnen Klassen untereinander sowie die Sortier- und Suchalgorithmen verstanden haben und auch mit eigenen Worten im Praktikum erklären können!
Aufgabe 2a:
ConsoleLogger.java:
public final class ConsoleLogger extends AbstractLogger{
protected void logMsg(String msg, int level) {
System.out.println(composeLogMsg(msg, level));
}
public void close() {
System.out.close();
}
}
FileLogger.java:
import java.io.*;
public final class FileLogger extends AbstractLogger{
private PrintStream uebergabe;
public FileLogger(String string) throws FileNotFoundException {
uebergabe = new PrintStream(new FileOutputStream(string));
}
protected void logMsg(String msg, int level){
uebergabe.println(composeLogMsg(msg, level));
}
public void close() {
System.out.close();
}
}
Aufgabe 3b:
MyArrays.java:
static void merge(int[] src, int[] dest, int lo, int mid, int hi) {
Log.info(“src :”+arrayToString(src, lo, mid, hi));
int end_lo=mid;
int start_hi=mid;
int srclo=lo;
int destlo=lo;
while(srclo < end_lo && start_hi < hi){
if(src[srclo]<src[start_hi]){
dest[destlo++]=src[srclo++];
}
else{
dest[destlo++]=src[start_hi++];
}
}
while(srclo<end_lo){
dest[destlo++]=src[srclo++];
}
while(start_hi<hi){
dest[destlo++]=src[start_hi++];
}
Log.info(“dest:”+arrayToString(dest, lo, mid, hi));
}
//Hier noch ein dickes Dankeschön an meinen Kommilitonen für den Hinweis, dass noch eine Variable fehlte! Er weiß wer gemeint ist.
public static int binSearch(int[] feld, int x) {
int start = 0;
int end = feld.length;
int middle = (start+end)/2;
while(start<end && feld !=null){
Log.info(arrayToString(feld, start, middle, end));
if(x==feld[middle]){
Log.info(“found at ” + middle);
return middle;
}
else if(x<feld[middle]){
end = middle;
}
else {
start = middle+1;
}
middle = (start+end)/2;
}
Log.info(“not found, return value = ” + -(middle+1));
return -(middle+1);
}
Die Aufgabenblätter sind hier zu finden: http://www.gm.fh-koeln.de/~ehses/ap/index.html
Aufgabe 1:
Die Testklassen CircleTest und RectangleTest findet ihr unter Aufgabe 2!
Circle.java:
public class Circle extends AbstractShape{
private double radius;
Circle(String name, double radius){
super(name);
this.radius=radius;
}
public double getArea(){
double temp = Math.PI * radius * radius;
return temp;
}
}
Rectangle.java:
public class Rectangle extends AbstractShape{
private double laenge, breite;
Rectangle(String name, double laenge, double breite){
super(name);
this.laenge=laenge;
this.breite=breite;
}
public double getArea(){
double temp = laenge * breite;
return temp;
}
}
AbstractShape.java:
public String toString() {
return getClass().getName()+”.”+ name;
}
Aufgabe 2:
AbstractShapeTest.java:
import junit.framework.TestCase;
public class AbstractShapeTest extends TestCase {
protected IShape s1;
protected IShape s2;
protected IShape s3;
public void testArea() {
double area13 = Math.PI * 10.5 * 10.5;
double area2 = Math.PI * 11.0 * 11.0;
assertEquals(area13, s1.getArea(), 1e-7);
assertEquals(area2, s2.getArea(), 1e-7);
assertEquals(area13, s3.getArea(), 1e-7);
}
public void testName() {
assertEquals(“a”, s1.getName());
assertEquals(“b”, s2.getName());
assertEquals(“c”, s3.getName());
}
public void testCompare() {
assertEquals(0, s1.compareTo(s3));
assertEquals(0, s3.compareTo(s1));
assertTrue(s1.compareTo(s2) < 0);
assertTrue(s2.compareTo(s1) > 0);
assertTrue(s3.compareTo(s2) < 0);
assertTrue(s2.compareTo(s3) > 0);
}
public void testEquals() {
assertFalse(s1.equals(s2));
assertFalse(s1.equals(s3));
assertFalse(s3.equals(s2));
}
public void testToString() {
String className = s1.getClass().getName();
assertEquals(className+”.a”, s1.toString());
assertEquals(className+”.b”, s2.toString());
assertEquals(className+”.c”, s3.toString());
}
}
CircleTest.java:
public class CircleTest extends AbstractShapeTest {
public void setUp() {
s1 = new Circle(“a”, 10.5);
s2 = new Circle(“b”, 11.0);
s3 = new Circle(“c”, 10.5);
}
}
RectangleTest.java:
public class RectangleTest extends AbstractShapeTest {
public void setUp() {
s1 = new Rectangle(“a”, Math.PI, 10.5 * 10.5);
s2 = new Rectangle(“b”, Math.PI, 11.0 * 11.0);
s3 = new Rectangle(“c”, Math.PI, 10.5 * 10.5);
}
}
Aufgabe 3:
ShapeNameComparator.java:
import java.util.Comparator;
public class ShapeNameComparator implements Comparator{
public int compare(Object arg0, Object arg1) {
return (((IShape)arg0).getName().compareTo(((IShape)arg1).getName()));
}
}
Seit heute steht der Release Candidate von Windows 7 der Öffentlichkeit zum Download bereit!
-> http://www.microsoft.com/windows/windows-7/download.aspx
Ich werde heute noch den Release Candidate auf meinem Netbook installieren, bei meinem produktiven Notebook mit Windows Vista, warte ich noch das SP2 für Vista ab. Sollte sich durch das SP2 kein merklicher Performanceschub ergeben, so wird auch auf meinem Notebook der Release Candidate Einzug erhalten, ansonsten erst zur RTM-Version.
Desweiteren habe ich eben noch die 1. Aufgabe des dritten AP 2 Praktikums aktualisiert! Zu dem hier auch noch die Lösungen für Aufgabe 2:
public void addAddress(IAddress address) {
addresses.put(address.getNickname(), address);
}
public boolean contains(String name) {
return addresses.containsKey(name);
}
public IAddress getAddress(String name) {
return (IAddress)addresses.get(name);
}
Lösungen und Hilfestellungen zu den Maple-Praktikas findet ihr unter: http://ma.rakai.de/