Lehre

Übersicht über alle Veranstaltungen

Theoretische Informatik

Die theoretische Informatik befasst sich mit den mathematischen Grundlagen der Informatik. Die zentralen Themen der Vorlesung sind formale Sprachen, Berechenbarkeit und Komplexitätstheorie.

Formale Sprachen sind das Thema der Vorlesung. Sie dienen der mathematisch präzisen Formulierung der auftretenden Probleme und Fragestellungen. Im Themengebiet formale Sprachen wird untersucht, wie sich formale Sprachen beschreiben und auch erkennen lassen. Dazu werden Grammatiken eingeführt und verschiedene Automatenmodelle zum Erkennen von formalen Sprachen eingeführt. Ein Beispiel für formale Sprachen sind Programmiersprachen. Es wird gezeigt, wie sich einerseits gültige Programme beschreiben lassen und auch andererseits, wie entschieden werden kann, ob ein Quelltext ein gültiges Programm ist.

Im Gebiet der Berechenbarkeit wird der Begriff des Algorithmus mathematisch präzise definiert. Es werden verschiedene Möglichkeiten aufgezeigt, allgemeine Berechnungsmodelle zu definieren. Des weiteren wird untersucht, inwiefern Problemstellungen algorithmisch lösbar sind.

In der Komplexitätstheorie wird untersucht, wie effizient oder schnell sich Probleme durch Algorithmen lösen lassen. es wird der begriff der Laufzeit eines Algorithmus definiert und Probleme auf ihre Schwierigkeit hin untersucht.

Petrinetze

Mit der zunehmenden Tendenz zu parallelen Berechnungen gewinnt auch die Frage nach der formalen Beschreibung und Analyse des Verhaltens von nichtsequentiellen Systemen an Bedeutung. Petrinetze bieten hierbei eine gute graphischen Anschaulichkeit: Die Stellen (passive Komponenten) werden als Kreise, die Transitionen (aktive Komponenten) als Rechtecke und die Flussrelation als Pfeile zwischen diesen dargestellt. In der Vorlesung werden die Platz-Transitionssysteme von C.A. Petri und ihre äquivalente Beschreibung als Verktoradditionssysteme und das automatentheoretische Pendant vorgestellt. Entscheidungsfragen wie Erreichbarkeit und Unbeschränktheit werden untersucht.

Team-Projekt

In diesem Programmierprojekt soll nun eine Software zur Verarbeitung und Visualisierung formaler Sprachen erstellt werden, wobei der Fokus auf den regulären Sprachen liegen soll.

Die Verarbeitung betrifft das Eingeben und Speichern von Sprachbeschreibungen (z.B. als Automat), das Uberführen von einer Beschreibung in eine andere (z.B. Automat hin zu regulärem Ausdruck), sowie das Anwenden elementarer Operationen, wie das Schneiden zweier Sprachen. [read more ...]

Spezielle Kapitel

Ein Überblick über weite Teile der Theoretischen Informatik durch Behandlung der Zusammenhänge zwischen den Formalen Sprachen, Berechenbarkeit und Komplexitätstheorie.

 

Literatur

- K.-J. Lange: Complexity and Structure in Formal Language Theory. Fundamenta Informaticae, 25(3) 327-352, 1996. Structures '93, 4070 (1993), 224-238.

Berechenbarkeit

Aufbauend auf den in der Vorlesung "Theoretische Informatik" gelegten Grundlagen werden Eigenschaften des Berechenbarkeitsbegriffes behandelt. Die behandelten Inhalte sind:

  • Die Sätze von Rice
  • Der Rekursionssatz
  • Der Unvollständigkeitssatz von Goedel
  • Die arithmetische Hierarchie
  • Berechenbarkeit und formale Sprachen: der Satz von Greibach

 

Literatur

H. Rogers: Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967.

J. Hopcroft, J. Ullmann: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1975.

Datenkompression

Fast jeder, der einen Computer verwendet, benutzt bewusst oder unbewusst Komprimierungsverfahren: Bewusst etwa zur Archivierung von Dateien um deren Speicherbedarf zu senken, unbewusst durch Verwendung von Standarddateiformaten, die vordefinierterweise Datenkompression vorsehen. Diese Veranstaltung bietet eine Einführung in die Grundlagen der Datenkompression und der häufig verwendeten Algorithmen. [read more ...]

Formale Sprachen

Ein Grundelement der Theorie Formaler Sprachen ist die endliche Beschreibung potentiell unendlicher Mengen von Wörtern, sogenannten formalen Sprachen. Diese treten als formale Beschreibung von Problemen, Funktionen oder sonstiger Objekte auf. [read more ...]

Algorithmische Geometrie

Obwohl einfache Schnittprobleme, z.B. zwischen Geraden in der Ebene, vom mathematischen Standpunkt aus nicht interessant sind, treten jedoch beim Schnitt von tausenden von Geraden Effizienzprobleme auf, zu deren Behandlung spezielle Algorithmen erforderlich sind. [read more ...]

Komplexitätstheorie

Die Veranstaltung gibt einen Einblick in die klassische Komplexitätstheorie. Die aus der Informatik 3 bekannten Begriffe des Ressourcenverbrauchs und der Reduktion werden nochmal motiviert, wiederholt und vertieft. [read more ...]

Model Checking

This course deals about a verification technique called model checking (MC). In MC, one is interested in gaining absolute certainty in properties holding for some systems. Systems can be hard or software and have to be modeled in order to treat them. Properties which are tested for are formulated in temporal logic.

A MC algorithm tests if a model satisfies some temporal logic formular. These algorethims are the main topic of this course.

Nach oben