Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
se:algorithmendatenstrukturen [2009-01-17 17:23] stefan |
se:algorithmendatenstrukturen [2009-01-17 20:39] stefan |
||
---|---|---|---|
Zeile 75: | Zeile 75: | ||
* in balancierten Binärbäumen haben alle Knoten in etwa die gleiche Tiefe: bei n Knoten ist die Höhe log<sub>2</sub>(n+1) | * in balancierten Binärbäumen haben alle Knoten in etwa die gleiche Tiefe: bei n Knoten ist die Höhe log<sub>2</sub>(n+1) | ||
* bei einem balancierten Binärbaum sind somit maximal log<sub>2</sub>(n+1) Vergleiche (=Höhe des Binärbaums) notwendig, um ein Element in einem solchen balancierten Binärbaum zu finden | * bei einem balancierten Binärbaum sind somit maximal log<sub>2</sub>(n+1) Vergleiche (=Höhe des Binärbaums) notwendig, um ein Element in einem solchen balancierten Binärbaum zu finden | ||
+ | |||
+ | ==== Heap ==== | ||
+ | * ein Heap ist ein Binärbaum, in dem alle Knoten Werte besitzen, die größer (oder gleich) sind als alle Werte ihrer Kindknoten | ||
+ | * der größte Wert befindet sich somit im Wurzelknoten | ||
+ | * Darstellung als Array: [0] = Wurzel, [1] und [2] 1. Ebene, [3], [4], [5], [6] 2. Ebene etc. | ||
+ | * Vorgänger des i. Knotens: i/2 (i >> 1) | ||
+ | * linker Nachfolger des i. Knotens: 2i (i << 1) | ||
+ | * rechter Nachfolger des i. Knotens: 2i + 1 ( (i << 1) + 1) | ||
+ | * Heap (= Binärbaum) mit n Knoten hat Höhe lg n, also können alle Operationen auf einem Heap mit O(lg n) durchgeführt werden | ||
+ | * Max-Heap: Nachfolger-Knoten haben kleinere Werte, Min-Heap: Nachfolger-Knoten haben größere Werte | ||
+ | * Wiederherstellen der Heap-Eigenschaft mittels ''maxHeapify'' | ||
==== Traversierung ==== | ==== Traversierung ==== | ||
Zeile 145: | Zeile 156: | ||
* Drei-Wege-Partitionierung | * Drei-Wege-Partitionierung | ||
* Quicksort in C (''stdlib.h''): ''void qsort(void *array, size_t n, size_t length, int (*compare)(const void *val1, const void *val2))'' | * Quicksort in C (''stdlib.h''): ''void qsort(void *array, size_t n, size_t length, int (*compare)(const void *val1, const void *val2))'' | ||
+ | * Heapsort | ||
+ | * Komplexität O(n lg n) | ||
+ | * in-place mittels Heap | ||
+ | * Counting-Sort | ||
+ | * Komplexität O(n) | ||
+ | * verwendet ein Ausgabearray und ein Hilfsarray für die Häufigkeitsverteilung der Werte | ||
+ | * Sortierung über Häufigkeitsverteilung der Werte (z.B. 5 Werte kleiner als "g", also muss "g" Index 5 im neuen Array bekommen) | ||
+ | * Radix-Sort | ||
+ | * Partitionierung der Daten z.B. anhand von Anfangsbuchstaben und rekursives Sortieren | ||
+ | * Sortierung anhand des Bitmusters von Zahlen | ||
+ | * Radix Exchange Sort: Bitmuster von links nach rechts durchgehen, 0 vor 1 einsortieren | ||
+ | * Straight Radix Sort: quasi ein Counting-Sort für Bitmuster von rechts nach links | ||
+ | ===== Backtracking ===== | ||
+ | * Backtracking ist ein Lösungsverfahren nach dem Trial-and-Error-Verfahren | ||
+ | * über Teillösungen soll zu einer Lösung des Gesamtproblems gefunden werden | ||
+ | * wenn ein Teilproblem nicht mehr weiter lösbar ist ("Sackgasse"), werden die vorherigen Teilschritte soweit rückgängig gemacht, dass ein anderer Weg ausprobiert werden kann | ||
+ | * Beispiele | ||
+ | * Wegfindung im Labyrinth (Maus sucht Käse) | ||
+ | * Teilsummenermittlung | ||
+ | * Acht-Damen-Problem | ||
+ | * Sudoku | ||
+ | |||
===== ToDo ===== | ===== ToDo ===== | ||
* Wichtige Bereiche im Skript mit Klebi kennzeichnen | * Wichtige Bereiche im Skript mit Klebi kennzeichnen | ||
Zeile 155: | Zeile 188: | ||
* <del>Codeoptimierung</del> | * <del>Codeoptimierung</del> | ||
* <del>Arrays mit Quicksort sortieren (C: qsort)</del> | * <del>Arrays mit Quicksort sortieren (C: qsort)</del> | ||
- | * Heapsort, Countingsort, Radixsort | + | * <del>Heapsort, Countingsort, Radixsort</del> |
- | * Backtracking (Was gibt vorgegebenes Programm aus?) | + | * <del>Backtracking (Was gibt vorgegebenes Programm aus?)</del> |
* Beispiele für Ermittlung der benötigten Zeit nachrechnen | * Beispiele für Ermittlung der benötigten Zeit nachrechnen | ||
- | * Codeoptimierungen ins Wiki eintragen | + | * <del>Codeoptimierungen ins Wiki eintragen</del> |