Informatik 3/Gedächtnisprotokoll Klausur SS06: Unterschied zwischen den Versionen
| Zeile 17: | Zeile 17: | ||
1. quickies, 2 = Baume, 3. Hash, 4. Kruskal/schnitt-def/restfluss, 5 = ?, 6. heuristik, 7. iteretiv dynamik ? | 1. quickies, 2 = Baume, 3. Hash, 4. Kruskal/schnitt-def/restfluss, 5 = ?, 6. heuristik, 7. iteretiv dynamik ? | ||
| − | + | '''Aufgabe 1). Quickies (7 Punkte)''' | |
| − | + | a)... | |
| − | '''Aufgabe 5). Heuristische Algorithmen | + | 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. | 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. | ||
| Zeile 31: | Zeile 49: | ||
'''c) 1 Punkt''' | '''c) 1 Punkt''' | ||
Geben Sie einen elemantaren Suchschritt für Ihre Lösungskodierung an. | Geben Sie einen elemantaren Suchschritt für Ihre Lösungskodierung an. | ||
| + | |||
| + | '''Aufgabe 6). Greedy (4 Punkte)''' | ||
| + | a)... | ||
| + | b)... | ||
| + | |||
| + | '''Aufgabe 7). Irgendwas.. (4 Punkte)''' | ||
Version vom 3. August 2006, 15:04 Uhr
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)
