Seiteninterne Suche

Lehre

Berechenbarkeit und Formale Sprachen

Dozent:

Prof. Dr. rer. nat. Rolf Wanka

Modulbeschreibung:

Berechenbarkeit und Formale Sprachen

Umfang/Stunden:

V4 + Ü2, 7.5 ECTS

Zielgruppe:

Studenten des Bachelor-Studiums Informatik, 3. Semester

Ort und Zeit der Vorlesung:

Mittwoch, 10:15 – 11:45 Uhr, H8
Freitag, 12:15 – 13:45 Uhr, H8

Ort und Zeit der Übungen:

Montag, 08:15 – 09:45 Uhr, 00.151-113
Montag, 12:15 – 13:45 Uhr, 02.133-113
Montag, 14:15 – 15:45 Uhr, 0.154-115
Dienstag, 12:15 – 13:45 Uhr, 02.133-113
Dienstag, 14:15 – 15:45 Uhr, 0.154-115
Dienstag, 16:15 – 17:45 Uhr, 0.154-115
Mittwoch, 14:15 – 15:45 Uhr, EE 0.135
Freitag, 14:15 – 15:45 Uhr, 0.151-115

Termine

  • 18. Oktober 2017: Beginn der Vorlesungen
  • 24. Oktober 2017: Beginn der Übungen
  • 31. Oktober 2017 (Reformationstag): Keine Übungen
  • 1. November 2017 (Allerheiligen): Keine Übungen

    Inhalte:

    • Turingmaschinen, die Churchsche These und Entscheidbarkeit
    • NP-Vollständigkeit
    • Primitive Rekursion und μ-Rekursion
    • Automaten, Grammatiken und die Chomsky-Hierarchie
    • Endliche Automaten
    • Kontextfreie Grammatiken und Kontextfreie Sprachen
    • Kellerautomaten

    Video-Aufzeichnung:

    Die Video-Aufzeichnung vom Wintersemester 2011/12 ist hier aus dem Uni-Netz erreichbar.

    YouTube-Videos zu Turingmaschinen:

    Übungen:

    Bitte melden Sie sich im EST für die Übungen an. Benutzen Sie im EST die Veranstaltungsanmeldung. Dort können Sie die Veranstaltung BFS (WS 17/18) auswählen. Das Anmeldepasswort erhalten Sie in der Vorlesung und in den Übungen. Als Bestätigung für die erfolgreiche Anmeldung erhalten Sie eine Email.

    • Blatt 0 (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. 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 = { anbncn | 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.
    • Die Folie zur Ackermann-Funktion gibt es hier.

    Turings Aufsatz

    Moore’s Law

    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

    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.

    Es gibt eine ganze Reihe sehr guter Bücher zu den Grundbegriffen der Theoretischen Informatik. Einige seien hier genannt:

    • Alexander Asteroth, Christel Baier. Theoretische Informatik, Pearson 2002.
    • John E. Hopcroft, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley 1997.
    • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2nd Edition 2001.
    • Juraj Hromkovic. Theoretische Informatik – Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kryptographie. Eine Einführung, Teubner, 2. Auflage 2004.
    • Bernard M. Moret. The Theory of Computation, Addison-Wesley 1997.
    • Uwe Schöning. Theoretische Informatik kurzgefaßt, Spektrum Akademischer Verlag, 5. Auflage 2008.
    • Michael Sipser. Introduction to the Theory of Computation, Cengage Learning Services, 2005.
    • Gottfried Vossen, Kurt-Ulrich Witt. Grundkurs Theoretische Informatik, Vieweg, 4. Auflage2006.
    • Klaus W. Wagner. Einführung in de Theoretische Informatik – Grundlagen und Modelle, Springer 1991.
    • Ingo Wegener. Theoretische Informatik – eine algorithmenorientierte Einführung, Teubner, 2. Auflage 1999.
    • Ingo Wegener. Kompendium Theoretische Informatik – Eine Ideensammlung, Teubner 1996.