Theoretical Computer Science

Vorlesung: Theoretische Informatik 1

Wintersemester 2022/23

News

27. Februar

Die Klausureinsicht findet am 17.03. von 11:00 bis 12:30 in Raum IZ 358 statt.

20. Februar

nr.	title	avg.	med.
1	Arden	8,9	10
2	Det.	9,0	10
3	CYK	8,7	9
4	Trip.	7,4	8
5	Pump.	7,2	8
6	S-Op.	3,7	3
7	Auto.	5,8	6
8	Quiz	2,4	2
9	Reset	2,8	3
10	Pfad.	3,5	4
	total	52,3	53

Die Prüfungsergebnisse der Abschlussklausur vom 16. Februar sind nun verfügbar:

• Ergebnisse

Eine Klausureinsicht wird im März stattfinden. Genaueres folgt in Kürze. Bei weiteren Fragen wenden Sie sich an René Maseli.
Eine Übersicht ist hier bereitgestellt. Die Bestehensquote beträgt 84%.

9. Februar

Hier finden sich die Lösungen für die Probeklausur.

30. Januar

Eine Probeklausur steht ab sofort zur Verfügung. Sie wird voraussichtlich in der nächsten Woche besprochen.

19. Dezember

Die Vorlesung am 20. Dezember entfällt.

2. Dezember

Am 5. und 6. Dezember tauschen Vorlesung und große Übung. Die Vorlesung wird daher dieses Mal am Montag und die Großübung am Dienstag stattfinden.

3. November

Die große Übung findet nun montags statt.

27. Oktober

Die Anmeldung für die kleinen Übungen ist nun hier verfügbar.

27. Oktober

Der Lerntreff Theorie, geleitet von Jan Grünke, findet immer donnerstags, von 13:15 bis 14:45 Uhr, im Raum IZ 358 statt.

24. Oktober

Die Uhrzeit der Vorlesung am Dienstag und der großen Übung wurden angepasst.

18. Oktober

Die Termine für Vorlesung und große Übung stehen nun fest. Start ist am 1. November um 15:00 Uhr in PK 11.2. Es wurde ein Chatraum geöffnet.

13. Juli

Webseite wurde erstellt und veröffentlicht. Die Informationen sind alle noch vorläufig.

Organisation

• Den Übungbetrieb organisiert René Maseli. Der Modulverantwortliche und Prüfer ist Prof. Dr. Roland Meyer.
• Für Fragen, Diskussionen oder ähnliches steht auch ein Chatraum bereit.
• Im zweiwöchigen Rhythmus werden auf dieser Seite Übungsblätter mit Hausaufgaben online gestellt. Diese Hausaufgaben werden in 4er Gruppen bearbeitet und abgegeben. Die Abgaben werden in Kleinübungen mit den Tutoren besprochen.
• Die Tutoren sind Dogukan Hizir, Marc Majohr, Nico Matuschyk und Johannes Schmechel.
• Um sich für die kleinen Übungen anzumelden, tragen Sie sich bis zum 8. November in diese Veranstaltung ein und schließen Sie sich einer der offenen Vierer-Gruppen unter der Vips-Ansicht an. Sie können auch den Chatraum nutzen, um geeignete Partner zu finden. Unvollständige Gruppen bzw. Einzelpersonen werden nach der ersten großen Übung zu Vierer-Gruppen zusammengefasst.
• Vorlesung:
  • Montag, 13:15 - 14:45 in PK 11.3, alle 14 Tage, startend am 14. November.
  • Dienstag, 15:00 - 16:30 in PK 11.2, startend am 1. November.
• Große Übung:
  • Montag, 13:15 - 14:45 in PK 11.3, alle 14 Tage, wenn keine Vorlesung stattfindet, startend am 7. November.
  Vorlesung und große Übung finden im zweiwöchigem Wechsel statt.
• Kleine Übung:
  • Montag, 16:45 - 18:15 in IZ 358 mit Marc Majohr, alle 14 Tage, startend am 14. November.
  • Donnerstag, 9:45 - 11:15 in IZ 358 mit Nico Matuschyk, alle 14 Tage, startend am 17. November.
  • Donnerstag, 15:00 - 16:30 in IZ 358 mit Dogukan Hizir, alle 14 Tage, startend am 17. November.
  • Freitag, 8:00 - 9:30 in IZ 358 mit Johannes Schmechel, alle 14 Tage, startend am 18. November.
• Lerntreff Theorie:
  • Donnerstag, 13:15 - 14:45 in IZ 358 mit Jan Grünke, startend am 3. November.
• Alle Termine sind hier verfügbar.

Kleine Übung

Vorlesungsnotizen

Wir bieten ein geTeXtes Skript an (aktualisiert am 15.11.2022). Ein Foliensatz steht ebenfalls zur Verfügung (Stand 07.02.2022). Falls Sie Fehler in den Notizen finden, kontaktieren Sie bitte René Maseli.

Zudem gibt es handschriftliche Notizen zu einzelnen Themen der Vorlesung.

• 1. - 14. November: Fixpunkte
  Achtung: In den Aufzeichnungen sind Pre und Post-Fixpunkt vertauscht. Die Aufzeichnungen sind korrekt, benutzen aber eine mit dem Skript inkonsistente Notation.
• 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
• Satz von Immermann und Szelepcsényi

Große Übung

Die Notizen der großen Übungen werden hier bereitgestellt. Außerdem finden sich hier Video-Aufzeichnungen aus dem letzten Wintersemester.

• 7. November: Verbände pdf mp4 (letztes Jahr)
• 21. November: Datenfluss-Analyse pdf mp4 (letztes Jahr)
• 6. Dezember: Arden's Lemma, Potenzmengenkonstruktion, Shuffle pdf mp4 (letztes Jahr)
• 19. Dezember: Shuffle, Myhill-Nerode pdf mp4
• 16. Januar: Minimerung, Pumping Lemma, Kontextfreie Grammatiken pdf mp4

Modul

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

Prüfung

• Die Prüfung findet am Donnerstag, dem 16. Februar 2023, von 15:30 Uhr bis 17:30 Uhr im Audi-Max und dem Hörsaal UP 3.007 darunter statt.
• Sie 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 Prüfung empfiehlt sich das Durcharbeiten der Klausuren aus den vergangenen Jahren: Winter 2016/17, Sommer 2017, Winter 2017/18, Sommer 2018, Winter 2018/19, Winter 2019/20, Winter 2020/21, Winter 2021/22.

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