[ITH] - [de] - [Einführung in die Theoretische Informatik]


Einführung in die Theoretische Informatik [2022 Sommer]
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 und den Formalisierungen durch Turingmaschinen, Registermaschinen und rekursive Funktionen,
kennen den Beweis der Äquivalenz der verschiedenen Formalisierungen des Berechenbarkeitsbegriffs und damit ein wichtiges Argument für die Gültigkeit der Church-Turing-These,
wissen um die Grenzen der Berechenbarkeit, können die Unentscheidbarkeit des Halteproblems nachweisen und durch die Reduktionsmethode auf weitere Probleme übertragen,
werden durch den Nachweis der Existenz universeller Maschinen und vollständiger aufzählbarer Probleme beispielhaft an Methoden und Fragestellungen der Berechenbarkeitstheorie herangeführt,
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,
kennen die Grenzen der tatsächlichen Berechenbarkeit, die Klassen P und NP und das P-NP-Problem, können die NP-Vollständigkeit des Erfüllbarkeitsproblem nachweisen und durch die Reduktionsmethode auf weitere Probleme übertragen und diese damit als vermutlich nicht effizient entscheidbar charakterisieren,
kennen grundlegende Begriffe der Theorie der Formalen Sprachen und können die in der Informatik betrachteten Sprachen gemäß den Stufen der Chomsky-Hierarchie als reguläre, kontextfreie, kontextsensitive und allgemeine Chomsky-Sprachen charakterisieren und die verschiedenen Stufen jeweils durch spezielle Typen von generativen Grammatiken und durch Automatenmodelle beschreiben.
Lerninhalte Die Vorlesung gibt eine Einführung in drei zentrale Gebiete der Theoretischen Informatik: in die Berechenbarkeitstheorie, in die Komplexitätstheorie sowie in die Theorie Formaler Sprachen und die zugehörige Automatentheorie.
Teilnahme-
voraus-
setzungen
empfohlen sind: Grundkenntnisse aus Mathematik 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