11449 - Strukturelle Komplexitätstheorie Modulübersicht

Modulnummer: 11449
Modultitel:Strukturelle Komplexitätstheorie
  Structural Complexity Theory
Einrichtung: Fakultät 1 - MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik
Verantwortlich:
  • Prof. Dr. rer. nat. habil Meer, Klaus
Lehr- und Prüfungssprache:Deutsch
Dauer:1 Semester
Angebotsturnus: jedes Sommersemester gerader Jahre
Leistungspunkte: 8
Lernziele:

Ziel des Moduls ist es, grundlegende Methoden zu erlernen mit deren Hilfe es möglich ist, Probleme gemäß der inhärenten Schwierigkeit bei ihrer algorithmischen Behandlung zu klassifizieren.

Hierzu gehören:

  • das Kennenlernen sinnvoller Ressourcen zur Beurteilung der Komplexität eines Problems,
  • das Verständnis für die grundlegende Struktur von Komplexitätsaussagen,
  • das Beherrschen mathematischer Methoden zur Analyse und Klassifikation von Problemen,
  • die selbständige Umsetzung der erlernten Methoden, um die Komplexität von Problemen richtig einzuschätzen.
Inhalte:Die Vorlesung stellt eine Einführung in die Strukturelle Komplexität dar. Die dabei zentralen Fragen sind die folgenden:
  • Wie misst man sinnvoll den Aufwand, der nötig ist, ein Problem algorithmisch zu lösen?
  • Welche Ressourcen spielen dabei eine Rolle?
  • Wie lassen sich Probleme hinsichtlich dieser Ressourcen sinnvoll vergleichen und klassifizieren?
  • Was sind inhärente Hindernisse, die der Existenz beliebig guter Lösungen gewisser Probleme entgegen stehen?
Im Einzelnen werden u. a. folgende Gesichtspunke behandelt:
  • Turingmaschine, Zeit- und Platzverbrauch einer Rechnung
  • Komplexitätsklassen bzgl. Zeit- oder Platzbedarf
  • Hierarchiesätze
  • die Klassen P und NP als Formalisierung effizient lösbarer und effizient verifizierbarer Probleme
  • NP-Vollständigkeit, Reduktion
  • Satz von Cook: NP-Vollständigkeit von SAT
  • weitere Bsp. NP-vollständiger Probleme
  • Randomisierte Algorithmen und die Klassen ZPP, RP und BPP
  • Komplexitätsklassen innerhalb von P: Paralleles Rechnen und NC
  • Komplexitätsklassen jenseits von NP: die Polynomhierarchie, PSPACE und NSPACE, Zählklassen
  • Ausblicke auf andere Zugänge zu Komplexität
Empfohlene Voraussetzungen:Die Kenntnis des Modells der Turingmaschine sowie der Begriffe Entscheidungsproblem und Berechenbarkeit wird empfohlen. Zu Beginn der Vorlesung werden diese kurz wiederholt.
Zum Beispiel Kenntnis des Inhalts von Modul
  • 11787 : Theoretische Informatik
Zwingende Voraussetzungen:keine
Lehrformen und Arbeitsumfang:
  • Vorlesung / 4 SWS
  • Übung / 2 SWS
  • Selbststudium / 150 Stunden
Unterrichtsmaterialien und Literaturhinweise:
  • M. R. Garey, D. S. Johnson: Computers and Intractability, Freeman 1979
  • C. H. Papadimitriou: Computational Complexity, Addison & Wesley 1994
  • I. Wegener: Komplexitätstheorie, Springer 2003
  • J. L. Balcazar, J. Diaz, J. Gabarro: Structural Complexity I + II, Springer 1995
  • S. Arora, B. Barak: Computational Complexity, Cambridge University Press 2009
Modulprüfung:Modulabschlussprüfung (MAP)
Prüfungsleistung/en für Modulprüfung:
  • mündliche Prüfung, 30-45 Minuten
Bewertung der Modulprüfung:Prüfungsleistung - benotet
Teilnehmerbeschränkung:keine
Zuordnung zu Studiengängen:
  • M.Sc. / Angewandte Mathematik (universitäres Profil) / Prüfungsordnung 2008
  • M.Sc. / Angewandte Mathematik (universitäres Profil) / Prüfungsordnung 2019
  • M.Sc. / Informatik (universitäres Profil) / Prüfungsordnung 2008 - 2. SÄ 2017
Bemerkungen:
  • Studiengang Informatik M.Sc.: Wahlpflichtmodul in Komplex „Grundlagen der Informatik“ (Niveaustufe 400)
  • Studiengang Angewandte Mathematik M.Sc.: Wahlpflichtmodul im Komplex „Anwendungen“, Bereich „Informatik“
Veranstaltungen zum Modul:Vorlesung: Strukturelle Komplexitätstheorie
Übung zur Vorlesung
Veranstaltungen im aktuellen Semester:
  • keine Zuordnung vorhanden

Unsere Webseite verwendet Cookies. Diese haben zwei Funktionen: Zum einen sind sie erforderlich für die grundlegende Funktionalität unserer Website. Zum anderen können wir mit Hilfe der Cookies unsere Inhalte für Sie immer weiter verbessern. Hierzu werden pseudonymisierte Daten von Website-Besuchern gesammelt und ausgewertet. Das Einverständnis in die Verwendung der technisch nicht notwendigen Cookies können Sie jeder Zeit wiederrufen. Weitere Informationen erhalten Sie auf unseren Seiten zum Datenschutz.

Erforderlich

Diese Cookies werden für eine reibungslose Funktion unserer Website benötigt.

Statistik

Für den Zweck der Statistik betreiben wir die Plattform Matomo, auf der mittels pseudonymisierter Daten von Websitenutzern der Nutzerfluss analysiert und beurteilt werden kann. Dies gibt uns die Möglichkeit Websiteinhalte zu optimieren.

Name Zweck Ablauf Typ Anbieter
_pk_id Wird verwendet, um ein paar Details über den Benutzer wie die eindeutige Besucher-ID zu speichern. 13 Monate HTML Matomo
_pk_ref Wird benutzt, um die Informationen der Herkunftswebsite des Benutzers zu speichern. 6 Monate HTML Matomo
_pk_ses Kurzzeitiges Cookie, um vorübergehende Daten des Besuchs zu speichern. 30 Minuten HTML Matomo