Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


Inhaltsverzeichnis



[ zurück zum Titelblatt ]



Grundlagen

  1. Grundlagen
    Einführung

    Algorithmen
    Themenübersicht

  2. Pascal
    Beispiel: Euklidischer Algorithmus
    Datentypen
    Ein-/Ausgabe
    Abschließende Bemerkungen
    Übungen

  3. Elementare Datenstrukturen
    Felder
    Verkettete Listen
    Speicherzuweisung
    Stapel
    Schlangen
    Abstrakte Datentypen
    Übungen

  4. Bäume
    Terminologie
    Eigenschaften
    Darstellung binärer Bäume
    Darstellung von Wäldern
    Traversierung von Bäumen
    Übungen

  5. Rekursion
    Rekurrente Beziehungen
    Teile und Herrsche
    Rekursive Traversierung von Bäumen
    Beseitigung der Rekursion
    Ausblick
    Übungen

  6. Analyse von Algorithmen
    Rahmen
    Klassifikation von Algorithmen
    Berechnungskomplexität
    Analyse des durchschnittlichen Falles
    Näherungsweise und asymptotische Ergebnisse
    Grundlegende rekurrente Beziehungen
    Ausblick
    Übungen

  7. Implementation von Algorithmen
    Auswahl eines Algorithmus
    Empirische Analyse
    Programmoptimierung
    Algorithmen und Systeme
    Übungen

    Literatur zu den Grundlagen

[ zurück nach oben ]



Sortieralgorithmen

  1. Elementare Sortierverfahren
    Spielregeln
    Selection Sort
    Insertion Sort
    Exkurs: Bubble Sort
    Kenngrößen der Leistungsfähigkeit elementarer Sortiermethoden
    Sortieren von Dateien mit großen Datensätzen
    Shellsort
    Distribution Counting
    Übungen

  2. Quicksort
    Der grundlegende Algorithmus
    Kenngrößen der Leistungsfähigkeit von Quicksort
    Beseitigung der Rekursion
    Kleine Teildateien
    Zerlegung mit Hilfe des mittleren von drei Elementen
    Auswählen
    Übungen

  3. Digitales Sortieren
    Bits
    Radix Exchange Sort
    Straight Radix Sort
    Kenngrößen der Leistungsfähigkeit digitaler Sortierverfahren
    Ein lineares Sortierverfahren
    Übungen

  4. Prioritätswarteschlangen
    Elementare Implementationen
    Die Datenstruktur des Heaps
    Algorithmen mit Heaps
    Heapsort
    Indirekte Heaps
    Weiterentwickelte Implementationen
    Übungen

  5. Mergesort
    Mischen
    Mergesort
    Mergesort von Listen
    Bottom-Up Mergesort
    Kenngrößen der Leistungsfähigkeit
    Optimierte Implementationen
    Weitere Bemerkungen zur Rekursion
    Übungen

  6. Externes Sortieren
    Sortieren-Mischen
    Ausgeglichenes Mehrweg-Mischen
    Replacement Selection
    Praktische Erwägungen
    Mehrphasen-Mischen
    Ein einfacherer Weg
    Übungen

    Literatur für Sortieren

[ zurück nach oben ]



Suchalgorithmen

  1. Elementare Suchmethoden
    Sequentielle Suche
    Binäre Suche
    Suche in einem Binärbaum
    Löschen
    Indirekte binäre Suchbäume
    Übungen

  2. Ausgeglichene Bäume
    Top-Down 2-3-4-Bäume
    Rot-Schwarz-Bäume
    Andere Algorithmen
    Übungen

  3. Hashing
    Hash-Funktionen
    Getrennte Verkettung
    Lineares Austesten
    Doppeltes Hashing
    Ausblick
    Übungen

  4. Digitales Suchen
    Digitale Suchbäume
    Digitale Such-Tries
    Digitales Mehrwege-Suchen
    Patricia
    Übungen

  5. Externes Suchen
    Indexsequentieller Zugriff
    B-Bäume
    Erweiterbares Hashing
    Virtueller Speicher
    Übungen

    Literatur für Suchen

[ zurück nach oben ]



Verarbeitung von Zeichenfolgen

  1. Suchen in Zeichenfolgen
    Kurzer historischer Abriß
    Der grobe Algorithmus
    Der Algorithmus von Knuth-Morris-Pratt
    Der Algorithmus von Boyer-Moore
    Der Algorithmus von Rabin-Karp
    Mehrfache Suche
    Übungen

  2. Pattern Matching
    Beschreibung von Mustern
    Automaten für das Pattern Matching
    Darstellung des Automaten
    Simulation des Automaten
    Übungen

  3. Syntaxanalyse (Parsing)
    Kontextfreie Grammatiken
    Der rekursive Abstieg (Top-Down-Syntaxanalyse)
    Bottom-Up-Syntaxanalyse
    Compiler
    Compiler-Compiler
    Übungen

  4. Datenkomprimierung
    Lauflängenkodierung
    Kodierung mit variabler Länge
    Erzeugung des Huffman-Codes
    Implementation
    Übungen

  5. Kryptologie
    Spielregeln
    Einfache Methoden
    Ver- und Entschlüsselungsmaschinen
    Kryptosysteme mit öffentlichen Schlüsseln
    Übungen

    Literatur für Verarbeitung von Zeichenfolgen

