Gedächtnisprotokoll AD09-1

2009-02-12T15:16:04Z

84.144.74.125: /* Aufagbe 2 */ Formel korrigiert (n in Potenz)

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

Gliederung muss nicht unbedingt korrekt sein.

=== 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>
* Wenn f <math>\in O(g)</math> gilt, dann kann <math>g \in \Omega(f)</math> nicht gelten
* <math>o(f) \cap O(f) = \emptyset</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?
* Gilt <math>7^{\log_2(n)} \in \Theta(n^3)</math>

=== NP ===
* Formulieren sie das Problem des Eulerkreis (Euler) für einen Graphen G = (V, E) als formale Sprache.
* 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?

=== Rekurrenzgleichung ===
* Gegeben ist eine rekursive Gleichung <math>T(n) = \begin{cases}0 & n = 0\\3T(n-1)+3 & n > 0\end{cases}</math>. Finden sie eine Formel in geschlossener Form (also ohne Summmenzeichen) und beweisen sie diese anschließend durch Induktion.

=== Suchbäume ===
* 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 ===
* 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?

=== Kurskal ===
''Gegeben ist ein Graph''
* 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.

=== Aufgabe 8 ===
* ''Gegeben sind 13 ganze Zahlen'' Geben sie an
** den Median
** den Mittelwert
* 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.

[[Kategorie: Gedaechtnisprotokoll|AD]]

Fachschaft Informatik - Benutzerbeiträge [de]

Gedächtnisprotokoll AD09-1