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: Montags, 14.15 - 15.45 Uhr, Hörsaal L2
  • Zentralübung: Montags 13.00 - 13.45 Uhr, Hörsaal L2

Übungsgruppen

Die Anmeldung zu den Übungsgruppen erfolgt über PAUL. 

  1. Mo  09:00 - 11:00 Uhr   Raum D1.303 (Tutor: Alexander Setzer) -> Findet ab sofort in D1.312 statt (zusammen mit Übungsgruppe 2)
  2. Mo  09:00 - 11:00 Uhr   Raum D1.312 (Tutor: Yulia Bespalova)
  3. Mo  11:00 - 13:00 Uhr   Raum D1.303 (Tutor: Jonas Schweichhart)
  4. Mo  11:00 - 13:00 Uhr   Raum D1.312 (Tutor: Christopher Volker Haensch)
  5. Di   11:00 - 13:00 Uhr   Raum D1.303 (Tutor: Christopher Volker Haensch)
  6. Di   14:00 - 16:00 Uhr   Raum D1 312 (Tutor: Fabian Dotzki)
  7. Do  11:00 - 13:00 Uhr   Raum D1.303 (Tutor: Christina Kolb) -> Entfällt ab sofort
  8. Mi  14:00 - 16:00 Uhr   Raum D1.312 (Tutor: Dennis Morasch)
  9. Fr   11:00 - 13:00 Uhr   Raum D1.303 (Tutor: Alexander Setzer) -> Entfällt ab sofort
  10. Mi  14:00 - 16:00 Uhr   Raum D1.303 (Tutor: Christina Kolb) -> Findet ab sofort in D1.312 statt (zusammen mit Übungsgruppe 8)

Beginn der Veranstaltung

  • Erste Vorlesung: Montag, 7. Oktober 2019
  • Erste Zentralübung: Montag, 21. Oktober 2019
  • Übungsbeginn: Montag, 14. Oktober 2019

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 Freitagnachmittag (also erstmalig am 11. 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 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.

Sollten bei der Benutzung von Panda Probleme auftreten, so bitten wir diese im Forum "Probleme / Anmerkungen" auf der Veranstaltungsseite auf Panda zu berichten.

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 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 den 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: 11.02.20, 14:00 - 16:00 Uhr, Hörsaal L1
    Klausureinsicht: 19.02.20, 14:00 - 15:30 Uhr, Raum F1.110
  2. Zweite Klausur: 31.08.20, 9:00 - 11:00, Hörsaal L1

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

Sie interessieren sich für: