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

Participants

• LA-Info-GyGe-Ma-2014 > Wahlpflichtbereich Informatik > (1st-3rd Semester, Elective) Modul "Berechenbarkeit und Komplexität"
• Mathe-Ba-2021 > Software Engineering > (1st-6th Semester, Elective) Modul "Berechenbarkeit und Komplexität"
• SE-Ba-2023 > Pflichtbereich > Pflichtbereich IV: Grundbegriffe der Theoretischen Informatik > (3rd-4th Semester, Compulsory) Modul "Berechenbarkeit und Komplexität"