Berechenbarkeit und Formale Sprachen

Dozent	Rolf Wanka
Modulbeschreibung	Berechenbarkeit und Formale Sprachen
Umfang	V4 + Ü2, Studenten des Bachelor-Studiums Informatik, 3. Semester
Ort und Zeit der Vorlesungen	Mo., 10:15 - 11:45 Uhr, H9 Fr., 08:30 - 10:00 Uhr, H9
Ort und Zeit der Übung	Mo., 14:15 - 15:45 Uhr, E1.11 (Rauch) Di., 12:15 - 13:45 Uhr, 04.137 (Rauch) Mi., 16:15 - 17:45 Uhr, 00.152 (Mühlenthaler) Do., 10:15 - 11:45 Uhr, 00.156 (Schmitt) Fr., 12:15 - 13:45 Uhr, 0.031 (Schmitt) Fr., 12:15 - 13:45 Uhr, 00.151 (Mühlenthaler)

Termine

• Beginn der Vorlesungen: 21. Oktober 2011
• Beginn des Übungsbetriebs: 25. Oktober 2011
• Ende der Vorlesungszeit: 11. Februar 2012
• Klausur: 4. April 2012

Inhalte:

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

Und hier der Busy Beaver mit 4 Zuständen.

Übungen:

• Bitte überprüfen Sie, ob die Punkte mit Ihren Unterlagen übereinstimmen.
  Punkteliste WS 11/12
  Eine Fassung mit vollständigen Matrikelnummern wird am gelben "schwarzen Brett" im blauen Hochhaus aushängen.

• Blatt 0 (pdf)
• Blatt 1 (pdf)
• Blatt 2 (pdf)
• Blatt 3 (pdf)
• Blatt 4 (pdf)
• Blatt 5 (pdf)
• Blatt 6 (pdf)
• Blatt 7 (pdf)
• Blatt 8 (pdf)
• Blatt 9 (pdf) (Vorlage GCP.txt zum Einsenden der Lösungen zu Aufgabe 47)
• Blatt 10 (pdf)
• Blatt 11 (pdf)
• Blatt 12 (pdf)
• Blatt 13 (pdf)
• Blatt 14 (pdf)

Skript (partiell):

• Die Turingmaschine aus der Vorlesung als pdf-File.

• Das Bild mit der Ausrede, warum man kein schnelles Programm hat schreiben können, als pdf-File. 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

• 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-File.

• Die Folien zum Vortrag über Schönings Algorithmus für 3SAT finden Sie hier.

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.

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.

Grötschels Aufsatz zum Rundereiseproblem

Artikel aus Spektrum der Wissenschaft

• 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.
  (19,90 EUR, Amazon.de)

  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.
  (9,90 EUR, Amazon.de)

  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.
  (6,50 EUR, Amazon.de)

  Literarische Annäherung an einen "unbekannten Unsterblichen".

• Andrew Hodges. Alan Turing: The Enigma. Walker & Company, 2000.

  Ausführliche Biographie.

• Robert Harris. Enigma. Heyne, 1996.
  (8,95 EUR, Amazon.de)

  Nicht ganz so literarisch, aber dafür spannend mit frühen Computern und zu knackenden Codes.

Literatur:

• Ingo Wegener. Theoretische Informatik - eine algorithmenorientierte Einführung, Teubner, 3. Auflage 2005.

• Amazon.de
• buch.de

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