Berechenbarkeit und Komplexität (WS 2017/18)

Vergangene Veranstaltung

Diese Seite bezieht sich auf eine Vorlesung aus vorherigen Jahren. Aktuelle Termine und Arbeitsmaterialien sind hier zu finden.

Dozentin
Prof. Dr. Barbara König

Übungsleitung
Christina Mika-Michalski

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 WS16/17 orientieren. Die Arbeitsunterlagen zur dieser Vorlesung finden Sie hier.

Hinweise

  • 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
  • Die Teilname an den Übungen und die Bearbeitung der Übungs-Zettel 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. Daher gilt folgende Bonus-Regelung:
    Wer 50% der Übungspunkte erreicht, erhält eine um 0.3 bessere Note.

Prüfungen

  • Für Studierende des Duisburger Bachelor-Studiengangs "Angewandte Informatik" können aus zwei Prüfungsformen eine auswählen. Die Prüfung kann wahlweise in Form einer Klausur am Ende des Semesters oder in Form einer mündlichen Prüfung des Moduls "Theoretische Informatik" (in Kombination mit "Automaten und formale Sprachen") geprüft werden. Studenten, die bereits eine mündliche Prüfung in "Automaten und formale Sprachen" abgelegt haben, werden nur in "Berechenbarkeit und Komplexität" mündlich geprüft.
  • Für Studierende des Essener Bachelor-Studiengangs "Angewandte Informatik" und Nebenfach-Studenten findet am Ende des Semesters eine Klausur statt. Bitte melden Sie sich zur Klausur online im LSF an.
  • Für Schülerstudenten gelten die Regelungen des Studiengangs, für den sie eingetragen sind. Es ist keine Anmeldung beim Prüfungsamt erforderlich.

Literatur

Termine

Vorlesung

Die Dozentin wird im wöchentlichen Wechsel in Duisburg und in Essen anwesend sein. Sie müssen "Ihren" Campus jedoch nicht verlassen, da es eine Video-Konferenz in den jeweils anderen Hörsaal geben wird.

  • Donnerstag, 14-16, LB 134 (Duisburg) und R14 R02 B97 (Essen)
  • Erste Vorlesung am 12.10.

Übungen in Duisburg

  • Gruppe D1: Mittwoch, 8:30-10, LC 137 (Pascal Breuer)
  • Gruppe D2: Donnerstag, 12-14, LC 137 (Katja Poltermann)
  • Gruppe D3: Mittwoch, 16-18, LC 137 (Paul A. Meteng-Kamdem)

Übungen in Essen

  • Gruppe E1: Dienstag, 8:30-10, SH 403 (Lara Stoltenow)
  • Gruppe E2: Donnerstag, 12-14, SH 406 (Lara Stoltenow)
  • Gruppe E3: Donnerstag, 16-18, SH 403 (Sophie Selter)

Tutorium

Das Tutorium wird voraussichtlich in den ersten drei Vorlesungswochen ausschließlich in Essen stattfinden und in diesen drei Wochen einen Überblick über Inhalte aus Automaten und formale Sprachen geben. Dies dient der Angleichung der Vorkenntnisse zwischen Duisburger und Essener Studenten. Anschließend wird das Tutorium im wöchentlichen Wechsel in Duisburg und Essen stattfinden. Im Tutorium können Fragen zur Vorlesung und zum Übungsstoff beantwortet werden, sowie einzelne Themen aus der Vorlesung wiederholt werden. Bitte stellen Sie rechtzeitig vor Beginn des Tutoriums Ihre Fragen wahlweise in das hierfür vorgesehene Moodle-Topic, oder senden Sie Ihre Fragen via E-Mail an Christina Mika-Michalski. Sind jeweils bis Mittwoch, 13 Uhr, keine Fragen per E-Mail eingegangen, entfällt das Tutorium in der jeweiligen Woche. Eine entsprechende Ankündigung erfolgt dann im Moodle. Diese Regelung gilt erst ab der vierten Vorlesungswoche (also der ersten Woche in der das Tutorium in Duisburg stattfindet).

  • Duisburg: Do, 8-10, LK 053
  • Essen: Do, 8-10, SH 406

Das erste Tutorium findet am 19.10.2017 statt.

Weitere Termine in Essen:
26.10 fällt aus.
2.11.2017
9.11.2017

Erster Termin Duisburg: 16.11.2017

Prüfung/Klausur

Die Klausur zu Berechenbarkeit und Komplexität findet am 6. März 2018 von 15-17 Uhr statt (Räume: LA 0034).

Die Erstklausur (nur für Essener Bachelorstudiengänge - Systems Engineering, Lehramt) findet am Campus Essen statt am 5. Febuar 2018 von 8.30 bis 10.30 Uhr im Raum: S04 T01 A01 (altes Audimax)

Links