Prof. Dr. J. Hromkovič, Dr. H.-J. Böckenhauer — Departement Informatik — HS 2018
Theoretische Informatik
Termine
| Vorlesung |
Dienstag |
8–10 |
HG G 5 |
Beginn: 18. September 2018 |
|
|
Freitag |
8–10 |
HG G 5 |
Beginn: 21. September 2018 |
| Übungen |
Dienstag |
13–15 |
Räume gemäss Gruppeneinteilung |
Beginn: 25. September 2018 |
|
Mittwoch |
15–17 |
Räume gemäss Gruppeneinteilung |
Beginn: 26. September 2018 |
|
|
Donnerstag |
16–18 |
Räume gemäss Gruppeneinteilung |
Beginn: 27. September 2018 |
Literatur
- Die Vorlesung orientiert sich an dem Buch Theoretische Informatik von Juraj
Hromkovič.
- Aktuell ist die fünfte Auflage des Buchs
(ETH Store).
Wir raten Ihnen dazu, diese fünfte Auflage zu erwerben, da sie gegenüber
den Vorgänger-Versionen neues Material und viele Verbesserungen enthält.
- Ergänzende Literatur: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman:
Automatentheorie, Formale Sprachen und
Berechenbarkeit, 3. Auflage, Pearson Studium, 2011
Gruppeneinteilung
- Wir empfehlen, die wöchentlichen Übungsaufgaben in Kleingruppen
von bis zu 3 Personen zu bearbeiten.
- Die Einteilung in die Übungsgruppen finden Sie hier.
- Für Änderungswünsche oder eine nachträgliche Anmeldung zu den Übungen
kontaktieren Sie bitte Dr. Hans-Joachim Böckenhauer per E-Mail.
Zwischenklausuren
- Es werden zwei freiwillige Zwischenklausuren am Dienstag, dem 6.
November, und am Dienstag, dem 11. Dezember,
jeweils zur Vorlesungszeit von 8 bis 10 Uhr stattfinden.
- Um an den freiwilligen Zwischenklausuren teilzunehmen, müssen Sie
in myStudies für die Vorlesung angemeldet sein.
- Zulassungsbedingung zu den freiwilligen Zwischenklausuren sind 50
Prozent der Punkte aus den Übungen.
- Es sind keine Hilfsmittel zugelassen, ausser eigenem leerem
Schreibpapier und einem dokumentenechten Schreibstift in
blauer oder schwarzer Farbe.
- Die Raumaufteilung für die erste und die zweite Zwischenklausur erfolgt alphabetisch nach Nachnamen:
- Alle Teilnehmer werden gebeten, um 8:00 Uhr anwesend zu sein
und vor den entsprechenden Räumen zu warten.
- Prüfungsstoff für die erste Zwischenklausur:
Übungen bis und mit Blatt 5 und Wiedergabe des
Vorlesungsstoffs bis und mit 26. Oktober (Abschnitt 5.2 im Buch)
- Prüfungsstoff für die zweite Zwischenklausur:
Übungen bis und mit Blatt 10 und Wiedergabe des
Vorlesungsstoffs bis und mit 30. November.
- Die Ergebnisse der beiden Zwischenklausuren finden Sie hier (mit den Änderungen
nach der Klausureinsicht).
- Die Klausureinsicht für die zweite Zwischenklausur findet
am Freitag, dem 21. Dezember,
von 9:00 bis 10:00 Uhr im
Vorlesungsraum HG G 5 statt. Ausgabe der Klausuren bis
9:45 Uhr. Von 8:15 bis 9:00 findet normal die Vorlesung
statt.
- Wenn Sie die Gesamtnote der beiden Zwischenprüfungen als Endnote
übernehmen wollen, füllen Sie bitte dieses Formular zur Notenübernahme aus und geben Sie
es unterschrieben bei der Klausureinsicht oder bis zum 9.
Januar 2019 im Büro CAB F 11 ab.
- Wichtig: Sie müssen auch in diesem Fall zur
Sessionsprüfung angemeldet bleiben, sonst kann die Note nicht
eingetragen werden.
- Die Noten derjenigen Teilnehmer, die ein Formular zur
Notenübernahme abgegeben haben, wurden am 10. Januar dem
Studiensekretariat gemeldet und werden in den nächsten
Tagen verfügt. Falls Sie noch nachträglich ein
Formular abgeben möchten, kontaktieren Sie bitte Dr.
Hans-Joachim Böckenhauer per E-Mail.
Sessionsprüfung
- Die Sessionsprüfung findet am 7. Februar 2019 von 9:00 bis
12:00 Uhr im Raum HIL G 41 (Hönggerberg) statt.
- Es sind keine Hilfsmittel zugelassen, ausser eigenem leerem
Schreibpapier und einem dokumentenechten Schreibstift in
blauer oder schwarzer Farbe.
- Prüfungsstoff für die Sessionsprüfung ist der Stoff
der gesamten Vorlesung sowie der Stoff aller Übungen.
- Diejenigen Studierenden, die an den beiden
Zwischenklausuren teilgenommen haben und dort eine Gesamtnote von
mindestens 4.0 erreicht haben, können die dort
erreichte Gesamtnote als Endnote übernehmen und müssen
nicht an der Sessionsprüfung teilnehmen.
- Auch wenn Sie die Note der Zwischenprüfungen übernehmen
wollen und das Formular abgeben, müssen Sie sich auf jeden Fall zur
Prüfung anmelden. Ihre Noten werden dann eingetragen und Sie
werden automatisch abgemeldet.
- Bei Teilnahme an der Sessionsprüfung zählt
ausschliesslich die Note der Sessionsprüfung.
- Die Klausureinsicht für die Sessionsprüfung findet am Montag, dem 25.
Februar, und am Donnerstag, dem 28. Februar, jeweils von
12:00 Uhr bis 13:00 Uhr im Raum CAB F 11 statt.
- Alle Studierenden, die als Gesamtnote in den Zwischenprüfungen
oder in der Sessionsprüfung die Note 6.0 erreicht haben,
bekommen als Anerkennung einen Buchpreis. Die Buchpreise
können während der Klausureinsicht im Raum CAB F 11
abgeholt werden.
Vorlesungsinhalt
- 18.09.2018 Allgemeine informelle Einführung
- 21.09.2018 Alphabete, Wörter, Sprachen,
Entscheidungsprobleme (Abschnitt 2.2 ohne Def. 2.10, Abschnitt
2.3 bis und mit Def. 2.11)
- 25.09.2018 Berechnungsprobleme (Rest von Abschnitt 2.3,
informell), Informationsbegriff nach Shannon (informell),
Kolmogorov-Komplexität (Abschnitt 2.4 bis und mit Lemma 2.4)
- 28.09.2018 Kolmogorov-Komplexität (bis und mit Satz 2.2),
Ausblick auf Primzahlsatz (Satz 2.3),
Einführung Endliche Automaten (Kapitel 3)
- 02.10.2018 Endliche Automaten (bis und mit Definition 3.2)
- 05.10.2018 Entwurf endlicher Automaten (Rest von Abschnitt 3.2),
Simulation und modularer Automatenentwurf (Abschnitt 3.3)
- 09.10.2018 Nichtregularität: Beweise direkt über den
Automaten und Pumping-Lemma (Abschnitt 3.4 bis vor Satz 3.1)
- 12.10.2018 Nichtregularität: Beweise mit
Kolmogorov-Komplexität (Rest von Abschnitt 3.4),
nichtdeterministische endliche Automaten: Einführung und
Potenzmengenkonstruktion (Abschnitt 3.5 bis und mit Satz 3.2, noch ohne Beweis)
- 16.10.2018 Formaler Beweis der Potenzmengenkonstruktion und
Beispiel für Unvermeidbarkeit exponentiellen
Zustandswachstums (Rest von Abschnitt 3.5)
- 19.10.2018 Turingmaschinen (Abschnitte 4.2 und 4.3) ohne die
explizite Konstruktion konkreter TM, Mehrband-TM (Abschnitt
4.4 bis und mit Lemma 4.2)
- 23.10.2018 Churchsche These (Rest von Abschnitt 4.4),
nichtdeterministische Turingmaschinen (Abschnitt 4.5),
Kodierung von Turingmaschinen (Abschnitt 4.6, informell),
Abzählbarkeit (Anfang von Abschnitt 5.2)
- 26.10.2018 Abzählbarkeit (Rest von Abschnitt 5.2),
Methode der Reduktion (Anfang von Abschnitt 5.3, bis Satz 5.6)
- 30.10.2018 Methode der Reduktion (Satz 5.6 bis und mit Lemma 5.8)
- 02.11.2018 Satz von Rice (Abschnitt 5.4),
Methode der Kolmogorov-Komplexität (Abschnitt 5.6),
Komplexitätstheorie (Kapitel 6) bis und mit Definition 6.2.
- 06.11.2018 1. freiwillige Zwischenklausur
- 09.11.2018 Exkurs über mathematisch unlösbare Probleme (kein Prüfungsstoff),
Grammatiken (Kapitel 10) bis und mit Chomsky-Hierarchie (Definition
10.2).
- 13.11.2018 Reguläre Grammatiken (Abschnitt 10.3),
reguläre Ausdrücke (Abschnitte 3.1 und Anfang von
3.2.1 im Buch von Hopcroft, Motwani, Ullman)
- 16.11.2018 Reguläre Ausdrücke (Rest von
3.2.1 im Buch von Hopcroft, Motwani, Ullman),
Komplexitätstheorie (Rest von Abschnitt 6.2, Anfang von
Abschnitt 6.3 bis und mit Lemma 6.5)
- 20.11.2018 Komplexitätstheorie, Fortsetzung bis und mit
Satz von Savitch (Rest von Abschnitt 6.3 und Abschnitt
6.4)
- 23.11.2018 Polynomzeitreduktionen (Abschnitt 6.6 bis und mit
Lemma 6.7), NP-Schwere von CLIQUE, VC und 3SAT (Abschnitt 6.6
ab Lemma 6.8 bis und mit Lemma 6.11, letzteres Lemma noch
ohne vollständigen Beweis)
- 27.11.2018 NP-Vollständigkeit von 3SAT (Beweis von Lemma
6.11), Polynomzeit-Verifizierer (Abschnitt 6.5)
- 30.11.2018 Satz von Cook (Satz 6.9)
- 04.12.2018 Äquivalenz von allgemeinen Grammatiken und
Turingmaschinen (Abschnitt 10.5), kontextfreie Grammatiken,
Chomsky-Normalform, Pumping-Lemma und Beweise der
Nicht-Kontextfreiheit (Abschnitt 10.4 bis und mit Beispiel
10.6)
- 07.12.2018 Kellerautomaten und ihre Äquivalenz zu
kontextfreien Grammatiken (Rest von Abschnitt 10.4 ohne Lemma
von Ogden und dessen Anwendung)
- 11.12.2018 2. freiwillige Zwischenklausur
- 14.12.2018 Randomisierung, Kommunikationsprotokoll zum Vergleich
von Binärstrings (Abschnitte 8.1 bis und mit 8.3)
- 18.12.2018 Optimierungsprobleme (Abschnitt 2.3 ab Definition
2.14 bis und mit Aufgabe 2.20, Rest von Abschnitt 6.6 ab
Definition 6.12) und Approximationsalgorithmen (Abschnitt 7.3)
- 21.12.2018 Ausblick auf weitere Themen der theoretischen
Informatik (nicht prüfungsrelevant):
Speicherplatzhierarchien, deterministischer und
nichtdeterministischer logarithmischer Speicherplatz,
randomisierter Primzahltest
Übungen
Kontakt: Dr. Hans-Joachim Böckenhauer, ,
Haftungsausschluss: disclaimer.html,
Letzte Änderung:
