Berechenbarkeit und Komplexität

Dozent: Prof. Dr. Christian Scheideler

Modulinformation

  • Pflichtmodul im Gebiet Algorithmen und Komplexität
  • Teilnahmevoraussetzung für Anmeldungen zu BuK (neue PO): erfolgreicher Abschluss der Module Modellierung sowie Datenstrukturen und Algorithmen
  • Teilnahmevoraussetzung für Anmeldungen zu EBKfS (alte PO): erfolgreicher Abschluss der Module Modellierung oder Datenstrukturen und Algorithmen
  • 5 SWS (Semesterwochenstunden): 2 SWS Vorlesung + 1 SWS Zentralübung + 2 SWS Übung
  • 6 ECTS

Termine

  • Vorlesung: Donnerstags 14.15 - 15.45 Uhr, Hörsaal C1
  • Zentralübung: Montags 13.00 - 13.45 Uhr, Hörsaal L2
    • Zusatztermin zur Zentralübung: Donnerstag, 31. Januar 2019, 16-18 Uhr, Q 1.101

Übungsgruppen

Die Anmeldung zu den Übungsgruppen erfolgt über PAUL. 

  1. Di   09:00 - 11:00 Uhr   Raum D1.312 (Tutor: Yulia Bespalova)
  2. Di   14:00 - 16:00 Uhr   Raum D1.312 (Tutor: Philipp Heinisch)
  3. Di   14:00 - 16:00 Uhr   Raum D1.303 (Tutor: Tamara Pilz)
  4. Entfällt
  5. Entfällt
  6. Fr   07:00 - 09:00 Uhr   Raum P1 1.01 (Tutor: Tamara Pilz)
  7. Di   16:00 - 18:00 Uhr   Raum N3.211 (Tutor: Dennis Morasch)
  8. Fr   09:00 - 11:00 Uhr   Raum P1 1.01 (Tutor: Tamara Pilz)
  9. Mi   14:00 - 16:00 Uhr   Raum N3.211 (Tutor: Kristian Hinnenthal / Christina Kolb)
  10. Mi   14:00 - 16:00 Uhr   Raum O1.252 (Tutor: Michael Skowronek)

Beginn der Veranstaltung

  • Erste Vorlesung: Donnerstag, 11. Oktober 2018
  • Erste Zentralübung: Montag, 22. Oktober 2018
  • Übungsbeginn: Dienstag, 16. Oktober 2018

Änderungen

  • Am Freitag, 21. Dezember 2018, ist vorlesungsfrei. Daher findet die Übung 8 an diesem Tag nicht statt. Betroffene Studenten dürfen in dieser Woche eine beliebige andere Übungsgruppe besuchen und auch dort vorrechnen.
  • Am Dienstag, 15. Januar 2019, finden ab 12 Uhr keine Veranstaltungen statt. Übungen 2,3, und 7 fallen daher aus. Betroffene Studenten dürfen in dieser Woche eine beliebige andere Übungsgruppe besuchen und auch dort vorrechnen.
  • Am Mittwoch, 23. Januar 2019, findet Übung 10 ausnahmsweise in Raum P 1 4.08.1 statt.
  • Am Donnerstag, 31. Januar 2019, findet ein Zusatztermin zur Zentralübung von 16-18 Uhr im Raum Q 1.101 statt. Hier werden die noch fehlenden Aufgaben der letzten Heimübungen besprochen. Nach Möglichkeit gibt es auch Zeit für Fragen zu alten Aufgaben.

Diese Vorlesung gibt eine Einführung in grundlegende Methoden und Techniken zur Charakterisierung der Schwierigkeit von Berechnungsproblemen. Als formales Rechenmodel werden Turingmaschinen definiert. Ausgehend hiervon werden die wichtigsten Begriffe und Techniken der Berechenbarkeitstheorie (wie z.B. Entscheidbarkeit, Unentschuldbarkeit, Diagonalisierung, Reduktionen) und der Komplexitätstheorie (wie z.B. Zeitkomplexität, Klassen P und NP, NP-Vollständigkeit, polynomielle Reduktionen, Speicherkomplexität) definiert und erläutert.

