Mathematik und Informatik

Komplexitätstheorie

Modulinformationen

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 wird ergänzt mit Übungsaufgaben und Anmerkungen.
 
U.a. werden folgende Themen behandelt:
- grundlegende Komplexitätsklassen
- NP-Vollständigkeit
- Interaktive Beweissysteme
- probabilistische Komplexitätsklassen
- Approximation

Vertiefungsrichtung

Angewandte Algebra und Diskrete Mathematik (AD)

ECTS10
ArbeitsaufwandBearbeiten von Basistext und Leittext: 200 Stunden
Bearbeiten von Übungs- und Einsendeaufgaben: 50 Stunden
Studientag u. Prüfungsvorbereitung: 50 Stunden
Dauer des Modulsein Semester
Häufigkeit des Modulsin jedem Sommersemester
AnmerkungDer Basistext muss vor Semesterbeginn beschafft werden. Basistext: Ingo Wegener: Komplexitätstheorie: Grenzen der Effizienz von Algorithmen, Springer, 2003. Nicht zusammen mit dem nicht mehr angebotenen Modul "Grundzüge der Komplexitätstheorie" nutzbar.
Inhaltliche VoraussetzungGrundlagen der theoretischen Informatik, wie sie z.B. im Modul "Grundlagen der Theoretischen Informatik" des Bachelorstudiengangs Informatik vermittelt  werden.

Aktuelles Angebot

Kurs 01686 Komplexitätstheorie [VU]

Prüfungsinformation

M.Sc. Praktische Informatik
 Art der PrüfungsleistungVoraussetzung
Unbenoteter Leistungsnachweisbestandene Kursabschlussklausur oder bestandenes Klausurersatzgesprächkeine
Benotete Prüfungbestandene benotete mündliche Modulprüfungkeine
 Stellenwert der Note: 1/6
M.Sc. Informatik
 Art der PrüfungsleistungVoraussetzung
Unbenoteter Leistungsnachweisbestandene Kursabschlussklausur oder bestandenes Klausurersatzgesprächkeine
Benotete Prüfungbestandene benotete mündliche Modulprüfungkeine
 Stellenwert der Note: 1/9
M.Sc. Mathematik
 Art der PrüfungsleistungVoraussetzung
Unbenoteter Leistungsnachweisbestandene Kursabschlussklausur oder bestandenes Klausurersatzgesprächkeine
Benotete Prüfungbestandene benotete mündliche Modulprüfungkeine
 Stellenwert der Note: 1/6
B.Sc. Informatik
 Art der PrüfungsleistungVoraussetzung
Benotete Prüfungbestandene benotete mündliche ModulprüfungLeistungsnachweis zu einem Modul aus dem Pflichtbereich
 Stellenwert der Note: 1/12

Download

Ansprechpartner

mathinf.webteam | 11.08.2017
FernUni-Logo FernUniversität in Hagen, Fakultät für Mathematik und Informatik
  • Logo FernUni
  • Kontakt
  • VU
  • Moodle
  • Service
  • A-Z
  • Impressum/Datenschutz
  • © FernUniversität in Hagen