|
|
|
Komplexitätstheorie (WiSe 21/22) |
|
|
Das Semester dieser Veranstaltung ist beendet. |
|
|
grundlegende Überarbeitung: Sommersemester 2016 |
Umfang: 10.0 ECTS |
|
nächster geplanter Einsatz: -keine Angaben vorhanden- |
Autorinnen und Autoren |
|
Teilnahmevoraussetzungen |
Beschreibung |
|
|
|
|
Beschreibung |
KursbeschreibungIn der Komplexitätstheorie beschäftigt man sich damit, welche Probleme mit eingeschränkten Ressourcen (z.B. Zeit oder Speicherplatz) berechnet werden können. Man fasst Probleme dabei zu Komplexitätsklassen zusammen und untersucht deren Beziehung untereinander.
Im Kurs werden die Grundlagen der Komplexitätstheorie aus einer algorithmischen Perspektive vermittelt. Als Basistext wird das Buch von Ingo Wegener "Komplexitätstheorie: Grenzen der Effizienz von Algorithmen" verwendet. Der Leittext ergänzt mit Übungsaufgaben und Anmerkungen.
U.a. werden folgende Themen behandelt:
- grundlegende Komplexitätsklassen
- NP-Vollständigkeit
- Interaktive Beweissysteme
- probabilistische Komplexitätsklassen
- Approximation |
|
|
|
|
Material |
|
|
Diese Lehrveranstaltung beinhaltet zugriffsgeschütztes Material, das nur nach dem Einloggen und bei vorhandener Belegung der Lehrveranstaltung eingesehen werden kann. Studierende der FernUniversität sollten sich einloggen. |
|
|
|
Das für diese Veranstaltung bereits definierte Material ist noch nicht freigegeben.
Bitte versuchen Sie es später noch einmal. |
|
|
|
|
|
Zusatzveranstaltungen |
|
|
Die zu dieser Lehrveranstaltung angebotenen Zusatzveranstaltungen werden Teilnehmern nach dem Login angezeigt. |
|
|
