Einführung in die Komplexitätstheorie (Sommersemester 2021)

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

Allgemeine Information

• Semesterwochenstunden: 2
• ECTS: 3
• Benotet: Ja
• Einschreibefrist: 18.03.2021 - 09.04.2021
• Lehrform: Vorlesung / Übung
• Belegungsart: Wahlpflichtmodul
• Lehrsprache: Deutsch

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 wendet, bietet eine fundierte Einführung in die Komplexitätstheorie. Schwerpunktmäßig wird die Bedeutung komplexitätstheoretischer Aussagen für den Algorithmenentwurf herausgearbeitet.

Dabei ist ein Bestandteil auch der Nachweis der theoretischen Komplexität, z.B. Reduktion auf bekannte Probleme, Beweise, und weitere Verfahren zur Laufzeitanalyse.

Literatur

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

Lern- und Lehrformen

Die Veranstaltung besteht aus regelmäßigen Vorlesungen und Übungen.

Die Vorlesung findet voraussichtlich in HS 2 statt und wird zusätzlich per Zoom live übertragen und per TeleTask aufgezeichnet. Die Details für das Zoommeeting der Vorlesung werden über das Moodle rechtzeitig bekannt gegeben.

Bitte melden Sie sich parallel zur Anmeldung beim Studienreferat auch bis zum 9. April im Moodlekurs an (der Kurs wird spätestens ab dem 7. April unten verlinkt). Termine, Ankündigungen, Materialien usw. für die Vorlesung und Übung werden über das Moodle bereitgestellt. Die Bearbeitung der Übungen kann alleine oder in Zweiergruppen erfolgen.

Hier ist der Link zum Moodlekurs.

Leistungserfassung

Die Vorlesung wird von einer wöchentlichen Übungsveranstaltung begleitet.

In der Mitte des Semesters und am Ende des Semesters wird die Leistung voraussichtlich in einer 90-minütigen Klausur geprüft. Die Endnote setzt sich zu einem Drittel aus der Zwischen- und zu zwei Dritteln aus der Endklausur zusammen.

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

Termine

Die Vorlesung findet wöchentlich am Dienstag um 11 Uhr statt, voraussichtlich in Hörsaal 2 und per Zoom.

Eine Übungsbesprechung findet wöchentlich am Mittwoch um 9:15 Uhr per Zoom statt (erster Termin: 14.04.).

Zurück