Theoretische Grundlagen der Informatik //
Theoretical Foundations of Computer Science

Termin: Mi 8.30-10 h/D 301 (V), Fr 12-14 h/A 703 (V) - 21.05.: G 201, Mo 10-12 h/G 304 (Ü), Mo 14-16 h/G 305 (Ü), Mo 16-18 h/D 247 (Ü)

Doz.: Ulrik Brandes (V), Daniel Fleischer, Jürgen Lerner (Ü)

Adressaten:

Voraussetzungen:

Angebot im Lehrexport:

• Lehramt Mathematik
• Lehramt, Haupt-/Zusatzfach Informatik
• Mathematik Nebenfach oder Schwerpunkt Informatik
• Nebenfach Informatik in einem Magisterstudiengang
• Psychologie, Wahlpflichtfach Information Engineering
• Verwaltungswissenschaft, benachbartes Fach
• Wirtschaftspädagogik, Doppelwahlpflichtfach Information Engineering
• Wirtschaftswissenschaften, Wahlpflichtfach Informatik

Inhalt:

• Formale Sprachen und Automatentheorie
  • Chomsky-Hierarchie (reguläre, kontextfreie, Typ0-Sprachen, reguläre Ausdrücke)
  • Grammatiken (Typen, Eindeutigkeit, Abgeschlossenheit)
  • Automatenmodelle ((endliche Automaten, Kellerautomaten, Turingmaschinen)
• Entscheidbarkeit und Berechenbarkeit
  • Entscheidbarkeit, Aufzählbarkeit
  • Universelle Turingmaschine, Diagonalisierung, Halteproblem
  • Berechenbarkeit, $\mu$-rekursive Funktionen, Church/Turing-These
• Komplexitätstheorie
  • Optimierungs- und Entscheidungsprobleme
  • Codierung
  • Klassen P und NP, NP-Vollständigkeit

Literatur:

• I. Wegener "Theoretische Informatik - eine algorithmenorientierte Einführung" B.G. Teubner Verlag, 2.~Aufl.~1999
• U. Schöning "Theoretische Informatik -- kurzgefasst" Spektrum Akademischer Verlag, 4. Aufl. 2001
• J.E. Hopcroft, R. Motwani, J.D. Ullman "Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie" Pearson Studium, 2. Aufl. 2002
• M.R. Garey, D.S. Johnson: "Computers and Intractability: A Guide to the Theory of NP-Completeness" Freeman, 1979

Leistungsnachweis:

Leistungspunkte: