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 8: | Zeile 8: | ||
* <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> | ||
* Kann für zwei Funktionen f,g f <math>\in O(g) \Rightarrow g \in \Omega(f)</math> gelten? | * 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>o(n^2) \cap O(n^2) = \emptyset</math> ? | ||
* Gilt <math>7^{log_2 n} \in \Theta(n^3)</math>? | * Gilt <math>7^{log_2 n} \in \Theta(n^3)</math>? | ||
Zeile 16: | Zeile 16: | ||
* 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>7^{\log_2(n)} \in \Theta(n^3)</math> | |||
=== NP === | === NP === | ||
Zeile 26: | Zeile 27: | ||
=== 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 75: | Zeile 71: | ||
[[Bild:avl.png]] | [[Bild:avl.png]] | ||
[[Kategorie:Gedaechtnisprotokoll|AD]] | [[Kategorie: Gedaechtnisprotokoll|AD]] |