[ zurück nach oben ]



Geometrische Algorithmen

  1. Elementare geometrische Methoden
    Punkte, Linien und Polygone
    Schnitt von Strecken
    Einfacher geschlossener Pfad
    Enthaltensein in einem Polygon
    Ausblick
    Übungen

  2. Bestimmung der konvexen Hülle
    Spielregeln
    Einwickeln
    Das Durchsuchen nach Graham
    Innere Elimination
    Aspekte der Leistungsfähigkeit
    Übungen

  3. Bereichssuche
    Elementare Verfahren
    Gitterverfahren
    Zweidimensionale Bäume
    Mehrdimensionale Bereichssuche
    Übungen

  4. Geometrischer Schnitt
    Horizontale und vertikale Linien
    Implementation
    Allgemeiner Schnitt von Strecken
    Übungen

  5. Probleme des nächsten Punktes
    Das Problem des nächsten Paares
    Voronoi-Diagramme
    Übungen

    Literatur für Geometrische Algorithmen

[ zurück nach oben ]



Algorithmen für Graphen

  1. Elementare Algorithmen für Graphen
    Glossar
    Darstellung
    Tiefensuche
    Nichtrekursive Tiefensuche
    Breitensuche
    Labyrinthe
    Ausblick
    Übungen

  2. Zusammenhang
    Zusammenhängende Komponenten
    Zweifacher Zusammenhang
    Algorithmen zur Vereinigungs-Suche
    Übungen

  3. Gewichtete Graphen
    Minimaler Spannbaum
    Prioritätssuche
    Das Verfahren von Kruskal
    Kürzester Pfad
    Minimaler Spannbaum und kürzeste Pfade in dichten Graphen
    Geometrische Probleme
    Übungen

  4. Gerichtete Graphen
    Tiefensuche
    Transitive Hülle
    Alle kürzesten Pfade
    Topologisches Sortieren
    Streng zusammenhängende Komponenten
    Übungen

  5. Fluß in einem Netzwerk
    Das Problem des Flusses in einem Netzwerk
    Das Verfahren von Ford-Fulkerson
    Suche in Netzwerken
    Übungen

  6. Paarung
    Bipartite Graphen
    Problem der stabilen Ehe
    Weiterentwickelte Algorithmen
    Übungen

    Literatur für Algorithmen für Graphen

[ zurück nach oben ]



Mathematische Algorithmen

  1. Zufallszahlen
    Anwendungen
    Methode der linearen Kongruenz
    Methode der additiven Kongruenz
    Test der Zufälligkeit
    Bemerkungen zur Implementation
    Übungen

  2. Arithmetik
    Arithmetik für Polynome
    Berechnung und Interpolation von Polynomen
    Multiplikation von Polynomen
    Rechenoperationen mit großen ganzen Zahlen
    Rechenoperationen mit Matrizen
    Übungen

  3. Gaußsches Eliminationsverfahren
    Ein einfaches Beispiel
    Beschreibung des Verfahrens
    Variationen und Erweiternungen
    Übungen

  4. Kurvenanpassung
    Interpolation mit Hilfe von Polynomen
    Spline-Interpolation
    Methode der kleinsten Quadrate
    Übungen

  5. Integration
    Symbolische Integration
    Einfache Quadraturverfahren
    Zusammengesetzte Verfahren
    Adaptive Quadratur
    Übungen

    Literatur für Mathematische Algorithmen

  6. [ zurück nach oben ]



Weiterführende Themen

  1. Parallele Algorithmen
    Allgemeine Ansätze
    Perfektes Mischen
    Systolische Felder
    Ausblick
    Übungen

  2. Die schnelle Fourier-Transformation
    Berechnen, Multiplizieren, Interpolieren
    Komplexe Einheitswurzeln
    Berechnung in den Einheitswurzeln
    Interpolation mit Hilfe der Einheitswurzeln
    Implementation
    Übungen

  3. Dynamische Programmierung
    Das Rucksack-Problem
    Das Produkt mehrerer Matrizen
    Optimale binäre Suchbäume
    Zeit- und Speicheraufwand
    Übungen

  4. Lineare Programmierung
    Lineare Optimierungsaufgaben
    Geometrische Interpretation
    Die Simplexmethode
    Implementation
    Übungen

  5. Erschöpfendes Durchsuchen
    Erschöpfendes Durchsuchen in Graphen
    Backtracking
    Digression: Erzeugung von Permutationen
    Approximationsalgorithmen
    Übungen

  6. NP-vollständige Probleme
    Deterministische und nichtdeterministische Algorithmen mit polynomialer Zeit
    NP-Vollständigkeit
    Der Satz von Cook
    Einige NP-vollständige Probleme
    Übungen
[ zurück nach oben ]


[ zurück nach oben ]

[ zurück zum Titelblatt ]


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]