دانلود کتاب Algorithmen - Eine Einführung

فهرست مطالب :

Inhaltsverzeichnis\nVorwort\nI Grundlagen\n 1 Die Rolle von Algorithmen in der elektronischen Datenverarbeitung\n 1.1 Algorithmen\n 1.2 Algorithmen als Technologie\n 2 Ein einführendes Beispiel\n 2.1 Sortieren durch Einfügen\n 2.2 Analyse von Algorithmen\n 2.3 Entwurf von Algorithmen\n 3 Wachstum von Funktionen\n 3.1 Asymptotische Notation\n 3.2 Standardnotationen und Standardfunktionen\n 4 Teile-und-Beherrsche\n 4.1 Das Max-Teilfeld-Problem\n 4.2 Strassens Algorithmus zur Matrizenmultiplikation\n 4.3 Die Substitutionsmethode zum Lösen von Rekursionsgleichungen\n 4.4 Die Rekursionsbaum-Methode zum Lösen von Rekursionsgleichungen\n 4.5 Die Mastermethode zum Lösen von Rekursionsgleichungen\n 4.6* Beweis des Mastertheorems\n 5 Probabilistische Analyse und randomisierte Algorithmen\n 5.1 Das Bewerberproblem\n 5.2 Indikatorfunktionen\n 5.3 Randomisierte Algorithmen\n 5.4 * Probabilistische Analyse und mehr zur Verwendung der Indikatorfunktion\nII Sortieren und Ranggrößen\n 6 Heapsort\n 6.1 Heaps\n 6.2 Die Heap-Eigenschaft aufrechterhalten\n 6.3 Einen Heap bauen\n 6.4 Der Heapsort-Algorithmus\n 6.5 Prioritätswarteschlangen\n 7 Quicksort\n 7.1 Beschreibung von Quicksort\n 7.2 Die Performanz von Quicksort\n 7.3 Eine randomisierte Version von Quicksort\n 7.4 Analyse von Quicksort\n 8 Sortieren in linearer Zeit\n 8.1 Untere Schranken für das Sortieren\n 8.2 Countingsort\n 8.3 Radixsort\n 8.4 Bucketsort\n 9 Mediane und Ranggrößen\n 9.1 Minimum und Maximum\n 9.2 Auswahl in linearer erwarteter Zeit\n 9.3 Auswahl in linearer Zeit im schlechtesten Fall\nIII Datenstrukturen\n 10 Elementare Datenstrukturen\n 10.1 Stapel und Warteschlangen\n 10.2 Verkettete Listen\n 10.3 Implementierung von Zeigern und Objekten\n 10.4 Darstellung von gerichteten Bäumen\n 11 Hashtabellen\n 11.1 Adresstabellen mit direktem Zugriff\n 11.2 Hashtabellen\n 11.3 Hashfunktionen\n 11.4 Offene Adressierung\n 11.5* Perfektes Hashing\n 12 Binäre Suchbäume\n 12.1 Was ist ein binärer Suchbaum?\n 12.2 Abfragen in einem binären Suchbaum\n 12.3 Einfügen und Löschen\n 12.4* Zufällig erzeugte binäre Suchbäume\n 13 Rot-Schwarz-Bäume\n 13.1 Eigenschaften von Rot-Schwarz-Bäumen\n 13.2 Rotationen\n 13.3 Einfügen eines Knotens\n 13.4 Löschen eines Knotens\n 14 Erweitern von Datenstrukturen\n 14.1 Dynamische Ranggröße\n 14.2 Wie man eine Datenstruktur erweitert\n 14.3 Intervallbäume\nIV Fortgeschrittene Entwurfs- und Analysetechniken\n 15 Dynamische Programmierung\n 15.1 Schneiden von Eisenstangen\n 15.2 Matrizen-Kettenmultiplikation\n 15.3 Elemente dynamischer Programmierung\n 15.4 Längste gemeinsame Teilsequenz\n 15.5 Optimale binäre Suchbäume\n 16 Greedy-Algorithmen\n 16.1 Ein Aktivitäten-Auswahl-Problem\n 16.2 Elemente der Greedy-Strategie\n 16.3 Huffman-Codierungen\n 16.4* Matroiden und Greedy-Methoden\n 16.5* Ein Task-Scheduling-Problem als Matroid\n 17 Amortisierte Analyse\n 17.1 Aggregat-Analyse\n 17.2 Account-Methode\n 17.3 Die Potentialmethode\n 17.4 Dynamische Tabellen\nV Höhere Datenstrukturen\n 18 B-Bäume\n 18.1 Die Definition von B-Bäumen\n 18.2 Grundoperationen auf B-Bäumen\n 18.3 Löschen eines Schlüssels aus einem B-Baum\n 19 Fibonacci-Heaps\n 19.1 Die Struktur von Fibonacci-Heaps\n 19.2 Operationen der fusionierbaren Heaps\n 19.3 Verringern eines Schlüssels und Entfernen eines Knotens\n 19.4 Beschränkung des maximalen Grades\n 20 van-Emde-Boas-Bäume\n 20.1 Vorbereitende Ansätze\n 20.2 Eine rekursive Datenstruktur\n 20.3 Die van-Emde-Boas-Bäume\n 21 Datenstrukturen disjunkter Mengen\n 21.1 Operationen auf disjunkten Mengen\n 21.2 Darstellung disjunkter Mengen mithilfe verketteter Listen\n 21.3 Wälder disjunkter Mengen\n 21.4* Analyse der Vereinigung nach dem Rang mit Pfadverkürzung\nVI Graphenalgorithmen\n 22 Elementare Graphenalgorithmen\n 22.1 Darstellungen von Graphen\n 22.2 Breitensuche\n 22.3 Tiefensuche\n 22.4 Topologisches Sortieren\n 22.5 Starke Zusammenhangskomponenten\n 23 Minimale Spannbäume\n 23.1 Aufbau eines minimalen Spannbaums\n 23.2 Die Algorithmen von Kruskal und Prim\n 24 Kürzeste Pfade von einem Startknoten aus\n 24.1 Der Bellman-Ford-Algorithmus\n 24.2 Kürzeste Pfade von einem Startknoten aus in DAGs\n 24.3 Dijkstras Algorithmus\n 24.4 Differenzbedingungen und kürzeste Pfade\n 24.5 Beweise der Eigenschaften kürzester Pfade\n 25 Kürzeste Pfade für alle Knotenpaare\n 25.1 Kürzeste Pfade und Matrizenmultiplikation\n 25.2 Der Floyd-Warshall-Algorithmus\n 25.3 Johnsons Algorithmus für dünn besetzte Graphen\n 26 Maximaler Fluss\n 26.1 Flussnetzwerke\n 26.2 Die Ford-Fulkerson-Methode\n 26.3 Maximales bipartites Matching\n 26.4* Push/Relabel-Algorithmen\n 26.5* Der Relabel-to-Front-Algorithmus\nVII Ausgewählte Themen\n 27 Mehrfädige Algorithmen\n 27.1 Grundlagen von dynamischem Multithreading\n 27.2 Mehrfädige Matrizenmultiplikation\n 27.3 Mehrfädiges Sortieren durch Mischen\n 28 Operationen auf Matrizen\n 28.1 Lösen linearer Gleichungssysteme\n 28.2 Matrixinversion\n 28.3 Symmetrische positiv definite Matrizen, Summe der quadratischen Fehler\n 29 Lineare Programmierung\n 29.1 Standard- und Schlupfform\n 29.2 Darstellung von Problemen als lineare Programme\n 29.3 Der Simplexalgorithmus\n 29.4 Dualität\n 29.5 Die initiale zulässige Basislösung\n 30 Polynome und die FFT\n 30.1 Darstellung von Polynomen\n 30.2 Die DFT und FFT\n 30.3 Effiziente Implementierung der FFT\n 31 Zahlentheoretische Algorithmen\n 31.1 Elementare zahlentheoretische Begriffe\n 31.2 Größter gemeinsamer Teiler\n 31.3 Modulare Arithmetik\n 31.4 Lösen modularer linearer Gleichungen\n 31.5 Der chinesische Restsatz\n 31.6 Potenzen eines Elements\n 31.7 Das RSA-Kryptosystem\n 31.8* Primzahltests\n 31.9* Primfaktorzerlegung\n 32 String-Matching\n 32.1 Der naive String-Matching-Algorithmus\n 32.2 Der Rabin-Karp-Algorithmus\n 32.3 String-Matching mit endlichen Automaten\n 32.4* Der Knuth-Morris-Pratt-Algorithmus\n 33 Algorithmische Geometrie\n 33.1 Eigenschaften von Strecken\n 33.2 Bestimmung von Schnittpunkten in einer Menge von Strecken\n 33.3 Bestimmen der konvexen Hülle\n 33.4 Berechnung des dichtesten Punktepaares\n 34 NP-Vollständigkeit\n 34.1 Polynomielle Zeit\n 34.2 Verifikation in polynomieller Zeit\n 34.3 NP-Vollständigkeit und Reduktion\n 34.4 NP-Vollständigkeitsbeweise\n 34.5 NP-vollständige Probleme\n 35 Approximationsalgorithmen\n 35.1 Das Knotenüberdeckungsproblem\n 35.2 Das Problem des Handelsreisenden\n 35.3 Das Mengenüberdeckungsproblem\n 35.4 Randomisierung und lineare Programmierung\n 35.5 Das Teilsummenproblem\nVIII Anhang\n A Summen\n A.1 Summenformeln und Eigenschaften\n A.2 Abschätzungen für Summen\n B Mengen usw\n B.1 Mengen\n B.2 Relationen\n B.3 Funktionen\n B.4 Graphen\n B.5 Bäume\n C Kombinatorik und Wahrscheinlichkeitstheorie\n C.1 Kombinatorik\n C.2 Wahrscheinlichkeiten\n C.3 Diskrete Zufallsvariablen\n C.4 Die geometrische Verteilung und die Binomialverteilung\n C.5* Die Ränder der Binomialverteilung\n D Matrizen\n D.1 Matrizen und Matrizenoperationen\n D.2 Elementare Matrizeneigenschaften\nLiteraturverzeichnis\nIndex