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)