Die Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Verwaltung des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Mathematik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Universität Bremen
Zeige Wirtschaftsinformatik-Format Pdf_icon Systems Engineering-Format Pdf_icon Informatik-Format Pdf_icon Digitale Medien-Format Pdf_icon

Wirtschaftsinformatik-Ansicht

Komplexitätstheorie


Complexity Theory
Modulnummer
Bachelor
Pflicht/Wahl
Winf-Schwerpunkt-Pflicht
Winf-Schwerpunkt-Wahlpflicht
Wahl
Schwerpunkt
IT-Management
E-Business
Logistik
Computational Finance
Anzahl der SWS
V UE K S Prak. Proj.
0 0 4 0 0 0 4
Kreditpunkte : 6 Turnus

i.d.R. unregelmäßig angeboten

Formale Voraussetzungen : -
Inhaltliche Voraussetzungen : Grundlagen zu Berechenbarkeit und Komplexität aus Theoretische Informatik 2
Vorgesehenes Semester : ab 1. Semester
Sprache : Deutsch
Ziele :
  • Mathematische Beweise verstehen können und in der Lage sein, einfache Beweise selbst zu führen.

  • Kenntnis der wichtigsten Komplexitätsklassen und ihrer Zusammenhänge erworben haben.

  • Den kombinatorischen Charakter von NP-vollständigen Problemen verstehen und die Berechnungskomplexität von typischen Informatik-Problemen grob einschätzen können.

  • Das Werkzeug der Reduktion kennen und in Beispielen anwenden könenn.

  • Einblick haben in die Grenzen der effizienten Berechenbarkeit und in die Schwierigkeiten der Komplexitätstheorie.

Inhalte :

Die Komplexitätstheorie beschäftigt sich mit den Grenzen der Berechenbarkeit unter beschränkten Ressourcen: welche Probleme lassen sich mit einem bestimmten Aufwand an Zeit (oder anderen Ressourcen) lösen, welche nicht? Sie stellt damit eine wichtige Grundlage für den Entwurf und das Verständnis von effizienten Algorithmen dar und versucht darüberhinaus, die natürliche Neugier nach dem in der Informatik prinzipiell machbaren zu befriedigen. Die Vorlesung beschäftigt sich mit folgenden Themen:

  • Grundlegende Begriffe wie Reduktionen, Härte und Vollständigkeit
  • Das P vs. NP Problem und dessen Variationen
  • NP-vollständige Probleme aus verschiedenen Teilgebieten der Informatik
  • Hierarchietheoreme und verwandte Resultate
  • Platzkomplexitätsklassen wie PSpace und LogSpace
  • Schaltkreiskomplexität und effiziente Parallelisierbarkeit
  • Die polynomielle Hierarchie
Unterlagen (Skripte, Literatur, Programme usw.) :
  • Oded Goldreich. Computational Complexity: a Conceptual Perspective. Cambridge University Press, 2008.
  • Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
  • Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  • Ingo Wegener. Komplexitätstheorie - Grenzen der Effizienz von Algorithmen. Springer, 2003.
  • Michael Sipser. Introduction to the Theory of Computation (2nd Edition). Thomson Course Technology, 2006
Form der Prüfung : Übungsaufgaben und Fachgespräch oder mündliche Prüfung
Arbeitsaufwand
Präsenz 56
Übungsbetrieb/Prüfungsvorbereitung 124
Summe 180 h
Lehrende: Prof. Dr. C. Lutz Verantwortlich Prof. Dr. C. Lutz
Zurück

Zeige Wirtschaftsinformatik-Format Pdf_icon Systems Engineering-Format Pdf_icon Informatik-Format Pdf_icon Digitale Medien-Format Pdf_icon