Theoretical Computer Science

Vorlesung: Theoretische Informatik 1

Wintersemester 2019/20

News

18. Februar

Die Klausurergebnisse und die dazugehörigen Statistiken findet sie in den folgenden beiden Links.

• Klausurergebnisse
• Statistiken

17. Februar

Die Klausureinsicht findet am Mittwoch, den 19.02., von 11:00 bis 12:30 Uhr in Raum IZ 358 statt. Die Ergebnisse werden morgen (Dienstag) anonymisiert hier online gestellt.

3. Februar

Es wird folgendes zur Klausurvorbereitung angeboten:

• Eine Extraübung am 11.02 (Dienstag) von 15:00 bis 18:00 Uhr in PK 11.1. Wir werden dort eine Altklausur durchrechnen.
• Drei weitere Lerntreffe am Mo., Di. und Mi. (10.02, 11.02 und 12.02) um 13:00 - 14:30 Uhr in Raum IZ305.

21. Januar

Das neue und auch letzte Hausaufgabenblatt 6 ist nun online.

15. Januar

Der Ort für die Klausur steht nun fest. Diese findet in der Mensa 2, Beethovenstraße 15 (Nordcampus) statt.

14. Januar

Die Klausur findet am 13. Februar ab 15:00 Uhr mit einer Bearbeitungszeit von 120 Minuten statt. Informationen über den Ort werden nachgereicht. Weitere Informationen zur Abschlussklausur finden Sie nun weiter unten auf dieser Seite.
Einige Fehler im Skript wurden korrigiert.

07. Januar

Frohes neues Jahr! Hausaufgabenblatt 5 ist online.

10. Dezember

Hausaufgabenblatt 4 ist online. Es gibt eine Bonusaufgabe (Aufgabe 5). Diese muss nicht bearbeitet werden.

03. Dezember

Skript wurde um den Zusammenhang zwischen Fixpunkten und Nullstellen erweitert.

26. November

Das dritte Hausaufgabenblatt ist online. Es gibt die Aufgaben sowohl in Deutsch als auch in Englisch.
Die Hausaufgabenabgabe wurde von 14:00 Uhr auf 15:00 Uhr verschoben. Damit ist der Abgabetermin nun nach dem Lerntreff.
Das Skript wurde um eine (kurze) Motivation und diverses andere erweitert.

25. November

Der Raum für die Übung von Gruppe 1 wurde geändert zu IZ 161.

12. November

Übungsblatt 2 ist hochgeladen.

07. November

Die Tutoren der Übungsgruppen 1 und 2 haben gewechselt. Übungsgruppe 1 wird nun von Peter Chini gehalten, und Übungsgruppe 2 von Frieso Gerken.
Das aktuelle Hausaufgabenblatt wurde mit den fehlenden Punktzahlen versehen. Es gibt 5 Punkte pro Aufgabe/Teilaufgabe.

01. November

Die Gruppeneinteilung ist fertig. Sie können Ihre Gruppe in dem Onlineanmeldesystem Zahnrad nachschlagen.
Die Räume der Übungsgruppen 2 und 3 wurden vertauscht. Gruppe 2 (geleitet von Peter Chini) findet in IZ 305 statt, Gruppe 3 (geleitet von Thorsten Palm) in IZ 358.

29. Oktober

Skript aktualisiert (Definition of Pre und Postfixpunkten war vertauscht)
Es gibt einen "Lerntreff Theorie" jede Woche am Donnerstag von 13:15 - 14:45 Uhr in Raum IZ 305 (Beginn: 07. November, der Kalendar wurde aktualisiert). Dieser Lerntreff wird von Micheal Perk gehalten, und dient hauptsächlich dazu um Verständnisfragen zu dem Inhalt der Veranstaltungen Theoretische Informatik und Logik zu stellen.

25. Oktober

Benutzen Sie das Onlineanmeldesystem Zahnrad, um sich für die kleinen Übungen bis zum 31. Oktober (einschließlich) anzumelden.
Es wird einmalige Extraübungen in der zweiten Vorlesungswoche (05.11 - 08.11) geben. Details sind weiter unten zu finden.
Es gibt einen Kalendar zur Veranstaltung. Dieser ist weiter unten verlinkt.

21. Oktober

Die erste große Übung findet am Dienstag, den 05. November, ab 15:00 - 16:30 in PK 2.2 statt.

2. Oktober

Die erste Vorlesung findet am Montag, dem 28. Oktober, ab 13:15 - 14:45 in PK 11.3 statt.
In dieser Vorlesung werden weitere Details zur Organisation bekannt gegeben.

Organisation

• Die Vorlesungen und Großübungen werden von Prof. Dr. Roland Meyer und Thomas Haas gehalten.
  Der Modulverantwortliche und Prüfer ist Prof. Dr. Roland Meyer.
• Einträge im Vorlesungsverzeichnis: Vorlesung, Großübung, Übung in Kleingruppen.
• Die Termine für Vorlesung und Großübung sind
  • Montag, 13:15 - 14:45 in PK 11.3,
  • Dienstag, 15:00 - 16:30 in PK 2.2.
• Vorlesung und Großübung finden im zweiwöchigen Wechsel statt. In der ersten Vorlesungswoche finden zwei Vorlesungen (Mo. und Di.) und keine große Übung statt. In der zweiten Woche findet eine Vorlesung (Mo.) und eine große Übung (Di.) statt. In der dritten Wochen wieder zwei Vorlesungen usw. Dies können Sie in dem folgenden Kalendar nachschauen.
  • Google Kalendar (benötigt Google Account)
  • Webbrowser Kalendar (benötigt kein Google Account)
  • Offline Kalendar (Aktualität nicht garantiert)

Übungen

