Die Einsicht zur Nachschreibeklausur findet am Donnerstag den 28.03.2013 im Raum 6103 am LuF Theoretische Informatik statt.
| Matrikelnummer | Uhrzeit |
|---|---|
| 0-300766 | 9:00-9:30 |
| 300767-310601 | 9:30-10:00 |
| 310602-999999 | 10:00-10:30 |
Die vorläufigen Ergebnisse der zweiten Klausur finden sich hier (nur aus dem RWTH-Netz / per VPN erreichbar).
Berechenbarkeit und Komplexität (WS 2012/13)
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.
Anmeldung zu den Übungsgruppen
Bitte melden Sie sich zu den Übungsgruppen über Campus Office an (bis Freitag den 12. Oktober). Die Übungen starten erst ab dem 15. Oktober. Sie können sich jetzt bereits anmelden. In der ersten Vorlesungsstunde wird genaueres erläutert. Falls Sie jetzt also nicht wissen, wie man mit Campus Office umgeht, dann wird es Ihnen in der Vorlesung erklärt.Inhalt
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:
Teil 1: Berechenbarkeit
- Kapitel 1: Einführung und Grundlagen
- Kapitel 2: Modellierung von Rechnern und Programmiersprachen
- Kapitel 3: Nichtberechenbare Probleme
Teil 2: Komplexität
- Kapitel 4: Die Komplexitätsklassen P und NP
- Kapitel 5: NP-Vollständigkeit
- Kapitel 6: Heuristiken und Approximationsalgorithmen für NP-harte Probleme
Downloads
- Skript
- Folien 1
- Folien 2
- Folien 3
- Folien 4
- Folien 5
- Folien 6
- Folien 7
- Folien 8
- Folien 9
- Folien 10
- Folien 11
- Folien 12
- Folien 13
- Folien 14
- Folien 15
- Folien 16
- Folien 17
- Folien 18
- Folien 19
Übungsblätter
- Blatt 1 (Lösungsvorschläge)
- Blatt 2 (Lösungsvorschläge)
- Blatt 3 (Lösungsvorschläge)
- Blatt 4 (Lösungsvorschläge)
- Blatt 5 (Lösungsvorschläge)
- Blatt 6 (Lösungsvorschläge)
- Blatt 7 (Lösungsvorschläge)
- Blatt 8 (Lösungsvorschläge)
- Blatt 9 (Lösungsvorschläge)
- Blatt 10 (Lösungsvorschläge)
- Blatt 11 (Lösungsvorschläge)
- Blatt 12 (Lösungsvorschläge)
Probeklausur
Literatur
- 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.