Informatik 3/Gedächtnisprotokoll Klausur SS06: Unterschied zwischen den Versionen
| (7 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| − | ==Erstmal alle | + | ==Erstmal alle Aufgaben identifizieren== |
* Quickies | * Quickies | ||
* Baume (AVL) | * Baume (AVL) | ||
| − | * Hash | + | * Hash - in Java |
| − | * Kruskal/ | + | * Kruskal/Schnitt-def |
| − | * Restfluss | + | * Restfluss |
| − | * | + | * Heuristik |
| + | * ne '''perfekte''' Skipliste zeichnen | ||
* Aufwandsklassen von Breitensuche/Edmonds-Karp Variante von Ford-Fulkerson/Prim | * Aufwandsklassen von Breitensuche/Edmonds-Karp Variante von Ford-Fulkerson/Prim | ||
| − | * Rekursive | + | * Rekursive Dynamik iterativ umschreiben. - in Java |
| + | * Greedy Aufgabe - in Java implementieren | ||
* '''da war noch was...''' | * '''da war noch was...''' | ||
| Zeile 14: | Zeile 16: | ||
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)... | ||
| + | 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)''' | ||
Aktuelle Version vom 4. August 2006, 16:00 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)
