Hauptinhalt
Topinformationen
Komplexitätstheorie
DozentIn: Dr. rer. nat. Friedrich Bökler
Veranstaltungstyp: Vorlesung und Übung
Ort: 32/109
Zeiten: Mi. 10:00 - 12:00 (wöchentlich) - Übung, Do. 14:00 - 16:00 (wöchentlich) - Vorlesung
Beschreibung: In der Komplexitätstheorie knüpfen wir an die Inhalte der "Einführung in die theoretische Informatik" an. Wir nutzen mathematische Methoden, um Komplexitätsklassen und Berechnungsmodelle zu untersuchen. Zum Beispiel platzbeschränkte, randomisierte und Orakel-Turingmaschinen, Schaltkreiskomplexität, interaktive Beweissysteme und die Komplexität von Zähl- und Black-Box-Problemen.
Ein tiefes Verständnis der Inhalte der "Einführung in die theoretische Informatik" wird vorausgesetzt. Des Weiteren sind die Inhalte der "Einführung in die Algorithmik" (oder alternativ "Einführung in die Algorithmen und Datenstrukturen"), "Einführung in die Technische Informatik", sowie "Einführung in die Stochastik für Informatiker" hilfreich.
