• Prof. Dr. Bettina Just

• Prof. Dr. Bettina Just
• Prof. Dr. Hans-Rudolf Metz

Keine

Die Vorlesung behandelt: Berechenbarkeit, Entscheidbarkeit, rekursive Aufzählbarkeit; Halteprobleme; Gödels Unvollständigkeitssatz; Zeitkomplexitätsklassen; P-NP-Problem; Cooks Satz.

• Turing-Maschinen, -Berechenbarkeit, -Aufzählbarkeit, -Entscheidbarkeit
• Halteproblem
• Reduzierbarkeit
• Komplexitätsklassen, Zeitkomplexität, Speicherkomplexität
• P-NP-Problem, NP-Vollständigkeit
• Erfüllbarkeits-Problem der Aussagenlogik (SAT)
• Cookscher Satz
• Approximierbarkeit NP-vollständiger Berechnungsprobleme
• Optional: Fortgeschrittenere Themen wie Zufälligkeit und Pseudozufälligkeit, Anwendungen in der Kryptographie, PCP-Theorem, Beschreibungskomplexität

Fachkompetenzen

• Die Studierenden können grundsätzliche Möglichkeiten und Grenzen der Algorithmisierbarkeit bewerten und erläutern.
• Sie können Komplexitätsklassen von Berechnungsproblemen, insbesondere P und NP erläutern.

Methodenkompetenzen (fachlich & überfachlich)

• Die Studierenden können die Methodik der Reduktion anwenden, um unterschiedliche Berechnungsprobleme ineinander zu transformieren.

Sozialkompetenzen

• Die Studierenden sind in fachübergreifenden Diskussionen in der Lage, die grundsätzlichen Möglichkeiten der Informatik überzeugend darzulegen.

Selbstkompetenzen

• Die Studierenden haben Geduld und Durchhaltevermögen bei der Durchdringung komplizierter Beweise geübt.

• 6 CrP
• Arbeitsaufwand 180 Std.
• Präsenzzeit 60 Std.
• Selbststudium 120 Std.

• 4 SWS
• Seminaristischer Unterricht 4 SWS

• Informatik (M.Sc. 2022)

Nein

Bonuspunkte werden gemäß § 9 (4) der Allgemeinen Bestimmungen vergeben. Art und Weise der Zusatzleistungen wird den Studierenden zu Veranstaltungsbeginn rechtzeitig und in geeigneter Art und Weise mitgeteilt.

Prüfungsvorleistung: Hausübungen (Anzahl der Hausübungen wird den Studierenden rechtzeitig und in geeigneter Weise bekannt gegeben.)

Prüfungsleistung: Klausur oder mündliche Prüfung (Art des Leistungsnachweises wird den Studierenden rechtzeitig und in geeigneter Weise bekannt gegeben.)

• Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company.
• Arora, S.; Barak, B.: Computational Complexity – A Modern Approach. Cambridge University Press.
• Vazirani, V.: Approximation Algorithms. Springer.
• Wegener, I.: Komplexitätstheorie. Springer.