Lecture

Berechenbarkeit und Komplexität

Name in diploma supplementTheoretical Computer Science
Organisational Unit Fachgebiet Theoretische Informatik (http://www.ti.inf.uni-due.de/)
LecturersProf. Dr. Barbara König
SPW2LanguageGerman
Cyclewinter semesterParticipants at mostno limit

Preliminary knowledge

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.

Contents

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.

Literature

Teaching concept

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

Participants

  • AI-SE Bachelor 2017>Kernstudium >Pflichtbereich II: Informatik >Modul "Berechenbarkeit und Komplexität"3rd-4th Semester, Compulsory
  • LA Info GyGe Master 2014>Wahlpflichtbereich Informatik >Modul "Berechenbarkeit und Komplexität"1st-3rd Semester, Elective
WIWI‑C0006 - Lecture: Berechenbarkeit und Komplexität