Universität Paderborn - Home deutsch english Universität Paderborn
Die Universität der Informationsgesellschaft  42  

Sie befinden sich auf den alten Webseiten der Arbeitsgruppe!

Die aktuelle Version finden Sie unter http://www.cs.uni-paderborn.de/fachgebiete/ag-bloemer/lehre.

Inhalt dieser Seite:

Fachgebiet Codes und Kryptographie

Komplexitätstheorie (SS 2006)

Modulinformationen [^]

Für weiterführende Informationen siehe auch den Eintrag im Modulhandbuch.

Inhalt [^]

Die Komplexitätstheorie ist eine wichtige Ergänzung der Theorie der Algorithmen. Ihr Ziel ist es zu verstehen, warum gewisse Berechnungsprobleme schwierig sind und diese anhand ihrer Schwierigkeit zu klassifizieren. Das bekannteste und wichtigste Beispiel ist die Theorie der NP-Vollständigkeit.

Inhaltliche Gliederung:

  1. Komplexitätsklassen, P vs. NP
  2. Reduktionen und Vollständigkeit
  3. Platzkomplexität
  4. Hierarchiesätze
  5. Relativierung
  6. Polynomialzeit-Hierarchie
  7. Probalistische Komplexitätsklassen
  8. Approximationsalgoritmen

Prüfung [^]

Gegen Ende der vorlesungsfreien Zeit bieten wir am

eine letzte Möglichkeit für eine mündliche Prüfung an.

Die Anmeldung erfolgt, sofern Sie sich nicht über ihr Prüfungssekretariat anmelden müssen, bis spätestens zum 18. September 2006 durch eine formlose eMail an mra@upb.de. Geben Sie dabei bitte auf jeden Fall ihre Matrikelnummer und ihren Studiengang an.

Übersicht der Anmeldungen

Halten sie sich zunächst bitte beide Tage frei. Wir werden ihnen im Anschluss an die Anmeldung so bald wie möglich einen freien Termin zuteilen.

Sie können sich, sofern Ihre Prüfungsordnung dies nicht andersweitig regelt, bis zu 7 Tage vor Ihrem Prüfungstermin ohne Angabe von Gründen von der Prüfung wieder abmelden. Auch hierzu genügt eine formlose eMail an die obige Adresse.

Termine [^]

Skript [^]

Hier erscheint im Laufe des Semesters das Skript für die Vorlesung. Zur Nacharbeit und Vertiefung wird die unten angegebene Literatur empfohlen.

Heim-Übungen [^]

Hier erscheinen im Laufe des Semesters die Übungen zur Vertiefung des Lehrstoffes in Heimarbeit. Im Rahmen der Übung werden jede Woche einige Lösungen der Übungsaufgaben präsentiert. Musterlösungen zu den Übungsaufgaben werden gegebenenfalls an dieser Stelle erscheinen.

Mit einem (*) gekenntzeichnete Aufgaben können sicht unter Umständen als etwas kniffliger erweisen. Lassen Sie sich davon nicht entmutigen und versuchen Sie, die Aufgaben dennoch zu lösen!

Wir fordern Sie jedoch ausdrücklich auf, in kleinen Gruppen (2-3 Personen) gemeinsam die Vorlesung nachzuarbeiten und die Übungen zu bearbeiten. Für den Lernerfolg (und den Spaß am Studieren) ist das sehr förderlich. Sie dürfen Ihre Übungen auch in solchen Gruppen abgeben.

Präsenz-Übungen [^]

Im Rahmen der zweiwöchentlich stattfindenden Tutorien werden spezielle Präsenz-Übungsaufgaben in der Gruppe gemeinsam bearbeitet. Die Präsenzaufgaben werden im Tutorium ausgeteilt und erscheinen vorerst nicht auf dieser Webseite.

Es wird keine Musterlösungen zu den Präsenzaufgaben geben, diese werden im Tutorium besprochen.

Bonuspunkte [^]

Es wird keine Bonuspunktregelung geben. Erbrachte Leistungen in Tutorien und Übungszettelabgabe werden jedoch wohlwollend bei der Benotung der mündlichen Prüfung berücksichtigt.

Literatur [^]


Letzte Änderung Mon, 7. Aug 2006, 11:07 CEST von