Buchholz: Mist, falsche Aufzählungen :-)

2006-04-09T10:54:12Z

Mist, falsche Aufzählungen :-)

Buchholz am 9. April 2006 um 10:51 Uhr

2006-04-09T10:51:22Z

Neue Seite

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

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

Informatik 3/Gedächtnisprotokoll Klausur WS0405 - Versionsgeschichte

Buchholz: Mist, falsche Aufzählungen :-)

Buchholz am 9. April 2006 um 10:51 Uhr