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?

2. Aufgabe: B-Bäume

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

3. Aufgabe: AVL-Bäume

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

4 und 5. Aufgabe: Graphen

• 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)

6. Aufgabe: Dynamisches Programmieren

• Hofstätter-Rekursion

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)?)

7. Aufgabe Heuristische Suche

• 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.