inf401 - Grundlagen der Theoretischen Informatik (Vollständige Modulbeschreibung)
Modulbezeichnung | Grundlagen der Theoretischen Informatik |
Modulkürzel | inf401 |
Kreditpunkte | 6.0 KP |
Workload | 180 h |
Einrichtungsverzeichnis | Department für Informatik |
Verwendbarkeit des Moduls |
|
Zuständige Personen |
|
Teilnahmevoraussetzungen | Keine Teilnehmervoraussetzungen |
Kompetenzziele | Einführung in die Theorie der Automaten, formalen Sprachen, Berechenbarkeit und Komplexität Fachkompetenzen Die Studierenden:
Die Studierenden:
Die Studierenden:
Die Studierenden:
|
Modulinhalte | Im ersten Teil der Vorlesung werden verschiedene Sprachklassen (reguläre und kontextfreie Sprachen) eingeführt. Für jede Sprachklasse werden die dazugehörigen Automatenmodelle (endliche Automaten und Kellerautomaten) vorgestellt, die zum Akzeptieren der jeweiligen Sprachen eingesetzt werden können. Diverse Eigenschaften der eingeführten Sprachen und Automaten werden bewiesen. 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, dass es Probleme gibt, die nicht algorithmisch entscheidbar sind. Dazu gehören auch viele Probleme von praktischem Interesse. Im dritten Teil der Vorlesung geht es um die Komplexität von Algorithmen, d.h. wie viel Zeit und Speicherplatz zum Lösen einer Aufgabe benötigt werden. Insbesondere werden Probleme betrachtet, die deterministisch oder nichtdeterministisch in polynomieller Zeit lösbar sind. Diese Problemklassen sind unter den Namen P und NP bekannt. |
Literaturempfehlungen | Essenziell:
|
Links | |
Unterrichtssprache | Deutsch |
Dauer in Semestern | 1 Semester |
Angebotsrhythmus Modul | jährlich |
Aufnahmekapazität Modul | unbegrenzt |
Lehr-/Lernform | V+Ü |
Vorkenntnisse | keine |
Lehrveranstaltungsform | Kommentar | SWS | Angebotsrhythmus | Workload Präsenz |
---|---|---|---|---|
Vorlesung | 3 | WiSe | 42 | |
Übung | 1 | WiSe | 14 | |
Präsenzzeit Modul insgesamt | 56 h |
Prüfung | Prüfungszeiten | Prüfungsform |
---|---|---|
Gesamtmodul | Am Ende des Semesters |
Klausur oder mündl. Prüfung |