English English

Termine

Art Termin / Ort Beginn Dozent
V3 Di 08:15h - 09:45h / Eph (Nur bis 01.12.2009)
Fr 11:45h - 13:15h / Eph 		13.10.2009 Vöcking

Kreditpunkte (ECTS-Credits): 6

Aktuelles

  • Entgegen der ursprüngliche Ankündigung findet am Dienstag, den 01.12., eine Vorlesung statt. Dafür entfällt die Vorlesung am 04.12. (Tag der Informatik).
  • Zur Vorbereitung auf die Klausuren haben wir einen Fragenkatalog zum Thema Berechenbarkeit erstellt.
  • Die Lösung von Übungsblatt 5 wird am Freitag, den 20.11. um 11.45 Uhr in einer Globalübung, die an Stelle der Vorlesung stattfindet, vorgestellt. In der Woche vom 23.11. bis 27.11. finden keine Kleingruppenübungen statt.
  • Die erste Zulassungklausur findet am Dienstag, den 24.11. um 8.15 Uhr statt.
  • Hörsaalaufteilung:
    Matrikelnummer Hörsaal
    0 bis 269999 AH I
    270000 bis 282999 AH II
    283000 bis 299999 Eph

Inhalt

Welche Probleme kann man mit dem Computer 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, Computer 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 realistischen Computern und praktischen Problemen 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. Im Einzelnen gliedert sich die Vorlesung wie folgt:

Vorläufiger Zeitplan

Einführung
  • 13. Okt Übersicht [Folien]
  • 16. Okt Modellierung von Problemen / Einführung der Turingmaschine (TM) [Folien]
  • 20. Okt Erläuterung des TM-Modells [Folien]
  • 23. Okt Einführung der Registermaschine (RAM) / Vergleich TM – RAM / Church-Turing-These [Folien]
Berechenbarkeit
  • 27. Okt Existenz unentscheidbarer Probleme / Unentscheidbarkeit der Diagonalsprache [Folien]
  • 30. Okt Unentscheidbarkeit des Halteproblems / Unterprogrammtechnik [Folien] [Ergänzungen]
  • 6. Nov Der Satz von Rice [Folien] [Ergänzungen]
  • 10. Nov Semi-Entscheidbarkeit, rekursive Aufzählbarkeit, Eigenschaften rekursiver und rekursiv aufzählbarer Sprachen [Folien] [Ergänzungen]
  • 13. Nov. Die Technik der Reduktion / Hilberts zehntes Problem [Folien]
  • 17. Nov. Das Postsche Korrespondenzproblem [Folien]
  • 27. Nov. LOOP- und WHILE-Programme

Teil 2: Komplexität

  • 2.1 Die Komplexitätsklasse P
  • 2.2 Die Komplexitätsklasse NP
  • 2.3 P versus NP
  • 2.4 NP-Vollständigkeit
  • 2.5 Der Satz von Cook und Levin
  • 2.6 NP-Vollständigkeit einiger Graphenprobleme
  • 2.7 NP-Vollständigkeit einiger Zahlprobleme
  • 2.8 Übersicht über die Komplexitätslandschaft
  • 2.9 Approximationsalgorithmen für NP-harte Probleme

Materialien zur Vorlesung

Ein Skript zur Vorlesung kann hier heruntergeladen werden.

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.

Übungen

  • Die Anmeldung zu den Übungen erfolgt am Semesteranfang über campusOffice. Die Anmeldung ist bis zum 16.10.2009, 15:00 Uhr freigeschaltet.
  • Alle Teilnehmerinnen und Teilnehmer der Vorlesung sollten sich anmelden, auch wenn keine Übungsteilnahme gewünscht ist (z.B. für E-Mail-Benachrichtigung, Klausurteilnahme).
  • Es wird eine Übungsgruppe (Übungsgruppe 5, Dienstags 10:00 - 11:30, Raum 4017) speziell für Studierende des Studiengangs Technik-Kommunikation und des Lehramtsstudiums Informatik angeboten.
  • Der Raum 4017 ist der Seminarraum der Lehrstuhls. Er befindet sich im Erdgeschoss des Erweiterungsbaus 1 (E1).

Übungsblätter

Übungsgruppen

1 Mo 10:15 - 11:45, 2356|054 (5054) Andreas Tönnis
2 Mo 12:15 - 13:45, 2356|056 (5056) Wied Pakusa
3 Mo 12:15 - 13:45, 4017 Oliver Göbel
4 Mo 14:00 - 15:30, 2356|056 (5056) Viktor Engelmann
5 Di 10:10 - 11:40, 4017
(für Technik-Kommunikation und Lehramt)		 Nadine Bergner
6 Di 12:15 - 13:45, 4017 Alexander Heinsius
7 Mi 12:00 - 13:30, 4017 Faried Abu Zaid
8 Mi 12:00 - 13:30, 2356|054 (5054) Robert Schulte
9 Mi 13:30 - 15:00, 2356|019 (6019) Benjamin Kaminski
10 Mi 13:30 - 15:00, 4017 Lisa Wagner
11 Do 12:00 - 13:30, 4017 Johannes Dams

Prüfungszulassung (Bachelor Informatik)

Zur Zulassung zur Bachelor-Prüfung sind mindestens 60 Punkte zu sammeln. Hierzu gibt es folgende Möglichkeiten:
  • Je 60 Punkte in den Zulassungsklausuren (24.11.2009, 02.02.2010)
  • Je 2 Punkte pro Übungsblatt für die speziell ausgezeichnete Aufgabe
  • Je 2 Punkte für das Vortragen der Lösung einer Aufgabe in den Übungsgruppen. Insgesamt jedoch höchstens 22 Punkte.

Leistungsnachweis

Für einen Leistungsnachweis sind mindestens 60 Punkte zu sammeln. Hierzu gibt es folgende Möglichkeiten:
  • Je 60 Punkte in den Klausuren (24.11.2009, 02.02.2010)
  • Je 2 Punkte pro Übungsblatt für die speziell ausgezeichnete Aufgabe
  • Je 2 Punkte für das Vortragen der Lösung einer Aufgabe in den Übungsgruppen. Insgesamt jedoch höchstens 22 Punkte.

Kontakt

  • Alexander Skopalik
    skopalik (at) informatik (dot) rwth-aachen (dot) de
    Sprechstunde: Mittwoch 16:00 bis 17:30 und Freitag 11:00 bis 12:15 (fällt am 18.11. aus)
  • Thomas Kesselheim
    thomask (at) informatik (dot) rwth-aachen (dot) de
    Sprechstunde: TBA