Theoretical Computer Science

Vorlesung: Theoretische Informatik 1

Wintersemester 2018/2019

News

22. August

Die Informationen zur Klausur im Sommersemester 2019 finden Sie auf der folgenden Seite: Klausur: Theoretische Informatik 1.

21. Februar

Die Ergebnisse der Abschlussklausur vom 7. Februar sind nun verfügbar:

• Statistiken und Notengrenzen
• Ergebnisse
• Die Klausureinsicht wird am Freitag, den 22.02, von 11:00 - 12:00 Uhr in Raum IZ 161 stattfinden.
• Update 14:12 Uhr: Durch einen Fehler waren die Punktzahlen der Aufgaben nicht korrekt. Dies ist nun behoben.

31. Januar

Die Überarbeitung der Vorlesungsnotizen ist nun abgeschlossen. Falls Sie einen Fehler in den Notizen entdecken, melden Sie ihn bitte Sebastian.

28. Januar

Weitere Informationen zur Abschlussklausur finden Sie nun weiter unten auf dieser Seite.

23. Januar

Viele Neuigkeiten:

• Die Vorlesungsnotizen zu den Vorlesungen am 21. und 22. Februar wurden überarbeitet.
• In der letzten Vorlesungswoche wird am 28. und 29. Februar jeweils eine Vorlesung zu den üblichen Terminen stattfinden.
• Es ist nun ein zusätzliches Übungsblatt zur Klausurvorbereitung verfügbar. Es beinhaltet Aufgaben zu den letzten beiden Vorlesungswochen, aber auch zum gesamten Rest der Vorlesung. Das Blatt soll nicht abgegeben werden und wird nicht bepunktet.
• Wir bieten in der Woche der Klausur montags und dienstags jeweils eine Fragestunde an:
  • Montag, 4. Februar, ab 13:15, Raum MS3.1 in der Mendelssohnstr. 2-3
  • Dienstag, 5. Februar, ab 15:00, Raum PK2.2
  In diesen Terminen werden wir auch das oben genannte Aufgabenblatt besprechen.

9. Januar

Zusätzlich zum 6. (und letzten bepunkteten) Aufgabenblatt gibt es nun auch eine überarbeitete Version der Vorlesungsnotizen, in der die Reihenfolge des Stoffs an die Vorlesung angepasst wurde.

13. Dezember

Weiter unten auf dieser Seite finden Sie nun den Termin der Abschlussklausur. Die Anmeldung zur Klausur erfolgt(e) über das Prüfungsamt. Weitere Informationen werden in den Wochen vor der Klausur bekanntgegeben.

12. Dezember

Das 5. Übungsblatt und eine aktualisierte Version der Vorlesungsnotizen sind nun online! Update 13. Dezember, 17:00 Uhr: In die Definition der Äquivalenzklassen in Aufgabe 1a) hatte sich ein Fehler eingeschlichen. Bitte laden Sie das Blatt ggf. neu herunter.

28. November

Zusätzlich zu Übungsblatt 4 gibt es nun auch eine neue Version der Vorlesungsnotizen, in der die Kapitel 4 - 6 korrigiert bzw. erweitert wurden! Update 19:50: In der Definition der Endzustände des Automatens, der durch das Eliminieren von internen Transtionen entsteht, war sowohl in den Notizen (Satz 4.3) als auch auf dem Aufgabenblatt (Aufgabe 1) ein Fehler. Bitte laden Sie das Blatt ggf. neu herunter.

24. Oktober

Aufgrund der hohen Teilnehmeranzahl, haben wir eine weitere Übungsgruppe eingerichtet:

• Gruppe 0: Donnerstag, 9:45 - 11:15 in IZ 305, Tutor: Peter Chini

Diese findet parallel zur Übungsgruppe 1 statt.

24. Oktober

Wir weisen auf den "Lerntreff Theorie" hin, der immer Dienstags von 16:45 - 18:15 in IZ 305 stattfindet. Der Lerntreff richtet sich an Teilnehmer der Bachelor-Theorieveranstaltungen (z.B. Theoretische Informatik 1), die Verständnisfragen zu Vorlesungsinhalten haben oder Hilfe bei ihren Hausaufgaben benötigen. Der Lerntreff wird von Pascal Baumann betreut.

17. Oktober

Das erste Übungsblatt ist nun verfügbar. Geben Sie dieses Blatt bis Donnerstag, 25.10.2018, 14:00 Uhr, durch Einwerfen in die Übungskästen neben Büro IZ 343 ab. Geben Sie in Gruppen von 4 Personen ab. Nutzen Sie z.B. die Veranstaltungen am 22. & 23.10 um sich mit anderen Studierenden aus der selben Übungsgruppe zu Abgabegruppen zusammenzuschließen.

