Mittwoch 10:00 - 12:00 in SR 11 (R-M-S 11–15)
Donnerstag 12:00 - 14:00 in Magnus Hörsaal (R-M-S 11–15)
Tutorium Donnerstag 14:00 - 16:00, SR 11 (R-M-S 11–15)
Fragestunde Donnerstag 16:00 - 17:00, Raum 311 (R-M-S 11–15)
Übungsblätter werden i.d.R. wöchentlich mittwochs ausgegeben. Die Abgabe erfolgt in der darauffolgenden Woche vor der Vorlesung. Alternativ steht der Briefkasten vor Raum 312 für eine vorzeitige Abgabe zur Verfügung. Einreichungen per E-Mail werden nur als ordentlich-formatiertes PDF Dokument (z.B. mittels Latex) akzeptiert.
Die Teilnahme am Übungsbetrieb wird dringend empfohlen, ist jedoch nicht verpflichtend. Durch die Aufgaben wird Bekanntes vertieft und weiterführende Inhalte vermittelt. Des Weiteren kann durch das Lösen der Aufgaben eine Bonifikation von bis zu einem Notenschritt für die Prüfung erworben werden. Eine Voraussetzung dafür ist das Vorrechnen mindestens einer Übungsaufgabe im Tutorium. Die Bonifikation wird erst angerechnet, wenn die Klausur selbstständig bestanden wurde.
Die Bearbeitung der Aufgaben in Gruppen wird begrüßt, jedoch muss von jedem Teilnehmer eine individuelle Ausarbeitung eingereicht werden. Blätter, auf denen plagiierte oder kopierte Lösungen gefunden werden, werden für jeden Betroffenen nicht bewertet. Im Wiederholungsfall kann es zur Aberkennung sämtlicher Bonifikation kommen.
Die Vorlesung befasst sich mit formalen Sprachen, Komplexititätsklassen und algorithmischen Fragestellungen der Logik. Im ersten Teil werden regulären Sprachen durch deterministische, nichtdeterministische, probabilistische und Zwei-Weg-Automaten sowie durch reguläre Ausdrücke und reguläre Gramatiken dargestellt. Es werden Verfahren zur Minimierung endlicher Automaten entwickelt und mit dem Satz von Myhill-Nerode die Grenzen der regulären Sprachen aufgezeigt. Die kontextfreien Sprachen werden über kontextfreie Grammatiken eingeführt und anhand von Syntaxbäumen veranschaulicht. Pumping-Lemmata, Normalformen und Abschluss- eigenschaften der kontextfreien Sprachen werden behandelt. Das Wortproblem für kontextfreie Sprachen wird algorithmisch gelöst, andere Entscheidungsprobleme für kontext- freie Grammatiken stellen sich als unentscheidbar heraus. Es wird gezeigt, dass die kontextfreien Sprachen auch durch Kellerautomaten definiert werden können. Ein Ausblick auf kontext-sensitive Sprachen, wie auch auf die Chomsky-Hierarchie wird gegeben. Im zweiten Teil werden die Komplexitätsklassen LOG-SPACE und PSPACE der auf logarithmischem bzw. polynomiellem Speicherplatz berechenbaren Entscheidungsprobleme eingeführt. Struktuelle Ergebnisse werden für diese Klassen hergeleitet und schwierigste Probleme werden identifiziert: Z.B. stellt sich PSPACE als die Klasse nicht trivialer Zwei- personen-Spiele heraus. Desweiteren wird gezeigt, dass randomisierte Berechnungen und Quantenberechnungen, die in polynomieller Zeit ablaufen, mit polynomiellen Speicher- platz simuliert werden können. Reguläre, kontextfreie und kontextsensitive Sprachen werden in die Komplexitätsklassen LOG-SPACE, P, NP und PSPACE eingeordnet. Im dritten Teil werden algorithmische Fragestellungen der Aussagenlogik wie Beweissysteme (Modus Ponens, Resolution, SAT-Solver) untersucht. Die Computational Tree Logic wird für die Temporale Aussagenlogik eingeführt und das Model Checking Problem wird gelöst. Ein Ausblick auf die Gödelschen (Un-)Vollständigkeitssätze für die Prädikaten- logik wird gegeben. Die Veranstaltung klassifiziert somit Probleme in Hinblick auf ihren Ressourcen-Verbrauch (Laufzeit, Speicherplatzbedarf). Desweiteren wird die Beschreibungskraft und die algorithmische Handhabbarkeit formaler Sprachen und Logiken untersucht.
Eher zum Teil 1:
Eher zum Teil 2:
Die Klausur findet am 05.08.2019 um 09:00 Uhr (s.t.) in Magnus Hörsaal (R-M-S 11–15) statt.
Handschriftliches Skript - GL-2a
Handschriftliches Skript - GL-2b
Theoretische Informatik 2 - Grundlagen
Theoretische Informatik 2 - Weiterführende Themen