Algorithmen: Entwurf Und Analyse

ISBN-13: 9783540107439 / Niemiecki / Miękka / 1981 / 772 str.

E. Horowitz; S. Sahni; M. Czerwinski

Opis

Zu den wichtigen und fundamentalen Konzepten der Informatik gehort sicher das des Algorithmus. Seit man sich mit Maschinen beschaftigt, die einfache mathematische Operationen ausfuhren konnen, befat man sich mit den Problemen, was uberhaupt berechnet werden kann und wie diese Berechnungen effizient durchgefuhrt werden konnen. Durch die Erfindung des Computers wurde die Behandlung dieser Fragen stark ge- fordert; dies hat zur Entdeckung vieler wichtiger und ideenreicher Algorithmen gefuhrt. Das Studium von Algorithmen ist ein besonderes Anliegen der Informatik. In diesem Buch wollen wir die Kenntnisse uber Algorithmen in zusammenhangender Weise so darstellen, da sowohl Stu- denten als auch in der Praxis Tatige den Entwurf und die Analyse neuer Algorithmen erlernen konnen. Ein Buch, das jeden Algorithmus enthalt, der jemals erfunden wur- de, mute einen enormen Umfang haben. Daher beschrankt man sich ubli- cherweise bei Buchern uber Algorithmen auf wenige Problembereiche, die dann im Detail behandelt werden. Zu jedem speziellen Problem wird der effizienteste Losungsalgorithmus vorgestellt und analysiert. Da wir mehrere Jahre lang Kurse nach dieser Methode abgehalten haben, kennen wir den groen Nachteil dieses Verfahrens. Der Student lernt zwar viele schnelle Algorithmen kennen und kann diese auch analysie- ren, im Entwurf guter Algorithmen bleibt er aber unsicher.

Spis treści

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.