Entwicklung korrekter Systeme
Modul "Theoretische Informatik II" (3VL,1Ü)
1 Organisatorisches
| Vorlesung | E.-R. Olderog | |
| Dienstag 10-12 | A07 0-030 (HS G) | |
| Donnerstag 10-12 | A01 0-006 | |
| Übungen | A. Schäfer | |
| Mittwoch 8-9 | A04 2-221 | |
| Mittwoch 9-10 | A04 2-221 | |
| Freitag 10-11 | A04 4-414 | |
| Freitag 11-12 | A04 4-414 | |
2 Anmeldung zu den Übungen
Hier können Sie sich zu einer Übungsgruppe anmelden. Bitte geben Sie in das Formular die E-Mail-Adressen aller Teilnehmer an. Es wird dann ein Link per E-Mail zugesendet, über den Sie dann die Namen der Teilnehmer und die gewünschten Termine angeben können. Die E-Mail-Adresse wird auch verwendet, um die endgültige Zuteilung bekanntzugeben, sobald diese feststeht.
3 Ziele
Einführung in Berechenbarkeits-, Automaten-, Komplexitätstheorie
4 Inhalt
Im ersten Teil der Vorlesung werden verschiedene Sprachklassen (z.B. reguläre und kontextfreie Sprachen) eingeführt, die u.a. deswegen wichtig sind, weil sie zur Beschreibung der Syntax von Programmiersprachen verwendet werden. Parallel dazu werden je Sprachklasse dazugehörige Automatenmodelle (z.B. endliche Automaten, Kellerautomaten, Turingmaschinen) vorgestellt, die als abstrakte Algorithmenbeschreibung, wie die jeweiligen Sprachen akzeptiert werden, aufgefaßt werden können. Zur Klassifikation dieser Sprachen dienen Grammatiken.
Im zweiten Teil der Vorlesung wird 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.
Im dritten Teil der Vorlesung geht es um die Komplexität von Algorithmen, d.h. wieviel Zeit und Speicherplatz 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.