Entscheidbarkeit, Berechenbarkeit und Komplexität (EBK)

Verstehe die Grenzen des Berechenbaren: Du beschäftigst dich mit Berechenbarkeit, Entscheidbarkeit und Komplexitätstheorie und analysierst grundlegende Fragen der Informatik – von Turingmaschinen über das Halteproblem bis hin zu NP-Vollständigkeit und dem P-vs-NP-Problem. Dabei lernst du, die prinzipiellen Grenzen algorithmischer Lösbarkeit zu erkennen und einzuordnen.

Inhalte

• Die Berechenbarkeits- und Komplexitätstheorie zählen zu den zentralen Grundpfeilern der theoretischen Informatik. Im Mittelpunkt stehen Fragen wie: Was lässt sich überhaupt algorithmisch berechnen? Wie aufwendig ist eine Berechnung? Und gibt es Probleme, die sich prinzipiell nicht lösen lassen? Das bekannteste und bedeutendste bislang ungelöste Problem der theoretischen Informatik ist das P-versus-NP-Problem, das fragt, ob sich alle effizient überprüfbaren Probleme auch effizient lösen lassen. Auch dieses Problem wird Bestandteil der Vorlesung sein.Im Rahmen der Veranstaltung werden grundlegende Kenntnisse zu Berechenbarkeit, Entscheidbarkeit und Komplexität vermittelt. Dabei beschäftigen wir uns unter anderem mit:
• dem abstrakten Modell eines Rechners
• der Turing-Maschine- dem intuitiven Berechenbarkeitsbegriff und der Church-Turing-These
• den primitiv rekursiven und $\mu$-rekursiven Funktionen
• rekursiven und rekursiv aufzählbaren Sprachen
• dem Halteproblem den wichtigsten Komplexitätsklassen (u. a. P, NP)
• Ein besonderer Bezug besteht zur Künstlichen Intelligenz: Bereits die historischen Wurzeln der Berechenbarkeitstheorie – insbesondere die Arbeiten Alan Turings sind eng mit der Idee maschineller Intelligenz verknüpft. Auch inhaltlich berühren sich beide Gebiete: Die Sicherheit moderner KI-Systeme etwa beruht häufig auf der Annahme, dass bestimmte Probleme praktisch nicht effizient lösbar sind (P $\neq$ NP). Zudem wirft die Frage, ob sich das Verhalten komplexer KI-Systeme zuverlässig vorhersagen lässt, strukturelle Parallelen zum Halteproblem auf.- der Unentscheidbarkeit- diversen Komplexitätsklassen- Reduktionen- der NP-Vollständigkeit- einigen NP-vollständigen Problemen (SAT, 3SAT, Node-cover)- einigen NP-harten Problemen

Lernziele/Kompetenzen

Die Studierenden sind in der Lage,

• das Konzept der Turingmaschine zu erläutern und auf aktuelle Fragestellungen anzuwenden,
• nicht eingearbeiteten Fachkollegen den Begriff der Unentscheidbarkeit auch anhand von Beispielen zu erläutern,
• zentrale Konzepte und Methoden der Komplexitätstheorie zu benennen und anzuwenden,
• den Berechenbarkeitsbegriff zu erläutern und
• einschlägige, aktuelle Forschungsthemen einzuordnen.

Literatur

• M. Aigner, "Diskrete Mathematik", 6th corrected ed. Wiesbaden, Germany: Springer Vieweg, 2006.
• J. Hromkovič, "Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography" (Texts in Theoretical Computer Science. An EATCS Series). Berlin, Germany: Springer, 2004.
• O. Goldreich, "Computational Complexity: A Conceptual Perspective". Cambridge, U.K.: Cambridge Univ. Press, 2008.
• J. E. Hopcroft, R. Motwani, and J. D. Ullman, "Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit", 3rd ed. Munich, Germany: Pearson Studium, 2011.
• K. R. Reischuk, "Komplexitätstheorie – Band I: Grundlagen: Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus", 2nd rev. and enlarged ed. Wiesbaden, Germany: Vieweg+Teubner, 1999.
• I. Wegener, "Complexity Theory: Exploring the Limits of Efficient Algorithms", R. Pruim, Transl. Berlin, Germany: Springer, 2005.
• S. Arora and B. Barak, "Computational Complexity: A Modern Approach". Cambridge, U.K.: Cambridge Univ. Press, 2009.
• D. C. Kozen, "Theory of Computation" (Texts in Computer Science). London, U.K.: Springer, 2006.
• N. Cutland, "Computability: An Introduction to Recursive Function Theory". Cambridge, U.K.: Cambridge Univ. Press, 1980.
• R. G. Downey and M. R. Fellows, "Fundamentals of Parameterized Complexity" (Texts in Computer Science). London, U.K.: Springer, 2013.
• Z. Hou, "Fundamentals of Logic and Computation: With Practical Automated Reasoning and Verification" (Texts in Computer Science). Cham, Switzerland: Springer, 2021.
• A. Pettorossi, "Automata Theory and Formal Languages: Fundamental Notions, Theorems, and Techniques". Cham, Switzerland: Springer, 2022.
• H. Chen, "Computability and Complexity". Cambridge, MA, USA: MIT Press, 2023.
• K. R. Chowdhary, "Theory of Computation: Automata, Formal Languages, Computation and Complexity". Singapore: Springer, 2025.

Dozentinnen / Dozenten

• Prof. Dr. Lutz Strüngmann

Empfohlene Vorkenntnisse 

• Mathematik für die Informatik 1 (MA1)
• Mathematik für die Informatik 2 (MA2)
• Mathematik für die Informatik 3 (MA3)

Daten zum Modul

Semester	1/2
Unterrichtssprache	Deutsch und Englisch
Häufigkeit	Unregelmäßig
Kreditpunkte (CP)	5
Modulverantwortlich	Prof. Dr. Lutz Strüngmann
Dauer	1 Semester
Studienleistung	Keine
Prüfungsvorleistung	Pflichtübung (PU)
Prüfungsleistung	Klausur 90 Minuten (K90)

Semesterwochenstunden (SWS) 

Vorlesung	2 SWS
Übung	2 SWS
Summe	4 SWS

Arbeitsaufwand (Workload) 

Vorlesung	45 h
Selbststudium	70 h
Aufgaben	15 h
Prüfungsvorbereitung	20 h
Summe	150 h