Berechenbarkeit und Komplexität (WS 2026/27)

Vorlesungsablauf

Die Veranstaltung wird an beiden Standorten in Präsenz stattfinden (Vorlesung + Übungsgruppen). Bitte melden Sie sich im Moodle-Kurs an (der Schlüssel wird in der ersten Vorlesung bekanntgegeben), dort werden auch alle Materialien bereitgestellt.

Dozentin
Prof. Dr. Barbara König

Übungsleitung
Florian Wittbold
Lara Wallentin

Links
Termine
Arbeitsmaterial
Hinweise

Inhalt und Lernziele

Die Berechenbarkeits- und Komplexitätstheorie ist eine wichtige Grundlage der Informatik. Hierbei geht es um Fragestellungen der Form: was kann überhaupt berechnet werden? Wie aufwendig ist diese Berechnung? Mit dem P-NP-Problem enthält 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. Im Einzelnen handelt es sich dabei um:

Berechenbarkeit:

  • Turing-Maschinen
  • Intuitiver Berechenbarkeitsbegriff, Churchsche These
  • LOOP-/WHILE-/GOTO-Berechenbarkeit, Primitiv rekursive und mu-rekursive Funktionen
  • Halteproblem, Unentscheidbarkeit, Reduktionen, Unentscheidbare Probleme

Komplexitätstheorie:

  • Komplexitätsklassen, P-NP-Problem
  • NP-Vollständigkeit, NP-vollständige Probleme
  • Polynomielle Reduktion

Die Vorlesung wird sich inhaltlich stark an der Vorlesung "Berechenbarkeit und Komplexität" aus dem WS25/26 orientieren. Die Arbeitsunterlagen zur dieser Vorlesung finden Sie hier.

Termine

Vorlesung

In Duisburg: Montags, 16:15 - 17:45 Uhr, im Raum LX 1203

In Essen: Donnerstags, 14:15 - 15:45 Uhr, im Raum S07 S00 D07

Tutorium

Details werden noch festgelegt und dann in Moodle bekanntgegeben

Übungen

Beginn ab der zweiten Vorlesungswoche (erste Übungen am 21. Oktober)

  • Campus Duisburg:
    • Mittwochs 8:30-10:00 ("8-10"), LC 137
    • Donnerstags 12:15-13:45 ("12-14"), LC 137
    • Donnerstags 16:15-17:45 ("16-18"), LC 137
  • Campus Essen:
    • Mittwochs 10:15-11:45 ("10-12"), SE 005
    • Donnerstags 10:15-11:45 ("10-12"), SE 111
    • Donnerstags 16:15-17:45 ("16-18"), SE 005
Übungsablauf und Bonuspunkte

Prüfung/Klausur

Termin wird noch bekanntgegeben

Hinweise zu den Prüfungsformen

Arbeitsmaterial

Links

  • Moodle-Kurs (Folien, Übungsblätter, Diskussionsforen, Videos usw.)

Literatur

Hinweise

Zielgruppe

Diese Vorlesung kann von Studierenden verschiedener Studiengänge gehört werden. Insbesondere handelt es sich dabei um:

  • Studierende im Duisburger Bachelor-Studiengang "Angewandte Informatik (Ingenieur- und Medieninformatik)"
  • Studierende im Essener Bachelor-Studiengang "Angewandte Informatik (Systems Engineering)"
  • Lehramtsstudenten
  • Studierende mit Nebenfach Informatik

Hinweise zu den Übungen

Die Teilname an den Übungen und die Bearbeitung der Übungsaufgaben ist dringend erwünscht, da sich ein Großteil des Stoffes durch Anwendung am Beispiel deutlich besser verstehen lässt als bei reinem Studium der Folien.

Die Abgabe der Übungen ist per Moodle möglich. Für weitere Hinweise zur Abgabe von Hausaufgaben siehe Moodle.

Zusätzlich zu den Hausaufgaben werden im Laufe des Semesters drei schriftliche Testate veranstaltet, deren Aufgaben sich aus zuvor in der Übung besprochenen Aufgabentypen zusammensetzen.

Die Teilnahme an den Testaten ist freiwillig und keine Voraussetzung für eine Klausurzulassung. Durch eine erfolgreiche Teilnahme an den Testaten kann jedoch ein Bonus von bis zu zwei Punkten bei der Klausur (entspricht einer Notenstufe, z.B. 2,0 statt 2,3) erreicht werden. Die genaue Bonusregelung wird im Moodle-Kurs ausführlich erklärt.

Hinweise zu den Prüfungen

  • Am Ende des Wintersemesters wird eine schriftliche Prüfung stattfinden. (Anmeldung online über LSF/HisInOne)
  • Die Nachschreibeklausur wird am Ende des Sommersemesters stattfinden. (Anmeldung ebenfalls über LSF/HisInOne)
    • Wichtiger Hinweis, insbesondere für Essener Studenten: für diese Klausur werden Sie nicht automatisch angemeldet! Wenn Sie diese mitschreiben wollen, müssen Sie sich nächstes Semester erneut über HisInOne anmelden.
  • Für Schülerstudenten gelten die Regelungen des Studiengangs, für den sie eingetragen sind. Es ist eine Anmeldung über die Organisatoren des Frühstudiums erforderlich.