Lehre

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.

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.

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 ...]

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 ...]

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 ...]

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 ...]

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 ...]

• Theoretische Informatik
• Seminar
• Proseminar