Hasso-Plattner-Institut
  
    • de
 

Christoph Meinel: "Effiziente Algorithmen". Fachbuchverlag Leipzig, 1991

Inhaltsverzeichnis

EINLEITUNG
1. MASCHINENMODELL UND KOMPLEXITÄT
  • 1.1 Aufbau und Wirkungsweise einer Registermaschine
  • 1.2 Komlexitätsanalyse von Algorithmen
  • 1.3 Asymptotische Komplexitätsanalyse von Algorithmen
  • 1.4 PIDGIN-PASCAL - eine höhere Programmiersprache
  • 1.5 Literaturhinweise
2. ÜBER DIE PRINZIPIELLE UND PRAKTISCHE LÖSBARKEIT VON PROBLEMEN
2.1 Berechenbarkeit
  • 2.1.1. RM-berechenbare Funktionen
  • 2.1.2. Partiell rekursive Funktionen
  • 2.1.3. Churchsche These
2.2 Diagonalisierung und Reduktionstechniken
  • 2.2.1. Diagonalisierung
  • 2.2.2. Reduktion
2.3 Praktisch realisierbare und praktisch unrealisierbare Berechnungen
2.4 Literaturhinweise
3. GRUNDLEGENDE DATENSTRUKTUREN
3.1 Felder
3.2 Listen
  • 3.2.1 Stapel
  • 3.2.2 Schlangen
3.3 Bäume
3.4 Literaturhinweise
4. GRUNDLEGENDE ENTWURFSTECHNIKEN FÜR EFFIZIENTE ALGORITHMEN
4.1 Die Methode des "Teile-und Herrsche"
4.2 Rekursive Algorithmen
  • 4.2.1. Analyse rekursiver Algorithmen
  • 4.2.2. Implementierung rekursiver Algorithmen auf Registermaschinen
4.3 Dynamisches Programmieren
4.4 Die Greedy-Methode
4.5 Such- und Durchlauftechniken
4.6 Literaturhinweise
5. EFFIZIENTES SORTIEREN
5.1 Sortieren durch Vergleich
  • 5.1.1. Eine untere Schranke für die Anzahl der Vergleiche
  • 5.1.2. Sortieren durch Mischen: Mergesort
  • 5.1.3. Sortieren durch Auswahl: Heapsort
  • 5.1.4. Sortieren durch Teilen: Quicksort
  • 5.1.5. Kurzer Vergleich der vorgestellten Verfahren
5.2 Sortieren strukturierter Schlüssel
  • 5.2.1. Fachverteilung von Wörtern: Bucketsort
  • 5.2.2. Sortieren reeller Zahlen durch Verteilen: Hybridsort
  • 5.2.3. Ein linearer Sortieralgorithmus große Zahlen
Literaturhinweise
6. EFFIZIENTES VERWALTEN VON (DATEN-) MENGEN
6.1 Elementare rechnerinterne Darstellung von Mengen
6.2 Verwalten durch Hashing
6.3 Verwalten von Mengen mit binären Suchbäumen
6.4 Balancieren von Suchbäumen
6.5 Optimale Suchbäume
6.6 Union-Find-Algorithmen
6.7 Literaturhinweise
7. EFFIZIENTE ALGORITHMEN AUF GRAPHEN
7.1 Graphen und ihre rechnerinterne Darstellung
7.2 Aufspannende Bäume mit minimalen Kosten
7.3 Durchsuchen und Durchlaufen von Graphen
  • 7.3.1. Methode des "Zuerst in die Tiefe gehen"
  • 7.3.2. Anwendungsbeispiele
  • 7.3.3. Methode des "Zuerst in die Breite gehen"
7.4 Ebene Graphen
  • 7.4.1. Ausblick: Planaritätstest
  • 7.4.2. Separatortheorem für ebene Graphen
  • 7.4.3. Maximale Paarungen in ebenen Graphen
7.5 Wegprobleme in Graphen
  • 7.5.1. Allgemeines Wegproblem
  • 7.5.2. Transitiver Abschluß
  • 7.5.3. Kürzeste und kostengünstigste Wege
  • 7.5.4. Wegprobleme und Matrizenmultiplikation
7.6 Literaturhinweise
8. EFFIZIENTE ALGEBRAISCHE BERECHNUNGEN
8.1 Schnelle Matrizenmultiplikation und ihre Anwendung
  • 8.1.1. Schnelle Matrizenmultiplikation nach Strassen
  • 8.1.2. Weitere asymptotische Verbesserungen
  • 8.1.3. Schnelle Invertierung von Matrizen
  • 8.1.4. Schnelle Determinantenberechnung
  • 8.1.5. Schnelle Boolesche Matrizenmultiplikation
8.2. Auswertung und Interpolation von Polynomen
  • 8.2.1. Rechnerinterne Darstellung von Polynomen
  • 8.2.2 Auswertung von Polynomen
  • 8.2.3. Interpolation
8.3 Schnelle Fourier-Transformation und ihre Anwendung
  • 8.3.1. (Diskrete) Fourier-Transformation
  • 8.3.2. Schnelle Fourier-Transformation
  • 8.3.3. Nichtrekursive schnelle Fourier-Transformation
  • 8.3.4. Schnelle Auswertung und Interpolation
  • 8.3.5. Schnelle Berechnung der Konvolution
  • 8.3.6. Schnelle Multiplikation von Polynomen
  • 8.3.7. Ausblick: Schnelle Multiplikation von n-Bit Zahlen
8.4. Modulare Arithmetik
  • 8.4.1. Grundlagen der modularen Arithmetik
  • 8.4.2. Effiziente Berechnung der modularen Darstellung
  • 8.4.3. Implementation des Chinesischen Restsatzes
8.5. Literaturhinweise
LITERATURVERZEICHNIS
STICHWORTVERZEICHNIS