Algorithmentheorie

ISBN-13: 9783540079330 / Niemiecki / Miękka / 1976 / 226 str.

J. Loeckx

Opis

Die Algorithmentheorie ist Ende der dreiBiger Jahre entstanden in Ver bindung mit Problemen der mathematischen Logik. Hit dem Aufkommen einer wissenschaftlich fundierten Informatik hat sie, insbesondere in den letzten zwanzig Jahren, an Bedeutung und Tragweite gewonnen. Das wird begreiflich, wenn man bedenkt, daB ein Programm flir eine elektronische Rechenanlage im wesentlichen ein Algorithmus ist und daB Resultate der Algorithmentheorie deshalb auch auf Programme anwendbar sind. Insbeson dere gibt es eine enge Verbindung zwischen der Algorithmentheorie und anderen flir die Informatik bedeutsamen Zweigen, wie der Automatentheorie, der Theorie der formalen Sprachen und der sich in den letzten Jahren heranbildenden Theorie der Programmierung. Wahrend die meisten Blicher liber Algorithmentheorie sich an Studenten der mathematischen Logik richten, ist dieses Buch flir Informatikstuden ten bestimmt. Zwar wird das Thema mit mathematischer Scharfe behandelt, aber es werden keine besonderen mathematischen Kenntnisse vorausgesetzt und die zahlreichen Kommentare zielen daraufhin, ein gutes intuitives Verstandnis zu ermoglichen; auBerdem hebt das Buch regelmaBig die Be deutung der Resultate flir die Informatik hervor. SchlieBlich sind die Notationen und bestimmte Beweismethoden der Automatentheorie und der Theorie der formalen Sprachen entnommen; insbesondere wird grundsatz lich mit Worten statt mit natlirlichen Zahlen gearbeitet."

Spis treści

