Berechenbarkeit und Formale Sprachen

Dozent	Rolf Wanka
Umfang	V4 + Ü2, Studenten des Bachelor-Studiums Informatik, 3. Semester
Ort und Zeit der Vorlesungen	Mo., 16:15 - 17:45 Uhr, H6 Do., 16:00 - 17:30 Uhr, H9
Ort und Zeit der Übung	Mo., 18:00 - 20:00 Uhr, E1.12 (Philipp Schneider) Mi., 16:00 - 17:30 Uhr, E1.11 (Sabine Helwig) Do.,  8:30 - 10:00 Uhr, E1.12 (Sabine Helwig) Do., 10:15 - 11:45 Uhr, 00.152 (Matthias Hoffmann) Fr.,  8:30 - 10:00 Uhr, E1.12 (Matthias Hoffmann)

Termine

• Beginn der Vorlesungen: 22. Oktober 2009
• Beginn des Übungsbetriebs: Ab 26. Oktober 2009
• Ende der Vorlesungszeit: 12. Februar 2010

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

Übungen:

• Punkteliste WS 09/10
  Eine Fassung mit vollständigen Matrikelnummern hängt am schwarzen Brett im blauen Hochhaus aus.

• Blatt 0 (pdf, ps)
• Blatt 1 (pdf, ps)
• Blatt 2 (pdf, ps, pdf auf 2 Blättern)
• Blatt 3 (pdf, ps, pdf auf 2 Blättern)
• Blatt 4 (pdf, ps, pdf auf 2 Blättern)
• Blatt 5 (pdf, ps, pdf auf 2 Blättern)
• Blatt 6 (pdf, ps, pdf auf 2 Blättern, Die Leiterplatte mit den Bohrlöchern)
• Blatt 7 (pdf, ps, pdf auf einzelnen Blättern)
• Blatt 8 (pdf, ps, pdf auf einzelnen Blättern)
• Blatt 9 (pdf, ps, pdf auf einzelnen Blättern)
• Blatt 10 (pdf, ps, pdf auf einzelnen Blättern)
• Blatt 11 (pdf, ps) (kurzes Übungsblatt)
• Blatt 12 (pdf, ps, pdf auf einzelnen Blättern)
• Blatt 13 (pdf, ps)

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

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

• Folien eines Vortrags Sachen gibt's, die gibt's gar nicht zum Halteproblem.

Turings Aufsatz

A. 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.

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.