50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Intensivkurs Berechenbarkeit und Komplexität


 

Veranstaltungsart und -inhalt
Titel Intensivkurs Berechenbarkeit und Komplexität
Dozent Prof. Dr. Rüdiger Reischuk Oliver Witt, M.Sc.
Voraussetzungen / Organisatorisches Bachelor-Absolventen, die das Masterstudium Informatik an der Universität zu Lübeck beginnen wollen, und im Bereich der Theoretische Informatik über geringere Kenntnisse verfügen als im Lübecker Bachelorstudiengang vermittelt wird

10-tägige LV, jeweils 2 x 1,5h vormittags und 2 x 1,5h nachmittags teils als Vorlesung, teils seminaristisch, teils als Übung
Termine Kurs, Anmeldung bis 19.9.2013 bei [email protected] Zeit und Ort: Blockveranstaltung 23.9.2013 9:00 - 07.10.2012 18:00, Seminarraum ITCS 2021, Geb. 64, 2.OG
Inhalte
  • kurze Auffrischung: Formale Sprachen, Grammatiken und Automaten das Turing-Maschinenmodell, (Un-)Entscheidbarkeit und Aufzählbarkeit Halteproblem, Church-Turing These, Satz von Rice Platz- und Zeitmaße, Effizienz, Komplexitätsklassen Polynomialzeitreduktion, NP-Vollständigkeit Erfüllbarkeitsproblem, graphtheoretische Optimierungsprobleme
  • Modellierung und Analyse algorithmischer Konzepte beherrschen Möglichkeiten und Grenzen der Informatik beurteilen können algorithmische Probleme nach ihrer Komplexität klassifizieren können
    		•
    Empfohlene Literatur
    • J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley
    • S. Arora, B. Barak, Computational Complexity, Cambridge University Press
    Wiki Wiki »Intensivkurs«