This site is available only in German.

Theoretische Informatik 2 (B-GL2) – Sommersemester 2017

Im Logbuch finden Sie Informationen zum Inhalt der einzelnen Vorlesungsstunden.

Aktuelles

  • 16.06.
    Blatt 9 ist online. (Abgabe am 27.6.)

Inhalt der Veranstaltung

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 Abschlusseigenschaften der kontextfreien Sprachen werden behandelt. Das Wortproblem für kontextfreie Sprachen wird algorithmisch gelöst, andere Entscheidungsprobleme für kontextfreie Grammatiken stellen sich als unentscheidbar heraus. Es wird gezeigt, dass die kontextfreien Sprachen auch durch Kellerautomaten definiert werden können. Ein Ausblick auf kontextsensitive 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 Zweipersonen-Spiele heraus. Desweiteren wird gezeigt, dass randomisierte Berechnungen und Quantenberechnungen, die in polynomieller Zeit ablaufen, mit polynomiellen Speicherplatz 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 (Frege Systeme, 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ädikatenlogik 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.

Literaturhinweise

  • Ingo Wegener, Kompendium Theoretische Informatik
  • Uwe Schöning, Theoretische Informatik – kurz gefasst
  • Michael Sipser, Introduction to the Theory of Computation (Weiterführende Literatur)
  • Jeffrey O. Shallit, A Second Course in Formal Languages and Automata Theory
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation
  • Sanjeev Arora und Boaz Barak, Computational Complexity, a modern approach, Cambridge University Press 2009.

Termine

Vorlesung:
  • Dienstag, 16 (c.t.) bis 18 Uhr im Magnus-Hörsaal
  • Mittwoch, 08 (c.t.) bis 10 Uhr im Magnus-Hörsaal
Übungen:
  • Gruppe 1: Donnerstag, 16 (c.t.) bis 18 Uhr in SR 307 – Tutor: Philipp Tertel
  • Gruppe 2: Freitag, 12 (c.t.) bis 14 Uhr in SR 307 – Tutor: Hung The Tran

Material

Kontakt

Bei Fragen helfen Philipp Tertel oder Hung The Tran gerne weiter.

Übungsbetrieb

Die Teilnahme an den Übungen und das Bearbeiten der Übungsaufgaben wird für eine erfolgreiche Prüfung unbedingt empfohlen. Die Abgabe bearbeiteter Blätter erfolgt

  • dienstags
  • vor Vorlesungsbeginn
  • im Hörsaal.

Falls ein Erscheinen nicht einzurichten ist, ist eine frühere Abgabe im kleinen Briefkasten vor Raum 313 ebenfalls zulässig. Dieser Briefkasten wird am Abgabetag vor Vorlesungsbeginn geleert. Später eingeworfene Abgaben werden nicht gewertet.

Damit ein reibungsloser Ablauf gewährleistet werden kann, muss jede Abgabe im Kopf der Titelseite gut leserlich mit Name und Matrikelnummer versehen sein.

Abgaben, die mehrere Blätter umfassen, müssen mittels eines Tackers zusammengefügt sein. An der Ecke zusammengefaltete Blätter, Büroklammern o.ä. ersetzen keine Tackernadel! Für nicht getackerte Abgaben kann nicht gewährleistet werden, dass sie vollständig korrigiert werden.

Übungsgruppen

Beginnend mit der zweiten Vorlesungswoche erscheinen wöchentlich Übungsblätter. Diese werden in den Übungsgruppen besprochen, die donnerstags von 16 bis 18 Uhr und freitags von 12 bis 14 Uhr stattfinden. Die Gruppen treffen sich zum ersten Mal in der dritten Vorlesungswoche.

Übungsblätter

Prüfung

Studiengänge

Für den Master Informatik (PO 2015) gliedert sich die Veranstaltung auf in
  • Theoretische Informatik 2: Grundlagen (5 CP, die Veranstaltung findet vom 18.4. bis zum 31.5. statt) und
  • Theoretische Informatik 2: weiterführende Themen (5 CP, die Veranstaltung findet vom 6.6. bis zum 19.7. statt).
Für den Bachelor Informatik wie auch für den alten Master Informatik (PO 2007) und den Master Wirtschaftsinformatik können nur beide Veranstaltungen zusammen geprüft werden (im Umfang von 10 CP). Für den Bachelor Informatik besteht auch die Möglichkeit, wie bisher die Veranstaltung im Umfang von 8 CP prüfen zu lassen.

Mündliche Prüfungen/Klausur

Abhängig von der Teilnehmerzahl finden mündliche Prüfungen oder eine Klausur nach Vorlesungsende statt. Mündliche Prüfungen werden nach Vereinbarung abgehalten. Übungspunkte werden bonifiziert: bei Erreichen von 50 % bzw. 70 % der möglichen Übungspunkte kann die Prüfungsnote um einen bzw. zwei Notenschritte verbessert werden, falls die Prüfung bestanden ist.