Berechenbarkeit und Komplexität (WS 2020/21)

Vergangene Veranstaltung

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

Vorlesungsablauf

Die Vorlesung fand im Wintersemester 2020/21 aufgrund der Covid-19-Situation nicht als Präsenzveranstaltung statt, sondern online. Bitte melden Sie sich im Moodle-Kurs an (für Zugangsschlüssel bitte Übungsleitung oder Dozentin kontaktieren) für alle Materialien und weitere Informationen (werden regelmäßig aktualisiert).

Wir werden wöchentlich Videos von der Vorlesung bereitstellen. Übungsaufgaben werden wie gewohnt online abgegeben und bewertet. Auch die Besprechung der Übungen erfolgt online durch Videos. Eure Fragen zum Stoff können im Moodle-Forum oder per Mail gestellt werden und werden von uns beantwortet.

Dozentin
Prof. Dr. Barbara König

Übungsleiterin
Lara Stoltenow

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

Termine

Vorlesung

online als Aufzeichnung zum Download, Links werden im Moodle bereitgestellt

Tutorium

Über BigBlueButton. Details werden noch festgelegt und dann in Moodle bekanntgegeben

Besprechung der Übungen

online als Aufzeichnung zum Download (siehe Moodle). Alle Fragen bitte im Diskussionsforum stellen oder ggf. im Tutorium.

Übungsablauf und Bonuspunkte

Prüfung/Klausur

Termin 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 per Moodle möglich. Hinweise zur PDF-Abgabe siehe dort.

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.

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)
  • Nur für Studierende im Studiengang "Angewandte Informatik", die die mündliche Prüfung bereits abgelegt und nicht bestanden haben (und sich daher im 2. oder 3. Versuch befinden), ist es noch ein letztes Mal möglich (aber nicht erforderlich), sich wie bisher mündlich prüfen zu lassen.
  • Für Schülerstudenten gelten die Regelungen des Studiengangs, für den sie eingetragen sind. Es ist keine Anmeldung beim Prüfungsamt erforderlich.