WS 2011/12: Berechenbarkeit und Komplexität

Dozentin:
Prof. Dr. Barbara König (Email)

Übungsleitung:
Henning Kerstan (Email)
vorher: Jan Stückrath (Email)

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 WS10/11 orientieren.

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)".
      Für diese Gruppe hat die Vorlesung den Titel "Berechenbarkeit und Komplexität"
    • Studierende im Essener Bachelor-Studiengang "Angewandte Informatik (Systems Engineering)".
      Für diese Gruppe hat die Vorlesung den Titel "Theoretische Informatik: Komplexitätstheorie und effiziente Algorithmen"
    • 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. Man kann dabei einmal im Semester seine Lösungen vortragen und bekommt dafür 10 Bonuspunkte gutgeschrieben.

Prüfungen

  • Für Studierende des Duisburger Bachelor-Studiengangs "Angewandte Informatik" wird am Ende des Semesters eine mündliche Prüfung des Moduls "Theoretische Informatik" (in Kombination mit "Automaten und formale Sprachen") stattfinden. 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. Nebenfach-Studenten melden sich bitte per Email an den Dozenten oder die Übungleitung 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.

  • Duisburg: Do, 14–16, LB 134
    (13.10., 27.10., 10.11., 24.11., 08.12., 15.12., 12.01., 26.01 )
  • Essen: Do, 14-16, S07 S00 D07
    (20.10., 03.11, 17.11., 01.12., 22.12., 19.01., 02.02.)

Übungen in Duisburg:

  • Mi, 08–10, LC 137, Gruppe D1
  • Do, 12–14, LC 137, Gruppe D2
  • Do, 16–18, LC 137, Gruppe D3

Übungen in Essen:

  • Do, 12-14, SH 403, Gruppe E1
  • Do, 16-18, SH 403, Gruppe E2

Die Übungsgruppen beginnen in der dritten Vorlesungswoche (ab 26.10.).

Prüfung/Klausur

  • Die mündlichen Modulprüfungen "Theoretische Informatik" für die Studierenden des Bachelor-Studiengangs "Angewandte Informatik (Ingenieur- und Medieninformatik)" finden im Sommersemester im Zeitraum 13.-17.08.2012 im Raum LF 264 statt. Bitte sagen Sie auf jeden Fall auch den Prüfern Bescheid, wenn Sie sich von der Prüfung abmelden sollten. (Kurzfristige Abmeldungen werden uns vom Prüfungsamt nicht mitgeteilt.)
  • Die mündlichen Modulprüfungen "Theoretische Informatik" für die Studierenden des Bachelor-Studiengangs "Angewandte Informatik (Ingenieur- und Medieninformatik)" finden im Zeitraum 21.-24.02.2012 statt. Ab sofort liegen im Sekretariat (LF 227) Listen aus, in die man sich eintragen kann, um einen Prüfungstermin zu erhalten.

  • Der Termin für die BeKo-Klausur (für den Essener Bachelor-Studiengang "Angewandte Informatik" und Studierende mit Nebenfach Informatik) steht jetzt fest.
    Datum: 8. Februar 2012
    Zeit: 10 - 12 Uhr
    Ort: Hörsaal S05 T00 B08, Campus Essen
    Erlaubte Hilfmittel: Keine
    Nebenfach-Studenten melden sich bitte per E-Mail an Henning Kerstan an.

  • Der Termin für die BeKo-Nachklausur (für den Essener Bachelor-Studiengang "Angewandte Informatik" und Studierende mit Nebenfach Informatik) wurde geändert!
    Datum: 20. März 2012
    Zeit: 10 - 12 Uhr
    Ort: S04 T01 A02, Campus Essen
    Erlaubte Hilfmittel: Keine
    Nebenfach-Studenten melden sich bitte per E-Mail an Henning Kerstan an.

Aktuelles

no news in this list.

© Universität Duisburg-Essen, Lehrstuhl Theoretische InformatikLogin