Algorithmen und Berechnungskomplexität II

Termine

Wann Wo Beginn LP Dozent
Mitwochs 12:30-14:00 AVZ III / HS 1 09. April 2014 4,0 Röglin
Die Termine der Tutorien sind weiter unten aufgelistet. 14. April 2014 2,0 Bruckschen, Heidemann, Kurnatowski, Loevenich, Omlor, Saljoki

Inhalt

In dieser Vorlesung werden wir uns mit der Berechenbarkeit und Komplexität von Problemen beschäftigen. Es gibt viele verschiedene Probleme. Wir werden formalisieren, was wir unter einem Problem verstehen und Rechnermodelle angeben, die bestimmen, was für Operationen wir zur Bestimmung von Lösungen benutzen dürfen. Wir haben im vergangenen Semester effiziente Algorithmen zur Lösung einer Vielzahl von Problemen entworfen. In dieser Vorlesung werden wir die Grenzen der Algorithmik kennenlernen und uns damit beschäftigen, für welche Probleme es keine effizienten Algorithmen gibt und welche überhaupt nicht algorithmisch gelöst werden können.

Datum Inhalt Literatur
9. April 1 Einleitung
1.1 Probleme und Funktionen
1.2 Rechnermodelle
1.2.1 Turingmaschinen
Skript
Folien
16. April 1.2.1 Turingmaschinen (Fortsetzung)
1.2.2 Registermaschinen
Skript
Folien
23. April 1.2.2 Registermaschinen (Fortsetzung)
1.2.3 Die Church-Turing-These
2 Berechenbarkeitstheorie
2.1 Entwurf einer universellen Turingmaschine
2.2 Die Unentscheidbarkeit des Halteproblems
Skript
30. April 2.2 Die Unentscheidbarkeit des Halteproblems (Fortsetzung)
2.3 Turing- und Many-One-Reduktionen
Skript
7. Mai 2.3 Turing- und Many-One-Reduktionen (Fortsetzung)
2.4 Der Satz von Rice
Skript
14. Mai 2.5 Rekursiv aufzählbare Sprachen Skript
21. Mai Keine Vorlesung wegen Dies Academicus
28. Mai 2.6 Weitere nicht entscheidbare Probleme
3 Komplexitätstheorie
3.1 Die Klassen P und NP
3.1.1 Die Klasse P
Skript
4. Juni 3.1.2 Die Klasse NP
3.1.3 P versus NP
Skript
18. Juni 3.2 NP-Vollständigkeit Skript
25. Juni 3.2 NP-Vollständigkeit (Fortsetzung) Skript
2. Juli 3.3 Weitere NP-vollständige Probleme
3.4 Ausblick
Skript
9. Juli 4 Approximationsalgorithmen
4.1 Traveling Salesman Problem
4.1.1 Nichtapproximierbarkeit
4.1.2 Metrisches TSP
Skript
17. Juli 4.1.3 Christofides-Algorithmus Skript

Übungen

Für den Erhalt des Übungsscheins müssen insgesamt mindestens 50% der zu erreichenden Punkte bei den Übungsaufgaben erreicht werden und Lösungen von zwei Aufgaben müssen im Laufe des Semesters erfolgreich in den Tutorien präsentiert werden. Eine Abgabe der Übungsaufgaben in Gruppen bis zu drei Studierenden ist möglich.

Wann Wo Tutor
Di 8 (c.t.) - 10 AVZ III / A301 Vitali Kurnatowski
Di 8 (c.t.) - 10 AVZ III / A7a Mosadeq Saljoki
Di 10 (c.t.) - 12 AVZ III / A7a Philipp Bruckschen
Di 14 (c.t.) - 16 AVZ III / A6a Philipp Bruckschen
Di 16 (c.t.) - 18 AVZ III / A6b Philipp Bruckschen
Mi 14 (c.t.) - 16 AVZ III / A6b Vitali Kurnatowski
Do 10 (c.t.) - 12 AVZ III / A301 Philipp Bruckschen
Do 12 (c.t.) - 14 AVZ III / A301 Johannes Loevenich
Do 12 (c.t.) - 14 AVZ III / A7a Lukas Heidemann
Do 14 (c.t.) - 16 AVZ III / A301 Yvonne Omlor
Fr 10 (c.t.) - 12 AVZ III / A7a Yvonne Omlor
Fr 10 (c.t.) - 12 AVZ III / A301 Johannes Loevenich
Fr 12 (c.t.) - 14 AVZ III / A7a Lukas Heidemann
  • Präsenzblatt (Besprechung in KW 16, keine Abgabe)
  • Übungsblatt 1 (Besprechung in KW 17, Abgabe bis 16.04., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 2 (Besprechung in KW 18, Abgabe bis 23.04., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 3 (Besprechung in KW 19, Abgabe bis 30.04., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 4 (Besprechung in KW 20, Abgabe bis 07.05., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 5 (Besprechung in KW 21, Abgabe bis 14.05., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 6 (Besprechung in KW 22, Abgabe bis 21.05., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 7 (Besprechung in KW 23)
  • Übungsblatt 8 (Besprechung in KW 25, Abgabe bis 04.06., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 9 (Besprechung in KW 26, Abgabe bis 18.06., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 10 (Besprechung in KW 27, Abgabe bis 25.06., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 11 (Besprechung in KW 28, Abgabe bis 02.07., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Probeklausur (Besprechung in KW 29, Abgabe in KW 28 im Tutorium)
lehre/ss14/algorithmen-und-berechnungskomplexitaetii.txt · Zuletzt geändert: 2017/05/04 14:59 von roeglin

Benutzer-Werkzeuge