Gesamtliste
Überblick über die Lehrinhalte und Qualifikationsziele der Module und Veranstaltungen
Diese Seite zeigt alle Module, die sich aktuell im System befinden. Für jedes Modul werden Lehrinhalte und Lernziele ausgegeben. Bitte suchen Sie mit der Suchfunktion ihres Browsers (Strg + F) nach den Namen des Moduls bzw. der Veranstaltung im Modul zu der Sie Informationen benötigen und klicken Sie dann auf den Link zum Modul. Die darauffolgende Seite enthält alle Informationen zu den Inhalten einer Veranstaltungen die Sie für eine Anerkennung benötigen sollten. Sollte die Institution weitere Informationen benötigen, nutzen Sie bitte zusätzlichen die Seiten der einzelnen Lehrstühle und dort den Bereich „Studium“.
Module (6 Credits)
Berechenbarkeit und Komplexität
- Name in diploma supplement
- Computability and complexity
- Responsible
- Admission criteria
- See exam regulations.
- Workload
- 180 hours of student workload, in detail:
- Attendance: 45 hours
- Preparation, follow up: 100 hours
- Exam preparation: 35 hours
- Duration
- The module takes 1 semester(s).
- Qualification Targets
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
- Relevance
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.
- Module Exam
The module-related examination is performed by a written exam (usually 90-120 minutes).
- Usage in different degree programs
- Elements
Lecture (3 Credits)
Berechenbarkeit und Komplexität
- Name in diploma supplement
- Computability and complexity
- Organisational Unit
- Lecturers
- SPW
- 2
- Language
- German
- Cycle
- winter semester
- Participants at most
- no 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
- 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
Exercise (3 Credits)
Berechenbarkeit und Komplexität
- Name in diploma supplement
- Computability and complexity
- Organisational Unit
- Lecturers
- SPW
- 2
- Language
- German
- Cycle
- winter semester
- Participants at most
- no limit
- Preliminary knowledge
keines
- Abstract
Übungen zu theoretischer Informatik, insbesondere zu den Gebieten Berechenbarkeit und Komplexität
- Contents
Es werden die Inhalte der Vorlesung durch Übungen vertieft.
- Literature
Siehe Literaturangaben der Vorlesung.
- Teaching concept
Erarbeiten der Vorlesungsinhalte mit den Tutoren; Vorstellung der Lösung der Übungsaufgaben; Korrektur und Bewertung der von den Studierenden abgegebenen Lösungen
- Participants
Aus Gründen der Performance und Übersichtlichkeit wird an dieser Stelle auf die Titel und vollständigen Namen der Dozenten verzichtet und es werden nur die Nachnamen ausgegeben. Die unterschiedlichen Titel der zugehörigen Dozenten sind den Bereitstellern und Nutzern dieser Listen bekannt und bewusst.