Theoretische Informatik II / Grundlagen der Theoretischen Informatik

Inhalt des Moduls (Überblick):

Im ersten Teil der Vorlesung werden einfache Automatenmodelle (endliche Automaten, Kellerautomaten) und entsprechende formale Grammatiken untersucht. Damit können reguläre bzw. kontextfreie Sprachen erkannt werden, was zum Beispiel für die Beschreibung von Programmiersprachen wichtig ist. Ferner werden grundlegende Eigenschaften dieser Sprachen und Automaten hergeleitet.

Im zweiten Teil der Vorlesung wird untersucht, welche Funktionen algorithmisch berechenbar und welche Probleme algorithmisch entscheidbar sind. Dazu wird der Begriff des Algorithmus auf verschiedene Weisen (Turingmaschinen, Grammatiken, Programme) formalisiert, was sich als äquivalent herausstellt. Es wird auch gezeigt, dass es Probleme gibt, die nicht algorithmisch entscheidbar sind.

Im dritten Teil der Vorlesung geht es um die Komplexität von Algorithmen, d.h., wieviel Zeit bzw. Speicherplatz zum Lösen einer Aufgabe benötigt wird. Insbesondere werden Probleme betrachtet, die deterministisch oder nichtdeterministisch in polynomieller Zeit lösbar sind. Diese wichtigen Problemklassen sind unter den Namen P und NP bekannt.

Ziel des Moduls:

Einführung in die Theorie formaler Sprachen, Automaten, Berechenbarkeit und Komplexität

weitere Informationen im WWW:

http://parsys.informatik.uni-oldenburg.de/teaching/gti_ws0203/

weitere Kommentare:

-

Literatur:

essentiell:

Skript (liegt zum Zeitpunkt der Erstellung dieser Modulbeschreibung noch nicht vor)

empfohlen:

Eike Best, Volker Claus, Ernst-Rüdiger Olderog: "Grundbegriffe der Theoretischen Informatik". Dieses Skriptum (Stand 4. August 1998) liegt zur Zeit auf theoretica.Informatik.Uni-Oldenburg.DE/~best/lecture-notes.html und wird gerade überarbeitet.

Uwe Schöning: "Theoretische Informatik - kurzgefasst". Spektrum Akad. Verlag.

Katrin Erk, Lutz Priese: "Theoretische Informatik - eine umfassende Einführung". Springer-Verlag.

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: "Introduction to Automata Theory, Languages, and Computation". Addison-Wesley. (Von diesem Klassiker soll es im Herbst eine deutsche Übersetzung bei www.pearsonstudium.de geben.)

Voraussetzungen:

Die Module "Diskrete Strukturen" und "Theoretische Informatik I" sollten gehört worden sein.

zu erbringende Leistungen: Hausübungen, Klausur

Kriterien zur Vergabe der Notenpunkte 0-100:

Mindestens 40% der Aufgaben aller Übungszettel müssen im Durchschnitt erfolgreich bearbeitet worden sein, um in der Modulnote mehr als 0 Punkte zu erreichen. Falls das der Fall ist, bestimmt das Ergebnis der Klausur die Modulnote.