Benutzer-Werkzeuge

Webseiten-Werkzeuge


se:algorithmendatenstrukturen

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
Nächste Überarbeitung
Vorhergehende Überarbeitung
se:algorithmendatenstrukturen [2009-01-17 20:12]
stefan
se:algorithmendatenstrukturen [2009-01-17 20:39]
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+  * <del>Codeoptimierungen ins Wiki eintragen</​del>​
se/algorithmendatenstrukturen.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)