Theoretische Informatik WS 03/04
Personen
Ort und Zeit
- Mittwochs 14-16, im Hörsaal I, Geb. 27
- Freitags 9-11, im Hörsaal I, Geb. 27
- Zwischenklausur: Samstag, 13. Dezember, 9.30 Uhr (s.t.) bis 12.00 Uhr
- Abschlussklausur: Montag, 1. März, 14.00 Uhr (s.t.) bis 16.30 Uhr
- Nachklausur: Mittwoch, 14. April, 9.30 Uhr (s.t.)
Mailingliste
Es gibt eine Mailingliste zu der Vorlesung. Das Webinterface der Mailingliste befindet sich
hier. Die Mailadresse ist
theoinf-ws0304-l@postino.mpi-sb.mpg.de.
Zum Anmelden einfach eine Email an
join-theoinf-ws0304-l@postino.mpi-sb.mpg.de
schicken. Informationen zum Abmelden befinden sich am Ende jeder Email, die über die Mailingliste verschickt wird.
Bitte beschränken Sie sich auf thematisch passende Beiträge. Off-topic Beiträge, Werbung und Postings wie
"Ich wünsche allen ein schönes Wochenende." sind unerwünscht. Achten Sie bitte bei Fragen zu
Übungen darauf, keine Lösungen oder Lösungsansätze über die Mailingliste zu verbreiten. Keine HTML-Mails.
Inhalt
Diese Vorlesung, die eine grundlegende Einführung in die theoretische
Informatik gibt, zerfällt in drei Themengebiete.
- Berechenbarkeit Wir befassen uns mit der Frage nach
einer mathematischen Definition des intuitiven Begriffs der
Berechenbarkeit. Welche Probleme sind prinzipiell
(unabhäging von verwendeten Rechnern oder Algorithmen)
lösbar oder unlösbar?
- Komplexität Als entscheidbar identifizierte Probleme
werden in diesem Teil weiter klassifiziert nach dem Aufwand,
den man zu ihrer Lösung betreiben muss. Wichtige Kriterien
für diesen Aufwand sind Zeit- und Platzverbrauch.
- Automaten In diesem Teil geht es um formale Sprachen,
insbesondere um die Klassen der regulären und der
kontextfreien Sprachen. Automaten sind mathematische Objekte,
die solche Sprachen erkennen, wohingegen es sich bei
Grammatiken um spracherzeugende Objekte handelt.
Scheinvergabe
Für die Vorlesung gibt es einen benoteten Schein mit 9 Leistungspunkten.
Dazu ist das Bestehen der Mittsemester- und Abschlussklausur oder der Nachklausur
notwendig.
Für die Zulassung zu den Klausuren gelten folgende Bedingungen:
- Zwischenklausur: 50% der Punkte aus den Übungsblättern 1 bis 6
- Abschlussklausur: 50% der Punkte aus den Übungsblättern 7 bis 13, einmaliges Vorrechnen in den Übungen und Bestehen der Zwischenklausur
- Nachklausur: 50% der Punkte aus den Übungsblättern 1 bis 6, 50% der Punkte aus den Übungsblättern 7 bis 13 und einmaliges Vorrechnen in den Übungen
Die Scheinnote setzt sich jeweils zur Hälfte aus der Note der
Zwischen- und der Abschlussklausur zusammen. Falls Sie die Nachklausur
mitschreiben, wird die Scheinnote ausschließlich durch die Note der Nachklausur bestimmt.
Literatur
Die Vorlesung wird sich hauptsächlich nach dem Buch von Ingo Wegener richten.
- Ingo Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 1999
Die erste Auflage von 1993 kann auch verwendet werden. Die zweite Auflage ist inhaltlich unverändert,
es wurden lediglich Fehler und einige Formulierungen verbessert.
- Harry R. Lewis, Christos H. Papadimitriou: Elements of the Theory of Computation
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation
- Uwe Schöning: Theoretische Informatik - kurzgefasst
- Michael Sipser: Introduction to the Theory of Computation
- Norbert Blum: Theoretische Informatik
Material
- Beispiele für Busy Beaver (PS.GZ, PDF) (korrigierte Version)
- Notizen zur lexikalischen Analyse (PS.GZ, PDF)
- Greibach-Normalform (PS.GZ, PDF)
Weiterführende Links
