Seminar: Komplexitätstheorie

 

Wintersemester 2017/2018

 
Handapparat des Lehrstuhls Informatik 7 in der Informatikbibliothek Urheberrecht: M. Ritzert

Ansprechpartner

Telefon

work
+49 241 80 21714

E-Mail

E-Mail
 
 

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

Martin Grohe
Christof Löding

 

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.