Hochschule Darmstadt - Fb Informatik

Drucken| Layout| Design| Schriftgröße English|
Modulbeschreibung
Modul:Komplexitätstheorie

Theory of Complexity

Belegnummern:41.4968 [PVL 41.4969]
Sprache:deutsch
Zuordnung:Dualer Master 2013 - Katalog T: Theorieorientierte Module
JIM 2013 - Elective Catalogue T
Master 2013 - Katalog T: Theorieorientierte Module
Master 2006 - Katalog T: Theorieorientierte Module
Master 2006 - Vertiefung CG: Computer Graphik
Master 2006 - Vertiefung IS: IT-Sicherheit
Master 2006 - Vertiefung WI: Wirtschaftsinformatik
MN Data Science 2016 - Katalog M-I_I: Allgemeine Wahlpflicht Informatik
Lehrform:V+Ü = Vorlesung+Übung
SWS:3+1
CP:6
Prüfung:Klausur
Anmeldung zur Prüfung:explizit und unabhängig von der Belegung
PVL (z.B. Praktikum):unbenotet (Erfolgreiche Teilnahme an den Übungen: Die Prüfungsvorleistung ist erbracht worden, wenn 50% der Übungsaufgaben bearbeitet wurden, korrekte Lösungen für zwei Übungsaufgaben im Rahmen der Übung vorgestellt wurden und eine korrekte Musterlösung für eine Übungsaufgabe ausgearbeitet und abgegeben wurde.)
Häufigkeit des Angebots:jährlich (zuletzt im SS 2017)
Lernziele:Im Mittelpunkt stehen folgende Lernziele:
  • Verständnis grundlegender Berechnungsmodelle und der zu diesen Modellen passenden Komplexitätsmaße
  • Fähigkeit, eigenständig Komplexitätsabschätzungen vorzunehmen
  • Verständnis für grundlegende Zusammenhänge zwischen Zeit- und Platzkomplexitätsklassen
  • Verständnis für grundlegende Zusammenhänge zwischen deterministischen und nichtdeterministischen Komplexitätsklassen
  • Fähigkeit, die grundlegenden Beweismethoden nachzuvollziehen und selbständig anzuwenden
  • Kenntnis von Ansätzen zum Umgang mit algorithmisch schwierigen Problemen
Lehrinhalte:
  • Analyse von Algorithmen
    • Analyse der Laufzeit und des Speicherplatzbedarfs von Algorithmen
  • Berechnungstheorie
    • Berechnungsmodelle (Turing-Maschinen, RAM)
    • Churchsche These und erweiterte Churchsche These
    • Unentscheidbarkeit und Turing-Reduzierbarkeit
  • Grundlegende Ergebnisse aus der Komplexitätstheorie
    • Komplexitätsmaße und Komplexitätsklassen
    • Speed-up und Bandkompression
    • Hierarchiesätze
    • nichtdeterministische Turing-Maschinen sowie Kompexitätsmaße und
    • Komplexitätsklassen (inklusive grundlegender Beziehungen zwischen deterministischen und nichtdeterministischen Komplexitätsklassen)
    • deterministische versus nichtdeterministische Maschinenmodelle und formale Sprachen
  • P = NP? Problem
    • deterministische Verifizierer und die Komplexitätsklasse NP
    • polynomielle Reduzierbarkeit, NP-Vollständigkeit und NP-vollständige Probleme
  • Umgang mit NP-vollständigen Problemen (pseudo-polynomielle Algorithmen, schwach exponentielle Algorithmen, Heuristiken, Approximationsalgorithmen)
Parallel zu Vorlesung und Übung arbeiten sich die Studierenden selbständig in das Thema probabilistische Komplexitätsklassen ein (mit Verständnisabfrage in einer Klausuraufgabe).
Literatur:
  • Homer, S., Selman, A.L.: Computability and Complexity Theory, Springer New York, 2001.
  • Hromkovic, J.: Algorithmics for Hard Problems, 2nd Edition, Springer, 2003.
  • Reischuk, K.R.: Einführung in die Komplexitätstheorie, Teubner, Stuttgart,1990.
Arbeitsformen / Hilfsmittel:Vorlesung, Übung zur Diskussion von Aufgaben, die zu Hause zu bearbeiten sind; Hilfsmittel: Folien, Übungsblätter
Modulverantwortung:Steffen Lange
Freigabe ab:SS 2015
Fachliche Kompetenzen:
  • Formale, algorithmische, mathematische Kompetenzen: hoch
  • Analyse-, Design- und Realisierungskompetenzen: schwach
  • Befähigung zum Wissenschaftlichen Arbeiten: mittel
Überfachliche Kompetenzen:
  • Fachübergreifende Sachkompetenzen: Mathematische und naturwissenschaftliche Grundkompetenz

[Fachbereich Informatik] [Hochschule Darmstadt]
© 2008 - 2019 FBI OBS Team. Alle Rechte vorbehalten.