Die Folien zur Vorlesung, sowie ein Skript, das im Laufe der Veranstaltung aktualisiert wird, finden Sie hier sowie auf der Veranstaltungsseite auf Panda.

Folien:

Skript: kann hier heruntergeladen werden (Stand: 24.01.2019).

Heimübungen:

Am Freitag nach jeder Vorlesung (also erstmalig am 12. Oktober) wird auf Panda ein Heimübungszettel veröffentlicht, der die aktuellen Themen der Vorlesung behandelt. Ein Heimübungszettel, der am Freitag in Woche x veröffentlicht wird, muss bis spätestens Montag, 13:00 Uhr, in Woche x+2 abgegeben werden (vor der Zentralübung). Die Zettel können in Gruppen von bis zu 3 Personen bearbeitet und abgegeben werden (deutlich beschriftet mit Namen und Matrikelnummern). Bitte geben Sie den Zettel nur einmal ab, und zwar entweder per Online Abgabe auf Panda (in dem einer der Gruppenmitglieder die Lösung hochlädt), oder im Kasten der Übungsgruppe auf D3 (in der eine der Personen angemeldet ist). Bitte geben Sie jede Lösung nur genau einmal ab! Verspätete Abgaben werden registriert und bekommen keine Punkte.

Wir empfehlen die Online Abgabe als PDF. Zum hochladen einer Lösung müssen Sie in einer Kleingruppe in Panda eingetragen sein (auch wenn Sie alleine abgeben!). Wenden Sie sich dazu an ihren Tutor

Sollten bei der Benutzung von Panda Probleme auftreten, so bitten wir diese im Forum "Probleme / Anmerkungen" auf der Veranstaltungsseite auf Panda zu berichten. Sollte aus technischen Problemen eine fristgerechte Abgabe nicht möglich sein, so kann die Lösung in Ausnahmefällen auch per Mail akzeptiert werden.

Bonuspunkte: Wer mindestens 70% aller Punkte auf Heimübungszetteln erreicht erhält einen Bonus von 0,3 Notenschritten auf eine bestandene Klausur.

Präsenzübungen:

Zusätzlich zu den Heimübungszetteln wird jeden Freitag auf Panda ein Präsenzübungszettel veröffentlicht. Die Aufgaben dieser Zettel werden in der darauffolgenden Woche in den Übungen behandelt, wo Ihnen ein Tutor zur Hilfe steht. Da in den Präsenzübungen nicht genug Zeit für das Bearbeiten und Vorstellen aller Aufgaben sein wird, empfehlen wir Ihnen dringend den Übungszettel schon vorher anzuschauen.

Klausurzulassung:

Gemäß der aktuellen Prüfungsordnung ist zur Zulassung zur Klausur dieses Semester eine Studienleistung nötig. Die Studienleistung setzt sich zusammen aus den folgenden Voraussetzungen:

  • Mindestens 40% aller Punkte in Heimübungszetteln erreichen
  • Mindestens einmal eine Aufgabe in den Präsenzübungen präsentieren

Ohne das Erbringen beider Leistungen werden Sie zur Klausur nicht zugelassen.

Klausur:

Die Vorlesung ist nur dann bestanden, wenn die Klausur mit mindestens 4,0 bestanden ist. Eine Beispielklausur zur Vorbereitung finden Sie hier.

Voraussichtliche Klausurtermine:

  1. Erste Klausur: 15.02.2019, 9:00 Uhr, SP1
  2. Zweite Klausur: 22.03.2019, 9:00 Uhr, O1

Klausureinsicht 2. Klausur: 29.03.2019, 10:00 Uhr, F1.110

Sie dürfen in der Klausur keine Hilfsmittel benutzen außer einem beidseitig handbeschriebenen DIN A4 Zettel.

Weitere Informationen

Bei Fragen wenden Sie sich bitte an Christina Kolb oder Kristian Hinnenthal.