Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

Informatik 3/Gedächtnisprotokoll Klausur WS0405

< Informatik 3
Version vom 9. April 2006, 10:54 Uhr von Buchholz (Diskussion) (Mist, falsche Aufzählungen :-))
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)


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.