50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Algorithmen, Komplexitätstheorie und Formale Sprachen


Type and Content

Title: Algorithmen, Komplexitätstheorie und Formale Sprachen
Host: Reischuk
Classification: Diplom-Studiengang Informatik 5. Semester, Pflicht
Bachelor-Studiengang Informatik, mit Ergänzungsfach Bioinformatik/Biomathematik, 5. Semester, Wahlpflicht
Conentent:
  • Entwurf und Analyse effizienter Algorithmen,
  • Komplexität algorithmischer Probleme,
  • Maschinenmodelle,
  • Berechenbarkeit,
  • Rekursionstheorem,
  • Sprachfamilien,
  • Hierarchien
Literature:
  • Aho, Hopcroft, Ullman, Design and Analysis of Computer Algorithms, Addison Wesley 1978
  • Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press 1990
  • R. Reischuk, Komplexitätstheorie, Band I: Grundlagen, Teubner 1998
  • Hopcroft, Ullman, Introduction to Automata Theory, Languages and Computation, Addison Wesley 1979
  • Harrison, Introduction to Formal Language Theory, Addison Wesley 1978
  • Kleinberg, Tardos, Algorithm Design, Addison Wesley 2005

Lecture

Host: Reischuk
Hours: 4 SWS, 8 ETCS
Dates: Mi. + Fr. 8h -10h, Raum R3
Skripte: 1. Quiz (Rekursionstheorie)

Exercise

Host: Reischuk, Hinkelmann
Hours: 2 SWS
Dates: Diplom: 2 SWS Übungen (2 Gruppen)
Mo. 16h -18h, Raum H4, ITCS Seminarraum Nr. 21, S 3b

Bachelor: 2 SWS Übung (1 Gruppe)
Mo. 16h -18h, Raum Seminarraum 1 (Minsky), ITCS Seminarraum Nr. 21, Notebookarbeitsraum (Neumann) Geb. 64, EG

Gruppe:
  • I – Seminarraum TCS
  • II – Seminarraum I (Gödel)
  • III – Seminarraum VK / V1
Übungsblätter: