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