Quelltext der Seite Informatik 3/Gedächtnisprotokoll Klausur WS0405

__NOTOC__

Dies ist ein Gedächtnisprotokoll von der Klausur vom Mittwoch, den 2. März 2005. [http://kbs.cs.tu-berlin.de/teaching/ws2004/info3/klausuren_ws2004.htm]

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