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

Zur Online-Bewerbung

Bewerbungszeitraum:
1. Februar - 15. M?rz