Informatik 3/Gedächtnisprotokoll Klausur WS0405: Unterschied zwischen den Versionen

Aktuelle Version vom 9. April 2006, 10:54 Uhr

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.

@@ Zeile 6: / Zeile 6: @@
 Insgesamt fünf kurze Fragen, unter anderem
-# Ist P teilmenge von NP?
+* Ist P teilmenge von NP?
-# Ein binärer Suchbaum hat immer die Höhe O(logn)?
+* 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?
+* 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?
+* Welche Ordung (minimal und maximal) hat ein gegebener B-Baums?
-# Einfügen, Löschen, Verschieben, mit nachvollziehbarem Lösungsweg aufschreiben.
+* 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)
+* Einfügen, Löschen, mit nachvollziehbarem Rechenweg (also Rotationen angeben)
 == 4 und 5. Aufgabe: Graphen ==
-# Adjazenzliste aufschreiben
+* Adjazenzliste aufschreiben
-# Klassen für Adjazenzlisten und -matrix definieren (also Klassenvariablen und Konstruktor)
+* Klassen für Adjazenzlisten und -matrix definieren (also Klassenvariablen und Konstruktor)
-# Matrix2array: Adjazenzmatrix zu einer Adjazenzliste umformen in java-code
+* Matrix2array: Adjazenzmatrix zu einer Adjazenzliste umformen in java-code
   AdjacencyList matrix2array( AdjacencyMatrix am ) { ... }
-# Aufwand abschätzen von verschiedenen Algorithmen, wenn als Adjazenzliste implementiert sind
+* Aufwand abschätzen von verschiedenen Algorithmen, wenn als Adjazenzliste implementiert sind
-## Ich glaube, es waren Prim und Kruskal.
+** Ich glaube, es waren Prim und Kruskal.
-## Außerdem auch die selbst programmierten Algorithmen mit O(...) abschätzen
+** Außerdem auch die selbst programmierten Algorithmen mit O(...) abschätzen
-# Den "komplementären" Graphen ermitteln, für den gilt
+* Den "komplementären" Graphen ermitteln, für den gilt
-## V'=V
+** V'=V
-## (E' geschnitten E) = {leere menge}
+** (E' geschnitten E) = {leere menge}
-## ((E vereinigt E'), V) ist vollständig
+** ((E vereinigt E'), V) ist vollständig
-## Das sind alle Kanten, außer die im Graphen vorhandenen. Implementieren in Pseudo-Code
+** 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)
+*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
+* 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)?)
+* 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.
+* 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]).
+* 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.
+* Nun sollen verschiedene Sachen, wie Optimierungsgröße, Elementarschritt angegeben werden.