Logo der Fakultät Logo LG Theoretische Informatik
 

Kurs 1686

Illustration

Komplexitätstheorie

Betreuung:

Prof. Dr. André Schulz

ECTS: 10 (SWS: 4 , Übungen: 2 SWS)

Arbeitsaufwand: 300 Stunden

Häufigkeit: in jedem Sommersemester

Dauer Modul: ein Semester


Inhalt:

In 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.

Wegener


Webseite des Buches beim Verlag

Buchinformationen

Folgende Themen werden behandelt (Auszug)

  • grundlegende Komplexitätsklassen
  • NP-Vollständigkeit
  • Interaktive Beweissysteme
  • probabilistische Komplexitätsklassen

Für folgende Informatik-Studiengänge vorgesehen: B (über Katalog M), D, L, M, MC.

Lernergebnisse / Kompetenzen:

Die Studierenden können sicher mit den wichtigsten Komplexitätsklassen umgehen, sie kennen zudem die zu Grunde liegenden Berechnungsmodelle. Die Studierenden haben ein Verständnis für die Grenzen der effizienten Berechenbarkeit erworben, und sind in der Lage, Probleme hinsichtlich ihrer algorithmischen Komplexität einzuschätzen und in Komplexitätsklassen richtig einzuordnen.

Moodle und Virtueller Studienplatz:
Alle wichtigen Dokumente finden sich im Virtuellen Studienplatz. Der Kurs ist aber so angelegt, dass er am besten aus der Moodle Lernumgebung zu benutzen ist. Dort sind alle wichtigen Informationen und Dokumente noch einmal zusammenhängend aufgeführt, und im Nachrichtenforum können kurzfristige Ankündigungen abgerufen werden.

Forum:

Für den Kurs haben wir ein Forum eingerichtet, welches im Gegensatz zu einem reinen Diskussionsforum als Frage und Antwort Forum organisiert ist. Alle Teilnehmenden sind aufgerufen nicht nur Fragen in dieses Forum zu stellen, sondern sich auch aktiv bei der Beantwortung von Fragen einzubringen. Die Nutzung des Forums erfordert eine Anmeldung. Sie müssen sich nicht mit ihrem Klarnamen anmelden (dürfen das aber).

Lesen Sie sich bitte auf den Webseiten des Forums die Richtlinien in den FAQs durch. Wer sich erfolgreich in die Betreuung des Forums einbringt, erhält Privilegien für die Moderation des Forums.

Inhaltliche Voraussetzungen:

Grundlagen der theoretischen Informatik, wie sie z.B. im Modul "Grundlagen der Theoretischen Informatik" des Bachelorstudiengangs Informatik vermittelt werden.

Detaillierter studentischer Arbeitsaufwand:

Bearbeiten von Basistext und Leittext 200 Stunden

Bearbeiten von Übungs- und Einsendeaufgaben 50 Stunden

Studientag u. Prüfungsvorbereitung 50 Stunden

Anmerkung:

Der Basistext muss vor Semesterbeginn beschafft werden. Nicht zusammen mit dem nicht mehr angebotenen Modul "Grundzüge der Komplexitätstheorie" nutzbar.

Termine:

Studientag Kurs 01686 in Hagen
Datum: am 15.07.17
Ort: FernUniversität Hagen

Christoph Doppelbauer | 03.08.2017
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen