Vorlesung

Berechenbarkeit und Komplexität

Name im Diploma SupplementTheoretical Computer Science
Anbieter Fachgebiet Theoretische Informatik (http://www.ti.inf.uni-due.de/)
LehrpersonProf. Dr. Barbara König
SWS2Sprachedeutsch
TurnusWintersemestermaximale Hörerschaftunbeschränkt

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

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

Hörerschaft

  • AI-SE Bachelor 2017>Kernstudium >Pflichtbereich II: Informatik >Modul "Berechenbarkeit und Komplexität"3.-4. Fachsemester, Pflicht
  • LA Info GyGe Master 2014>Wahlpflichtbereich Informatik >Modul "Berechenbarkeit und Komplexität"1.-3. Fachsemester, Wahlpflicht
WIWI‑C0006 - Vorlesung: Berechenbarkeit und Komplexität