Lecture

Berechenbarkeit und Komplexität

Name in diploma supplement

Computability and complexity

Organisational Unit

Fachgebiet Theoretische Informatik

Lecturers

Prof. Dr. Barbara König

SPW

2

Language

German

Cycle

winter semester

Participants at most

no limit

Participants

• LA Info GyGe MasterWahlpflichtbereich Informatik 1.-3. Sem, Elective, Module Berechenbarkeit und Komplexität
• Mathe BachelorSoftware Engineering 1.-6. Sem, Elective, Module Berechenbarkeit und Komplexität
• SE BachelorPflichtbereichPflichtbereich IV: Grundbegriffe der Theoretischen Informatik 3.-4. Sem, Compulsory, Module Berechenbarkeit und Komplexität

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

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

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