English English

Allgemeine Informationen

ECTS: 6
Sprache: Deutsch
Campus: hier
Modul-
anmeldung:
über CampusOffice
Art Termin / Ort Beginn Dozent
V3 Di 08:15h - 09:45h / Eph
Fr 11:45h - 13:15h / Eph
11. Oktober 2011 Vöcking

Ü2 siehe unten 24. Oktober 2011 siehe unten


Aktuelles

  • Die Ergebnisse der 2. Bachelor-Klausur nach der Einsicht wurden ins CampusOffice eingetragen. Statistik zur 2. Bachelor-Klausur:
    Note Punkte Anzahl Prozent
    5.0 0-49.5 3 9.09
    4.0 50-55.5 3 9.09
    3.7 56-61.5 927.27
    3.3 62-67.5 412.12
    3.0 68-74.5 515.15
    2.7 75-80.5 412.12
    2.3 81-86.5 1 3.03
    2.0 87-92.5 1 3.03
    1.7 93-99.5 1 3.03
    1.3100-106.50 0
    1.0107-120 2 6.06


Inhalt

Welche Probleme kann man mit Hilfe des Computers lösen? Und welche Probleme kann man effizient lösen? - Das sind die Fragestellungen, um die es in dieser Vorlesung geht. Wir versuchen diese Fragen mit mathematischen Methoden zu beantworten. Dazu müssen wir zunächst Begriffe wie Problem, Algorithmus und Effizienz modellieren. Anschließend werden wir verblüffend klare und weitgehende Aussagen über die (effiziente) Lösbarkeit von Problemen auf Rechnern machen können. Grundlage der Vorlesung sind mathematische Modelle und Methoden. Der Bezug zu praktischen Problemen und modernen Rechnern wird aber klar herausgearbeitet. Ein Highlight der Vorlesung ist die NP-Vollständigkeitstheorie, deren Auswirkung auf Theorie und Praxis wohl kaum überschätzt werden kann.


Vorlesungsmaterial

Skript zur Vorlesung

Fragenkatalog

Einführung
11./14. Okt. Motivation, Übersicht und Organisatorisches [Folien]
Modellierung von Problemen, Einführung der Turingmaschine [Folien]
18. Okt. Mehrband-Turingmaschinen und die universelle Turingmaschine [Folien]
21. Okt. Registermaschine (RAM), Church-Turing-These [Folien]

Berechenbarkeit
25. Okt. Unentscheidbare Probleme: Diagonalisierung [Folien]
28. Okt. Unentscheidbarkeit des Halteproblems: Unterprogrammtechnik [Folien]
4. Nov. Der Satz von Rice [Folien]
8. Nov. Rekursive Aufzählbarkeit, Die Reduktion [Folien]
11. Nov. Allgemeines Halteproblem [Folien]
15. Nov. Hilberts 10. Problem
18. Nov. Das Postsche Korrespondenzproblem [Folien]
22. Nov. Mächtigkeit von WHILE-Programmen [Folien]
25. Nov. Mächtigkeit von LOOP-Programmen [Folien]

Komplexität
29. Nov. Die Komplexitätsklassen P und NP [Folien]
6. Dez. Die Klasse NP und die polynomielle Reduktion [Folien]
13. Dez. NP-Vollständigkeit [Folien]
16. Dez. NP-Vollständigkeit ausgewählter Graphprobleme [Folien]
20. Dez. NP-Vollständigkeit einiger Zahlprobleme [Folien]
Überblick über die Komplexitätslandschaft [Folien]

Globalübung
24. Jan. 1. Globalübung
31. Jan. 2. Globalübung

Prüfungstermine
10. Jan. Präsenzübung
24. Feb. Bachelorklausur
22. Mrz. Wiederholungsklausur


Übungen

  • Der Raum 4017 ist der Seminarraum des Lehrstuhls. Er befindet sich im Erdgeschoss des Erweiterungsbaus 1 (E1).
1 Mo 12:15 - 13:45, 2356|056 (5056) Russ Lucas Jukić
2 Mo 12:15 - 13:45, 4017 Felix Canavoi
3 Mo 14:00 - 15:30, 2356|056 (5056) Jonathan Meyer
4 Di 12:00 - 13:30, 4017 Benjamin Kaminski
5 Mi 12:00 - 13:30, 4017 Michael Tegethoff
6 Mi 12:00 - 13:30, 2356|054 (5054) Andreas Tönnis
7 Mi 13:30 - 15:00, 2356|052 (5052) Sebastian Freitag
8 Mi 13:30 - 15:00, 4017 Michael Tegethoff
9 Do 10:00 - 11:30, 4017 Andreas Tönnis
10 Do 12:00 - 13:30, 2356|056 (5056) Jens Katelaan
11 Do 16:00 - 17:30, 4017 Svenja Schalthöfer

Hinweise zu den Übungen

  • Die Übungen können in Gruppen bis zu drei Personen abgegeben werden.
  • Die Abgabe der Übungen ist Dienstags in der Vorlesung oder bis 12:00 Uhr im Sammelkasten am Lehrstuhl für Informatik 1 möglich.
  • Übungspunkte werden im kleinen Umfang in der Bachelorklausur berücksichtigt:
    Bei 50 + 10k erworbenen Übungspunkten für k ∈ {1,...,6} werden k Punkte angerechnet.


Prüfungszulassung (Bachelor Informatik/Mathematik) und Leistungsnachweis

Für die Zulassung zur Bachelor-Prüfung bzw. für einen Leistungsnachweis sind mindestens 50 Punkte zu sammeln. Hierzu gibt es folgende Möglichkeiten:
  • 90 Punkte in der Präsenzübung am 10. Januar.
  • Je 4 Punkte pro Übungsblatt für die speziell ausgezeichnete Aufgabe.
  • Je 2 Punkte für das Vortragen der Lösung einer Aufgabe in den Übungsgruppen.

Weitere Literaturhinweise

Die folgenden Bücher eignen sich als zusätzliche Literatur und stehen in der Informatikbibliothek zur Verfügung.

  • J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 2001.
  • J. Hromkovic: Theoretische Informatik. Teubner 2004.
  • U. Schöning: Theoretische Informatik - kurzgefaßt. Spektrum Akademischer Verlag 2001.
  • M. Sipser: Introduction to the Theory of Computation. PWS Publishing 1997.
  • I. Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung. Teubner Verlag 1999.
  • I. Wegener: Kompendium Theoretische Informatik - Eine Ideensammlung. Teubner 1996.

Kontakt