Algorithmen - Horowitz, E.

. .

Sommaire:
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.