50 Jahre Uni Lübeck

Institut für Theoretische Informatik

SS 2007 – Einführung in die Informatik IV


Veranstaltungsart und -inhalt

Titel Einführung in die Informatik IV
Dozent Prof. Reischuk
Einordnung Diplom-Studiengang 4. Semester Pflicht
Bachelor-Studiengang 4. Semester Pflicht
Inhalte
  • 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
Buchempfehlungen
  • [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«

Vorlesung

Dozent Prof. Reischuk
Umfang 4 SWS, ECTS-Credits: 9
Termine Mi. 8.00h-10.00h, Raum T1/Transistorium und Fr. 8.00h-10.00h, H1

Übung

Assistent Hinkelmann
Umfang 3 SWS
Termine Gruppe 1: Mo. 14.00h-16.00h + Do. 11.00h-12.00h Seminarraum Informatik 4 (Minsky)
Gruppe 2: Mo. 14.00h-16.00h + Do. 11.00h-12.00h Seminarraum Informatik 2+3 (Cook+Karp)
Gruppe 3: Mo. 14.00h-16.00h ITCS-Seminarraum 2. OG. Zi. 2021 + Fr. 10.00h-11.00h H2