English English

Termine

Art
Termin / Ort
Beginn
Dozent
V3
Di 08:30h - 09:45h / Eph
Fr 12:00h - 13:15h / Eph
16.10.2007
Vöcking

Kreditpunkte (ECTS-Credits): 6

Aktuelles

Die Ergebnisse der zweiten Bachelor-/Vordiplomsklausur vom 27.3.2008 können online eingesehen werden (nur innerhalb des RWTH-Netzes):

Die entsprechende Notenzuordnung kann man der unten angegebenen Tabelle entnehmen.
  • 1.0: 111-120 Punkte
  • 1.3: 104-110,5 Punkte
  • 1.7: 97-103,5 Punkte
  • 2.0: 90-96,5 Punkte
  • 2.3: 83-89,5 Punkte
  • 2.7: 76-82,5 Punkte
  • 3.0: 69-75,5 Punkte
  • 3.3: 62-68,5 Punkte
  • 3.7: 55-61,5 Punkte
  • 4.0: 48-54,5 Punkte
  • 5.0: 1-47,5 Punkte

Die Einsicht findet am Freitag, den 04.04.2008, um 10:30 Uhr im Seminarraum 4017 am Lehrstuhl statt.

Die mündlichen Ergänzungsprüfungen für Diplomstudierende, die den zweiten bzw. dritten Versuch nicht bestanden haben, finden am Mittwoch, den 09.04.2008 statt. Anmeldung bis Freitag, den 04.04.2008, um 12:30 Uhr im Sekretariat des Lehrstuhls.


Prüfungen

Die Ergebnisse der Bachelor-/Vordiplomsklausur vom 18.2.2008 können online eingesehen werden (nur innerhalb des RWTH-Netzes):

Die entsprechende Notenzuordnung kann man der unten angegebenen Tabelle entnehmen.
  • 1.0: 111-120 Punkte
  • 1.3: 104-110,5 Punkte
  • 1.7: 97-103,5 Punkte
  • 2.0: 90-96,5 Punkte
  • 2.3: 83-89,5 Punkte
  • 2.7: 76-82,5 Punkte
  • 3.0: 69-75,5 Punkte
  • 3.3: 62-68,5 Punkte
  • 3.7: 55-61,5 Punkte
  • 4.0: 48-54,5 Punkte
  • 5.0: 1-47,5 Punkte

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:

Teil 1: Berechenbarkeit

  • 1.1 Modellierung von Problemen
  • 1.2 Computermodelle
  • 1.3 Nicht rekursive Probleme
  • 1.4 Semi-Entscheidbarkeit und Rekursive Aufzählbarkeit
  • 1.5 Eigenschaften rekursiver und rekursiv aufzählbarer Sprachen
  • 1.6 Die Technik der Reduktion
  • 1.7 Klassische Probleme aus der Rekursionstheorie
  • 1.8 Mächtigkeit von Programmiersprachen

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 Volesung kann hier heruntergeladen werden.

Errata:

  • Seite 10 und Seite 40 wurden am 26.11. überarbeitet. Bitte neu ausdrucken ...
  • Seite 44 Zeile 18: d durch x ersetzen

Folien

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.

Vorläufiger Zeitplan

  • Übersicht (16.10.)
Berechenbarkeit:
  • Was ist ein Problem? / Erläuterung TM (19./23.10.)
  • Mehrband-TM und Universelle TM (26.10.)
  • RAM versus TM / Church-Turing-These (30.10.)
  • Unentscheidbare Probleme / Diagonalisierung (2.11.)
  • Unentscheidbarkeit des Halteproblem (6.11.)
  • Unterprogrammtechnik / spezielles Halteproblem (9.11.)
  • Der Satz von Rice (13.11.)
  • Semi-Entscheidbarkeit und Rekursive Aufzählbarkeit (16.11.)
  • Eigenschaften rekursiver und rekursiv aufzählbarer Sprachen (20.11.)
  • Die Technik der Reduktion (23.11.)
  • Mächtigkeit von Programmiersprachen (27.11./30.11.)
  • Klassische Probleme aus der Rekursionstheorie I 4.12.)
  • Tag der Informatik (7.12.)
  • Klassische Probleme aus der Rekursionstheorie II (11.12.)
  • Präsensübung / Scheinklausur (14.12.)
Komplexität:
  • Die Komplexitätsklassen P und NP (18.12.)
  • Weihnachtspause (20.12. bis 5.1.)
  • Die Komplexitätsklassen P und NP (8.1.)
  • Polynomielle Reduktionen, NP-Vollständigkeit (11.1.)
  • NP-Vollständigkeit / Satz von Cook (15.1.)
  • Satz von Cook / NP-Vollständigkeit von Clique (18.1.)
  • NP-Vollständigkeit von Hamiltonkreis (22.1.)
  • NP-Vollständigkeit von Zahlproblemen (25.1.)
  • Übersicht über die Komplexitätslandschaft (29.1.)
  • Präsenzübung / Scheinklausur (1.2.)
  • Approximierbarkeit / Zusammenfassung (5./8.2.)

Übungen

  • Die Anmeldung zu den Übungen erfolgt am Semesteranfang per Web. Das i1 Übungsportal ist bis zum 18.10.07, 12:00 Uhr, für die Übungsanmeldung freigeschaltet. Ab Freitag 19.10.07 wird dort die Zuteilung der Übungsgruppen bekannt gegeben.
  • Jeder Teilnehmer der Vorlesung sollte sich bei obigem Übungsportal anmelden, auch wenn keine Übungsteilnahme gewünscht ist (z.B. für eMail -Benachrichtigung, Klausurteilnahme). In diesem Fall bitte keinen "Wunschtermin" auswählen.
  • Es wird eine Übungsgruppe (Übungsgruppe 7, Mittwochs 12:00 - 13: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).
  • Die Zuordnung zu den Übungsgruppen ist abgeschlossen. Das Ergebnis kann über das Übungsportal abgerufen werden.
  • Raumänderung: Die Übungsgruppe 2 montags um 10:15 findet im Raum 4017 statt und nicht in 5054.
Es gibt eine Liste von Fragen zum Thema Berechenbarkeit und eine Liste von Fragen zum Thema Komplexität , die zur Klausurvorbereitung hilfreich sind.

Prüfungen

  • Voraussetzung für den Erwerb eines Leistungsnachweises (Schein) ist die erfolgreiche Teilnahme an zwei speziellen Präsenzübungen. Diese finden unter Klausurbedingungen Ende Dezember und Ende Januar statt.
  • Die Vordiploms- bzw. Bachelorprüfung findet 18.02.2008 statt.
  • Notwendige Voraussetzung für die Zulassung zur Bachelorprüfung ist der Teilnahmenachweis. Für Studierende des Diplomstudiengangs ist dieser nicht erforderlich.

Kontakt

skopalik (at) informatik (dot) rwth-aachen (dot) de

Sprechstunde: Montags 16:00 bis 17:30 und Mittwochs 10:30 bis 12:00