[Termine] [Folien] [Übungen] [Forum] [Wiki] [Inhalt] [Literatur] [Prüfung] [Studienleistungen] [Lernraum-Betreuung/-Tutorium] [Repetitorium]
| Vorlesungsbeginn | 08.04.2008 |
| Übungsbeginn | 14.04.2008 |
| Wann? | Wo? | Wer? | |
| Vorlesung | di 10.15—11.45 | HS 6, HG 1 | Thomas Jansen |
| Vorlesung | do 12.15—13.45 | HS 5, HG 2 | Thomas Jansen |
Die Vorlesung "Grundbegriffe der theoretische Informatik" (GTI) bietet eine Einführung in die theoretische Informatik unter besonderer Berücksichtigung anwendungsbezogener Aspekte. Konkret werden die Teilgebiete Entscheidbarkeitstheorie und Komplexitätstheorie, Automatentheorie und Grammatiken behandelt.
Während es in der Vorlesungsreihe "Datenstrukturen, Algorithmen und Programmierung" vorrangig darum geht, für konkrete Probleme effiziente Algorithmen zu finden, wollen wir uns hier stärker auf die Probleme an sich konzentrieren und sehr viel grundsätzlicher untersuchen, wie sie gelöst werden können. Nach einer geeigneten Formalisierung stehen zunächst Negativresultate im Vordergrund: Welche Probleme kann man mit einem Computer überhaupt nicht lösen, welche (vermutlich) nicht effizient? Dabei ist es wichtig zu klären, in wie weit solche Aussagen für die Praxis wichtige Konsequenzen implizieren.
Eingeschränkte Rechenmodelle wie zum Beispiel Mealy-Automaten sind schon aus der Vorlesung "Rechnerstrukturen" bekannt. Wir wollen hier systematisch eingeschränkte Rechenmodelle untersuchen und dabei verstehen, wie ihr Verständnis in der Praxis hilfreich ist. Es ergeben sich wichtige und hilfreiche Beziehungen zu Grammatiken, die zur formalen Beschreibung der Syntax von Programmiersprachen benutzt werden. Auch hier konzentrieren wir uns auf die Aspekte, die uns in der Praxis zum Beispiel beim Entwurf eigener Programmiersprachen hilfreich sein können.
Trotz allen Praxisbezugs beschäftigt sich die Vorlesung mit Gegenständen, die abstrakter und komplexer sind, als das in anderen Veranstaltungen der Fall ist. Ehrliches Interesse, ein gewisser Grad an Durchhaltevermögen, regelmäßige Teilnahme an den Vorlesungen und deren ernsthafte Nachbereitung sowie regelmäßige und vor allem aktive Teilnahme an den Übungen helfen sehr, den wichtigen und auch wirklich spannenden Stoff gut zu verstehen und zu verinnerlichen.
Die Vorlesung folgt zwei Büchern von Ingo Wegener. Zur Ergänzung kann das dritte Buch der folgenden Liste hilfreich sein, das (wie der Titel schon sagt) eher eine Ideensammlung als ein Lehrbuch ist.
Für Studierende im Diplomstudiengang gibt es nach wie vor eine mündliche Fachprüfung. Prüfungstermine gibt es in ausreichender Anzahl, Terminabsprache erfolgt direkt mit mir am besten während meiner Sprechstunden.
Zur Vorlesung werden für Studierende im Bachelor-Studiengang sowie für Lehramtsstudierende schriftliche Fachprüfungen angeboten. Ort, Zeit und Dauer sind der unten stehenden Tabelle zu entnehmen. Zur Klausur sind bitte Lichtbildausweis und dokumentenechter Stift (nicht in rot) mitzubringen, Hilfsmittel (zum Beispiel Bücher, Mitschriften, Taschenrechner) sind nicht zugelassen. Es sei an dieser Stelle an die Studienleistungen erinnert. Prüfer sind Thomas Jansen und Beate Bollig.
| Studiengang | Termin | Ort | Dauer |
| Bachelor | 28.08.2008, 10 Uhr | HS 6, HG 1 | 3 Stunden |
| Lehramt | 28.08.2008, 10 Uhr | HS 6, HG 1 | 4 Stunden |
| Bachelor | 09.10.2008, 10 Uhr | Otto-Hahn-Straße 14, HS E 23 | 3 Stunden |
| Lehramt | 09.10.2008, 10 Uhr | Otto-Hahn-Straße 14, HS E 23 | 4 Stunden |
Klausurergebnisse der Klausuren vom 28.08.2008
| Matrikelnummer | Note |
| xxxx33 | 3,7 |
| xxxx64 | n.b. |
| xxxx73 | n.b. |
| xxxx77 | 2,7 |
Klausurergebnisse der Klausuren vom 09.10.2008
| Matrikelnummer | Note |
| xxxxx1 | n.b. |
| xxxxx2 | 3,3 |
Hier gibt es vorlesungsbegleitend die in der Vorlesung verwendeten Folien zum Nachschlagen. Sie sind als Ergänzung zu verstehen und sollen dazu einladen, in der Vorlesung weniger zu schreiben und mehr zu hören. Ohne die Erläuterungen sind sie vermutlich wenig hilfreich, darum ersetzt dieser Service sicher nicht den Besuch der Vorlesung
Die langen Fassungen enthalten alle schrittweisen Einblendungen, die anderen Fassungen sind zum Ausdruck geeignet. Korrigierte Fassungen gibt es immer nach den Vorlesungen, das Datum der letzten Aktualisierung ist vermerkt.
Es gibt auch einen GTI-Folien-Komplettsatz, der
alle inhaltlichen Folien (also ohne Ankündigungen und Wiederholungen) der Vorlesung enthält, und der im Gegensatz zu den vorlesungsbegleitenden Folien auch spätere Fehlerkorrekturen enthält.
Aktueller Stand: 08.07.2008, Größe: 2,39MB
| Vorlesungsdatum | Folien | Inhalte | |
| 1 | 08.04.2008 | 1-42 (1,07MB)
(lang (6,46MB)) (Version vom 15.04.2008) |
Motivation; Organisatorisches; Übersicht; Definition: algorithmisches Problem, Beispielproblem TSP, (erweiterte) Church'sche These, Definitionen: algorithmische Komplexität, (randomisierte) Turingmaschine, P |
| 2 | 10.04.2008 | 43-100 (0,99MB)
(lang (5,78MB)) (Version vom 10.04.2008) |
Las-Vegas-Algorithmen, EP, ZPP(ε(n)), Monte-Carlo-Algorithmen, BPP(&epsilon(n)), RP(&epsilon(n)), co-RP(&epsilon(n)), Theorem 3.3.1: EP=ZPP(1/2), Markow-Ungleichung, Probability Amplification, Theorem 3.3.2, ZPP, ZPP*, Theorem 3.3.4, RP, RP*, Chernoff-Schranken, Theorem 3.3.6, BPP, PP, Bemerkung 3.4.1, Theorem 3.4.2: Komplexiätslandschaft für Entscheidungsprobleme, Theorem 3.4.3 |
| 3 | 15.04.2008 | 101-150 (0,81MB)
(lang (4,65MB)) (Version vom 17.04.2008) |
nichtdeterministische TM, NP, Theorem 3.5.2: NP=RP*, Theorem 3.5.3: Komplexitätslandschaft für Entscheidungsprobleme, Definition 4.1.1: Turingreduktion, Turingreduktionen zwischen verschiedenen Problemtypen, Beispielprobleme MAX-SAT, Clique, BP, Theorem 4.3.1: DHC =T HC ≤T TSP2, Δ sym, Theorem 4.3.2: SAT =T3-SAT, Theorem 4.3.3: PARTITION ≤T BP, Theorem 4.3.4: Clique =T IS =T VC, Theorem 4.4.3: 3-SAT ≤T Clique |
| 4 | 17.04.2008 | 151-178 (0,32MB)
(lang (1,81MB)) (Version vom 17.04.2008) |
Theorem 4.4.4: 3-SAT ≤T DHC, Definition 4.5.1: ≤p, Definition 5.1.1: C-schwierig, C-einfach, C-äquivalent, C-vollständig, Theorem 5.2.1: Optimierungsproblementscheidungsvarianten in NP, Theorem 5.3.1: NP deterministisch in Exponentialzeit, Theorem 5.3.2: "NP=Verifikation", Theorem 5.4.3: Theorem von Cook |
| 5 | 22.04.2008 | 179-208 (0,35MB)
(lang (1,70MB)) (Version vom 22.04.2008) |
Theorem 5.4.3: Theorem von Cook, Definition 5.4.1: stereotype TM, Lemma 5.4.2: Simulation durch stereotype TM, Theorem 6.2.1: DHP und HP in NPC, Theorem 6.2.2: BMST in NPC, Theorem 6.3.1: SSS in NPC |
| 6 | 24.04.2008 | 209-248 (0,55MB)
(lang (2,50MB)) (Version vom 24.04.2008) |
Korollar 6.3.2: KP und PARTITION in NPC, Theorem 6.7.1: CP(0,1,3) in NPC, Definitionen 2.1.1/2.1.2: berechenbar, entscheidbar, total rekursiv, REK, Gödelnummer, Anzahl Probleme und Anzahl Algorithmen, Definition 2.6.1 D, Satz 2.6.2: D nicht rekursiv, Korollar 2.6.3: D nicht rekursiv, Definition 2.8.5: &le, &le* |
| 7 | 29.04.2008 | 249-279 (0,38MB)
(lang (2,07MB)) (Version vom 29.04.2008) |
Definition 2.6.6: universelle Sprache U, Satz 2.6.7: U nicht rekursiv, Definition 2.6.4: Halteproblem H, Satz 2.6.5: H nicht rekursiv, Satz 2.6.11: Satz von Rice, Definition 2.6.9: Hε, Satz 2.6.10: Hε nicht rekursiv, Satz 2.7.1: Abschlusseigenschaften rekursiver Sprachen, Definition 2.1.2: rekursiv aufzählbar, Satz 2.7.2, Lemma 2.7.3, Satz 2.7.4 und Korollar 2.7.5: Abschlusseigenschaften rekursiv aufzählbarer Sprachen, Definition 2.8.1: PKP, Definition MPKP, Lemma 2.8.7: MPKP ≤ PKP, Satz 2.8.9: PKP nicht rekursiv |
| 8 | 06.05.2008 | 280-305 (0,30MB)
(lang (2,03MB)) (Version vom 06.05.2008) |
Satz 2.8.9: PKP nicht rekursiv, Definition DFA, Beispiel-DFAs, Definition Synthese-Operatoren |
| 9 | 08.05.2008 | 306-337 (0,45MB)
(lang (2,18MB)) (Version vom 08.05.2008) |
Definition Synthese-Operatoren, DFA-Komplementbildung, DFA-Vereinigung, Definition 4.2.1: überflüssige Zustände, Satz 4.2.2: Berechnung überflüssiger Zustände, Definition 4.2.3: äquivalente Zustände, Definition 4.2.4: Äquivalenzklassenautomat, Satz 4.2.5: Äquivalenzklassenautomat, Satz 4.2.7: Berechnung des Äquivalenzklassenautomaten, Definition 4.2.8: Rechtsinvarianz, Beispiel 4.2.9: RA, Beispiel 4.2.10: Nerode Relation RL, Satz 4.2.11: Satz von Nerode |
| 10 | 13.05.2008 | 338-380 (0,64MB)
(lang (3,57MB)) (Version vom 13.05.2008) |
Korollar 4.2.12: minimaler DFA, Satz 4.2.13: Algorithmus für DFA-Minimierung, Lemma 4.3.1: Pumping-Lemma, Definition NFA, exponentielle Größenunterschiede NFA-DFA, Satz 4.4.5: Potenzmengenkonstruktion, Algorithmus 4.4.6: Potenzmengenkonstruktion ohne überflüssige Zustände, Satz 4.4.8: NFAs mit ε-Übergängen, Satz 4.6.1: Leerheitstest für DFAs und NFAs, Satz 4.6.2: Vollständigkeitstest für DFAs, Satz Vollständigkeitstest für NFAs, Komplexität von NFA-Minimierung, Komplexität von NFA-Komplementbildung, Komplexität des Gleichheitstests für DFAs und NFAs |
| 11 | 15.05.2008 | 381-427 (0,72MB)
(lang (4,11MB)) (Version vom 15.05.2008) |
Satz 4.6.10: Konkatenation regulärer Sprachen, Satz 4.6.8: Quotientenbildung regulärer Sprachen, Satz 4.6.12: Kleenescher Abschluss regulärer Sprachen, Satz 4.6.17: inverser Homomorphismus regulärer Sprachen, Definition Grammatik, Definition Wortproblem und Syntaxanalyseproblem, Definition Chomsky-Hierarchie, L3 ⊆ L2 ⊆ L1 ⊆ L0, Satz 5.2.2: Chomsky-0 → NTM, Satz 5.2.3: NTM → rekursiv aufzählbar, Satz 5.2.1: rekursiv aufzählbar → Chomsky-0, Korollar 5.2.4: Chomsky-0=NTM=DTM=rekursiv aufzälbar, Satz 5.3.1: Chomsky-3=regulär, Definition 5.3.2: reguläre Ausdrücke, Satz 5.3.3: reguläre Ausdrücke=regulär |
| 12 | 20.05.2008 | 428-467 (0,53MB)
(lang (2,40MB)) (Version vom 20.05.2008) |
Definition 5.4.1: DTAPE, NTAPE, Satz 5.4.5: L1=NTAPE(n), Satz 5.4.3: Platz und Zeit Korollar 5.4.6: Form von csg, Satz 5.4.8: Satz von Savitch, Definition 5.4.7: bandkonstruierbar, Satz 5.4.9: Satz von Immerman und Szelepcsenyi, Satz 5.4.10: Clique in DTAPE(n), Trennung Chomsky-1 von Chomsky-0, Trennung Chomsky-2 von Chomsky-3, Beispiele für cfl und cfg |
| 13 | 27.05.2008 | 468-512 (0,73MB)
(lang (3,57MB)) (Version vom 27.05.2008) |
Definition Syntaxbaum, Definition 6.1.5: Eindeutigkeit, Definition 6.2.1: Chomsky-Normalform, Definition Größe einer Grammatik, Satz 6.2.2: Transformation in Chomsky-Normalform, Satz 6.3.1: CYK-Algorithmus |
| 14 | 29.05.2008 | 513-552 (0,56MB)
(lang (2,75MB)) (Version vom 30.05.2008) |
Lemma 6.4.1: Pumping-Lemma für cfl, Satz 6.4.4: Chomsky-Hierarchie echt, Lemma 6.4.2: Ogdens Lemma, Definition 6.5.1: nutzlose Variable, Satz 6.5.2: Entfernung nutzloser Variabler, Korollat 6.5.3: Leerheitstest, Satz 6.5.4: Endlichkeitstest, Satz 6.5.5: cfl abgeschlossen gegen Vereinigung, Konkatenation, kleeneschen Abschluss, Satz 6.5.6: cfl nicht abgeschlossen gegen Durchschnitt, Komplement, Satz 6.5.7: cfl abgeschlossen gegen Substitution, Satz 6.6.1: für cfg G1, G2 über Nichtleerheit des Schnitts zu entscheiden nicht rekursiv, Satz 6.6.2: Entscheidung über Eindeutigkeit von cfg nicht rekursiv |
| 15 | 03.06.2008 | 553-594 (0,63MB)
(lang (3,53MB)) (Version vom 03.06.2008) |
Definition 6.6.3: BM, Lemma 6.6.4: BM als Durchschnitt zweier cfg, Lemma 6.6.5: Kontextfreiheit von BM, Lemma 6.6.6: zum Komplement von BM, Satz 6.6.7: unentscheidbare Probleme für cfg, Satz 6.7.1: inhärent mehrdeutige cfg, Definition NPDA und DPDA, Satz 7.2.3 und Satz 7.2.4: Äquivalenz der Akzeptanzmodi |
| 16 | 05.06.2008 | 595-631 (0,52MB)
(lang (2,66MB)) (Version vom 05.06.2008) |
Satz 7.2.3 und Satz 7.2.4: Äquivalenz der Akzeptanzmodi, Definition 7.1.1: Greibach-Normalform, Satz 7.1.2: Transformation in Greibach-Normalform, Definition 7.1.4: formale Potenzreihe |
| 17 | 10.06.2008 | 632-676 (0,68MB)
(lang (3,21MB)) (Version vom 10.06.2008) |
Lemma 7.1.5 zur Transformation in Greibach-Normalform, Lemma 7.1.6: Längenbeschränkung bei Greibach-Normalform, Satz 7.1.7: Größenzuwachs bei Transformation in Greibach-Normalform, Satz 7.3.1: NPDA zur Greibach-Normalform, Satz 7.3.2: L(NPDA) ist cfl, Satz 7.4.1: cfl Abschluss gegen inverse Homomorphismen, Satz 7.4.2: cfl Abschluss gegen Schnitt mit regulären Sprachen |
| 18 | 12.06.2008 | 677-701 (0,28MB)
(lang (1,50MB)) (Version vom 12.06.2008) |
Definition 8.1.1: DPDA-Normalform, Satz 8.1.2: zur DPDA-Normalform, Satz 8.1.3: dcfl Abschluss gegen Komplement, Satz 8.1.6: Abschlusseigenschaften dcfl, Satz 8.1.5: dcfl Abschluss gegen inverse Homomorphismen und Durchschnitt mit regulären Sprachen |
| 19 | 17.06.2008 | 702-723 (0,25MB)
(lang (1,19MB)) (Version vom 17.06.2008) |
Satz 8.1.6: Abschlusseigenschaften dcfl, Satz 8.1.7: für DPDA und DFA entscheidbare Probleme, Satz 8.1.8: für DPDA unentscheidbare Probleme, Satz 8.1.9: Unentscheidbarkeit von dcf, "Algorithmus" 8.2.1: Skizze LR(k)-Parser, Definition 8.2.2: Rechtssatzform, Definition 8.2.3: Schlüssel, Definition 8.2.4: FIRSTk(α), Definition 8.2.5: LR(k)-Grammatik |
| 20 | 19.06.2008 | 724-745 (0,26MB)
(lang (1,27MB)) (Version vom 19.06.2008) |
Definition 8.2.4: FIRSTk(α), Definition 8.2.5: LR(k)-Grammatik, Algorithmus 8.2.9: LR(k)-Parser, Lemma 8.3.1: Charakterisierung LR(k)-Grammatik, Definition 8.3.2: lebensfähiger Präfix, Definition 8.3.3: (gültiges) LR(k)-Item |
| 21 | 24.06.2008 | 746-783 (0,55MB)
(lang (2,39MB)) (Version vom 24.06.2008) |
Definition 8.3.2: lebensfähiger Präfix, Definition 8.3.3: (gültiges) LR(k)-Item, Definition 8.3.4: EFFk(&alpha), Satz 8.3.6: Charakterisierung LR(k)-Grammatik, Algorithmus 8.4.1 und Algorithmus 8.4.3: Berechnung aller LR(k)-Items, Satz 8.4.2: Korrektheit von Algorithmus 8.4.1, Satz 8.4.4: Entscheidung über lebensfähige Präfixe, Algorithmus 8.4.5: Berechnung von T, Satz 8.4.6: Korrektheit von Algorithmus 8.4.5, Algorithmus 8.4.7: Test auf LR(k)-Grammatik, Algorithmus 8.4.8: Berechnung der Parsetabelle, Satz 8.4.9: Korrektheit von Algorithmus 8.4.8, Korollar 8.4.10: Eindeutigkeit von LR(k)-Grammatiken, Satz 8.4.11: LR(k)-Parsing in Linearzeit, Satz 8.5.1: LR(k)-Grammatiken passen genau zu DPDA |
| 22 | 26.06.2008 | 784-812 (0,35MB)
(lang (1,73MB)) (Version vom 26.06.2008) |
Motivation Black-Box-Optimierung, Definition Black-Box-Algorithmus, Definition Randomisierte, iterierte lokale Suche, Definition Randomisierte lokale Suche, Definition Rein zufällige Suche, Definition Rein zufällige Suche mit Wörterbuch, Definition (1+1)-EA, Definition Simulated Annealing, Definition Metropolis-Algorithmus, Beschreibung deterministischer Black-Box-Algorithmen, Definition Optimierzeit, Definition Worst Case erwartete Optimierzeit, Definition Black-Box-Komplexität, Theorem Black-Box-Komplexität und Anzahl Zielfunktionen, Korollar Black-Box-Komplexität und Teilmengenbeziehung, Theorem allgemeine obere Schranke |
| 23 | 01.07.2008 | 813-845 (0,40MB)
(lang (1,94MB)) (Version vom 01.07.2008) |
Definition Black-Box-Algorithmus, Definition Optimierzeit, Definition Worst Case erwartete Optimierzeit, Definition Black-Box-Komplexität, Theorem Black-Box-Komplexität und Anzahl Zielfunktionen, Korollar Black-Box-Komplexität und Teilmengenbeziehung, Theorem allgemeine obere Schranke, Black-Box-Komplexität O(n3) für 3-SAT, Komplexität O(1) für N, Theorem 9.2.1: Yaos Minimax-Prinzip, Theorem 9.3.1: BN, Theorem 9.3.2: BT |
| 24 | 03.07.2008 | 846-876 (0,39MB)
(lang (2,20MB)) (Version vom 03.07.2008) |
Verallgemeinerung f*, Bf*, Bb*, Definition lokales Maximum, Definition (schwach) unimodal, Definition Pfad, Pfadfunktion, Definition Klasse der Pfadfunktion Fl(n), BFl(n), Lemma Pfadkonstruktion |
| 25 | 08.07.2008 | 877-903 (0,32MB)
(lang (1,82MB)) (Version vom 08.07.2008) |
BFl(n), NFL-Theorem, Definition Optimierungsziel, Lemma 1: gleiche Werteprojektionen implizieren gleiche Funktionen, Lemma 2: Gleichheit der Anzahlen von Werteprojektionen und Funktionen, Korollar 3: Gleichheit von Werteprojektionen und Funktionen, Interpretation NFL-Theorem |
| 26 | 10.07.2008 | 904-924 (0,35MB)
(lang (1,48MB)) (Version vom 09.07.2008) |
Gesamtwiederholung GTI, Sneak Preview KT: PCP-Theorem und Anwendung |