- 07.10.2015: Die Nachklausur ist korrigiert. Sie können
Ihren Punktestand im KVV einsehen.
Die Benotung erfolgt nach diesem Schema. Die Klausureinsicht
findet statt am Mittwoch, den 14. 10. 2015, von 11–12 Uhr im SR 049.
Dort kann auch die erste Klausur noch einmal eingesehen werden.
- 05.10.2015: Am 07.10.2015 findet von 12–14 Uhr
die Nachlausur statt. Außer Schreibutensilien ist lediglich ein
beidseitig handbeschriebenes DIN-A4 Blatt als Hilfsmittel erlaubt. Bitte
bringen Sie ein Personaldokument mit Lichtbild sowie Ihren
Studierendenausweis mit. Wir treffen uns im großen Hörsaal Informatik.
Bitte bis 12:05 Uhr die Plätze einnehmen. Klausurbeginn um 12:15 Uhr.
- 27.08.2015: Katharina Klost und Justus Pfannschmidt bieten ein
Vorbereitungstutorium für die Nachklausur an. Es findet statt am
Donnerstag den 01.10.2015, um 10 Uhr im SR 055.
- 22.07.2015: Die Punkte für die Klausur wurden im KVV
gemäß der Ergebnisse der Klausureinsicht korrigiert. Bitte überprüfen Sie das Ergebnis.
Die Nachklausur findet statt am Mittwoch, den 07.10.2015, von 12 bis 14 Uhr.
Bitte melden Sie sich im KVV dazu an, falls Sie teilnehmen möchten.
Vor der Nachklausur werden die Tutoren eine Vorbereitungsveranstaltung anbieten.
Details werden zu gegebener Zeit bekannt gegeben.
- 17.07.2015: Die Klausur ist korrigiert. Sie können Ihre Punkte im
Online-KVV einsehen. Die Benotung
erfolgt nach diesem Schema. Die Klausureinsicht findet
statt am Mittwoch, den 22.07.2015, um 11 Uhr st, im SR 055. Der
Termin für die Nachklausur wird nächste Woche bekannt gegeben.
- 13.07.2015: Die Raumaufteilung für die Klausur ist bekannt gegeben:
Nachnamen A–K schreiben im Hörsaal A, Nachnamen L–Z schreiben im
Hörsaal C des Henry-Ford-Baus.
- 01.07.2015: In der nächsten Woche, am 06.07 und 08.07., findet keine
Vorlesung statt.
- 30.06.2015: Am 15.07.2015 findet von 10–12 Uhr die Klausur statt.
Bitte melden Sie sich bis zum 12.07.2015
im Online-KVV
zur Klausur an, falls Sie teilnehmen möchten.
Außer Schreibutensilien
ist lediglich ein beidseitig handbeschriebenes DIN-A4 Blatt als Hilfsmittel erlaubt.
Bitte bringen Sie ein Personaldokument mit Lichtbild sowie Ihren Studierendenausweis mit.
Die Klausur findet statt in den Hörsälen A und C des Henry-Ford-Baus,
Garystraße 35–37. Die Aufteilung wird noch bekannt gegeben. Bitte bis
10:05 Uhr die Plätze einnehmen. Klausurbeginn um 10:15 Uhr.
- 24.06.2015: Wegen der AlP2-Klausur beginnt am Mittwoch, den 01.07.2015,
die Vorlesung um 10:00 st.
- 24.06.2015: Das zehnte Aufgabenblatt ist verfügbar. Dies ist das letzte Aufgabenblatt.
- 15.06.2015: Die Probeklausur ist verfügbar.
- 10.06.2015: Das neunte Aufgabenblatt ist verfügbar. Dies ist das vorletzte Aufgabenblatt.
Aufgrund der Probeklausur ist der Bearbeitungszeitraum eine Woche länger als
üblich.
- 03.06.2015: Das achte Aufgabenblatt ist verfügbar.
- 01.06.2015: Am Montag, den 15.06.2015, findet von
10–12 Uhr im HS Informatik
eine unverbindliche Probeklausur statt. Diese wird am
Mittwoch, den 17.06.2015, in der Vorlesungszeit nachbesprochen.
Bitte melden Sie sich bis zum 09.06.2015
im Online-KVV
zur Klausur an, falls Sie teilnehmen möchten.
Am Montag, den 22.06.2015 wird
Christoph Benzmüller
eine Gastvorlesung zum Thema Logik und Vollständigkeit halten.
Am Mittwoch, den 24.06.2015 wird die Vorlesung von
Klaus Kriegel
vertreten.
- 27.05.2015: Das siebte Aufgabenblatt ist verfügbar.
- 20.05.2015: Das sechste Aufgabenblatt ist verfügbar.
- 13.05.2015: Das fünfte Aufgabenblatt ist verfügbar.
- 06.05.2015: Das vierte Aufgabenblatt ist verfügbar.
- 29.04.2015: Das dritte Aufgabenblatt ist verfügbar.
- 24.04.2015: Im Rahmen des Mentoringprogramms bietet Justus Pfannschmidt
ein Wunschkonzert an. Dieses findet jeweils Dienstags, von 18–20 Uhr im SR 055 statt.
- 22.04.2015: Das zweite Aufgabenblatt ist verfügbar.
- 02.04.2015: Das erste Aufgabenblatt ist verfügbar.
- 02.04.2015: Der erste Vorlesungstermin
ist der 15.04.2015. Die Tutorien beginnen in der zweiten
Semesterwoche.
Die Anmeldung zu den Tutorien erfolgt über das
Online-KVV.
Ggf. gibt es noch Anpassungen der Tutoriumsgröße zu
Semesterbeginn.
Die Übungszettel werden ausschließlich online erscheinen
und zwar hier auf dieser Seite.
Themenübersicht
- Grundlagen
- Alphabete, Sprachen, Wörter
- einfache Operationen auf Sprachen
- reguläre Sprachen
- reguläre Ausdrücke
- endliche Automaten und Nichtdeterminismus
- Äquivalenz der Darstellungen
- Pumping Lemma
- Nerode-Relation und Minimalautomaten
- Anwendungen regulärer Sprachen, Lexer, Grep
- Turing Maschinen
- Definition(en) und Eigenschaften, Universalität
- Grenzen der Berechenbarkeit: Universalsprache,
Halteproblem, PKP
- Reduktionskonzept
- Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit
- kontextfreie Sprachen
- Grammatiken und Chomsky-Hierarchie
- kontextfreie Grammatiken
- Eindeutigkeit
- Chomsky-Normalform und der CYK-Algorithmus
- Pumping-Lemma
- Kellerautomaten und Äquivalenz der Darstellungen
- Varianten: eindeutig kontextfrei, deterministisch kontextfrei, u.a.
- Anwendungen im Übersetzerbau, Parser
Tatsächlicher Inhalt
- Mittwoch, den 15.04.2015
- Administrativa
- Einleitung
- Was ist theoretische Informatik?
- Geschichte, Motivation und Fragestellungen
- Montag, den 20.04.2015
- Alphabete, Wörter, Sprachen
- Operationen auf Sprachen
- reguläre Ausdrücke und reguläre Sprachen
- Mittwoch, den 22.04.2015
- deterministische endliche Automaten (DEAs) mit Beispielen
- Montag, den 27.04.2015
- nichtdeterministische endliche Automaten (NEAs)
- Äquivalenz von NEAs und DEAs; Potenzmengenkonstruktion
- Mittwoch, den 29.04.2015
- Abschluss Potenzmengenkonstruktion und Beweis
- Montag, den 04.05.2015
- Äquivalenz von endlichen Automaten und regulären Ausdrücken: rA → NEA
- Algorithmus von Kleene: DEA → rA
- Mittwoch, den 06.05.2015
- Algorithmus von Kleene: Abschluss
- Abschlusseigenschaften regulärer Sprachen
- Pumping-Lemma (Intuition und Formulierung)
- Montag, den 11.05.2015
- Pumping-Lemma (Beweis und Beispiele)
- Mittwoch, den 13.05.2015
- Myhill-Nerode Relation
- Minimalautomaten
- Montag, den 18.05.2015
- Tabellenausfüllalgorithmus zum Bestimmen eines Minimalautomaten
- Anwendungen von regulären Sprachen: Übersetzerbau
- Mittwoch, den 20.05.2015
- Turing-Maschinen und Berechenbarkeit
- Montag, den 25.05.2015
- Keine Vorlesung (Pfingstmontag)
- Mittwoch, den 27.05.2015
- Berechenbarkeit, Church-Turing These
- Kodierung von Turing-Maschinen
- Diagonalsprache
- universelle Sprache und universelle Turingmaschine
- Montag, den 01.06.2015
- Semientscheidbarkeit
- Halteproblem
- Reduktionskonzept
- Abschlusseigenschaften entscheidbarer und semientscheidbarer
Sprachen
- Beispiele untentscheidbarer Sprachen
- Mittwoch, den 03.06.2015
- Beispiele untentscheidbarer Sprachen
- Postsches Korrespondenzproblem
- Hilberts Entscheidungsproblem
- Erkennen von Computerviren
- Grammatiken: Definition und Beispiele
- Montag, den 08.06.2015
- Chomsky-Hierarchie
- kontextfreie Grammatiken: Syntaxbaum und Eindeutigkeit
- Mittwoch, den 10.06.2015
- Montag, den 15.06.2015
- unverbindliche Probeklausur
- Mittwoch, den 17.06.2015
- Besprechung der Probeklausur
- Montag, den 22.06.2015
- Gastvorlesung von Christoph Benzmüller
- Mittwoch, den 24.06.2015 (vertreten von Klaus Kriegel)
- Anwendungen der Chomsky-Normalform: CYK-Algorithmus und
Pumping Lemma für kontextfreie Sprachen
- Montag, den 29.06.2015
- Pumping Lemma für kontextfreie Sprachen
- Mittwoch, den 01.07.2015
- weitere Eigenschaften von kontextfreien Sprachen
- Kellerautomaten
- Montag, den 06.07.2015
- Mittwoch, den 08.07.2015
- Montag, den 13.07.2015
- Mittwoch, den 15.07.2015
- Mittwoch, den 22.07.2015
- Mittwoch, den 07.10.2015
- Mittwoch, den 14.10.2015
Voraussetzungen
- Grundlegende Kenntnisse zu diskreter Mathematik
werden vorausgesetzt.
Literatur
- Uwe Schöning: Theoretische Informatik – kurz gefasst,
5. Auflage, Spektrum Akademischer Verlag, 2008
Alles Wichtige knapp und übersichtlich zusammengefasst.
Gut zur Prüfungsvorbereitung, aber eventuell wenig motivierend.
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und
Komplexität, Pearson Studium, 3. Auflage, 2011
Der Klassiker. Enthält viele motivierende
Beispiele und Hintergrundwissen. Die deutsche Übersetzung ist eine
Zumutung etwas gewöhnungsbedürftig.
- Ingo Wegener: Theoretische Informatik – Eine
algorithmenorientierte Einführung, 3. Auflage, Teubner, 2005
Sehr detailliert, manchmal etwas technisch.
- Michael Sipser: Introduction to the Theory of Computation,
2nd ed., Thomson Course Technology, 2006
Sehr schön und verständlich geschrieben. Die hinteren
Kapitel gehen weit über den Vorlesungsstoff hinaus.
Für Leute mit Interesse an der theoretischen Informatik.
- Ingo Wegener: Kompendium theoretische Informatik –
Eine Ideensammlung, Teubner, 1996
Verständliche Darstellung der wesentlichen Ideen ohne großen
technischen Ballast. Nicht unbedingt als Hauptquelle für die
Veranstaltung geeignet, aber als Ergänzung empfohlen.
- Anil Maheshwari und Michiel Smid: Introduction to Theory of
Computation, 2014 [link]
Vorlesungsskript aus Kanada.
- Andrew Hodges: Alan Turing, The Enigma
Biographisches zu einem Pionier der theoretischen Informatik, jetzt auch als Film.
Es wird eine Klausur am Ende des Semesters geben,
sowie eine Ersatzklausur vor Beginn des
nächsten Semesters.
Dabei gilt die Freiversuchsregel. Das heißt, man kann die
Ersatzklausur nutzen,
um das Ergebnis aus der Hauptklausur
zu verbessern (nur bei erstmaligem Absolvieren des Moduls).
Die Klausur findet statt am Mittwoch den 15.07.2015 von 10–12 Uhr im
HS Informatik und in den Hörsälen A und C des Henry-Ford-Baus,
Garystraße 35–37. Details werden noch bekannt gegeben.
Für den Scheinerhalt muss man
-
regelmäßig an dem Tutorium teilnehmen (bei mindestens 80% der
Termine);
-
mindestens 60% der Punkte auf den Übungszetteln Erreichen und
mindestens zweimal im Tutorium vorrechnen; und
-
die Klausur mit mindestens 50% der Gesamtpunktzahl
bestehen.
Die erfolgreiche Teilnahme am Übungsbetrieb und Teilnahme an der Klausur
sind unabhängige Leistungen.
Die Scheine sind benotet. Die Note beruht nur auf den
Klausurergebnissen.
Die Vorlesung findet statt Montag und Mittwoch, 10–12 Uhr, im
großen Hörsaal in der Takustraße 9.
Es gibt fünf Tutor_innen (Benjamin Berendsohn, Samuel Domiks, Katharina Klost,
Kristin Knorr und Justus Pfannschmidt).
Montag
|
14:00–16:00 |
Takustr. 9 Seminarraum 051 |
Katharina Klost |
Dienstag |
12:00–14:00 |
Takustr. 9 Seminarraum 053 |
Benjamin Berendsohn |
|
18:00–20:00 |
Takustr. 9 Seminarraum 055 |
Wunschkonzert (Justus Pfannschmidt) |
Mittwoch |
08:00–10:00 |
Takustr. 9 Seminarraum 051 |
Justus Pfannschmidt |
|
12:00–14:00 |
Takustr. 9 Seminarraum 051 |
Kristin Knorr |
12:00–14:00 |
Takustr. 9 Seminarraum 055 |
Katharina Klost |
|
14:00–16:00 |
Takustr. 9 Seminarraum 005 |
Justus Pfannschmidt |
Donnerstag |
12:00–14:00 |
Takustr. 9 Seminarraum 051 |
Kristin Knorr |
12:00–14:00 |
Arnimallee 3 HS 001 |
Samuel Domiks |
|
16:00–18:00 |
Takustr. 9 Seminarraum 051 |
Benjamin Berendsohn |
Sprechzeit des Dozenten: Dienstag 14–15 Uhr in Zimmer 114 und
nach Vereinbarung
Die Übungszettel werden jede Woche hier verlinkt. Sie werden
ausschließlich online erscheinen.
Die normale Bearbeitungszeit ist von Mittwoch bis zum Freitag
9 Tage später. Die Zettel sind vor 10 Uhr
in die entsprechenden Tutorenfächer einzuwerfen. Die Bearbeitung
erfolgt in Zweiergruppen.
Übungszettel, die nach dem angegebenen Termin
abgegeben werden, zählen als nicht bearbeitet.
Nr. | Ausgabe | Abgabe |
pdf | tex | Bemerkungen |
1 |
01.04.2015 |
24.04.2015 |
|
|
|
2 |
22.04.2015 |
04.05.2015 |
|
|
|
3 |
29.04.2015 |
08.05.2015 |
|
|
|
4 |
06.05.2015 |
15.05.2015 |
|
|
|
5 |
13.05.2015 |
22.05.2015 |
|
|
|
5a |
13.05.2015 |
keine |
|
|
Pumping-Lemma Aufgaben |
6 |
20.05.2015 |
29.05.2015 |
|
|
Beispiel TM
summe.flex
|
7 |
27.05.2015 |
05.06.2015 |
|
|
|
8 |
03.06.2015 |
12.06.2015 |
|
|
|
9 |
09.06.2015 |
26.06.2015 |
|
|
vorletztes Aufgabenblatt
Chomsky-Normalform
|
10 |
24.06.2015 |
03.07.2015 |
|
|
letztes Aufgabenblatt
|
Probeklausur |
15.06.2015 |
keine |
|
|
|