Spezielle Gebiete der Theoretischen Informatik

Pflichtfach
5 ECTS-P
4 SWS
jedes Semester


Verantwortlich

Prof. Dr. Erwin Holland-Moritz


Ziele

Die Studierenden sollen:

  • den in der Vorlesung dargestellten theoretischen Stoff selbständig auf entsprechende Problemstellungen anwenden können.
  • Vorgestellte Beweisverfahren sollen nachvollzogen werden können und auf ähnliche Fragestellungen angewandt werden.
  • Lösungen zu gestellten theoretischen Problemen sollen in Teamarbeit selbständig erarbeitet werden und in den Übungseinheiten vorgetragen werden.Zum Ende des Semesters muss jeder Studierende ein Referat ( 30 Min.) zu einem Thema halten, das auf dem dargebotenen Lehrstoff aufbaut, aber diesen nicht nur wiedergibt.


    • Lehrinhalte

    Diese Pflichtveranstaltung baut auf dem Grundlagenfach Theoretische Informatik des Bachelor-Studiengangs auf. Themen sind hier Berechenbarkeit, Entscheidbarkeit und Komplexität.

    Analog zu den regulären Sprachen lässt sich das akzeptierende Konzept der kontextsensitiven und rekursiv-aufzählbaren Sprachen (Typ-1 und Typ-0) , die Turingautomaten , zu Turingmaschinen erweitern. Von berechenbar spricht man, wenn ein Problem lösbar ist, d.h. eine Maschine konstruiert werden kann, die das Problem löst. Die Turing Berechenbarkeit wird als erste mathematische Formalisierung und Präzisierung des Berechenbarkeitsbegriffs eingeführt (Programmiersprache Turing). Anschließend werden andere Berechenbarkeitsbegriffe behandelt. Ihnen liegt nicht mehr ein intuitiver Berechenbarkeitsbegriff zugrunde, sondern Konzepte prozeduraler Programmiersprachen. Hierzu gehören loop-, while­und goto-Berechenbarkeit. Zusammenfassend wird die Churchsche These besprochen und als Beispiel für eine totale Funktion, die zwar zum Beispiel while-, aber nicht loop-berechenbar ist, das Verhalten der Ackermannfunktion diskutiert.

    Der Entscheidbarkeitsbegriff ist für Mengen und damit auch für Sprachen definiert. Auf Entscheidbarkeitsprobleme wurde bereits beispielhaft im theoretischen Grundkurs des Bachelor-Studiengangs hingewiesen. Diese Thematik soll hier vertieft werden. Man unterscheidet zwischen entscheidbaren, semientscheidbaren und unentscheidbaren Mengen. Hierzu werden Beispiele gegeben, insbesondere verschiedene nicht entscheidbare Mengen besprochen. Zum letzteren Komplex gehören unter anderem das Halteproblem, das "game of life", das Korrektheitsproblem, das Postsche Korrespondenzproblem.

    Schließlich wird als letzte Thematik wird das Komplexitätsproblem betrachtet. Komplexität bedeutet zum Beispiel, wie viel Rechenaufwand, d.h. Anzahl der Schritte, ist nötig, um ein berechenbares Problem zu lösen, oder wie viel Speicherplatz wird zur Lösung des Problems benötigt. Es werden Komplexitätsklassen eingeführt. Besonders erwähnt werden die P-und NP-Klassen. P bzw. NP ist hierbei die Klasse von Sprachen, die von deterministischen bzw. nicht deterministischen Turingautomaten in polynomineller Laufzeit akzeptiert wird. Der Begriff der NP-Vollständigkeit wird erläutert und als Beispiel unter anderem das Erfüllbarkeitsproblem der Aussagenlogik besprochen. Die NP-Vollständigkeit ist aber auch für das ungelöste P-NP-Problem von Bedeutung.


    Lehrmethoden

    Vorlesung (2 SWS) + Übung (1 SWS) + Seminar (1 SWS)


    Vorraussetzungen

    Theoretische Informatik als Grundlagenfach des Bachelor-Studiengangs


    Ort, Ressourcen


    Literatur

    G. Vossen , K.-U. Witt: Grundlagen der theoretischen Informatik

    A. Asteroth , C. Baier: Theoretische Informatik

    J. E. Hopcroft , J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie

    P. Sander et al.: Automaten, Sprachen und Berechenbarkeit


    raster