Komplexitätstheorie (Sommersemester 2014)

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

General Information

• Weekly Hours: 4
• Credits: 6
• Graded: yes
• Enrolment Deadline: 1.4.2014 - 28.4.2014
• Teaching Form: VU
• Enrolment Type: Compulsory Elective Module

Programs, Module Groups & Modules

Description

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.

Literature

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

• Aufzeichnung im tele-TASK Portal

 

Learning

Vorlesung mit Übung

 Allgemeine Hinweisungen zum Übungsbetrieb:

• Die Anmeldung zur Übung muss elektronisch erfolgen. Unter http://fb10lehre steht dazu eine Webapplikation bereit, in der auch im Verlauf des Semesters die Übungspunkte eingesehen werden können. Außerdem können dort auch die Übungsaufgaben heruntergeladen sowie die Lösungen als PDF hinterlegt werden. Der Server fb10lehre ist nur HPI-intern zu erreichen, für die Anmeldung muss die HPI OpenID verwendet werden.
• Gruppenarbeit ist erwünscht.  Jedes Übungsblatt kann  von maximal 3 Studenten bearbeitet warden.
• Die Lösungen sollen nicht  handschriftlich  sondern im PDF-Format abgegeben werden. 

Examination

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. 

Dates

Vorlesung:

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

Übungen:

• Mo. 13:30 Uhr, A-1.2
• Das erste Treffen findet am 14.04 statt.

Zwischenklausur

• Mi. 04.06.2014 
• Schriftlich

Endklausur

• N.N.

Zurück