Die Theoretische Informatik beschäftigt sich mit den grundlegenden Fragestellungen der Informatik. Hierzu werden Computer- und Automatenmodelle idealisiert und mathematisch untersucht.
| Einführung | 01:19:11 | |
|---|---|---|
| Einführung | 00:18:00 | |
| Organisatorisches | 00:20:44 | |
| Methodik der Beweisführung | 00:19:07 | |
| Induktive Beweise | 00:21:20 |
| Deterministische endliche Automaten | 01:19:21 | |
|---|---|---|
| Automaten: Das einfachste Maschinenmodell | 00:21:25 | |
| Erkennung von Wörtern mit Automaten | 00:14:49 | |
| Arbeitsweise von endlichen Automaten | 00:11:36 | |
| Entwurf und Analyse endlicher Automaten | 00:18:07 | |
| Alternative Beschreibung der Arbeitsweise von DEAs | 00:13:24 |
| Reguläre Ausdrücke | 01:21:40 | |
|---|---|---|
| Optimierte Teilmengenkonstruktion | 00:16:43 | |
| Reguläre Ausdrücke | 00:17:14 | |
| Sprachen vs. Ausdrücke | 00:15:01 | |
| Bestimmung der Semantik | 00:15:38 | |
| Beweismethodik für weitere Äquivalenzen | 00:17:04 |
| Umwandlung regulärer Ausdrücke | 01:23:38 | |
|---|---|---|
| Korrektheit der Umwandlungen | 00:19:52 | |
| Zustandselimination in VNEAs | 00:20:28 | |
| Reguläre Ausdrücke - Zusammenfassung | 00:21:31 | |
| Arbeitsweise von Grammatiken - präzisiert | 00:21:47 |
| Sprachklassen | 01:18:01 | |
|---|---|---|
| Sprachklassen | 00:20:48 | |
| Umwandlung am Beispiel | 00:08:55 | |
| Ankündigung Probeklausur | 00:03:32 | |
| Eigenschaften regulärer Sprachen | 00:17:28 | |
| Produktkonstruktion am Beispiel | 00:15:56 | |
| Bild unter Homomorphismen | 00:11:22 |
| Eigenschaften regulärer Sprachen | 01:23:48 | |
|---|---|---|
| Test für Eigenschaften regulärer Sprachen | 00:16:39 | |
| Äquivalenz für Zustande | 00:14:35 | |
| Minimierung endlicher Automaten | 00:18:24 | |
| Inverse Homomorphismen | 00:04:05 | |
| Äquvalenzklassen der Sprache | 00:18:50 | |
| Beweis des Pumping Lemmas | 00:11:15 |
| Kontextfreie Sprachen | 01:20:01 | |
|---|---|---|
| Anwendung des Pumping Lemmas | 00:14:43 | |
| Kontextfreie Sprachen | 00:17:00 | |
| Kontextfreie Grammatik für Palindrome | 00:14:06 | |
| Ableitungsbäume | 00:15:28 | |
| Mehrdeutigkeit | 00:18:44 |
| Pushdown Automaten | 01:13:12 | |
|---|---|---|
| Maschinenmodell für Typ-2 Sprachen | 00:21:03 | |
| Pushdown Automat Beispiel | 00:14:22 | |
| Akzeptierte Sprache eines Pushdown Automaten | 00:18:27 | |
| Erkennen mit leerem Stack ist oft einfacher | 00:19:20 |
| Pushdown Automaten und Grammatiken | 01:20:47 | |
|---|---|---|
| Sind PDAs Maschinen für Typ-2 Sprachen? | 00:15:09 | |
| Von Pusdown Automat zu Grammatik | 00:20:32 | |
| Brauchen wir Nichtdeterministische Automaten | 00:19:40 | |
| Eigenschaften kontextfreier Sprachen | 00:11:57 | |
| Abgeschlossenheit unter Substitution | 00:13:29 |
| Die Chomsky Normalform | 01:25:40 | |
|---|---|---|
| Durchschnitt, Komplement und Differenz | 00:14:42 | |
| Die Chomsky Normalform | 00:19:37 | |
| Unnütze Symbole eliminieren | 00:16:08 | |
| Tests für Eigenschaften kontextfreier Sprachen | 00:18:52 | |
| Unentscheidbare Probleme für Typ-2 Sprachen | 00:16:21 |
| Touringmaschinen | 01:18:39 | |
|---|---|---|
| Beweis des Pumping Lemmas | 00:17:38 | |
| Beschreibung von Touringmaschinen | 00:19:02 | |
| Erkannte Sprache einer Touringmaschine | 00:20:00 | |
| Simulation einer Maschine mit Registern | 01:18:39 |
| Nichtdeterministische Touringmaschinen | 01:12:41 | |
|---|---|---|
| Nichtderministische Touringmaschine | 00:23:00 | |
| Touringmaschinen als Maschinenmodell für L0 | 00:18:26 | |
| Automat für Typ1 Sprachen | 00:14:54 | |
| Abschlusseigenschaften | 00:16:21 |
| Abschlusseigenschaften von Touringmaschinen | 00:51:31 | |
|---|---|---|
| Nachweis der Abschlusseigenschaften | 00:19:58 | |
| Prüfen von Eigenschaften summarisch | 00:11:48 | |
| Zusammenfassung der Modelle | 00:19:45 |
