Vorlesung

Berechenbarkeit und Komplexität

Name im Diploma Supplement

Computability and complexity

Anbieter

Fachgebiet Theoretische Informatik

Lehrperson

Prof. Dr. Barbara König

SWS

2

Sprache

deutsch

Turnus

Wintersemester

maximale Hörerschaft

unbeschränkt

Hörerschaft

• LA Info GyGe MasterWahlpflichtbereich Informatik 1.-3. FS, Wahlpflicht, Modul Berechenbarkeit und Komplexität
• Mathe BachelorSoftware Engineering 1.-6. FS, Wahlpflicht, Modul Berechenbarkeit und Komplexität
• SE BachelorPflichtbereichPflichtbereich IV: Grundbegriffe der Theoretischen Informatik 3.-4. FS, Pflicht, Modul Berechenbarkeit und Komplexität

empfohlenes Vorwissen

Kenntnisse der Modellierungsmethoden der Informatik werden nachdrücklich empfohlen.

Abstract

Die Vorlesung gibt eine Einführung in die theoretische Informatik, insbesondere in die Gebiete Berechenbarkeit und Komplexität.

Lehrinhalte

Die Berechenbarkeits- und Komplexitätstheorie ist eine wichtige Grundlage der Informatik. Hierbei geht es um Fragestellungen der Form: was kann überhaupt berechnet werden? Wie teuer ist diese Berechnung?

Mit dem P-NP-Problem erläutert dieses Gebiet auch das wichtigste bisher ungelöste Problem der theoretischen Informatik. Im Rahmen dieser Veranstaltung werden grundlegende Kenntnisse zu den Bereichen Berechenbarkeit und Komplexität vermittelt. Inhalte im Einzelnen:

• Berechenbarkeit (Turing-Maschinen, Intuitiver Berechenbarkeitsbegriff, Churchsche These, LOOP-, WHILE-, GOTO-Berechenbarkeit, Primitiv rekursive und mu-rekursive Funktionen, Ackermannfunktion, Halteproblem, Unentscheidbarkeit, Reduktionen, Postsches Korrespondenzproblem, Weitere unentscheidbare Probleme)
• Komplexität (Komplexitätsklassen, P-NP-Problem, NP-Vollständigkeit, Weitere NP-vollständige Probleme, Randomisierung, Primzahltests). 

Hinweis:

• Die Vorlesung wird wechselweise in Duisburg und Essen durchgeführt, jeweils mit Übertragung an den anderen Campus. Achten Sie auf die Modalitäten für die Essener Teilnehmer.

Literaturangaben

• U. Schöning: "Theoretische Informatik - kurzgefasst", Spektrum, Akademischer Verlag (4. Auflage), 2000
• Skript zur Vorlesung, siehe Homepage (http://www.informatik.uni-duisburg.de/AGThInf/)

didaktisches Konzept

Vorlesung mit Folien und Erklärung komplexer Inhalte mit stiftbasierter Eingabe auf dem TabletPC; Videoübertragung an den anderen Campus; Bereitstellung von Vorlesungsvideos