Komplexitätstheorie (Sommersemester 2016)

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

Allgemeine Information

• Semesterwochenstunden: 4
• ECTS: 6
• Benotet: Ja
• Einschreibefrist: 22.04.2016
• 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.

Voraussetzungen

 

Literatur

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

 

Lern- und Lehrformen

Vorlesung, Übungen.

Die Vorlesung wird auf www.tele-task.de live übertragen und steht dort im Archiv zur Verfügung.

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 gibt es eine 90-minütige Zwischenklausur.

Am Semesterende gibt es eine  30-minütige mündliche Prüfung.  

Die Endnote setzt sich zu 30% aus der Zwischenklausur und 70% aus der mündlichen Prüfung zusammen.

Nach Bekanntgabe der Note aus der mündlichen Prüfung 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

Vorlesung:

• Mi.  11:00-12:30 Uhr, HS 3 

• Do. 11:00-12:30 Uhr, HS 2   

Übungen:

• Mo. 13:30 Uhr, A-1.1

• Erste Sitzung findet am 25.04 statt.

Allgemeine Hinweisungen zum Übungsbetrieb:

• Die Anmeldung zur Übung  per Email an nuhad.shaabani(at)hpi.de.
• Gruppenarbeit ist erwünscht.  Jedes Übungsblatt kann von maximal 3 Studenten bearbeitet werden.
• Aktive Teilnahme an der Lösung der Aufgaben. 
• Die Lösungen sollen nicht  handschriftlich  sondern im PDF-Format abgegeben werden. 

Zurück