Die Theoretische Informatik beschäftigt sich mit den grundlegenden Fragestellungen der Informatik. Hierzu werden Computer- und Automatenmodelle idealisiert und mathematisch untersucht.
Die Automatentheorie und die Theorie der formalen Sprachen (Thema des ersten Semesters) ist grundlegend für die Entwicklung von Programmiersprachen und Compilern. Sie untersucht, mit welchen Techniken welche Arten von Sprachen effizient analysiert werden können.
Die Berechenbarkeitstheorie befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen.
Die Komplexitätstheorie untersucht Effizienz von Algorithmen im Hinblick auf Platz- und Zeitbedarf und kümmert sich insbesondere um die Frage, wie effizient man bestimmte Probleme lösen kann.
Die Veranstaltung ist prinzipiell für Studenten des ersten Semesters geeignet, setzt jedoch ein gutes Verständnis mathematischer Konzepte und Methoden voraus. Für die meisten Studenten ist es daher sinnvoller, zunächst an den entsprechenden Mathematikveranstaltungen teilzunehmen und die theoretische Informatik erst im dritten Semester zu belegen.
| Lehrziele und Lernformen | 01:04:26 | |
|---|---|---|
| Lehrziele und Lernformen | 00:10:48 | |
| Lehrinhalte | 00:09:35 | |
| Lehrinhalt: Analyse von Grundsatzfragen | 00:03:56 | |
| Typische Theoretische Fragenstellungen | 00:02:23 | |
| Themen der Theoretischen Informatik | 00:06:30 | |
| Organisatorisches | 00:03:27 | |
| Leistungserfassung | 00:03:50 | |
| Welche Vorkenntnisse sollten Sie mitbringen? | 00:05:38 | |
| Was ist eigentlich ein Beweis? | 00:05:44 | |
| Wichtige Beweismethoden | 00:14:32 |
| Endliche Automaten und Reguläre Sprachen | 00:22:51 | |
|---|---|---|
| Automaten: Das einfachste Maschinenmodell | 00:02:28 | |
| Verwendungszwecke fuer endliche Automaten | 00:02:14 | |
| Automaten beschreiben Sprachen | 00:02:01 | |
| Modelle zur Beschreibung regulärer Sprachen | 00:04:14 | |
| Erkennung von Wörtern mit Automaten | 00:02:26 | |
| Endliche Automaten - Mathematisch präzisiert | 00:02:20 | |
| Beschreibung von Endlichen Automaten | 00:02:29 | |
| Arbeitsweise von Endlichen Automaten | 00:02:14 | |
| Arbeitsweise von DEAs - Mathematisch präzisiert | 00:04:13 |
| Endliche Automaten und Reguläre Sprachen | 01:13:49 | |
|---|---|---|
| Analyse der Sprache des Wechselschalters | 00:09:25 | |
| Entwurf und Analyse endlicher Automaten | 00:35:14 | |
| Endliche Automaten mit Ausgabefunktion | 00:11:02 | |
| Mealy-Automaten sind Äquivalent zu DEAs | 00:03:16 | |
| Beweis der Äquivalenz (Skizze) | 00:04:46 | |
| Nichtdeterministische Automaten | 00:18:55 |
| Nichtdeterministische endliche Automaten | 01:25:10 | |
|---|---|---|
| Arbeitsweise von NEAs | 00:02:51 | |
| Überführungsfunktion Delta | 00:02:51 | |
| Bestimmung der Epsilon-Hülle | 00:05:24 | |
| Nachweis der erkannten Sprache | 00:04:41 | |
| Nachweis der erkannten Sprache II | 00:14:56 | |
| Beziehung zu Deterministischen Automaten | 00:08:45 | |
| Teilmengenkonstruktion am Beispiel | 00:22:47 | |
| Deterministische Automaten für Textanalyse | 00:01:11 | |
| Analyse der optimierten Teilmengenkonstruktion | 00:13:08 |
| Reguläre Ausdrücke | 01:21:23 | |
|---|---|---|
| Reguläre Ausdrücke: Eine algebraische Beschreibung für Sprachen | 00:05:53 | |
| Reguläre Ausdrücke als Suchmuster in Unix | 00:05:50 | |
| Reguläre Ausdrücke präzisiert | 00:09:33 | |
| Entwicklung regulärer Ausdrücke | 00:07:36 | |
| Sprachen vs. Ausdrücke | 00:03:07 | |
| Rechenregeln für reguläre Ausdrücke | 00:11:13 | |
| Beweismethodik für weitere Äquivalenzen | 00:06:22 | |
| Umwandlung regulärer Ausdrücke in Automaten | 00:11:32 | |
| Korrektheit der Umwandlungen | 00:12:07 | |
| Iterative Bestimmung der Ausdrücke | 00:14:23 |
| Grammatiken | 01:29:08 | |
|---|---|---|
| Eine effizientere Umwandlungsmethode | 00:10:56 | |
| Zustandselimination in RA-Automaten | 00:16:43 | |
| Reguläre Ausdrücke - Zusammenfassung | 00:02:25 | |
| Einheit 2.4:Grammatiken | 00:00:42 | |
| Beschreibungsformen für Sprachen | 00:05:18 | |
| Komponenten von Grammatiken | 00:11:03 | |
| Arbeitsweise von Grammatiken-präzisiert | 00:12:30 | |
| Klassifizierung von Grammatiken | 00:13:26 | |
| Sprachklassen | 00:03:29 | |
| Typ-3 Sprachen vs. reguläre Sprachen | 00:13:42 |
| Eigenschaften regulärer Sprachen | 01:27:43 | |
|---|---|---|
| Eigenschaften regulärer Sprachen | 00:09:52 | |
| Wichtige Eigenschaften formaler Sprachen | 00:08:06 | |
| Abschluss unter Vereinigung, Verkettung, Hülle | 00:02:51 | |
| Abschluss unter Komplementbildung | 00:04:07 | |
| Abschluss unter Durchschnitt und Differenz | 00:10:33 | |
| Abschluss unter Spiegelung | 00:10:57 | |
| Abschluss unter Homomorphismen | 00:18:14 | |
| Tests fuer Eigenschaften regulärer Sprachen | 00:09:50 | |
| Test auf Zugehörigkeit | 00:05:45 | |
| Äquivalenztest für Zustände | 00:08:38 |
| Reguläre Sprachen | 01:21:19 | |
|---|---|---|
| Äquivalenztest für Sprachen | 00:08:35 | |
| Minimierung endlicher Automaten | 00:08:35 | |
| Eine algebraische Charakterisierung regulärer Sprachen | 00:12:09 | |
| Der Satz von Myhill/Nerode | 00:07:48 | |
| Grenzen regulärer Sprachen | 00:04:48 | |
| Das Pumping Lemma für reguläre Sprachen | 00:12:15 | |
| Anwendungen des Pumping Lemmas | 00:12:33 | |
| Eigenschaften regulärer Sprachen im Rückblick | 00:09:35 |
| Rückblick: Kontextfreie Grammatiken | 00:56:46 | |
|---|---|---|
| Rückblick kontextfreie Grammatiken | 00:15:02 | |
| Geschachtelte Klammerausdrücke Geschachtelte Klammerausdrücke | 00:11:56 | |
| Kontextfreie Grammatik für Palindrome | 00:08:03 | |
| Arithmetische Ausdrücke | 00:03:57 | |
| Links- und rechtsseitige Ableitungen | 00:13:41 | |
| Syntaxanalyse und Compilation | 00:08:26 | |
| Mehrdeutigkeit | 00:18:35 | |
| Zusammenfassung | 00:08:10 |
| Pushdown-Automaten und Grammatiken | 02:00:33 | |
|---|---|---|
| Von Grammatiken zu Pushdown-Automaten | 00:10:39 | |
| Korrektheitsbeweis im Detail | 00:22:56 | |
| Von Pushdown-Automaten zu Grammatiken | 00:08:40 | |
| Umwandlung eines PDA in eine Grammatik | 00:06:24 | |
| Brauchen wir Nichtdeterministische Automaten? | 00:04:20 | |
| DPDAs sind nicht mächtig genug | 00:11:05 | |
| Einheit 3.3: Eigenschaften kontexfreier Sprachen | 00:04:01 | |
| Substitutionen von Sprachen | 00:18:38 |
| Vereinigung, Verkettung, Hülle, Homomorphismen | 01:31:52 | |
|---|---|---|
| Abschluss unter Spiegelung | 00:11:38 | |
| Abschluss unter inversen Homomorphismen | 00:24:04 | |
| Die Chomsky Normalform | 00:15:03 | |
| Einheitsproduktionen eliminieren | 00:06:49 | |
| Unnütze Symbole eliminieren | 00:04:44 | |
| Berechnung erzeugender / erreichbarer Symbole | 00:04:00 | |
| Erzeugung der Chomsky Normalform | 00:09:20 | |
| Tests für Eigenschaften kontextfreier Sprachen | 00:17:10 |
| Allgemeine und kontextsensitive Sprachen | 02:05:23 | |
|---|---|---|
| Unentscheidbare Probleme für Typ-2 Sprachen | 00:13:02 | |
| Das Pumping Lemma für kontextfreie Sprachen | 00:07:34 | |
| Beweis des Pumping Lemmas | 00:06:57 | |
| Anwendung des Pumping Lemmas | 00:06:34 | |
| Rückblick: Eigenschaften kontextfreier Sprachen | 00:03:34 | |
| Einheit 4: Allgemeine und kontextsensitive Sprache | 00:02:58 | |
| Turingmaschinen | 00:12:19 | |
| Abarbeitung von Turing-Programmen | 00:38:37 |
| Ausdruckskraft von Turingmaschinen | 00:00:00 | |
|---|---|---|
| Allgemeine und kontextsensitive Sprache | 00:14:12 | |
| Programmiertechnik: Mehrere Spuren | 00:03:54 | |
| Programmiertechnik: Mehrere Bänder | 00:11:03 | |
| Beschränkte Turingmaschinenmodelle | 00:15:52 | |
| Modelle für Typ-0 und Typ-1 Sprachen | 00:01:23 | |
| Maschinenmodelle vs. Grammatiken | 00:24:10 | |
| Korrektheit der Konstruktion | 00:20:35 |
| Linear beschränkte Automaten | 01:22:29 | |
|---|---|---|
| Linear Beschränkte Automaten | 00:12:48 | |
| Eigenschaften von Typ-0/Typ-1 Sprachen | 00:05:51 | |
| Abschlusseigenschaften | 00:29:52 | |
| Grenzen der Sprachklassen | 00:06:11 | |
| Zusammenfassung: Typ-0/Typ-1 Sprachen | 00:01:43 | |
| Rückblick Theoretische Informatik I | 00:27:15 |
