Informatik 3/Gedächtnisprotokoll Klausur SS06

Erstmal alle Aufgaben identifizieren

Quickies
Baume (AVL)
Hash - in Java
Kruskal/Schnitt-def
Restfluss
Heuristik
ne perfekte Skipliste zeichnen
Aufwandsklassen von Breitensuche/Edmonds-Karp Variante von Ford-Fulkerson/Prim
Rekursive Dynamik iterativ umschreiben. - in Java
Greedy Aufgabe - in Java implementieren
da war noch was...

Dann die Reihenfolge

1. quickies, 2 = Baume, 3. Hash, 4. Kruskal/schnitt-def/restfluss, 5 = ?, 6. heuristik, 7. iteretiv dynamik ?

Aufgabe 1). Quickies (7 Punkte)

a)...
b)...
 ...

Aufgabe 2). Hashtabellen und Skiplisten (9 Punkte)

a)...
b)...
c)...

Aufgabe 3). Bäume (7 Punkte)

a)...
b)...
c)...
d)...

Aufgabe 4). Graphen (15 Punkte)

a)...
b)...
c)...
d)...
e)...
f)...

Aufgabe 5). Heuristische Algorithmen (4 Punkte)

Büchernarr möchte seine Büchersammlung neu ordnen. Er besitzt n-Bücher, die er auf einen langen Regal nebeneinander platzieren möchte, sodass benachbarte Bücher sich möglichst ähnlich sind. Die Ähnlichkeit zweier Bücher i und j ist durch eine Funktion a(i,j) gegeben, wobei der Wert der Funktion um so größer ist, je ähnlicher sich die Bücher sind. Insgesamt sei die beste Lösung die, bei der die Summe der Ähnlichkeiten zwischen allen benachbarten Büchern möglichst groß ist.

a) 2 Punkte Geben Sie eine geeignete Kodierung einer Lösung für das obige Problem an (formal).
b) 1 Punkt Geben Sie die zu optimierende Zielfunktion sowie die Optimierungsrichtung (max/min) an.
c) 1 Punkt Geben Sie einen elemantaren Suchschritt für Ihre Lösungskodierung an.

Aufgabe 6). Greedy (4 Punkte)

a)...
b)...

Aufgabe 7). Irgendwas.. (4 Punkte)