Berechenbarkeit und Komplexität

Die Theoretische Informatik beschäftigt sich auf systematische Weise und unter Verwendung mathematischer Mittel mit zentralen Fragen der Informatik. Sie besteht aus zahlreichen Teildisziplinen, von denen in dieser Vorlesung hauptsächlich die Theorie der Berechenbarkeit und die Komplexitätstheorie behandelt werden. In der Theorie der Berechenbarkeit geht es um die Definition abstrakter Modelle von Berechnung und um die fundamentale Frage, welche Probleme prinzipiell berechenbar sind und welche nicht. Eine zentrale Rolle spielen dabei Turingmaschinen als elementares Berechnungsmodell, das aber dennoch äquivalent zu komplexeren und praxisnäheren Modellen wie modernen Programmiersprachen ist. Die Komplexitätstheorie betrachtet zusätzlich die zur Berechnung verwendeten Ressourcen wie Laufzeit und Speicherplatz. Eine zentrale Frage ist dann, welche Probleme mit vertretbarem Aufwand berechenbar sind, wobei "vertretbarer Aufwand" meist mit "in polynomieller Zeit" gleichgesetzt wird. Zusätzlich zu den erwähnten Themen werden wir auch einige in Theoretische Informatik 1 offen gebliebene Fragen aus dem Gebiet der formalen Sprachen klären und beispielsweise ein Automatenmodell für kontextsensitive Sprachen und Typ-0-Sprachen angeben. Im letzteren Fall sind das Turingmaschinen, was eine direkte Verbindung zwischen formalen Sprachen und der Theorie der Berechenbarkeit liefert.

Lernergebnisse

• Fundamentale Konzepte und Ergebnisse aus den Gebieten Berechenbarkeit, Komplexität und Prädikatenlogik kennen und
  verinnerlicht haben.

• Verschiedene Berechnungsmodelle kennen und die Grenzen der Berechenbarkeit einschätzen können.

• Die Komplexität von typischen Informatik-Problemen einschätzen können und sensibilisiert sein für die Existenz schwieriger
  Probleme.

• Induktionsbeweise über die Struktur von Zahlen, Wörtern, Berechnungssequenzen und/oder ähnliche Strukturen nachvollziehen und
  selbständig durchführen können.

• Selbständig Algorithmen entwerfen und formal spezifizieren können.

• In Gruppen Probleme analysieren und gemeinsam Lösungsstrategien entwickeln und präsentieren können.

Inhalte

1) Berechenbarkeit

• Turingmaschinen

• Linear beschränkte Automaten

• Grammatiken der Typen 0 und 1, Abschlusseigenschaften

• LOOP-Programme und WHILE-Programme

• Primitiv rekursive Funktionen und -rekursive Funktionen

• Unentscheidbarkeit

• Unentscheidbare Probleme für Turingmaschinen

• Satz von Rice

• Postsches Korrespondenzproblem

• Äquivalenzproblem kontextfreier Grammatiken

• Semi-Entscheidbarkeit und Rekursive Aufzahlbarkeit

• Universelle Turingmaschinen

• Reduktionen

2) Komplexität

• Zeit- und Platzbeschränkte Turingsmaschinen

• Komplexitätsklassen P, NP, PSpace, ExpTime

• P vs NP-Problem

• NP-Vollständigkeit

• NP-vollständige Probleme aus verschiedenen Gebieten

• Komplemente und coNP

• Approximation NP-harter Probleme

• Satz von Savitch

Modulverantwortung

Prof. Dr. C. Lutz

Lehrender

Prof. Dr. Sebastian Siebertz
Fachbereich Mathematik / Informatik

Veranstaltungsdetails

Veranstaltungsform:
Vorlesung + Übung (Terminauswahl möglich)

Veranstaltungszeiten:
im Sommersemester - Präsenzunterricht
wöchentlich Mo 12:00 - 14:00 Übung
wöchentlich Mo 14:00 - 16:00  Vorlesung
wöchentlich Di 12:00 - 14:00  Übung
wöchentlich Di 14:00 - 16:00  Übung
wöchentlich Di 16:00 - 18:00  Übung
wöchentlich Mi 08:00 - 10:00  Fragestunde
wöchentlich Mi 16:00 - 18:00  Übung
wöchentlich Do 08:00 - 10:00  Übung
wöchentlich Do 16:00 - 18:00  Übung

Prüfungen & Abschluss

Prüfung:

• i. d. R. Bearbeitung von Übungsaufgaben und Fachgespräch

Abschluss:

• Modulzertifikat

Umfang

Dauer: 1 Semester

Arbeitsaufwand:
56 Std. Präsenzveranstaltungen
+ 124 Std. angeleitetes Selbststudium
(entspricht 6 CP)

Teilnahmeentgelt

450 Euro (= 75 Euro pro CP)

Mitglieder des Alumni-Vereins der Universität Bremen erhalten 5 % Rabatt.

Bewerbung

Eine Bewerbung ist zum jetzigen Zeitpunkt leider nicht möglich.

Bewerbungszeitraum:
1. Februar - 15. März