Algorithmik

Algorithmen und Datenstrukturen

Algorithmen

 

  • Groß-O-Notation: Definition, Anwendung für eine erste Klassifizierung der behandelten Algorithmen: z.B. O(1), O(log n), O(sqrt(n)), O(n), O(n*log n), O(n*log2 n), O(n2), O(n3)
  • schnelle Sortierverfahren (QuickSort, HeapSort, MergeSort, Fachsortieren) und die möglichst exakte mathematische Analyse ihres Aufwandes
  • abstrakte Datentypen als wichtiges Hilfsmittel für effiziente Erstellung großer Softwaresysteme
  • Listen als erstes Beispiel für einen abstrakten Datentyp (ADT): Implementation (bei gleichbleibender Spezifikation) als verkettet bzw. als sequenziell gespeicherte Struktur, Aufwand von Grundoperationen auf Listen in Abhängigkeit von der Implementation; ArrayList als professionelle Implementation des ADT Liste
  • Listen als eine einfache Möglichkeit zum Modellieren des ADT dictionary
  • Simulation verschiedener Konzepte von selbstanordnenden Listen und Vergleich ihrer Effizienz
  • Suchbäume als zweite (und effizientere) Lösung des Wörterbuchproblems; Abschätzung des Erwartungswertes der mittleren Suchpfadlänge von natürlichen Suchbäumen
  • AVL-Bäume als Beispiel für balancierte (Such-)Bäume; worst-case-Abschätzung der Höhe sowie der mittleren Suchpfadlänge von AVL-Bäumen in Abhängigkeit von der Schlüsselzahl. Interessanterweise konnte hier im Unterricht durch zielstrebiges Verfolgen einer spontanen Idee ein Ergebnis erzielt werden, das sich zumindest in den gängigen Fachbüchern nicht finden lässt: AVL-Bäume haben eine mittlere Suchpfadlänge von Imittel(n) <= 1.04log(n), sind also (im worst case!) nur ca. 4% schlechter als perfekte Suchbäume. Das Ergebnis wurde mit Hilfe der von Schülern gefundenen Formel für die mittlere Suchpfadlänge eines Fibonaccibaums (= worst-case-AVL-Baum) hergeleitet. (Näheres hier)

  • B-Bäume als effiziente externe Datenstruktur; Implementation von B-Bäumen (mit den Operationen Suchen und Einfügen) mittels Dateien; Ideensammlung für eine effiziente Entferne-Operation

Ralf Dorn, Fachleiter Informatik (erreichbar: ralf.dorn[at]hhgym.de