 |
Theoretische Informatik II
| Dozent |
Rolf Wanka |
| Umfang |
V3 + Ü2,
Studenten der Informatik, 2. Semester |
Ort
und Zeit der Vorlesungen
|
Mi. 9:15-10:00 Uhr, Hörsaal H7
Fr. 12:15 - 13:45 Uhr, Hörsaal H7
|
Ort
und Zeit der Übung
|
Mo. 14:00-15:30, 00.153 (Roman König)
Di. 14:15-15:45, 00.156 (Sabine Helwig)
Di. 16:15-17:45, 00.153 (Sabine Helwig)
Mi. 16:00-17:30, 00.152 (Sabine Helwig)
Do. 8:30-10:00, 00.152 (Florian Forster)
|
Termine
-
Die Klausur
findet am 1. April 2009 ab 14:30 Uhr im H8 statt.
Inhalte:
- Turingmaschinen, die Churchsche These und Entscheidbarkeit
- NP-Vollständigkeit
- Grammatiken und die Chomsky-Hierarchie
- Kontextfreie Grammatiken und Kontextfreie Sprachen
- Kellerautomaten
Sie können sich
hier
die erreichten Punkte anschauen.
Übungsblätter:
- Blatt 0
(pdf, ps)
- Blatt 1
(pdf, ps)
- Blatt 2
(pdf, ps)
- Blatt 3
(pdf, ps)
- Blatt 4
(pdf, ps)
- Blatt 5
(pdf, ps)
- Blatt 6
(pdf, ps)
- Blatt 7
(pdf, ps)
- Blatt 8
(pdf, ps)
- Blatt 9
(pdf, ps)
- Blatt 10
(pdf, ps)
- Blatt 11
(pdf, ps)
- Blatt 12
(pdf, ps)
- 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 = { 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-File.
Turings Aufsatz
A. M. Turing.
On Computable Numbers, With an Application to the Entscheidungsproblem,
Proc. London Math. Soc. 2(42) (1936), 230-265.
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".
-
Robert Harris.
Enigma.
Weltbild, 2005.
(4,99 EUR,
Amazon.de)
Nicht ganz so literarisch, aber dafür spannend mit frühen Computern
und zu knackenden Codes.
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.
|
|
