inf451 - Komplexitätstheorie (Vollständige Modulbeschreibung)

inf451 - Komplexitätstheorie (Vollständige Modulbeschreibung)

Originalfassung Englisch PDF Download
Modulbezeichnung Komplexitätstheorie
Modulkürzel inf451
Kreditpunkte 6.0 KP
Workload 180 h
Einrichtungsverzeichnis Department für Informatik
Verwendbarkeit des Moduls
  • Master Informatik (Master) > Theoretische Informatik
Zuständige Personen
  • Lehrenden, Die im Modul (Prüfungsberechtigt)
  • Lehrenden, Die im Modul (Modulverantwortung)
Teilnahmevoraussetzungen
Keine Teilnehmervoraussetzungen
Kompetenzziele
Thema des Moduls ist die Berechnungskomplexität algorithmischer Probleme. Darunter versteht man die Fragen, wie viel Rechenzeit, wie viel Speicherplatz und wie viel Prozessor- oder (Hardware-)Ressourcen benötigt werden, um ein algorithmisches Problem zu lösen. Da genaue Antworten auf diese Fragen in der Regel sehr schwer zu geben sind, ist man an annäherungsweisen Aussagen interessiert. Konkrete Probleme möchte man klassifizieren, mit Hilfe möglichst effizienter Algorithmen lösen, und man möchte nach Möglichkeit untere Effizienzschranken nachweisen. Die Inhalte, die in diesem Modul gelehrt werden, sind allgemein und hängen weder vom benutzten algorithmischen Modell noch von der gewählten Programmiersprache ab.
Fachkompetenzen
Die Studierenden:
  • verenden Turingmaschinen und deren Varianten - definieren Zeit-, Raum- und Hardwarebedarf algorithmischer Probleme
  • benennen relevante Komplexitätklassen
  • schätzen wichtige Probleme bezüglich ihrer Komplexität ein
Methodenkompetenzen
Die Studierenden:
  • analysieren die Komplexität von Algorithmen
  • setzen Techniken der Simulation, der Reduktion und der Diagonalisierung ein
  • schätzen Probleme bzgl. ihrer Komplexität ein und vergleichen sie mit bekannten Problemen
Sozialkompetenzen
Die Studierenden:
  • stellen Beweis, Beweisskizzen und algorithmische Lösungen in der Übung vor
Modulinhalte
  • Mathematische Grundlagen
  • Turingmaschinen, Registermaschinen
  • Raum- und Zeitkomplexitätsklassen, Äquivalenzsätze, Hierarchiesätze
  • Komplexitätsklassen P, NP, NPC und PSPACE
  • Alternierende Automaten und die polynomiale Zeithierarchie
  • Schaltkreise
Literaturempfehlungen
  • Eike Best: Skript zur Vorlesung (2015)
  • Michael R. Garey, David S. Johnson: Computers and Intractability.Freeman, New York (2003).
  • Steven Homer, Alan L. Selman: Computability and Complexity Theory. Springer (2000).
  • John E. Hopcroft, Jeffrey D. Ullmann: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979).
  • Rüdiger Reischuk: Komplexitätstheorie. 2. Auflage. Teubner, Stuttgart/Leipzig (1999).
  • Michael Sipser: Introduction to the Theory of Computation. Third Edition, Cengage (2005).
Links
Unterrichtssprache Deutsch
Dauer in Semestern 1 Semester
Angebotsrhythmus Modul unregelmäßig
Aufnahmekapazität Modul unbegrenzt
Lehr-/Lernform 1VL + 1Ü
Vorkenntnisse keine
Lehrveranstaltungsform Kommentar SWS Angebotsrhythmus Workload Präsenz
Vorlesung 2 SoSe 28
Übung 2 SoSe 28
Präsenzzeit Modul insgesamt 56 h
Prüfung Prüfungszeiten Prüfungsform
Gesamtmodul
Am Ende des Semesters
Fachpraktische Übungen und Klausur