zum Inhalt springen

Einführung in die Theoretische Informatik

Die Vorlesung beinhaltet eine Einfühung in die Theoretische Informatik, die das notwendige Fundament fast aller Disziplinen der Informatik bildet. Zentrale Arbeitsgebiete wie z.B. Compilerbau, Rachnerarchitektur oder Künstliche Intelligenz basieren direkt auf diesen Ergebnissen. Neben den klassischen Gebeiten der Formalen Sprachen, Automatentheorie, Berechnenbarkeit und Komplexität werden auch modernere Gebiete wie z.B. approximierende und randomisierte Algorithmen behandelt. Die in der Veranstaltung Grundzüge der Informatik II vermittelten Grundkenntnisse zur Berechenbarkeits- und Komplexitätstheorie werden weiter vertieft. Die Vorlesung folgt nicht nur dem klassischen Definition-Satz-Beweis-Stil, sondern versucht darüber hinaus diese Thematik aus algorithmen-orientierter Sichtweise zu behandeln.

Scheinerwerb: Erfolgreiche Teilnahme an einer 2-std. Klausur. Bis zu 20% der zum Bestehen notwendigen Punkte können als Bonuspunkte in den Übungen erworben werden.

Literatur:

  • Schöning, Uwe: Theoretische Informatik kurz gefasst. 5. Aufl., Spektrum 2008.
  • Hopcroft, John E., Motwani, Rajeev und Ullman, Jeffrey D.: Introduction to Automata theory, Languages, and Computation. Second Edition, Addison Wesley 2001.
  • Asteroth, Alexander und Baier, Christel: Theoretische Informatik. Pearson Studium 2003.
  • Hromkovic, Juraj: Theoretische Informatik. 3. Aufl, Teubner 2007.
  • Hollas, Boris: Grundkurs Theoretische Informatik mit Aufgaben und Prüfungsfragen. Spektrum 2007.