Algorithmentheorie

Inhaltsverzeichnis

• 0: Einige Begriffe und Notationen.
• 0.1 Mengen und Funktionen.
• 0.2 Zeichen und Worte.
• 1 Grundbegriffe.
• 1.1 Algorithmen.
• 1.2 Abzählbarkeit.
• 1.3 Abzählungen von Worten.
• 2: Die Turing-Maschine.
• 2.1 Definition der Turing-Maschine.
• 2.2 Einige spezielle Turing-Maschinen.
• 2.3 Die universelle Turing-Maschine.
• 2.4 Einige nicht-berechenbare Funktionen.
• 2.5 Rekursiv-aufzählbare und rekursive Mengen.
• 3: Andere Formalismen als Turing-Maschinen.
• 3.1 Die rekursiven Funktionen.
• 3.2 Die Markov-Algorithmen.
• 4: Nicht-deterministische Algorithmen und Grammatiken.
• 4.1 Die Begriffe.
• 4.2 Semi-Thue-Algorithmen und semi-Thue-Grammatiken.
• Eine Schlußbemerkung.
• Literatur.
• Lösungen und Lösungshinweise der wichtigsten Übungen.
• Die wichtigsten Notationen.
• Alphabetische Liste der wichtigsten Funktionen.
• Alphabetisches Sachregister.