Berechenbarkeit und Formale Sprachen

Dozent:

Prof. Dr. rer. nat. Rolf Wanka

Modulbeschreibung:

Berechenbarkeit und Formale Sprachen

Umfang/Stunden:

V4 + Ü2, 7.5 ECTS

Zielgruppe:

Studierende des Bachelor-Studiums Informatik, 3. Semester
Studierende der Mathematik mit Nebenfach Informatik
Studierende des Master-Studiums Informatik mit entsprechender Auflage bei der Zulassung

Organisation:

Alle Informationen zur Vorlesung und Übung sind in dem StudOn-Kurs der Vorlesung vermerkt. Bitte treten Sie dem Kurs Vorlesungskurs bei. Der StudOn-Kurs der Übung wird nicht benutzt.

Inhalte:

• Turingmaschinen, die Churchsche These und Entscheidbarkeit
• NP-Vollständigkeit
• Automaten, Grammatiken und die Chomsky-Hierarchie
• Endliche Automaten und reguläre Ausdrücke
• Kontextfreie Grammatiken und Kontextfreie Sprachen
• Kellerautomaten

Video-Aufzeichnung:

Die Video-Aufzeichnung vom Wintersemester 2011/12 ist hier aus dem Uni-Netz erreichbar.
Benutzername und Passwort finden Sie im StudOn-Kurs.

YouTube-Videos zu Turingmaschinen:

• Eigene Bauteile
• Lego (Uni Aarhus)
• Busy Beaver mit 4 Zuständen

Übungen:

Detaillierte Informationen zur Abgabe der Übungen werden in der ersten Vorlesung bekannt gegeben.

Skript

• Eine offizielle Mitschrift finden Sie im StudOn-Kurs.
• Die Turingmaschine aus der Vorlesung als pdf-File.
• Das Bild mit der Ausrede, warum man kein schnelles Programm hat schreiben können, als pdf. Es stammt aus dem Buch:
  • Michel R. Garey, David S. Johnson. Computers and Intractability – A Guide to the Theory of NP-Completeness, Freeman and Co., 1979
• Beweis des Satzes, daß es zu jedem nichtdeterministischen Kellerautomaten eine äquivalente kontextfreie Grammatik gibt, als pdf (Es ist Theorem 5.4; es wird noch benötigt, dass der Keller zum Ende der Rechnung leer ist). Er stammt aus dem Buch:
  • John E. Hopcroft, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation
• Vortrag über das Halteproblem: Folien zu einem Vortrag im Schnupperstudium Informatik: Sachen gibt’s, die gibt’s gar nicht
• Die Grammatik G aus der Vorlesung, die die Sprache L = { aⁿbⁿcⁿ | n ≥ 1 } erzeugt, gibt es hier.
• Es gibt die Abschnitte 1.6 (Unentscheidbare Probleme), 1.7 (Reduktionen und der Satz von Rice) und 1.8 (Rekursive Aufzählbarkeit) in ausgearbeiteter Form hier als pdf.
• Anwendung des CYK-Algorithmus (pdf)

---

Turings Aufsatz

• Alan M. Turing.
  On Computable Numbers, With an Application to the Entscheidungsproblem, Proc. London Math. Soc. 2(42) (1936), 230-265.
• Charles Petzold.
  The Annotated Turing. A Guided Tour through Alan Turing’s Historic Paper on Computability and the Turing Machine. Wiley, 2008.

Moore’s Law

• G. E. Moore.
  Cramming more components onto integrated circuits. Electronics 38 (1965) 114-117.

Einer der Erfindungsaufsätze zu Quicksort

• C.A.R. Hoare. (Turing Award 1980) Quicksort. The Computer Journal 5 (1962) 10-16. [doi: 10.1093/comjnl/5.1.10] (Download mit IP-Adresse der Uni Erlangen)
• Bzgl. der „Zeitlosigkeit“ der Ergebnisse der Unentscheidbarkeitstheorie und der P-NP-Theorie: Achten Sie besonders auf die Fußnote der Table 1 auf S. 13!

Gotos in höheren Programmiersprachen

• Edsger W. Dijkstra. (Turing Award 1972)
  Go To Statement Considered Harmful. Communications of the ACM 11 (1968) 147-148.Besonders gefällt der Anfang: „… the quality of programmers is a decreasing function of the density of go to statements in the programs they produce.“

Grötschels Aufsatz zum Rundereiseproblem

• Martin Grötschel.
  Schnelle Rundreisen: Das Travelling-Salesman-Problem. S. 95-129.
  In: Stephan Hußmann, Brigitte Lutz-Westphal (Hrsg.). Kombinatorische Optimierung erleben. Vieweg, 2007.

Artikel aus Spektrum der Wissenschaft mit Bezug zur NP-Vollständigkeit

• Martin Grötschel und Manfred Padberg. Die optimierte Odyssee, Spektrum der Wissenschaft, April 1999 (Traveling Salesperson Problem ist NP-vollständig)
• Ian Stewart. Wer wird Millionär?, Spektrum der Wissenschaft, Mai 2002. (Minesweeper ist NP-vollständig)
• Barry Cipra. Wer wird Millionär?, Spektrum der Wissenschaft, November 2003. (Über die Millennium-Probleme; ganz unten über die P-NP-Problematik)
• Jean-Paul Delahaye, Sudoku oder die einsamen Zahlen, Spektrum der Wissenschaft, März 2006, S. 100-106. (inkl. Linkliste; Sudoku ist NP-vollständig)

Populärwissenschaftlich-Literarisches

• Douglas R. Hofstadter. Gödel, Escher, Bach – ein Endloses Geflochtenes Band. dtv, 1991.
  Für dieses sehr gute Buch erhielt Hofstadter 1980 den Pulitzer-Preis. Es enthält anschauliche Diskussionen (auch des Beweises) des Gödelschen Unvollständigkeitssatzes, Universeller Turingmaschinen, Formaler Ersetzungssysteme, … Immer wieder sind Selbstanwendungen (wie die beim Beweis der Unentscheidbarkeit des Halteproblems) das Thema. Selbstanwendungen werden auch in der darstellenden Kunst und der Musik beschrieben.
  Läßt man sich am besten zum Geburtstag schenken :-) Aber Achtung: Wenn es um schwierigen Stoff geht, ist auch das Lesen schwierig.
• Simon Singh. Fermats letzter Satz. dtv, 2000.
  Es geht zwar letztendlich um den sog. „Großen Fermat“, aber das Buch erzählt auch viel von der Entwicklung der Mathematik der letzten 2000 Jahre. Gegen Ende tauchen auch Informatik-Probleme auf. :-) Insgesamt tolle Darstellungen.
• Rolf Hochhuth. Alan Turing. Rowohlt, 1998.
  Literarische Annäherung an einen „unbekannten Unsterblichen“.
• Andrew Hodges. Alan Turing: The Enigma. Walker & Company, 2000. Ausführliche Biographie.
• Robert Harris. Enigma. Heyne, 1996.
  Nicht ganz so literarisch, aber dafür spannend mit frühen Computern und zu knackenden Codes.

Literatur:

Die Vorlesung orientiert sich sehr stark an den Lehrbüchern:

• Ingo Wegener. Theoretische Informatik – eine algorithmenorientierte Einführung, Teubner, 3. Auflage 2005.
• Uwe Schöning. Theoretische Informatik – kurz gefasst, Spektrum Akademischer Verlag, 5. Auflage 2008.

Eine gelungene Abrundung präsentiert Ingo Wegener in:

• Ingo Wegener. Kompendium Theoretische Informatik – Eine Ideensammlung, Teubner 1996.