Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Einführung in die Theoretische Informatik (TI)

Studienpunkte: 9

Lern- und Qualifikationsziele

Studierende erlangen die Fähigkeit, die theoretischen Grundlagen der Informatik zu verstehen und ihre Ergebnisse anzuwenden.

Inhalte

Einführung in grundlegende Konzepte der Theoretischen Informatik. Im Zentrum stehen

  • Automatentheorie (endliche Automaten, Kellerautomaten und Turingmaschinen),
  • formale Sprachen (Chomsky-Hierarchie),
  • Berechenbarkeit (Unentscheidbarkeit des Halteproblems, Satz von Rice) und
  • Komplexität (P vs NP Problem, NP-Vollständigkeit).

Daneben werden zum Umgang mit schwer lösbaren Problemen erste algorithmische Ansätze zur approximativen oder randomisierten Lösung von NP-harten Problemen aufgezeigt.

 

Dozent

Prof. Dr. Susanne Albers

Links

Einführung in die Theoretische Informatik (WS 09/10)