• Zusätzlich zur großen Übung gibt es Übungen in Kleingruppen.
  • Benutzen Sie das Onlineanmeldesystem Zahnrad, um sich für die kleinen Übungen bis zum 31. Oktober (einschließlich) anzumelden.
  • Am Dienstag nach der Vorlesung wird ein Blatt mit Übungsaufgaben hochgeladen.
  • Dieses Übungsblatt muss bis Donnerstag, 15:00, in der darauffolgenden Woche bearbeitet und abgegeben werden. Dies ist im Kalendar verzeichnet.
  • Die Abgabe erfolgt in 4er-Gruppen. Zur Abgabe dienen Boxen im Institut für Theoretische Informatik, neben Büro IZ 343.
  • In der darauffolgenden Woche erfolgt die Rückgabe der korrigierten Abgaben sowie die Besprechung der Aufgaben im Rahmen einer Kleingruppen-Übungsstunde.
  • Es wird einmalige Extraübungen in der zweiten Vorlesungswoche (05.11 - 08.11) geben. Bitte finden Sie sich spätestens in diesen Extraübungen in 4er-Gruppen zusammen. In den Extraübungen werden die Grundlagen von Beweisen und deren Techniken erläutert (siehe Beweisen).
• Es gibt insgesamt 6 Übungsblätter, die bepunktet werden. Ihre Bepunktung ist für das Erbringen der Studienleistung relevant (siehe unten).
• Alle Übungen finden im Informatikzentrum in den Räumen des Instituts für Theoretische Informatik statt.
  Die Übungstermine sind wie folgt:
  • Gruppe 1: Dienstag, 16:45 - 18:15 in IZ 161, Tutor: Peter Chini
  • Gruppe 2: Donnerstag, 9:45 - 11:15 in IZ 305, Tutor: Frieso Gerken
  • Gruppe 3: Donnerstag, 9:45 - 11:15 in IZ 358, Tutor: Thorsten Palm
  • Gruppe 4: Donnerstag, 11:30 - 13:00 in IZ 305, Tutor: Thorsten Palm
  • Gruppe 5: Freitag, 11:30 - 13:00 in IZ 305, Tutor: Kai Uwe Harz
  • Gruppe 6: Freitag, 13:15 - 14:45 in IZ 358, Tutor: Kai Uwe Harz

Lerntreff

Übungsblätter

H: Wird hochgeladen am ...
A: Abgabe am Donnerstag, dem ..., um 15:00.
B: Rückgabe und Besprechung in der Woche ...

• Übungsblatt 1 (H: 29.10, A: 07.11, B: 12.11 - 15.11)
• Übungsblatt 2 (H: 12.11, A: 21.11, B: 26.11 - 29.11)
• Übungsblatt 3 / Exercise sheet 3 (H: 26.11, A: 05.12, B: 10.12 - 13.12)
• Übungsblatt 4 / Exercise sheet 4 (H: 10.12, A: 19.12, B: 07.01 - 10.01)
• Übungsblatt 5 / Exercise sheet 5 (H: 07.01, A: 16.01, B: 21.01 - 24.01)
• Übungsblatt 6 / Exercise sheet 6 (H: 21.01, A: 30.01, B: 04.02 - 07.02)

Vorlesungsnotizen

Vorlesungsnotizen (Aktualisiert am 14.01.2020)

Falls Sie Fehler in den Notizen finden, kontaktieren Sie bitte Thomas.

• Fixpunkte
• Datenflussanalyse
• Folien zu Datenflussanalyse
• Folien zu regulären Sprachen und weiterführenden Resultaten
• Regular languages and finite automata
• Equivalence
• Homomorphisms
• Complexity of problems for regular languages
• Minimization
• Pumping lemma for regular languages and ultimate periodicity
• Overview of the results for regular languages
• Reduktionssysteme, Kontextfreie Grammatiken und die Chomsky Hierarchie
• Normal forms for context-free grammars
• Pumping lemmas for context-free languages
• Pushdown automata and context-free languages
• Closure properties of context-free languages
• Deterministic context-free languages and complementation
• Decision algorithms for context-free languages
• Context-sensitive languages
• Immermann and Szelepcséyi's theorem

Modul

• Prüfungsleistung: Zu erbringen durch Bestehen einer schriftliche Abschlussklausur zu Beginn des vorlesungsfreien Zeitraums.
• Studienleistung: Zu erbringen durch das erfolgreiche Bearbeiten von mindestens 50% der Übungsaufgaben.

Abschlussklausur

• Die Abschlussklausur findet in der ersten Woche der vorlesungsfreien Zeit am Donnerstag, dem 13. Februar 2020, ab 15:00 Uhr in der Mensa 2 Beethovenstraße 15 (Nordcampus) statt.
• Die Klausur besteht aus 10 Aufgaben zu je 10 Punkten, die Bearbeitungszeit beträgt 120 Minuten.
• Als Hilfsmittel sind ausschließlich Sprachwörterbücher sowie ein beidseitig handschriftlich beschriebenes DIN A4-Blatt erlaubt.
• Zur Vorbereitung auf die Klausur empfiehlt sich das Durcharbeiten der Klausuren aus den vergangenen Jahren: Winter 2016/17, Sommer 2017, Winter 2017/18, Sommer 2018, Winter 2018/19.

Literatur

• U. Schöning: Theoretische Informatik - kurzgefasst. Springer, 2008.
• J. E. Hopcroft, R. Motwani, J. D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley Longman, 2002.
• M. Sipser: Introduction to the Theory of Computation. Cengage Learning, 2012.
• M. Nebel: Formale Grundlagen der Programmierung. Vieweg+Teubner, 2012.
  Erhältlich als E-Book (auf den Seiten der Universitätsbibliothek, ggf. nur aus dem Uni-Netz).