Bearbeiten von „Gedächtnisprotokoll AD09-1“

Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten).

Muss nicht richtig sein ;)

1. O-Notation


2. 
- Was ist wenn ein NP-schweres Problem in P liegt?
- n^log2 7 in Theta(n^3)

3. NP
Formale Sprache von Eulerkreis


4. Rekurrenzgleichung
- T(0)=0, T(n) = 3T(n-1) + 3
- Was muss Abbildung von L->M machen damit es Reduktion ist?

5. Suchbäume
- Kann ein RS-Baum ein AVL-Baum sein?
- Alle Suchbäume von {1,2,3}

6. Stack/Queue/Array

7. Kruskal

8. Median/Mittelwert 
- schechtste Laufzeit von: Heapsort, Radixsort und Sortieren durch Auswahl

9. Heap
- malen
- Sind alle Heaps spezielle Suchbäume?

10. AVL
- 
- Komplexität von Medianberechnung
- rotieren
@@ Zeile 1: / Zeile 1: @@
-Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten) und es gab 100Punkte.
+Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten).
-Die Klausur war eine gute Mischung aus Multiple-Choice-Fragen und Anwendungsaufgaben. Wenn man das Tutorium bei Frank Heitmann besucht hatte, war es gut möglich die Klausur zu bestehen.
-Gliederung muss nicht unbedingt korrekt sein.
+Muss nicht richtig sein ;)
-=== O-Notation ===
+. O-Notation
-Jeweils Ja/Nein ankreuzen, ein Zusatzpunkt für kurze Begründung
-* <math>2^{n+3} \in O( 2^{n-3} )</math>
-* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</math>
-* Kann für zwei Funktionen f,g f <math>\in O(g) \Rightarrow g \in \Omega(f)</math> gelten?
-* Gilt <math>o(n^2) \cap O(n^2) = \emptyset</math> ?
-* Gilt <math>7^{log_2 n} \in \Theta(n^3)</math>?
-* Ist folgende Behauptung richtig? Schlechteste Laufzeit von QuickSort ist <math>n\cdot log(n)</math>
-=== Aufagbe 2 ===
-* Zeigen sie durch ein Gegenbeispiel, dass der kürzeste Pfad zwischen zwei Punkten nicht zwingend eine Kante des minimalen Spannbaums des Graphen nutzen muss.
-* Was bedeutet es, wenn ein NP-schweres Problem in P liegt?
-=== NP ===
+.
-* Formulieren sie das Problem des Eulerkreis (Euler) für einen Graphen G = (V, E) als formale Sprache.
+- Was ist wenn ein NP-schweres Problem in P liegt?
-* Welche Eigenschaften muss eine Abbildung <math>f : L \rightarrow M</math> mit <math>L \in \Sigma*</math> und <math>M \in \Tau*</math> besitzen, damit es eine polynominalle Reduktion ist?
+- n^log2 7 in Theta(n^3)
+. NP
+Formale Sprache von Eulerkreis
-=== Rekurrenzgleichung ===
-* Gegeben ist eine rekursive Gleichung <math>T(n) = \begin{cases}0 & n = 0\\3T(n-1)+3 & n > 0\end{cases}</math>. Trages Sie die ersten 5 Werte in eine Tabelle ein, finden sie eine Formel in geschlossener Form (also ohne Summmenzeichen) und beweisen sie diese anschließend durch Induktion.
-=== Suchbäume ===
+. Rekurrenzgleichung
-* Wenn sie in einem Suchbaum alle Elemente aufsteigend ausgeben wollen, in welcher Reihenfolge müssen sie dann suchen? Ankreuzmöglichkeiten: preorder inorder postorder
+- T(0)=0, T(n) = 3T(n-1) + 3
-* Anzahl innerer Knoten eines Binärbaums der Höhe h
+- Was muss Abbildung von L->M machen damit es Reduktion ist?
-a) wenn der Baum minimal
+. Suchbäume
-b) wenn der Baum maximal
+- Kann ein RS-Baum ein AVL-Baum sein?
-ist. Jeweils eine geschlossene Form(d.h. ohne Summenzeichen) angeben und begründen!
+- Alle Suchbäume von {1,2,3}
-* Kann ein Rot-Schwarz-Baum ein AVL-Baum sein?
-* Zeichnen sie alle binären Suchbäume der Menge {1,2,3}.
-* Ist jeder Suchbaum eine spezielle Form des Heaps?
-=== Aufgabe 6 ===
+. Stack/Queue/Array
-* Kreuzen sie in der Tabelle die Zugriffsmethoden auf die einzelnen Datenstrukturen an.
-         | Schlange | Keller | Feld | stack | array | queue
- --------+----------+--------+------+-------+-------+--------
- fifo    |          |        |      |       |       |
- --------+----------+--------+------+-------+-------+--------
- lifo    |          |        |      |       |       |
- --------+----------+--------+------+-------+-------+--------
- random  |          |        |      |       |       |
- access  |          |        |      |       |       |
-* Wann wird ein Sortierverfahren als stabil bezeichnet?
+. Kruskal
+. Median/Mittelwert
+- schechtste Laufzeit von: Heapsort, Radixsort und Sortieren durch Auswahl
-=== Kurskal ===
+. Heap
-''Gegeben ist ein Graph''
+- malen
-* Bestimmen sie den minimalen Spannbaum und tragen sie in die Tabelle ein, wann sie welche Kante zum Spannbaum hinzugefügt haben, und welche ausgelassen wurden.
+- Sind alle Heaps spezielle Suchbäume?
-* Mit welcher Datenstruktur würden sie Kruskal implementieren, ohne groß Laufzeit zu verschenken?
-=== Aufgabe 8 ===
+. AVL
-* ''Gegeben sind 13 ganze Zahlen'' Geben sie an
+-
-** den Median
+- Komplexität von Medianberechnung
-** den Mittelwert
+- rotieren
-* Geben sie in O-Notation die Laufzeit von X im schlechtesten Fall an.
-** Heapsort
-** Radixsort
-** Sortieren durch Einfügen
-=== Heap ===
-''Gegeben ist ein Heap in Array-Darstellung''
-* Zeichnen sie den Heap
-=== Aufgabe 10 ===
-* Geben sie die Komplexität an, imt dem der Median aus einer Teilmenge von N berechnet werden kann.
-* ''Gegeben ist ein verletzer AVL-Baum''. Führen sie die notwendigen Rotationen durch, um den AVL-Baum zu korrigieren.
-[[Bild:avl.png]]
-[[Kategorie:Gedaechtnisprotokoll|AD]]