Komplexitätstheorie

Inhalte:

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

Qualifikationsziele:

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:

Die Lehrveranstaltung ist so angelegt, dass er 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.

• Moodle Lernumgebung

Forum:

Für die Lehrveranstaltung 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).

Das Forum ist über Moodle zu erreichen.

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

Lehr- und Betreuungsformen:

• Lehrveranstaltungsmaterial
• Einsendeaufgaben mit Korrektur und/oder Musterlösung
• internetgestütztes Diskussionsforum
• Studientag/e
• Betreuung und Beratung durch Lehrende

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

Verwendung des Moduls:

• B.Sc. Informatik
• M.Sc. Informatik
• M.Sc. Mathematik
• M.Sc. Praktische Informatik