17. Oktober

Tragen Sie sich bis zum 23.10.2018, 12:00 Uhr, auf den Listen, die neben Büro IZ 344 aushängen, für eine der Übungsgruppen ein.

4. Oktober

Die erste Vorlesung findet am Dienstag, dem 16. Oktober, ab 15:00 - 16:30 in PK 2.2 statt.
In dieser Vorlesung werden weitere Details zur Organisation bekannt gegeben.

Organisation

• Die Vorlesungen und Großübungen werden von Sebastian Muskalla und Prof. Roland Meyer gehalten.
  Der Modulverantwortliche und Prüfer ist Prof. 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 2.2,
  • Dienstag, 15:00 - 16:30 in PK 2.2.
• Vorlesung und Großübung finden im zweiwöchigen Wechsel statt:
  • In der dritten (29.10, 30.10), fünften (12.11, 13.11), ..., elften (7.1, 8.1) und dreizehnten (21.1, 22.1) Woche des Semesters finden montags und dienstags jeweils eine Vorlesung statt. In diesen Woche gibt es keine Großübung.
  • In der vierten (5.11), sechsten (19.11), ..., zwölften (14.1) und vierzehnten (28.1) Woche des Semesters findet montags eine Großübung statt, in welcher der Vorlesungsstoff anhand von Beispielen und Übungsaufgaben vertieft wird. In diesen Wochen finden keine Vorlesungen statt und der Termin dienstags entfällt.
  • Kalender-Datei mit allen Terminen rund um TheoInf1: https://tcs.cs.tu-bs.de/documents/teaching/TheoInf1/20182019/TheoInf1.ics

Übungen

• Zusätzlich zur Großübung gibt es Übungen in Kleingruppen.
  • Am Mittwoch nach der Vorlesung wird ein Blatt mit Übungsaufgaben hochgeladen.
  • Dieses Übungsblatt muss bis Donnerstag, 14:00, in der darauffolgenden Woche bearbeitet und abgegeben werden.
  • 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.
  • Kalender-Datei mit allen Terminen rund um TheoInf1: https://tcs.cs.tu-bs.de/documents/teaching/TheoInf1/20182019/TheoInf1.ics
• 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 0: Donnerstag, 9:45 - 11:15 in IZ 305, Tutor: Peter Chini
  • Gruppe 1: Donnerstag, 9:45 - 11:15 in IZ 358, Tutor: Benedikt Fuhrmann
  • Gruppe 2: Donnerstag, 11:30 - 13:00 in IZ 305, Tutor: Thomas Graave
  • Gruppe 3: Donnerstag, 15:00 - 16:30 in IZ 305, Tutor: Michael Perk
  • Gruppe 4: Freitag, 8:00 - 9:30 in IZ 358, Tutor: Niklas Wrege
  • Gruppe 5: Freitag, 11:30 - 13:00 in IZ 305, Tutorin: Leonie Basso
  • Gruppe 6: Freitag, 13:15 - 14:45 in IZ 358, Tutor: Florian Furbach

Übungsblätter

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

• Übungsblatt 1 (H: 17.10, A: 25.10, B: 29.10 - 02.11)
• Übungsblatt 2 (H: 31.10, A: 08.11, B: 12.10 - 16.11)
• Übungsblatt 3 (H: 14.11, A: 22.11, B: 26.11 - 30.11)
• Übungsblatt 4 (H: 28.11, A: 06.12, B: 10.12 - 14.12)
• Übungsblatt 5 Aktualisiert 13.12, 17:00 (H: 12.12, A: 20.12, B: 07.01 - 11.01)
• Übungsblatt 6 (H: 09.01, A: 17.01, B: 21.01 - 25.01)
• Übungsblatt zur Klausurvorbereitung

Vorlesungsnotizen

Vorlesungsnotizen (Aktualisiert am 31.01.2019)

Falls Sie Fehler in den Notizen finden, kontaktiere Sie bitte Sebastian.

• 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 7. Februar 2019, ab 13:45 auf dem Nordcampus statt.
• Wenn Ihr Nachname mit einem der Buchstaben A - H beginnt, schreiben Sie die Klausur in Hörsaal BI 84.1 auf dem Nordcampus (Bienroder Weg). Ansonsten, also wenn Ihr Nachname mit einem der Buchstaben I - Z beginnt, schreiben Sie die Klausur in der Sporthalle (BI 83) auf dem Nordcampus (Bienroder Weg).
• 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.

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).