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

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

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

AdjacencyList matrix2array( AdjacencyMatrix am ) { ... }

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

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

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

Party-Problem: du hast N gäste, N plätze und sollst eine geeignete Repräsentationsstruktur für die Sitzordnung schaffen.
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]).
Nun sollen verschiedene Sachen, wie Optimierungsgröße, Elementarschritt angegeben werden.