Bearbeiten von „Gedächtnisprotokoll AD08-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 12: | Zeile 12: | ||
Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen) | Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen) | ||
Finden Sie die geschlossene Form für folgende Rekurenzgleichung: | Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)<br> | ||
Sie können annehmen dass | Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist. | ||
Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt) | Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt) | ||
Zeigen Sie anhand der Definition des O-Kalküls: | Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g). | ||
== Suchen == | == Suchen == | ||
Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit | Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit bekannten Sortieralgorithmen | ||
Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert? | Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert? | ||
Zeile 26: | Zeile 26: | ||
Quicksort | Quicksort | ||
Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben. | |||
== Hashing == | == Hashing == | ||
Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion | Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion h(k,i) = h_1(k) + i * h_2(k) mit h_1(k) = k mod m und k_2 = 1 + k mod (m-1). Geben Sie die Sondierungsfolge an. | ||
== Bäume == | == Bäume == | ||
Zeile 39: | Zeile 37: | ||
Algoritmus implementieren der berechnet wieviele Knoten k mit a <= k <= b es gibt. (in O(log n)) | Algoritmus implementieren der berechnet wieviele Knoten k mit a <= k <= b es gibt. (in O(log n)) | ||
== Graphen == | == Graphen == | ||
Zeile 49: | Zeile 45: | ||
* Welchem aus der Veranstaltung bekannten Problem ähnelt dieses? | * Welchem aus der Veranstaltung bekannten Problem ähnelt dieses? | ||
* Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an. | * Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an. | ||
== Dynamische Programmierung == | == Dynamische Programmierung == | ||
Zeile 70: | Zeile 53: | ||
* Laufzeit? | * Laufzeit? | ||
[[Kategorie:Gedaechtnisprotokoll | [[Kategorie:Gedaechtnisprotokoll]] |