Grundlegende Algorithmen

1 Einleitung und Grundlagen.- 1.1 Ziele.- 1.2 Einführendes Beispiel: Berechnung der Fibonacci-Zahlen.- 1.3 Grundlagen.- 1.4 Übungsaufgaben.- 2 Sortieren.- 2.1 Einfache Sortieralgorithmen.- 2.2 Mergesort.- 2.3 Heapsort.- 2.4 Quicksort.- 2.5 Interludium: Divide-and-Conquer-Algorithmen.- 2.6 Eine untere Schranke für das Sortieren.- 2.7 Bucketsort.- 2.8 Übungsaufgaben.- 3 Selektieren.- 3.1 Quickselect.- 3.2 Ein linearer Selektionsalgorithmus.- 3.3 Der Spinnen-Algorithmus.- 3.4 Eine untere Schranke.- 3.5 Ein randomisierter Median-Algorithmus.- 3.6 Neuere Ergebnisse.- 3.7 Übungsaufgaben.- 4 Suchen.- 4.1 Wörterbücher.- 4.2 Ausnutzen von Sortierung.- 4.3 Hashing.- 4.4 Binäre Suchbäume.- 4.5 AVL-Bäume.- 4.6 (a,b)-Bäume.- 4.7 Weitere Varianten von Suchbäumen.- 4.8 Tries.- 4.9 Übungsaufgaben.- 5 Graphen.- 5.1 Grundlagen der Graphentheorie.- 5.2 Traversieren von Graphen.- 5.3 Zusammenhang von Graphen.- 5.4 Kürzeste Wege.- 5.5 Interludium: Fibonacci-Heaps.- 5.6 Minimale Spannbäume.- 5.7 Interludium: Union-Find-Datenstrukturen.- 5.8 Übungsaufgaben.- 6 Texte.- 6.1 Alphabete und Zeichenketten.- 6.2 Der Algorithmus von Knuth, Morris und Pratt.- 6.3 Der Algorithmus von Boyer und Moore.- 6.4 Tries für Texte.- 6.5 Interludium: Datenkompression.- 6.6 Übungsaufgaben.- 7 Arithmetik.- 7.1 Euklidischer Algorithmus.- 7.2 Modulare Arithmetik.- 7.3 Primzahlen.- 7.4 Interludium: Kryptographie.- 7.5 Die schnelle Fouriertransformation.- 7.6 Multiplikation ganzer Zahlen.- 7.7 Optimale Klammerung von Matrizenprodukten.- 7.8 Matrizenmultiplikation.- 7.9 Übungsaufgaben.- 8 Schwierige Probleme.- 8.1 Unentscheidbarkeit.- 8.2

$$\mathcal{NP}
$$
-Vollständigkeit.- 8.3 Approximative Algorithmen.- 8.4 Übungsaufgaben.- A Literaturhinweise.- A.1 Lehrbücher zur Algorithmik.- A.2 Lehrbücherzu angrenzenden Themen.- A.3 Originalarbeiten.- B Gofer-Skripten.- B.1 Berechnung von Fibonacci Zahlen.- C Index.