Algorithmen und Berechnungskomplexität II

Termine

Wann Wo Beginn Dozent
VorlesungMitwoch 12:30-14:00 AVZ III / HS 1 19. April 2017 Röglin
Übungen 24. April 2017

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
19. April 1 Einleitung
1.1 Probleme und Funktionen
1.2 Rechnermodelle
1.2.1 Turingmaschinen
Folien
26. April 1.2.1 Turingmaschinen (Fortsetzung)
1.2.2 Registermaschinen
Folien
3. Mai 1.2.2 Registermaschinen (Fortsetzung)
1.2.3 Die Church-Turing-These
2 Berechenbarkeitstheorie
2.1 Entwurf einer universellen Turingmaschine
Folien
10. Mai 2.2 Die Unentscheidbarkeit des Halteproblems
2.3 Turing- und Many-One-Reduktionen
17. Mai dies academicus (keine Vorlesung)

Ü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.

Die Abgabe erfolgt im entsprechend gekennzeichneten Briefkasten in der Römerstraße.
Es werden nur Abgaben akzeptiert, bei denen auf der ersten Seite gut erkennbar die Nummer der Übungsgruppe notiert ist.

Nr. Wann Wo Tutor
1 Dienstag 10:15 - 11:45 AVZ III / A7a Torben Plitt
2 Dienstag 14:15 - 15:45 AVZ III / A6a Danny Rademacher
3 Dienstag 16:15 - 17:45 AVZ III / A6b Danny Rademacher
4 Mittwoch 14:15 - 15:45 AVZ III / A6b Florian Glässer
5 Mittwoch 16:15 - 17:45 AVZ III / A6a Florian Glässer
6 Donnerstag 10:15 - 11:45 AVZ III / A301 Florian Nelles
7 Donnerstag 12:15 - 13:45 AVZ III / A301 Florian Nelles
8 Freitag 10:15 - 11:45 AVZ III / A7a Jan Hoeckendorff
9 Freitag 12:15 - 13:45 AVZ III / A7a Jan Hoeckendorff

Anmeldung zu den Übungen:

Die Anmeldung zu den Übungsgruppen erfolgt über das Tutorienvergabesystem (TVS). Eine einmalige Registrierung ist vom Netz der Universität Bonn aus erforderlich. Anschließend können Sie von überall auf das TVS zugreifen.

Bei Fragen zum Übungsbetrieb wenden Sie sich bitte an Clemens Rösner (roesner@cs.uni-bonn.de).

  • Präsenzblatt (Besprechung in KW 17, keine Abgabe)
  • Übungsblatt 1 (Besprechung in KW 18, Abgabe bis 26.04., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 2 (Besprechung in KW 19, Abgabe bis 03.05., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 3 (Besprechung in KW 20, Abgabe bis 10.05., 12:30 Uhr, im Briefkasten in der Römerstraße)
  • Übungsblatt 4 (Besprechung in KW 21, keine Abgabe)
  • Übungsblatt 5 (Besprechung in KW 22, Abgabe bis 24.05., 12:30 Uhr, im Briefkasten in der Römerstraße)

Prüfungen

Die erste Klausur findet Dienstag, den 1. August 2017, zwischen 14 und 17 Uhr im Universitäts-Hauptgebäude statt.

Die zweite Klausur findet Montag, den 25. September 2017, zwischen 9 und 12 Uhr im Universitäts-Hauptgebäude statt.

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript.


Page Tools