Bearbeiten von „Gedächtnisprotokoll AD09-1“
Zur Navigation springen
Zur Suche springen
Warnung: Du bist nicht angemeldet. Deine IP-Adresse wird bei Bearbeitungen öffentlich sichtbar. Melde dich an oder erstelle ein Benutzerkonto, damit Bearbeitungen deinem Benutzernamen zugeordnet werden.
Die Bearbeitung kann rückgängig gemacht werden. Bitte prüfe den Vergleich unten, um sicherzustellen, dass du dies tun möchtest, und veröffentliche dann unten deine Änderungen, um die Bearbeitung rückgängig zu machen.
| Aktuelle Version | Dein Text | ||
| Zeile 1: | Zeile 1: | ||
Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten) | 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. | Gliederung muss nicht unbedingt korrekt sein. | ||
| Zeile 8: | Zeile 7: | ||
* <math>2^{n+3} \in O( 2^{n-3} )</math> | * <math>2^{n+3} \in O( 2^{n-3} )</math> | ||
* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</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 === | === 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. | * 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? | * Was bedeutet es, wenn ein NP-schweres Problem in P liegt? | ||
* Gilt <math>n^{\log_2(7)} \in \Theta(n^3)</math> | |||
=== NP === | === NP === | ||
| Zeile 23: | Zeile 23: | ||
=== Rekurrenzgleichung === | === Rekurrenzgleichung === | ||
* Gegeben ist eine rekursive Gleichung <math>T(n) = \begin{cases}0 & n = 0\\3T(n-1)+3 & n > 0\end{cases}</math>. | * 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 === | === Suchbäume === | ||
* Kann ein Rot-Schwarz-Baum ein AVL-Baum sein? | * Kann ein Rot-Schwarz-Baum ein AVL-Baum sein? | ||
* Zeichnen sie alle binären Suchbäume der Menge {1,2,3}. | * Zeichnen sie alle binären Suchbäume der Menge {1,2,3}. | ||
* Ist jeder Suchbaum eine spezielle Form des Heaps? | * Ist jeder Suchbaum eine spezielle Form des Heaps? | ||
=== Aufgabe 6 === | === Aufgabe 6 === | ||
| Zeile 53: | Zeile 49: | ||
''Gegeben ist ein Graph'' | ''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. | * 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 === | === Aufgabe 8 === | ||
| Zeile 73: | Zeile 69: | ||
* Geben sie die Komplexität an, imt dem der Median aus einer Teilmenge von N berechnet werden kann. | * 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. | * ''Gegeben ist ein verletzer AVL-Baum''. Führen sie die notwendigen Rotationen durch, um den AVL-Baum zu korrigieren. | ||
[[Kategorie:Gedaechtnisprotokoll|AD]] | [[Kategorie: Gedaechtnisprotokoll|AD]] | ||