Berechenbarkeit und Komplexität

Modul: Berechenbarkeit und Komplexität (6 Credits)
Name im Diploma Supplement	Computability and complexity
Verantwortlich	Prof. Dr. Barbara König
Voraussetzungen	Siehe Prüfungsordnung.
Workload	180 Stunden studentischer Workload gesamt, davon: Präsenzzeit: 45 Stunden Vorbereitung, Nachbereitung: 100 Stunden Prüfungsvorbereitung: 35 Stunden
Dauer	Das Modul erstreckt sich über 1 Semester.
Qualifikationsziele	Die Studierenden verfügen über die Kompetenz, Sachverhalte der theoretischen Informatik formal zu beschreiben und zu analysieren, insbesondere mit Bezug auf die Gebiete Berechenbarkeitstheorie und Komplexität beherrschen Berechnungsmodelle wie Turing-Maschinen, LOOP-, WHILE-, GOTO-Programme, primitiv rekursive und mu-rekursive Funktionen sind in der Lage, durch den Beweis der Äquivalenz dieser Berechnungsmodelle die Churchsche These nachzuvollziehen verstehen Begriffe wie Unentscheidbarkeit und Reduzierbarkeit und können diese in einem Informatikkontext anwenden kennen wichtige unentscheidbare Probleme (Halteproblem, Postsches Korrespondenzproblem, etc.) besitzen die Fähigkeit, die Unentscheidbarkeit einer Problemstellung formal zu beweisen kennen verschiedene Komplexitätsklassen sowie das P=NP-Problem und das Konzept der (NP-)Vollständigkeit können die Komplexität von Problemen mit den bekannten Komplexitätsformeln abschätzen und sind in der Lage, Reduktionen formal durchzuführen besitzen ein tieferes Verständnis für zentrale Konzepte der theoretischen Informatik sind dadurch in der Lage, informatische Probleme mit formalen Methoden der theoretischen Informatik zu behandeln und zu lösen
Praxisrelevanz	Dieses Modul vermittelt wesentliche Grundlagen, die für weite Bereich der praktischen Informatik relevant sind und ohne deren Kenntnis weder effektive noch effiziente Lösungen erstellt werden können.
Prüfungsmodalitäten	Zum Modul erfolgt eine modulbezogene Prüfung in der Gestalt einer Klausur (in der Regel: 90-120 Minuten).
Verwendung in Studiengängen	LA Info GyGe Master > Wahlpflichtbereich Informatik > 1.-3. FS, Wahlpflicht Mathe Bachelor > Software Engineering > 1.-6. FS, Wahlpflicht SE Bachelor > Pflichtbereich > Pflichtbereich IV: Grundbegriffe der Theoretischen Informatik > 3.-4. FS, Pflicht
Bestandteile	Vorlesung Berechenbarkeit und Komplexität (3 Credits) Übung Berechenbarkeit und Komplexität (3 Credits)
Modul: Berechenbarkeit und Komplexität (WIWI‑M0043)

Vorlesung: Berechenbarkeit und Komplexität (3 Credits)
Name im Diploma Supplement	Computability and complexity
Anbieter	Fachgebiet Theoretische Informatik
Lehrperson	Prof. Dr. Barbara König
Semesterwochenstunden	2	Sprache	deutsch
Turnus	Wintersemester	maximale Hörerschaft	###LABEL_NOLIMIT###
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
Vorlesung: Berechenbarkeit und Komplexität (WIWI‑C0006)

Übung: Berechenbarkeit und Komplexität (3 Credits)
Name im Diploma Supplement	Computability and complexity
Anbieter	Fachgebiet Theoretische Informatik
Lehrperson	Prof. Dr. Barbara König
Semesterwochenstunden	2	Sprache	deutsch
Turnus	Wintersemester	maximale Hörerschaft	###LABEL_NOLIMIT###
empfohlenes Vorwissen keines
Abstract Übungen zu theoretischer Informatik, insbesondere zu den Gebieten Berechenbarkeit und Komplexität
Lehrinhalte Es werden die Inhalte der Vorlesung durch Übungen vertieft.
Literaturangaben Siehe Literaturangaben der Vorlesung.
didaktisches Konzept Erarbeiten der Vorlesungsinhalte mit den Tutoren; Vorstellung der Lösung der Übungsaufgaben; Korrektur und Bewertung der von den Studierenden abgegebenen Lösungen
Übung: Berechenbarkeit und Komplexität (WIWI‑C0005)