Seminar: Komplexitätstheorie
Wintersemester 2017/2018
Inhalt
Thema der Komplexitätstheorie sind die prinzipiellen Grenzen effizienter Berechenbarkeit. Dabei beschäftigt sich die Komplexitätstheorie mit der "inhärenten Schwierigkeit" algorithmischer Probleme. Gefragt wird also nicht, wie effizient ein bestimmter Algorithmus ein Problem löst, sondern wie effizient sich sich das Problem prinzipiell lösen lässt. Effizienz wird dabei gemessen als der Verbrauch von Ressourcen wie Rechenzeit, Speicherplatzverbrauch oder der Kommunikationsbandbreite.
Eine besondere Schwierigkeit besteht darin, unterschiedliche Resourcenmaße miteinander zu vergleichen, daraus ergeben sich Fragen wie "Lässt sich jeder Speicherplatzeffiziente Algorithmus durch eine Zeiteffizienten simulieren?" oder "Arbeiten randomisierte Algorithmen prinzipiell effizienter als deterministische".
Voraussetzungen
Dieses Seminar ist an Bachelor und Master Studentinnen und Studenten gerichtet.
Für eine erfolgreiche Teilnahme am Seminar wird ein sicherer Umgang mit den Themen der Vorlesungen "Datenstrukturen und Algorithmen" und "Berechenbarkeit und Komplexität" benötigt. Kenntnisse aus der Vorlesung "Komplexitätstheorie" sind hilfreich aber nicht obligatorisch.
Organisatorisches
Die Vorträge werden in Deutsch oder Englisch gehalten.
Termine
Dieses Seminar findet als Blockseminar am Ende des Semesters statt.
Genauere Termine werden noch bekannt gegeben.
Dozenten
Anforderungen
Alle Teilnehmerinnen und Teilnehmer des Seminars erhalten je ein ausgewähltes Thema, welches normalerweise aus einem publiziertem Paper oder einem Buch stammt. Die Themen werden im ersten Seminartermin zugeteilt.
Zum erfolgreichen Bestehen des Seminars gehört das Erstellen einer 5-seitigen Ausarbeitung sowie dem halten eines 45-60 minütigen Vortrags.