Berechenbarkeit und Komplexität

Modul - Informatik: Theoretische Informatik 2

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

In Kürze

Inhalt:
Turingmaschinen und die Theorie der Berechenbarkeit.

Niveau: Bachelor-Modul 

Veranstaltungsform:
Vorlesung + Übung

Semester: Sommersemester

Umfang: 6 CP

Modulverantwortung

Prof. Dr. C. Lutz

 

Lehrender

Prof. Dr. Sebastian Siebertz
Fachbereich Mathematik / Informatik

 

Zielgruppe

  • Interessierte an den Arbeitsfeldern Informationstechnik und Medien

Zugangsvoraussetzungen

  • Hochschulzugangsberechtigung

  • eine mindestens einjährige Berufspraxis

  • Sie sollten das Modul " Theoretische Informatik 1: Endliche Automaten und formale Sprachen " erfolgreich absolviert haben oder über vergleichbare Kenntnisse verfügen.

Veranstaltungsdetails

Veranstaltungsform:
Vorlesung + Übung

Veranstaltungszeiten:
im Sommersemester - Termine folgen

Erfahrungen aus vergangenen Semestern:

wöchentlich Di 10:00 - 12:00 - Übung Online
wöchentlich Mi 08:00 - 10:00 - Übung Online

Die Vorlesungen finden online asynchron statt.

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

Zugehörige Zertifikate:

Das Modul ist Bestandteil folgender Zertifikatsangebote:

Information & Beratung:

Sie interessieren sich für unser Angebot im Bereich "Informatik, Digitale Medien, Digitalisierung"? Wir beraten Sie gern:

Jörg Kastens

Telefon: 0421 - 218 61 617
eMail: jkastensprotect me ?!uni-bremenprotect me ?!.de