Theoretische Informatik II - Sommersemester 2024
| Dozent: | Dominik Scheder vorname.nachname@gmail.com |
| Termine: | Vorlesung | Dienstag | 13:45 - 15:15 | A10.205 (alt: 1/205) | Prof. Dr. Scheder |
| Mittwoch | 11:30 - 13:00 | A12.346 (alt: 1/346) | Prof. Dr. Scheder | ||
| Übung | Montag | 09:15 - 10:45 | A10.205 (alt: 1/205) | Schulze | |
| Freitag | 13:45 - 15:15 | A10.208.1 (alt: 1/208A) | Schulze |
Hinweis: Die Übungen beginnen in der zweiten Vorlesungswoche. Die erste Übung findet folglich am 08.04.2024 statt.
Hinweis zu den Übungen: Ein Übungsblatt wird jede Woche auf dieser Website veröffentlicht.
Vorlesungsskript
Mein Vorlesungsskript liegt ausschließlich online vor. Über Hinweise zu Fehlern, toten Links etc. freue ich mich!
Stundenplan
Sprechstunden
Dienstag, 15:30 - 17:00 und Mittwoch, 9:15 - 10:45. An anderen Tagen gerne auch, dann aber online und nach Verabredung!
Inhalt
- Boolesche Schaltkreise
- Unendliche Mengen
- Berechenbarkeitsbegriff auf natürlichen Zahlen: Primitive Rekursionn
- Formale Sprachen, insbesondere: reguläre Sprachen, endliche Automaten, reguläre Ausdrücke.
- Kontextfreie Sprachen. Parser.
- Turingmaschinen und Berechenbarkeit
- Komplexitätstheorie: Laufzeit und Speicherbedarf
Literatur
- Michael Sipser: Introduction to the Theory of Computing
- Uwe Schöning: Theoretische Informatik - kurz gefasst
