| Einführung in die Theoretische Informatik [2022/23 WiSe] | ||
|---|---|---|
| Code ITH |
Name Einführung in die Theoretische Informatik |
|
| LP 8 |
Dauer ein Semester |
Angebotsturnus jedes Sommersemester |
| Format Vorlesung 4 SWS + Übung 2 SWS |
Arbeitsaufwand 240 h; davon 90 h Präsenzstudium 15 h Prüfungsvorbereitung 135 h Selbststudium und Bearbeitung der Übungsaufgaben (eventuell in Gruppen) |
Verwendbarkeit B.Sc. Angewandte Informatik B.Sc. Informatik Lehramt Informatik B.Sc. Mathematik |
| Sprache Deutsch |
Lehrende Felix Joos, Wolfgang Merkle |
Prüfungsschema 1+1 |
| Lernziele | Die Studierenden sind mit grundlegenden Aspekten des Berechenbarkeitsbegriffs vertraut, insbesondere mit dessen anschaulicher Bedeutung, der Formalisierungen durch Turingmaschinen und der Church-Turing-These. Sie wissen um die Grenzen der Berechenbarkeit, können die Unentscheidbarkeit des Halteproblems nachweisen und durch die Reduktionsmethode auf weitere Probleme übertragen. Sie sind vertraut mit universellen Maschinen und weiteren Konzepten und Herangehensweisen der Berechenbarkeitstheorie. Sie kennen wichtige Sätze wie das Rekursionstheorem und den Satz von Rice und können diese selbstständig anwenden. Die Studierenden sind vertraut mit regulären Sprachen, insbesondere deren Charakterisierung durch endliche Automaten und mit dazu verwandten Konzepten wie L-Äquivalenz und Pumping-Lemma. Neben den regulären Sprachen können sie kontextfreie, kontextsensitive und allgemeine Chomsky-Sprachen in die Chomsky-Hierarchie einordnen. Zudem können sie die Stufen der Chomsky-Hierarchie durch generative Grammatiken charakterisieren und haben einen Überblick über die dazugehörigen Automatenmodelle. Die Studierenden können Probleme hinsichtlich deren Zeit- und Platzkomplexität beschreiben und erhalten durch die Hierarchiesätze einen Einblick in die Auswirkungen unterschiedlicher Zeit- und Platzschranken. Zudem kennen sie die Bedeutung der Klassen P und NP, das P-NP-Problem, die NP-Vollständigkeit des Erfüllbarkeitsproblems und können diese durch die Reduktionsmethode auf weitere Probleme übertragen. |
|
| Lerninhalte | Die Vorlesung gibt eine Einführung in drei zentrale Gebiete der Theoretischen Informatik: in die Berechenbarkeitstheorie, die Theorie Formaler Sprachen und die Komplexitätstheorie. | |
| Teilnahme- voraus- setzungen |
empfohlen sind: Grundkenntnisse aus Mathematik (wie in einführenden Mathematikvorlesungen vermittelt) und Informatik | |
| Vergabe der LP und Modulendnote | Das Modul wird mit einer benoteten Klausur abgeschlossen. Die Modulendnote wird durch die Note der Klausur festgelegt. Für die Vergabe der LP gilt die Regelung aus dem Kapitel Prüfungsmodalitäten. | |
| Nützliche Literatur | Wird vom Lehrenden bekannt gegeben | |