Berechenbarkeit und Komplexität (WS 2019/20)

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

Übungsleiterin
Lara Stoltenow

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

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 B07 (Essen)
  • Erste Vorlesung am 17.10.

Tutorium

Im wöchentlichen Wechsel in Duisburg und Essen:

  • Duisburg: Montag, 12-14, LC 137, am 4.11., 18.11., 2.12., 16.12., 13.1., 27.1.
  • Essen: Donnerstag, 12-14, R09 S05 B02, am 31.10., 14.11., 28.11., 12.12., 9.1., 23.1., 30.1.
Hinweise zum Tutorium

Übungsgruppen

In Duisburg

  • D1: Mi, 8:30-10, LC 137
  • D2: Do, 12-14, LC 137
  • D3: Do, 16-18, LC 137

In Essen

  • E1: Mi, 10-12, V15 R01 H63
  • E2: Do, 10-12, R12 R06 A79
  • E3: Do, 16-18, V15 R04 H25
Übungsablauf und Bonuspunkte

Prüfung/Klausur

Die mündlichen Prüfungen finden vom 17.-21. Februar 2020 im Raum LF 264 statt. Ab sofort liegen im Sekretariat LF 227 Terminlisten aus, in die Sie sich eintragen können.

Die schriftliche Prüfung findet am Montag, 17. Februar 2020, um 8:30 Uhr statt. Der Raum wird noch bekanntgegeben.

Hinweise zu den Prüfungsformen

Arbeitsmaterial

Links

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 Ü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.

Die Abgabe der Übungen ist in Papierform oder per Moodle möglich. Die Papierabgaben müssen in den mit "Berechenbarkeit und Komplexität" beschrifteten Briefkasten neben Raum LF 259 geworfen werden. Hinweise zur PDF-Abgabe siehe Moodle.

Den Bonus von einer Notenstufe (z.B. 2,0 statt 2,3) erhält, wer am Ende der Vorlesung mindestens 50% der Übungspunkte (also 120 Punkte oder mehr) erhalten hat. Es gibt einmalig die Möglichkeit 10 Punkte durch Vorrechnen einer Aufgabe in den Übungsgruppen zu erhalten.

Hinweise zum Tutorium

Das Tutorium findet für gewöhnlich im wöchentlichen Wechsel in Duisburg und Essen statt, die Termine stehen oben. Dort können zusätzliche Fragen zur Vorlesung und zum Übungsstoff beantwortet werden, sowie einzelne Themen aus der Vorlesung wiederholt werden.

Hinweise zu den Prüfungen

wird noch aktualisiert

  • Studierende des Bachelor-Studiengangs "Angewandte Informatik", die vor dem Wintersemester 2018/19 das Studium aufgenommen haben, können eine mündliche Prüfung des Moduls "Theoretische Informatik" (in Kombination mit "Automaten und Formale Sprachen") ablegen. 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 alle anderen Studierenden (Angewandte Informatik Duisburg ab WS 2018/19, Angewandte Informatik Essen, 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.