Theoretische Informatik
Übersicht
- Dozent: Prof. Dr. Peter Thiemann
- Assistent: Marius Weidner
- Vorlesung: HS 00 026 µ-Saal G.-Köhler-Allee 101, dienstags 16:15–17:30 Uhr und mittwochs 12:00–13:00 Uhr
Skript
Die aktuelle Version des Skripts wird jeweils nach der Vorlesung auf den neusten Stand gebracht.
Vorlesung
| Datum | Thema |
|---|---|
| Di, 21.04.2026 | Vorspann Sprachen |
| Mi, 22.04.2026 | Reguläre Sprachen, DEA |
| Di, 28.04.2026 | Reguläre Sprachen, Minimierung |
| Mi, 29.04.2026 | Reguläre Sprachen, Rechtskongruenz |
| Di, 05.05.2026 | Reguläre Sprachen, Satz von Nerode |
| Mi, 06.05.2026 | keine Vorlesung |
| Di, 12.05.2026 | Reguläre Sprachen, NEA |
| Mi, 13.05.2026 | Reguläre Sprachen, Pumping Lemma |
| Di, 19.05.2026 | Reguläre Sprachen, NEA-epsilon |
| Mi, 20.05.2026 | Reguläre Sprachen, Reguläre Ausdrücke |
| Di, 02.06.2026 | Grammatiken, Chomsky Hierarchie |
| Mi, 03.06.2026 | Kf Grammatiken: Ableitungsbäume, Grammatiktransformationen |
| Di, 09.06.2026 | Kf Grammatiken: Transformationen, CNF, CYK-Algorithmus |
| Mi, 10.06.2026 | Pumping Lemma für kf Sprachen |
| Di, 16.06.2026 | a^nb^nc^n, Abschlusseigenschaften von CFL, Kellerautomaten (NPDA) |
| Mi, 17.06.2026 | CFL => Kellerautomat (NPDA) |
| Di, 23.06.2026 | NPDA => CFG, Primitive Rekursion |
| Mi, 24.06.2026 | Primitive Rekursion, LOOP Berechenbarkeit |
| Di, 30.06.2026 | Mu Rekursion, WHILE Berechenbarkeit |
| Mi, 24.06.2026 | Mu Rekursion vs TM Berechenbarkeit, Ackermannfunktion |
| Mi, 22.07.2026 | Fragestunde |
Am Mittwoch, den 22.07.2026, findet eine Fragestunde zur Klausur und den Themen der Vorlesung statt.
Übungen
Es wird insgesamt 12 Übungsblätter geben. Die letzten beiden Übungsblätter sind Wiederholungsblätter zu den in der Vorlesung behandelten Themen.
| Datum | Abgabe | Material | Lösungen |
|---|---|---|---|
| Mi, 22.04.2026 | Di, 28.04.2026, 16:00 Uhr | Blatt 01 | Lösung |
| Mi, 29.04.2026 | Di, 05.05.2026, 16:00 Uhr | Blatt 02 | Lösung |
| Mi, 06.05.2026 | Di, 12.05.2026, 16:00 Uhr | Blatt 03 | Lösung |
| Mi, 13.05.2026 | Di, 19.05.2026, 16:00 Uhr | Blatt 04 | Lösung |
| Mi, 20.05.2026 | Di, 02.06.2026, 16:00 Uhr | Blatt 05 | Lösung |
| Mi, 03.06.2026 | Di, 09.06.2026, 16:00 Uhr | Blatt 06 | Lösung |
| Mi, 10.06.2026 | Di, 16.06.2026, 16:00 Uhr | Blatt 07 | Lösung |
| Mi, 17.06.2026 | Di, 23.06.2026, 16:00 Uhr | Blatt 08 | Lösung |
| Mi, 24.06.2026 | Di, 30.06.2026, 16:00 Uhr | Blatt 09 | Lösung |
| Mi, 01.07.2026 | Di, 07.07.2026, 16:00 Uhr | Blatt 10 | Lösung |
| Mi, 08.07.2026 | Mi, 15.07.2026, 08:00 Uhr | Blatt 11 | Lösung |
| Mi, 15.07.2026 | Di, 21.07.2026, 16:00 Uhr | Blatt 12 | Lösung |
Alle Übungsblätter müssen über Git eingereicht werden.
Hinweise:
- Es gibt ein Tutorial zur Übungsplattform
- Es darf nur ein einzelnes PDF-Dokument abgegeben werden.
- Handgeschriebene (und anschließend digitalisierte) Abgaben sind erlaubt.
- Wir prüfen die Abgaben auf Plagiate: Der Austausch von Ideen ist erlaubt, aber alle Abgaben müssen selbstständig erstellt werden.
- Abgaben per E-Mail sowie Abgaben nach der Deadline sind nicht möglich.
Leistungen
Studienleistung
Es gibt 12 Übungsblätter. Für jedes Übungsblatt gibt es 20 Punkte. Daraus ergibt sich eine maximale Gesamtpunktzahl von 240 Punkten. Zum Bestehen der Studienleistung werden 50% der Punkte (120 Punkte) benötigt.
Prüfungsleistung
Die Prüfung findet auf Papier und ohne jegliche Hilfsmittel statt. Genauere Informationen folgen vor der Klausur.