Friedrich-Alexander-Universität DruckenUnivisEnglish FAU-Logo
Techn. Fakultät Willkommen am Department Informatik FAU-Logo
Codesign
Lehrstuhl für Informatik 12
Theoretische Informatik II
SS 06

InformatikJahr 2006
Department Informatik  >  Informatik 12  >  Lehre  >  Theoretische Informatik II, SS 06

Theoretische Informatik II

Dozent Rolf Wanka
Umfang V3 + Ü2,
Studenten der Informatik, 2. Semester
Ort und Zeit der Vorlesungen
Mi. 9:15-10:00, Hörsaal H7
Fr. 12:30 - 14:00, Hörsaal H7
Ort und Zeit der Übung
Mo. 8:30-10:00, 00.151 (Roman König)
Mo. 14:00-15:30, 2.037 (Roman König)
Di. 14:00-16:00, 2.038 (Christian Rieß)
Di. 16:00-18:00, 2.037 (Christian Rieß)
Mi. 16:00-17:30, 00.152 (Sabine Helwig)
Do. 8:30-10:00, 00.152 (Sabine Helwig)


Die nächste Vordiplomklausur "Theoretische Informatik" wird am 28. März 2007 geschrieben.
Ort: Mensa-Süd
Uhrzeit: Ab 15:00 Uhr

Die Vordiplomklausur "Theoretische Informatik" vom 27. September 2006 ist korrigiert. Das Ergebnis hängt im blauen Hochhaus am Schwarzen Brett des LS 8. Die Klausureinsicht wird am Freitag, d. 20. Oktober 2006, ab 13:00 Uhr in 07.150 durchgeführt.

Erreichte Punkte aus den Übungsaufgaben des Sommersemesters 2006 gibt's hier.


Termine

  • Am Freitag, d. 28. April 2006, entfällt die Vorlesung wegen des Tags der Informatik
  • Am Freitag, d. 26. Mai 2006, wird die Vorlesung im Hörsaal H1 in der Chemie stattfinden (Karte hier)
  • Am Freitag, d. 4. August 2006, wird von 13:00 Uhr s.t. bis 14:00 Uhr eine Übungsklausur im Hörsaal H7 geschrieben. Bitte bringen Sie das Schreibpapier selbst mit.
  • Am Mittwoch, d. 27. September 2006, wird ab 8:30 Uhr im Hörsaal H7 die Klausur "Theoretische Informatik" geschrieben.

Inhalte:

  • Turingmaschinen, die Churche These und Entscheidbarkeit
  • NP-Vollständigkeit
  • Grammatiken und die Chomsky-Hierarchie
  • Kontextfreie Grammatiken und Kontextfreie Sprachen
  • Kellerautomaten

 


Übungsblätter:


Skript (partiell):

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


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.
    (20,- 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.
    (10,- 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".


Literatur:

Die Vorlesung orientiert sich sehr stark am Lehrbuch:
  • Ingo Wegener. Theoretische Informatik - eine algorithmenorientierte Einführung, Teubner, 3. Auflage 2005.
Das Buch kostet 24,90 EUR und kann im einschlägigen Internetbuchhandel, z.B. bei und in jeder Präsenzbuchhandlung bestellt werden. Eine gelungene Abrundung des Inhalts seines Buches 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. Ein paar seien hier genannt:

  • 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, 4. Auflage 2001.
  • 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.
  Impressum Stand: 15 February 2007.   R.W.