Theoretische Informatik 2 (B-GL2) – Sommersemester 2016

Im Logbuch finden Sie Informationen zum Inhalt der einzelnen Vorlesungsstunden.

Aktuelles

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 (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ä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

Termine

Vorlesung:
  • Montag, 12:00 – 14:00 im Magnushörsaal
  • Dienstag, 8:00 – 10:00 im Magnushörsaal
Übungen:
  • Mittwoch, 10:00 – 12:00 im Raum SR 11

Material

Kontakt

Bei Fragen hilft Noleen Köhler 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

  • montags
  • vor Vorlesungsbeginn
  • im Hörsaal.

Falls ein Erscheinen nicht einzurichten ist, ist eine frühere Abgabe im 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 der Übungsgruppe besprochen, die mittwochs von 10:00 – 12:00 Uhr in SR 11 stattfindet. Die Gruppe trifft sich zum ersten Mal in der dritten Vorlesungswoche.

Übungsblätter

Prüfung

Studiengänge

Für den neuen Master Informatik gliedert sich die Veranstaltung auf in
  • Theoretische Informatik 2: Grundlagen (5 CP, die Veranstaltung findet vom 11.4. bis zum 25.5. statt) und
  • Theoretische Informatik 2: weiterführende Themen (5 CP, die Veranstaltung findet vom 30.5. bis zum 30.7. statt) .
Für den Bachelor Informatik wie auch für den alten Master Informatik 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 40 % bzw. 70 % aller möglichen Übungspunkte kann die Prüfungsnote um einen bzw. zwei Notenschritte verbessert werden, falls die Prüfung bestanden ist.

  • Die Bearbeitung der Übungsblätter in Gruppen ist erlaubt; Lösungen müssen jedoch eigenständig aufgeschrieben werden, damit die erreichten Punkte anerkannt werden.
  • Blätter, auf denen plagiierte oder kopierte Lösungen gefunden werden, werden für jeden Betroffenen nicht bewertet; jedem „Wiederholungstäter“ werden keinerlei Bonuspunkte angerechnet. Diese Regeln gelten auch für aus dem Internet abgeschriebene Lösungen.