0: Einige Begriffe und Notationen.- 0.1 Mengen und Funktionen.- 0.1.1 Mengen.- 0.1.2 Funktionen.- 0.1.3 Einige spezielle Funktionen.- 0.2 Zeichen und Worte.- 0.2.1 Zeichenreihen und Worte.- 0.2.2 Wortfunktionen.- 0.2.3 Eine Bemerkung zur Interpretation.- 1 Grundbegriffe.- 1.1 Algorithmen.- 1.1.1 Der Begriff Algorithmus.- 1.1.2 Der Begriff der berechenbaren Funktion.- 1.1.2.1 Algorithmische und algebraische Definitionen.- 1.1.2.2 Berechenbare Funktionen.- 1.1.2.3 Der Fall der partiellen Funktionen.- 1.1.2.4 Algorithmen und berechenbare Funktionen.- 1.1.3 Eine Präzisierung des Begriffs Algorithmus.- 1.1.4 Algorithmentheorie.- 1.1.5 Historischer Hintergrund der Algorithmentheorie.- 1.1.6 Algorithmentheorie und Informatik.- 1.2 Abzählbarkeit.- 1.2.1 Einleitung.- 1.2.2 Abzählbare Mengen.- 1.2.3 Satz.- 1.2.4 Satz.- 1.2.5 Satz.- 1.2.6 Eine intuitive Erklärung.- 1.3 Abzählungen von Worten.- 1.3.1 Eine Abzählung von V*…..21.- 1.3.2 Eine Abzählung von V*n…..23.- 1.3.2.1 Einleitung.- 1.3.2.2 Eine Abzählung von Nn…..24.- 1.3.2.3 Eine Abzählung von V*n…..26.- 1.3.2.4 Bemerkung.- 1.3.3 Die Funktionen VnWm.- 1.3.4 Bemerkung.- 1.3.5 Satz.- 2: Die Turing-Maschine.- 2.1 Definition der Turing-Maschine.- 2.1.1 Der Grundgedanke.- 2.1.2 Das physikalische Modell.- 2.1.2.1 Die Maschine.- 2.1.2.2 Die Arbeitsweise.- 2.1.2.3 Die Definition einer Funktion.- 2.1.2.4 Der Speicher der Turing-Maschine.- 2.1.3 Die formale Definition.- 2.1.3.1 Die Maschine.- 2.1.3.2 Die Konfiguration.- 2.1.3.3 Die Funktion succ.- 2.1.3.4 Drei Relationen.- 2.1.3.5 Die von einer Turing-Maschine definierte Funktion.- 2.1.4 Beispiele.- 2.1.5 Berechenbare Funktionen.- 2.1.6 Die These von Turing.- 2.1.7 Eine wichtige Bemerkung.- 2.1.8 Eine weitere Bemerkung.- 2.1.9 Die Berechenbarkeit anderer Funktionen als Wortfunktionen.- 2.2 Einige spezielle Turing-Maschinen.- 2.2.1 Einleitung.- 2.2.2 Echte Startzustände und Endzustände.- 2.2.3 Normalisierte Turing-Maschinen.- 2.2.4 Reduktion des Zeichenvorrats einer Turing-Maschine.- 2.2.5 Turing-Maschinen mit mehreren Bändern.- 2.2.6 Eine äquivalente Definition der Berechenbarkeit für Funktionen mit n tupeln als Werte.- 2.3 Die universelle Turing-Maschine.- 2.3.1 Der Grundgedanke.- 2.3.2 Die Beschreibung einer Turing-Maschine mittels eines Wortes.- 2.3.2.1 Der Zeichenvorrat W.- 2.3.2.2 Das Wort DET.- 2.3.2.3 Beispiele.- 2.3.2.4 Die V-Beschreibung.- 2.3.3 Weitere Definitionen und Notationen.- 2.3.3.1 Die Mengen DE und D.- 2.3.3.2 Die Turing-Maschinen TE(x) und T(x).- 2.3.3.3 Gödel-Nummer.- 2.3.4 Die universelle Turing-Maschine.- 2.3.4.1 Simulation einer Turing-Maschine.- 2.3.4.2 Eine universelle Turing-Maschine.- 2.3.5 Kommentar.- 2.3.6 Konstruktionen mit Turing-Maschinen.- 2.4 Einige nicht-berechenbare Funktionen.- 2.4.1 Das Halteproblem.- 2.4.2 Das Halteproblem bei leerem Band.- 2.4.3 Das uniforme Halteproblem.- 2.4.4 Das Äquivalenzproblem.- 2.4.5 Schlußbemerkung.- 2.5 Rekursiv-aufzählbare und rekursive Mengen.- 2.5.1 Definitionen.- 2.5.2 Der Bildbereich einer totalen berechenbaren Funktion.- 2.5.3 Die Akzeptorfunktion.- 2.5.4 Die Beziehung zwischen rekursiv-aufzählbaren und rekursiven Mengen.- 2.5.5 Beispiele von Mengen, die rekursiv-aufzählbar, aber nicht rekursiv sind.- 2.5.6 Beispiele von Mengen, die nicht rekursiv-aufzählbar sind.- 2.5.7 Quantifizierungen von Mengen.- 2.5.8 Effektive Abzählungen von Funktionen und Mengen.- 2.5.8.1 Die berechenbaren Funktionen.- 2.5.8.2 Die rekursiv-aufzählbaren Mengen.- 2.5.8.3 Bemerkung.- 2.5.9 Kommentar.- 2.5.9.1 Ein praktischer Aspekt.- 2.5.9.2 Eine graphische Darstellung.- 2.5.9.3 Über die Natur von rekursiv-aufzählbaren und rekursiven Mengen.- 2.5.9.4 Axiomatische Systeme.- 2.5.9.5 Über die Nützlichkeit partieller Funktionen.- 3: Andere Formalismen als Turing-Maschinen.- 3.1 Die rekursiven Funktionen.- 3.1.1 Einleitung.- 3.1.2 Definition.- 3.1.2.1 Die axiomatische Definitionsmethode.- 3.1.2.2 Die Basisfunktionen.- 3.1.2.3 Die Komposition.- 3.1.2.4 Die Rekursion.- 3.1.2.5 Die Minimalisierung.- 3.1.2.6 Definitionen.- 3.1.2.7 Satz.- 3.1.2.8 Wichtige Bemerkungen.- 3.1.3 Beispiele.- 3.1.4 Endliche Funktionen.- 3.1.5 Das Ziel der nächsten Abschnitte.- 3.1.6 Fallunterscheidung.- 3.1.7 Erweiterte Initialisierung.- 3.1.8 Simultane Rekursion.- 3.1.9 Rekursion mit variablen Schritten.- 3.1.10 Reduktion des Zeichenvorrats.- 3.1.11 Die Äquivalenz von berechenbaren und rekursiven Funktionen.- 3.1.12 Wortbeschreibungen, die universelle rekursive Funktion und unlösbare Probleme.- 3.1.12.1 Wortbeschreibungen.- 3.1.12.2 Satz.- 3.1.12.3 Unlösbare Probleme.- 3.1.13 Verallgemeinerung für andere Funktionen als Wortfunktionen.- 3.1.14 Satz.- 3.2 Die Markov-Algorithmen.- 3.2.1 Einleitung.- 3.2.2 Definitionen.- 3.2.2.1 Der Markov-Algorithmus.- 3.2.2.2 Informelle Beschreibung des Markov- Algorithmus.- 3.2.2.3 Drei Relationen.- 3.2.2.4 Die von einem Markov-Algorithmus definierte Funktion.- 3.2.2.5 Markov-berechenbare Funktionen.- 3.2.3 Beispiele.- 3.2.4 Die Äquivalenz mit Turing-Maschinen.- 3.2.5 Bemerkung.- 4: Nicht-deterministische Algorithmen und Grammatiken.- 4.1 Die Begriffe.- 4.1.1 Nicht-deterministische Algorithmen.- 4.1.2 Die formale Definition nicht-deterministischer Algorithmen.- 4.1.3 Grammatiken.- 4.1.4 Axiomatische Systeme.- 4.2 Semi-Thue-Algorithmen und semi-Thue-Grammatiken.- 4.2.1 Semi-Thue-Algorithmen.- 4.2.1.1 Informelle Beschreibung.- 4.2.1.2 Formale Definition.- 4.2.1.3 Beispiele.- 4.2.2 Semi-Thue-Grammatiken.- 4.2.2.1 Einleitung.- 4.2.2.2 Formale Definition.- 4.2.2.3 Beispiel.- 4.2.2.4 Kontextfreie Grammatiken.- 4.2.3 Semi-Thue-Grammatiken und rekursiv-aufzählbare Mengen.- 4.2.4 ?-freie semi-Thue-Grammatiken.- 4.2.5 Weiterentwicklung der Theorie.- 4.2.6 Das Korrespondenzproblem von Post.- Eine Schlußbemerkung.- Literatur.- Lösungen und Lösungshinweise der wichtigsten Übungen.- Die wichtigsten Notationen.- Alphabetische Liste der wichtigsten Funktionen.- Alphabetisches Sachregister.