Computability and Complexity - Interactive curriculae of TU Ilmenau

The interactive curriculae provide information on the degree programmes offered by the TU Ilmenau.

Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).

You can find all details on planned lectures and classes in the course catalogue.

Please note that this page is no longer updated. All modules and study plans from PO version 2021 onwards (Bachelor and Master study programs) are now available on the Campus Portal.

module properties Computability and Complexity in degree program Bachelor Informatik 2021
module number	200050
examination number	2200695
department	Department of Computer Science and Automation
ID of group	2241 (Automata and Logics)
module leader	Prof. Dr. Dietrich Kuske
term	summer term only
language	Deutsch
credit points	5
on-campus program (h)	34
self-study (h)	116
obligation	obligatory module
exam	oral examination performance, 25 minutes
details of the certificate
link to Moodle course	https://moodle.tu-ilmenau.de/course/view.php?id=2844
teacher	Prof. Kuske
signup details for alternative examinations
maximum number of participants
previous knowledge and experience	Sicherheit im Umgang mit mathematischen Begriffen (vgl. z. B. Modul "Grundlagen und diskrete Strukturen") Grundkenntnisse zu Algorithmen (vgl. z. B. Modul "Algorithmen und Programmierung für IN und II" oder "Algorithmen und Datenstrukturen 1") Vertrautheit mit Automatenmodellen und Grammatiken (vgl. z. B. Modul "Automaten und Formale Sprachen")
learning outcome	Fachkompetenz: Die Studierenden kennen die grundlegenden Begriffe und Sachverhalte der Berechbarkeitstheorie und der NP-Vollständigkeitstheorie sowie weitere Grundkonzepte der Komplexitätstheorie sowie die zentrale Bedeutung des P-NP-Problems. Sie kennen wesentliche Vertreter der wichtigen Komplexitätsklassen. Diese Kenntnisse haben sie vorangig in der Vorlesung und im Selbstudium erworben. Methodenkompetenz: Die Studierenden können Simulationen beschreiben, Reduktionen (Berechbarkeitstheorie und NP-Vollständigkeitsbeweise) durchführen und analysieren, sie können Probleme in Komplexitätsklassen einsortieren. Diese Fähigkeiten haben sie vorangig in der Übung und im Selbstudium erworben. Sozialkompetenz: Die Studierenden können kritische Fragen zum behandelten Stoff, Probleme bei der Erarbeitung des Wissens bzw. bei der Lösung der Aufgaben klar formulieren und in Diskussionen mit Kommilitonen und Lehrenden vertreten.
content	Berechnungsmodelle (Turingmaschine, GOTO-Programme) Simulation zwischen Modellen Formalisierung des Berechenbarkeitsbegriffs, Church-Turing-These Halteproblem Nicht berechenbare Funktionen, nicht entscheidbare Probleme Reduktion Unentscheidbarkeit semantischer Fragen (Satz von Rice) Postsches Korrespondenzproblem, Unentscheidbarkeit bei Grammatiken und logischen Systemen Die Klassen P und NP NP-Vollständigkeit Satz von Cook/Levin P-NP-Problem Reduktionen, NP-Vollständigkeitsbeweise Grundlegende NP-vollständige Probleme
media of instruction and technical requirements for education and examination in case of online participation	Folien und Übungsblätter
literature / references	Schöning, "Theoretische Informatik kurzgefasst" Asteroth, Baier, "Theoretische Informatik" Wegener, "Theoretische Informatik" Hopcroft, Motwani, Ullman, "Einführung in die Automatentheorie, Formale Sprachen und Komplexität
evaluation of teaching