Entwicklung korrekter Systeme

Modul "Theoretischen Informatik II" - GTI

Auf dieser Seite

 

weiter zum Seitenanfang

1 Inhalte

Nach Vermittlung diverser (mathematischer) Grundlagen wird im ersten Teil der Vorlesung untersucht, welche Funktionen algorithmisch berechenbar bzw. welche Probleme algorithmisch entscheidbar sind. Dazu wird der Begriff des Algorithmus formalisiert. Turingmaschinen und Grammatiken stellen sich als äquivalente Ansätze heraus. Es wird gezeigt, daß es Probleme gibt, die nicht algorithmisch entscheidbar sind. Dazu gehören leider auch viele Probleme von praktischem Interesse.

Zur Beschreibung der Syntax von Programmiersprachen sind reguläre und kontextfreie Sprachen am wichtigsten. Im zweiten Teil der Vorlesung wird gezeigt, daß solche Sprachen von einfacheren Maschinen als Turingmaschinen erkannt werden können, nämlich durch endliche Automaten und Kellerautomaten. Ferner werden grundlegende Eigenschaften dieser Sprachen und Automaten hergeleitet.

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

 

weiter zum Seitenanfang zurück

2 Übungsblätter

Sie haben hier die Möglichkeit, die aktuellen Übungsblätter zu dieser Lehrveranstaltung im Postscript-, PDF- oder DVI-Format abzurufen. Wir bitten Sie jedoch im Interesse aller, die Übungsblätter nicht gedankenlos auszudrucken, insbesondere nicht auf den Laserdruckern der ARBI. Fotokopien sind unter Berücksichtigung aller Kosten in der Regel günstiger als Laserdrucke!

Dieses Angebot richtet sich hauptsächlich an diejenigen, die auf anderem Wege kein Exemplar der Übungsblätter erhalten konnten.

zum Seitenanfang zurück