Einführung in die Komplexitätstheorie: Verständnis der grundlegenden Begriffe, Konzepte, Methoden und Resultate.
Grundlegende Begriffe der Komplexitätstheorie, deterministische und nicht-deterministische Komplexitätsklassen, NP-vollständige Probleme, logarithmischer Speicherbedarf, die Polynomielle Hierarchie, exponentiell schwierige Probleme, Anwendungen. Didaktisches Konzept: *) Der Stoff wird durch den LVA-Leiter präsentiert. *) Interaktion: Die TeilnehmerInnen werden durch Fragen zum Mitdenken angeregt bzw. ermutigt, selbst durch Fragen/Kommentare zur Vorlesung beizutragen. *) Hausübungen ermöglichen den TeilnehmerInnen, die in der LVA ermittelten Methoden (insbes. "saubere" mathematische Beweise von Komplexitätsresultaten) einzuüben. *) Leseaufgaben dienen dazu, dass die TeilnehmerInnen sich selbständig in verwandte/weiterführende Themen einarbeiten. Leitsungsbeurteilung: erfolgt auf der Basis der Hausübungen/Leseübungen sowie einer schriftlichen Prüfung.
Anmeldung über TISS
aktuelle Infos bitte LVA abonnieren Ort: TISS
*) Grundkenntnisse in mathematischer Logik und Grundkenntnisse in Komplexitätstheorie (entsprechend der Vorlesung "Formale Methoden der Informatik") werden vorausgesetzt. *) Die TeilnehmerInnen müssen grundlegende mathematische Fertigkeiten (wie das Ausführen von Induktionsbeweisen) entsprechend den Mathematik-LVAs im Bachelor Studium mitbringen.
