inf451 - Komplexitätstheorie

inf451 - Komplexitätstheorie

Department für Informatik 6 KP
Modulteile Semesterveranstaltungen Sommersemester 2018 Prüfungsleistung
Vorlesung
  • Kein Zugang 2.01.451 - Komplexitätstheorie Lehrende anzeigen
    • Prof. Dr. Eike Best
    • Jonas Prellberg
    • Evgeny Erofeev
    • Dr. Harro Wimmel
    • Uli Schlachter
    • Manuela Wüstefeld

    Montag: 10:00 - 12:00, wöchentlich (ab 09.04.2018), V
    Dienstag: 10:00 - 12:00, wöchentlich (ab 03.04.2018), Ü
    Termine am Dienstag, 10.07.2018 10:00 - 12:00, Montag, 01.10.2018 09:00 - 16:00, Montag, 01.10.2018 11:30 - 13:00

Übung
Hinweise zum Modul
Teilnahmevoraussetzungen
Keine Teilnehmervoraussetzungen
Prüfungszeiten
Am Ende des Semesters
Prüfungsleistung Modul
Fachpraktische Übungen und Klausur
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

Nach oben