Informatik 3/Gedächtnisprotokoll Klausur WS0405

Dies ist ein Gedächtnisprotokoll von der Klausur vom Mittwoch, den 2. März 2005. [1]

1. Aufgabe

Insgesamt fünf kurze Fragen, unter anderem

1. Ist P teilmenge von NP?
2. Ein binärer Suchbaum hat immer die Höhe O(logn)?
3. Ein binärer Suchbaum hat immer das maximum der Höhen seiner beiden Kinder plus eins?

2. Aufgabe: B-Bäume

1. Welche Ordung (minimal und maximal) hat ein gegebener B-Baums?
2. Einfügen, Löschen, Verschieben, mit nachvollziehbarem Lösungsweg aufschreiben.

3. Aufgabe: AVL-Bäume

1. Einfügen, Löschen, mit nachvollziehbarem Rechenweg (also Rotationen angeben)

4 und 5. Aufgabe: Graphen

1. Adjazenzliste aufschreiben
2. Klassen für Adjazenzlisten und -matrix definieren (also Klassenvariablen und Konstruktor)
3. Matrix2array: Adjazenzmatrix zu einer Adjazenzliste umformen in java-code

AdjacencyList matrix2array( AdjacencyMatrix am ) { ... }

1. Aufwand abschätzen von verschiedenen Algorithmen, wenn als Adjazenzliste implementiert sind
   1. Ich glaube, es waren Prim und Kruskal.
   2. Außerdem auch die selbst programmierten Algorithmen mit O(...) abschätzen
2. Den "komplementären" Graphen ermitteln, für den gilt
   1. V'=V
   2. (E' geschnitten E) = {leere menge}
   3. ((E vereinigt E'), V) ist vollständig
   4. Das sind alle Kanten, außer die im Graphen vorhandenen. Implementieren in Pseudo-Code
3. Ein Mauslabyrinth, wobei die Maus immer beim Betreten eines Feldes "bezahlen" muss, in eine geeignete Repräsentation umwandeln (z.B. einen gerichteten Graphen)

6. Aufgabe: Dynamisches Programmieren

1. Hofstätter-Rekursion

h(n) = h(n - h(n - 1) ) + h(n - h(n - 2) ) für n > 2
h(1) = h(2) = 1 

1. Aus gegebenem, rekursivem Java-Code die Formel erkennen und eine nicht-rekursive Implementierung schaffen. Aufwand abschätzen (O(n)?)

7. Aufgabe Heuristische Suche

1. Party-Problem: du hast N gäste, N plätze und sollst eine geeignete Repräsentationsstruktur für die Sitzordnung schaffen.
2. Weiterhin sind "Beziehungs"-werte gegeben. das "Klima" der Party ist gut, wenn jeder neben jemandem sitzt, der ihm gefällt (Beziehung z:GxG->[-1;1]).
3. Nun sollen verschiedene Sachen, wie Optimierungsgröße, Elementarschritt angegeben werden.