Benutzer-Werkzeuge
se:algorithmendatenstrukturen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste Überarbeitung Beide Seiten der Revision | ||
|
se:algorithmendatenstrukturen [2009-01-17 20:12] stefan |
se:algorithmendatenstrukturen [2009-01-17 20:35] stefan |
||
|---|---|---|---|
| Zeile 82: | Zeile 82: | ||
| * Vorgänger des i. Knotens: i/2 (i >> 1) | * Vorgänger des i. Knotens: i/2 (i >> 1) | ||
| * linker Nachfolger des i. Knotens: 2i (i << 1) | * linker Nachfolger des i. Knotens: 2i (i << 1) | ||
| - | * rechter Nachfolger des i. Knotens: 2i + 1 ((i << 1) + 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 | * 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 | * Max-Heap: Nachfolger-Knoten haben kleinere Werte, Min-Heap: Nachfolger-Knoten haben größere Werte | ||
| Zeile 169: | Zeile 169: | ||
| * Straight Radix Sort: quasi ein Counting-Sort für Bitmuster von rechts nach links | * 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 179: | Zeile 189: | ||
| * <del>Arrays mit Quicksort sortieren (C: qsort)</del> | * <del>Arrays mit Quicksort sortieren (C: qsort)</del> | ||
| * <del>Heapsort, Countingsort, Radixsort</del> | * <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 | * Codeoptimierungen ins Wiki eintragen | ||
se/algorithmendatenstrukturen.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
