- 10.07.2018:
Die Klausur ist korrigiert. Sie können Ihre Punkte im
Online-KVV einsehen.
Die Benotung erfolgt nach diesem Schema.
Die Klausureinsicht findet statt am 11.07.2018, von 10:00–11:00 Uhr
im Hörsaal Informatik
Die Nachklausur findet statt am Montag, den 8. Oktober 2018, von
10–12 Uhr, im Henry-Ford-Bau.
- 08.07.2018: Am Montag, den 09.07.2018 findet
von 10–12 Uhr die Klausur 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. Nachnamen A–G schreiben im Hörsaal B im
Henry-Ford-Bau, Garystr. 35, Nachnamen H–P schreiben im
großen Hörsaal der Informatik, Takustraße 9,
Nachnamen Q–S schreiben im Seminarraum 006,
Takustraße 9, und Nachnamen T–Z schreiben im
Seminarraum 032, Arnimallee 6.
Bitte bis 10:05 die Plätze einnehmen. Die Klausur beginnt um
10:15.
- 27.06.2018: Das elfte Aufgabenblatt ist online.
Dies ist das letzte Aufgabenblatt.
- 25.06.2018: Die Klausuranmeldung ist freigeschaltet.
Falls Sie die Klausur mitschreiben möchten, melden Sie
sich bitte bis zum 7. Juli 2018 im KVV an.
- 20.06.2018: Das zehnte Aufgabenblatt ist online.
- 13.06.2018: Das neunte Aufgabenblatt ist online.
- 06.06.2018: Das achte Aufgabenblatt ist online.
- 30.05.2018: Das siebte Aufgabenblatt ist online.
- 29.05.2018: Am 04.06.2018 findet in
der Vorlesungszeit eine Probeklausur statt.
Die Probeklausur enthält Aufgabentypen, die auch
repräsentativ für die Abschlussklausur sind. Die
Probeklausur kann abgegeben werden und zum Ende des Semesters
verwendet werden, um bis zu 20 Übungspunkte auszugleichen.
- 23.05.2018: Das sechste Aufgabenblatt ist online.
- 16.05.2018: Das fünfte Aufgabenblatt ist online.
- 09.05.2018: Das vierte Aufgabenblatt ist online.
- 02.05.2018: Das dritte Aufgabenblatt ist online.
- 26.04.2018: Die Klausur findet statt am
Montag, den 9. Juli 2018, von 10–12 Uhr.
Die Nachklausur ist am Montag, den 8. Oktober 2018.
Weitere Details werden zu gegebener Zeit bekannt gegeben.
- 25.04.2018: Das zweite Aufgabenblatt ist online.
- 01.04.2018: Das erste Aufgabenblatt ist online.
- 01.04.2018: Der erste Vorlesungstermin
ist der 16.04.2018. Die Tutorien beginnen in der
zweiten Semesterwoche.
Die Anmeldung zu den Tutorien wird über das
Online-KVV erfolgen. Ggf. gibt es noch Anpassungen der
Tutoriumsgröße zu Semesterbeginn.
Die Übungszettel werden ausschließlich online erscheinen
und zwar hier auf dieser Seite.
- 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
- Montag, den 16.04.2018 (vertreten von Max Willert)
- Administrativa
- Einleitung
- Was ist theoretische Informatik?
- Geschichte, Motivation und Fragestellungen
- Alphabete, Wörter, Sprachen
- Mittwoch, den 18.04.2018 (vertreten von Max Willert)
- Operationen auf Sprachen
- Definition und Beispiele von regulären Ausdrücken
- Interpretation eines regulären Ausdrucks, inklusive eines Beispiels
- Definition reguläre Sprache
- Montag, den 23.04.2018
- deterministische endliche Automaten (DEAs) mit
Beispielen
- Mittwoch, den 25.04.2018
- nichtdeterministische endliche
Automaten (NEAs)
- Montag, den 30.04.2018
- Äquivalenz von NEAs und DEAs; Potenzmengenkonstruktion
- Äquivalenz von endlichen Automaten und regulären Ausdrücken
- Mittwoch, den 02.05.2018
- Äquivalenz von endlichen Automaten und regulären Ausdrücken
- rA → NEA durch strukturelle Induktion
- DEA → rA durch den Algorithmus von Kleene
- Montag, den 07.05.2018
- Algorithmus von Kleene: Abschluss
- weitere Eigenschaften regulärer Sprachen
- Mittwoch, den 09.05.2018
- Das Pumping Lemma: Intuition und Beweis
- Montag, den 14.05.2018
- Das Pumping Lemma: Anwendung
- Die Myhill-Nerode Relation
- Mittwoch, den 16.05.2018
- Minimalautomaten
- Finden eines Minimalautomaten
- Montag, den 21.05.2018
- Keine Vorlesung (Pfingsten)
- Mittwoch, den 23.05.2018
- Finden eines Minimalautomaten
- Reguläre Sprachen im Übersetzerbau
- Montag, den 28.05.2018
- Turing-Maschinen und Entscheidbarkeit
- Mittwoch, den 30.05.2018 (vertreten von K. Klost)
- Entscheidbarkeit, Diagonalsprache, Universalsprache,
universelle Turingmaschine, Semientscheidbarkeit
- Montag, den 04.06.2018
- Mittwoch, den 06.06.2018 (vertreten von K. Klost)
- Semientscheidbarkeit/rekursive Aufzählbarkeit
- Halteproblem
- Reduktionskonzept
- Abschlusseigenschaften von entscheidbaren und semientscheidbaren
Sprachen
- Montag, den 11.06.2018
- Weitere unentscheidbare Probleme:
- Postsches Korrespondenzproblem,
- Hilberts Entscheidungsproblem und
Gödelscher Unvollständigkeitssatz,
- diophantische Gleichungen,
- Erkennen von Computerviren
- Rekursionssatz und sich-fortpflanzende Programme
- Satz von Rice: Alle interessanten semantischen Eigenschaften von Turing-Maschinen
sind nicht entscheidbar.
- Mittwoch, den 13.06.2018
- Grammatiken: Definition und Beispiele
- Montag, den 18.06.2018
- Chomsky-Hierarchie: Definition und Eigenschaften
- Die Chomsky-Hierarchie ist echt
- Mittwoch, den 20.06.2018
- kontextfreie Grammatiken: Syntaxbaum, Eindeutigkeit und
inhärente Mehrdeutigkeit
- Chomsky-Normalform
- Montag, den 25.06.2018
- Anwendungen der Chomsky-Normalform: CYK-Algorithmus und
Pumping-Lemma für kontextfreie Sprachen.
- Mittwoch, den 27.06.2018
- Pumping-Lemma für kontextfreie Sprachen.
- Montag, den 02.07.2018
- Abschlusseigenschaften kontextfreier Sprachen
- Kellerautomaten
- Montag, den 09.07.2018
- Mittwoch, den 11.07.2018, 10–11 Uhr
- Montag, den 08.10.2018, 10–12 Uhr
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,
3rd ed., Cengage Learning, 2012
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, 2017 [link]
Vorlesungsskript aus Kanada.
- Andrew Hodges: Alan Turing, The Enigma
Biographisches zu einem Pionier der theoretischen Informatik.
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 Montag, den 9. Juli 2018, von
10–12 Uhr im großen Hörsaal Informatik,
Hörsaal B des Henry Ford Bau, SR 006 Takustr. 9, SR 025/026,
030, 032 Arnimallee 6.
Die Nachklausur findet statt am Montag, den 8. Oktober 2018, von
10–12 Uhr in den Hörsälen A und B des Henry Ford
Baus.
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 vier Tutor_innen (Benjamin Berendsohn, Sasha Jiang,
Kristin Knorr und Valentin Wolf).
Monday
|
08:00–10:00 |
Takustr. 9, Seminarraum 005 |
Kristin Knorr |
12:00–14:00 |
Takustr. 9, Seminarraum 051 |
Kristin Knorr |
14:00–16:00 |
Takustr. 9, Seminarraum 053 |
Benjamin Aram Berendsohn |
16:00–18:00 |
Takustr. 9, Seminarraum 051 |
Benjamin Aram Berendsohn |
Tuesday |
08:00–10:00 |
Takustr. 9, Seminarraum 053 |
Valentin Wolf |
16:00–18:00 |
Takustr. 9, Seminarraum 049 |
Kristin Knorr |
Wednesday |
14:00–16:00 |
Takustr. 9, großer HS |
Katharina Klost Central Problem Session |
Thursday |
12:00–14:00 |
Takustr. 9, Seminarraum 053 |
Benjamin Aram Berendsohn |
16:00–18:00 |
Takustr. 9, Seminarraum 046 |
Shasha Jiang |
Friday |
12:00–14:00 |
Takustr. 9, Seminarraum 053 |
Shasha Jiang |
Sprechzeit des Dozenten: Dienstag 14–15 Uhr in Zimmer 112 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.2018 |
27.04.2018 |
|
|
|
2 |
25.04.2018 |
04.05.2018 |
|
|
Aufgabe 2(b)(i) wurde vereinfacht |
3 |
02.05.2018 |
11.05.2018 |
|
|
|
4 |
09.05.2018 |
18.05.2018 |
|
|
|
5 |
16.05.2018 |
25.05.2018 |
|
|
Nerode-Relation |
5a |
16.05.2018 |
keine |
|
|
Aufgaben zum Pumping-Lemma |
6 |
23.05.2018 |
01.06.2018 |
|
|
summe.flex |
7 |
30.05.2018 |
08.06.2018 |
|
|
|
Probeklausur |
04.06.2018 |
keine |
|
|
|
8 |
06.06.2018 |
15.06.2018 |
|
|
|
9 |
13.06.2018 |
22.06.2018 |
|
|
|
10 |
20.06.2018 |
29.06.2018 |
|
|
Chomsky-Normalform |
11 |
27.06.2018 |
06.07.2018 |
|
|
Letztes Aufgabenblatt |