Algorithmen

1. Einleitung.- 1.1 Was ist ein Algorithmus?.- 1.2 Die Beschreibung von Algorithmen in SPARKS.- 1.3 Strukturiertes Programmieren.- 1.4 Die Analyse von Algorithmen.- Literaturhinweise.- Übungen.- 2. Elementare Datenstrukturen.- 2.1 Keller und Schlangen.- 2.2 Bäume.- 2.3 Halden und Sortieren mit Halden.- 2.4 Mengen und Vereinigung disjunkter Mengen.- 2.5 Graphen.- 2.6 Hash-Technik.- Literaturhinweise.- Übungen.- 3. Das Prinzip "Teile-und-Herrsche".- 3.1 Die allgemeine Methode.- 3.2 Binäre Suche.- 3.3 Auffinden von Maximum und Minimum.- 3.4 Sortieren durch Mischen.- 3.5 Quicksort.- 3.6 Auswahl.- 3.7 Matrizenmultiplikation nach Strassen.- Literaturhinweise.- Übungen.- 4. Die Greedy-Methode.- 4.1 Die allgemeine Methode.- 4.2 Optimale Speicherung auf Bändern.- 4.3 Das Rucksackproblem.- 4.4 Erstellen von Auftragsfolgen mit Schlußterminen.- 4.5 Optimale Mischmuster.- 4.6 Minimale spannende Bäume.- 4.7 Kürzeste Wege bei einer einzigen Quelle.- Literaturhinweise 227 Übungen.- 5. Dynamisches Programmieren.- 5.1 Die allgemeine Methode.- 5.2 Mehrstufige Graphen.- 5.3 Bestimmung aller kürzesten Wege.- 5.4 Optimale binäre Suchbäume.- 5.5 0/1-Rucksack.- 5.6 Entwurf zuverlässiger Systeme.- 5.7 Das Problem des Handlungsreisenden.- 5.8 Zeitplanung von Flußbetrieben.- Literaturhinweise.- Übungen.- 6. Elementare Such- und Durchlauftechniken.- 6.1 Die Techniken.- 6.2 Codeoptimierung.- 6.3 UND/ODER-Graphen.- 6.4 Spielbäume.- 6.5 Doppelt zusammenhängende Komponenten und die Suchmethode "Zuerst in die Tiefe gehen".- Literaturhinweise.- Übungen.- 7. Rückverfolgung.- 7.1 Die allgemeine Methode.- 7.2 Das 8-Damen-Problem.- 7.3 Summe von Teilmengen.- 7.4 Färben von Graphen 4.- 7.5 Hamilton'sehe Kreise.- 7.6 Das Rucksackproblem.- Literaturhinweise.- Übungen.- 8.Verzweigen und Beschränken.- 8.1 Die Methode.- 8.2 Das Null/Eins-Rucksackproblem.- 8.3 Das Problem des Handlungsreisenden.- 8.4 Effizienz-Betrachtungen.- Literaturhinweise.- Übungen.- 9. Algebraische Vereinfachung und Umformung.- 9.1 Die allgemeine Methode.- 9.2 Auswertung und Interpolation.- 9.3 Die Schnelle Fourier-Transformation.- 9.4 Modulare Arithmetik.- 9.5 Noch schnellere Auswertung und Interpolation.- Literaturhinweise.- &F#x00DC;bungen.- 10. Theorie der Unteren Schranke.- 10.1 Vergleichsbäume zum Sortieren und Suchen.- 10.2 Orakel und Umkehrschluß.- 10.3 Techniken für algebraische Probleme.- 10.4 Einige untere Schranken für parallele Berechnungen.- Literaturhinweise.- Übungen.- 11. NP-Schwere und NP-Vollständige Probleme.- 1.1 Grundlagen.- 1.2 Das Theorem von Cook.- 1.3 NP-schwere Graphenprobleme.- 1.4 NP-schwere Planungsprobleme.- 1.5 NP-schwere Codeerzeugungsprobleme.- 1.6 Einige vereinfachte NP-schwere Probleme.- Literaturhinweise.- Übungen.- 12. Approximationsalgorithmen für NP-Schwere Probleme.- 12.1 Einführung.- 12.2 Absolute Approximation.- 12.3 ? - Approximation.- 12.4 Polynomiale Approximationsschemata.- 12.5 Voll-polynomiale Approximationsschemata.- 12.6 Probabilistisch gute Algorithmen.- Literaturhinweise.- Übungen.- Anhang A. Sparks.- Stichwortverzeichnis.