Algorithmen : Entwurf und Analyse
著者
書誌事項
Algorithmen : Entwurf und Analyse
Springer, 1981
- : Germany
- : U.S.A.
大学図書館所蔵 全3件
注記
Includes index
内容説明・目次
内容説明
Zu den wichtigen und fundamentalen Konzepten der Informatik gehoert sicher das des Algorithmus. Seit man sich mit Maschinen beschaftigt, die einfache mathematische Operationen ausfuhren koennen, befasst man sich mit den Problemen, was uberhaupt berechnet werden kann und wie diese Berechnungen effizient durchgefuhrt werden koennen. Durch die Erfindung des Computers wurde die Behandlung dieser Fragen stark ge foerdert; 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, dass sowohl Stu denten als auch in der Praxis Tatige den Entwurf und die Analyse neuer Algorithmen erlernen koennen. Ein Buch, das jeden Algorithmus enthalt, der jemals erfunden wur de, musste 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 Loesungsalgorithmus vorgestellt und analysiert. Da wir mehrere Jahre lang Kurse nach dieser Methode abgehalten haben, kennen wir den grossen 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.
目次
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.- UEbungen.- 2. Elementare Datenstrukturen.- 2.1 Keller und Schlangen.- 2.2 Baume.- 2.3 Halden und Sortieren mit Halden.- 2.4 Mengen und Vereinigung disjunkter Mengen.- 2.5 Graphen.- 2.6 Hash-Technik.- Literaturhinweise.- UEbungen.- 3. Das Prinzip "Teile-und-Herrsche".- 3.1 Die allgemeine Methode.- 3.2 Binare 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.- UEbungen.- 4. Die Greedy-Methode.- 4.1 Die allgemeine Methode.- 4.2 Optimale Speicherung auf Bandern.- 4.3 Das Rucksackproblem.- 4.4 Erstellen von Auftragsfolgen mit Schlussterminen.- 4.5 Optimale Mischmuster.- 4.6 Minimale spannende Baume.- 4.7 Kurzeste Wege bei einer einzigen Quelle.- Literaturhinweise 227 UEbungen.- 5. Dynamisches Programmieren.- 5.1 Die allgemeine Methode.- 5.2 Mehrstufige Graphen.- 5.3 Bestimmung aller kurzesten Wege.- 5.4 Optimale binare Suchbaume.- 5.5 0/1-Rucksack.- 5.6 Entwurf zuverlassiger Systeme.- 5.7 Das Problem des Handlungsreisenden.- 5.8 Zeitplanung von Flussbetrieben.- Literaturhinweise.- UEbungen.- 6. Elementare Such- und Durchlauftechniken.- 6.1 Die Techniken.- 6.2 Codeoptimierung.- 6.3 UND/ODER-Graphen.- 6.4 Spielbaume.- 6.5 Doppelt zusammenhangende Komponenten und die Suchmethode "Zuerst in die Tiefe gehen".- Literaturhinweise.- UEbungen.- 7. Ruckverfolgung.- 7.1 Die allgemeine Methode.- 7.2 Das 8-Damen-Problem.- 7.3 Summe von Teilmengen.- 7.4 Farben von Graphen 4.- 7.5 Hamilton'sehe Kreise.- 7.6 Das Rucksackproblem.- Literaturhinweise.- UEbungen.- 8. Verzweigen und Beschranken.- 8.1 Die Methode.- 8.2 Das Null/Eins-Rucksackproblem.- 8.3 Das Problem des Handlungsreisenden.- 8.4 Effizienz-Betrachtungen.- Literaturhinweise.- UEbungen.- 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.- bungen.- 10. Theorie der Unteren Schranke.- 10.1 Vergleichsbaume zum Sortieren und Suchen.- 10.2 Orakel und Umkehrschluss.- 10.3 Techniken fur algebraische Probleme.- 10.4 Einige untere Schranken fur parallele Berechnungen.- Literaturhinweise.- UEbungen.- 11. NP-Schwere und NP-Vollstandige 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.- UEbungen.- 12. Approximationsalgorithmen fur NP-Schwere Probleme.- 12.1 Einfuhrung.- 12.2 Absolute Approximation.- 12.3 ? - Approximation.- 12.4 Polynomiale Approximationsschemata.- 12.5 Voll-polynomiale Approximationsschemata.- 12.6 Probabilistisch gute Algorithmen.- Literaturhinweise.- UEbungen.- Anhang A. Sparks.- Stichwortverzeichnis.
「Nielsen BookData」 より