50 years Univerity of Lübeck

Institute for Theoretical Computer Science

SS 2007 – Einführung in die Informatik IV


Classification and Contents

Title Einführung in die Informatik IV
Lecturer Prof. Reischuk
Classification Diplom-Studiengang 4. Semester Pflicht
Bachelor-Studiengang 4. Semester Pflicht
Contents
  • Modellierung, Analyse und Lösung algorithmischer Probleme
  • Algorithmische Komplexität: Komplexitätsmaße, Komplexitätsklassen, NP-Vollständigkeit, Erfüllbarkeitsprobleme der Logik, diskrete Optimierungsprobleme
  • Formale Sprachen: Formale Grammatiken, reguläre Sprachen und Ausdrücke, kontextfreie und kontextsensitive Sprachen, Chomsky Hierarchie, Pumping Lemma, Wortprobleme
  • Maschinenmodelle: endliche Automaten, Turing-Maschinen, Registermaschinen, Determinismus, Nichtdeterminismus, Reduktion zwischen Problemen, Simulation, Entscheidbarkeit, Aufzählbarkeit
Literature
  • [HU94] J. Hopcroft, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Add.Wesley 1994
  • [Ha78] M. Harrison: Introduction to Formal Language. Theory. Add.Wesley 1978
  • [Sa98] J. Savage: Models of Computation. Add.Wesley 1998
  • [Re98] R. Reischuk: Komplexitätstheorie, Band I: Grundlagen, Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus.Teubner 1998
  • [GJ79] M. Garey, D. Johnson: Computers and Intractability. Freeman, 1979
  • [KT05] J. Kleinberg, E. Tardoz: Algorithmen Design. Add. Wesley 2005
Wiki Wiki zur Veranstaltung »Einführung in die Informatik – IV«

Lecture

Lecturer Prof. Reischuk
Credits 4 SWS, ECTS-Credits: 9
Hours We 8.00h-10.00h, T1 and Fr. 8.00h-10.00h, H1

Exercises

Assistent Hinkelmann
Credits 3 SWS
Hours Group 1: Mo. 14.00h-16.00h + Do. 11.00h-12.00h Seminarraum Informatik 4 (Minsky)
Group 2: Mo. 14.00h-16.00h + Do. 11.00h-12.00h Seminarraum Informatik 2+3 (Cook+Karp)
Group 3: Mo. 14.00h-16.00h ITCS seminar room, 2nd floor + Fr. 10.00h-11.00h H2