1 Einführung
1.1 Prinzipielle Lösbarkeit
1.2 Praktisch unlösbare Probleme
1.3 Empirische Analyse
1.4 Bit-Komplexität
1.5 Probleminstanzen und Analyseformen
1.6 Vergleich von Aufwänden

2 Effizienz von Algorithmen
2.1 Effizienzbegriff
2.2 Aufwand: Polynomial versus exponentiell
2.3 Analyse mit Wahrscheinlichkeiten
2.4 Asymptotische Aufwandsordnungen

3 Hilfsmittel "Mathematik"
3.1 Approximation von Funktionen
3.1.1 Exponentialfunktionen
3.1.2 Polynomfunktionen
3.2 Rekursionsgleichungen
3.2.1 Rekursions- oder rekurrente Gleichungen
3.2.2 Computeralgebrasysteme (CAS)
3.2.3 Raten und Einsetzen
3.2.4 Konstruktive Induktion
3.2.5 Iterationsmethode
3.2.6 Die Meistermethode (master method)
3.2.7 Charakteristische Gleichung

4Teile und herrsche
4.1 Die Idee
4.2 Quicksort
4.2.1 Das Verfahren
4.2.2 Funktionsorientierte Beschreibung
4.2.3 Effizienz von Quicksort
4.2.4 Interne Suchverfahren
4.3 Mergesort
4.3.1 Das Verfahren
4.3.2 Funktionsorientierte Beschreibung mit Multiple-value-context
4.3.3 Effizienzanalysen
4.4 Binäres Suchen
4.4.1 Das Verfahren
4.4.2 Funktionsorientierte Beschreibung mit Multiple-value-context
4.4.3 Effizienzanalysen
4.5 Multiplikation großer ganzer Zahlen
4.6 Schnelle Matrixmultiplikation

5 Systematische Suche
5.1 Rucksackprobleme
5.2 Tiefensuche
5.3 Breitensuche
5.4 Beschränkung des Suchbaumes
5.5 Nichtdeterminismus

6 Verzweigen und Beschränken
6.1 Bewerten, auswählen und expandieren
6.2 Anwendung auf das Rucksackproblem
6.3 Das Rundreiseproblem
6.3.1 Problemstellung
6.3.2 Naiver Algorithmus
6.3.3 Lösung mit Verzweigen und Beschränken

7 Dynamisches Programmieren
7.1 "Bottom up" versus "top down"
7.2 Traditionell: Iterative Berechnung
7.3 Aufwandsbetrachtung
7.4 Rekursive Berechnung mit memoizing
7.5 Lösung des Rundreiseproblems

8 Greedy-Algorithmen
8.1 Idee
8.2 Bruchteilrucksack
8.3 Aufbau von Greedy-Algorithmen
8.4 Kürzeste Wege in Graphen
8.5 Minimaler Spannbaum

9 Probabilistische Algorithmen
9.1 Effizienzverbesserung
9.2 Pseudozufallszahlen
9.3 Numerische probabilistische Algorithmen
9.4 Las-Vegas-Algorithmen
9.5 Monte-Carlo-Algorithmen
9.5.1 Beschreibung des Verfahrens
9.5.2 Äquivalenz zweier Multimengen
9.5.3 Primzahltest nach Fermat
9.5.4 Primzahltest von Solovay und Strassen

10 P =? =NP
10.1 Probleme, Sprachen und Entscheidbarkeit
10.2 Die Klassen P und NP
10.3 NP-Vollständigkeit
10.3.1 Polynomiale Reduktion
10.3.2 NP-schwere Probleme
10.3.3 NP-vollständige Probleme
10.3.4 Nachweis der NP-Vollständigkeit eines Problems
10.4 Satz von Steven A. Cook (1971)
10.5 Vorteile praktischer Unlösbarkeit
10.6 Das RAMSEY-Problem
10.7 Pseudopolynomiale Algorithmen

11 Effiziente Näherungsalgorithmen
11.1 Approximation des Optimums
11.2 Heuristiken
11.2.1 Begriff
11.2.2 Heuristiken für das Springerproblem
11.3 Lokale Suche
11.3.1 Verzweigen und Begrenzen, Greedy und hill climbing
11.3.2 Threshold accepting, simulated annealing, Tabu-Suche
11.3.3 Der Sintflut-Algorithmus
11.4 DNA Computing und evolutionäre Algorithmen
11.4.1 Molekulargenetische Grundlagen und DNA Computing
11.4.2 Evolutionäre Algorithmen
11.4.3 Neuronale Netze
11.5 Polynomzeit-Näherungsschema

Literaturverzeichnis

Sachwortverzeichnis