Berechenbarkeit und Komplexität

Die Vorlesung gibt eine Einführung in die Gebiete der Berechenbarkeits- und Komplexitätstheorie.

Der Bearbeitungszeitraum für die Klausuren beträgt jeweils 50 Minuten, als Hilfsmittel ist ein handbeschriebenes DIN-A4 Blatt zugelassen. Beide Klausuren sind offen, d.h. es kann auch der Zweittermin wahrgenommen werden ohne am Ersttermin teilgenommen zu haben.

• Die Erstklausur findet am Montag, den 24.07.2017 um 15:00 Uhr s.t. (im Anschluss an die Klausur Logik) im Raum H22 statt.
• Die Klausureinsicht der Erstklausur findet am Donnerstag, den 17.8.2017 von 15:00 bis 16:00 Uhr (im Anschluss an die Klausureinsicht Logik) im Raum O27/531 statt.
• Die Zweitklausur findet am Dienstag, den 17.10.2017 um 15:00 Uhr s.t. (im Anschluss an die Klausur Logik) in den Räumen H21 und H13 statt. Die Raumzuordnung lautet wie folgt:
  • Nachname beginnend mit A-J: H21
  • Nachname beginnend mit K-Z: H13
• Die Klausureinsicht der Zweitklausur findet am Freitag, den 27.10.2017 von 16:00 bis 17:00 Uhr (im Anschluss an die Klausureinsicht Logik) im Raum O27/531 statt.

Für Studierende, für die laut Prüfungsordnung/Modulhandbuch die Fächer Logik und BuK zu einem Modul zusammengefasst sind, wird das Studiensekretariat, nachdem beide Klausurnoten feststehen, die Endnote für das Modul berechnen.

Zum Notenbonus:
Hat man die Übungen zu Berechenbarkeit und Komplexität erfolgreich absolviert (50 % der Punkte erreicht), so erhält man bei bestandener BuK-Klausur einen Notenbonus von 0,3 bzw. 0,4 (sofern die Note vor der Anhebung weder 1,0 noch 5,0 lautet). Es kann auch ein erfolgreicher Übungsbesuch aus einem vergangenem Semester für den Bonus eingebracht werden.

Vorlesungsmaterialien werden über die Lernplattform moodle zur Verfügung gestellt.

Der gesamte Übungsbetrieb wird über die Lernplattform moodle durchgeführt.

• U. Schöning: Theoretische Informatik - kurz gefasst. Spektrum Akademischer Verlag, 5. Auflage, 2008.
• Skript
• A. Meier, H. Vollmer: Komplexität von Algorithmen. Nachdruck. Lehmanns media, 2015.
• M. Garey, D. Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness. Nachdruck. W H Freeman & Co, 1979.