Komplexitätstheorie (Sommersemester 2012)

Dozent: Prof. Dr. Christoph Meinel (Internet-Technologien und -Systeme)

Allgemeine Information

• Semesterwochenstunden: 4
• ECTS: 6
• Benotet: Ja
• Einschreibefrist: 1.4.2012 - 25.4.2012
• Lehrform: VU
• Belegungsart: Wahlpflichtmodul

Studiengänge, Modulgruppen & Module

Beschreibung

Ziel der Komplexitätstheorie ist die Quantifizierung von Computerressourcen (Rechenzeit, Speicherplatz, Hardwareaufwand, Kommunikationsaufwand, ...), die zur algorithmischen Lösung konkreter Probleme bzw. von Problemklassen benötigt werden. Die Vorlesung, die sich an Master-Studenten der Studiengänge IT Systems Engineering, Informatik und Mathematik wendet, bietet eine fundierte Einführung in die Komplexitätstheorie. Schwerpunktmäßig wird die Bedeutung komplexitätstheoretischer Aussagen für den Algorithmenentwurf herausgearbeitet.

Literatur

• Skript zur Vorlesung
• Christos H Papadimitriou: Computational Complexity. Addison Wesley, 1994

 

Übungsblätter

Die Lösungen können Mittwochs vor der Übung oder alternativ im Kasten im Foyer des Hauptgebäudes abgegeben werden.

• 1. Übungsblatt vom 12.04.2012 (PDF)
  Aufgrund der verkürzten Bearbeitungszeit muss von den Aufgaben 1.1 und 1.2 nur eine Aufgabe nach Wahl bearbeitet werden
• 2. Übungsblatt vom 19.04.2012 (PDF)
• Im HPI-Ordner R:\Komplexitaetstheorie: Programm-Datei leantm.pl -- Bearbeitungshinweis: Dies ist das PROLOG-Programm des Turingmaschinen-Simulators <a href=leantm.pl>leanTM</a>. Sie benoetigen zur Ausfuehrung ein PROLOG-System. Wir empfehlen <a href=www.swi-prolog.org> SWI-PROLOG</a>, das fuer alle populaeren Plattformen kostenlos erhaeltlich ist."
• 3. Übungsblatt: im HPI-Ordner R:\Komplexitaetstheorie (27.04.)

Lern- und Lehrformen

Vorlesung mit Übung

Leistungserfassung

Die Vorlesung wird von einer wöchentlichen Übungsveranstaltung begleitet. Zudem sind wöchentlich Übungsaufgaben zu lösen und in der Übungsveranstaltung vorzurechnen.

In der Mitte des Semesters und am Semesterende wird die Leistung in einer 90-minütigen Klausur geprüft. Die Endnote setzt sich zu 30% aus der Zwischen- und 70% aus der Endklausur zusammen.

Nach Bekanntgabe der Note aus der Endklausur besteht die Möglichkeit, sich freiwillig mündlich prüfen zu lassen, um die Abschlussnote unter Berücksichtigung der vorherigen Klausur- und Übungsleistung zu verbessern.

Voraussetzung zur Teilnahme an sämtlichen Prüfungen ist das Erreichen von 50% der Übungspunkte sowohl vor als auch nach der Zwischenklausur.

Termine

siehe vorl. Stundenplan,

Übung

• neuer Übungstermin!
  Mittwoch, 15:15 - 16:45 Uhr, am 18.04. in HS 2, ab 25.04. in H-2.58

Zurück