Theoretische Informatik

Vorlesung mit Übung im Sommersemester 2009

http://user.informatik.uni-goettingen.de/~damm/TI/

Prof. Dr. Carsten Damm

Nichts ist praktischer als eine gute Theorie.
 
  -- Gustav Robert Kirchhoff

Beschreibung: Man mag diesem Zitat zustimmen oder nicht - jedenfalls gibt es viele schlagende Beispiele für die Wirksamkeit der Theorie in der Informatik und ihren Anwendungen. Zum Beispiel kann dank der Theorie der formalen Sprachen und endlichen Automaten heutzutage eine einzige Person Aufgaben im Rahmen eines studentischen Compilerbau-Praktikums bewältigen, für die in den Anfängen der Computerzeit noch 25 Bearbeiterjahre angesetzt werden mussten. Die Komplexitätstheorie auf der anderen Seite gibt uns Hinweise, welche Probleme effizient lösbar sind (und welche Strategien dafür erfolgversprechend sind) und welche nicht (und welche Alternativen sich dann bieten). Aus gutem Grund ist diese Veranstaltung darum Pflicht im Bachelorstudiengang Informatik. Darüberhinaus ist sie z.B. auch für Mathematiker interessant.

Stichpunkte zum Inhalt: Formale Sprachen und Automaten (Wiederholung) - Theorie der Berechenbarkeit (mit Exkurs: Kolmogorov-Komplexität, ggf. Exkurs Hoare-Kalkül) - Berechenbarkeit und Chomsky-Klassen - Berechnungskomplexität

Literatur: u.a. Dirk W. Hoffmann: Theoretische Informatik, Uwe Schöning: Theoretische Informatik kurz gefasst, Uwe Schöning: Perlen der Theoretischen Informatik, Mike Sipser: Introduction to the Theory of Computation

Leistungsnachweis: Die Vorlesung wird begleitet durch eine Übung. Für benotete Leistungsnachweise (4ECTS) ist regelmäßige aktive Übungsteilnahme (Kriterien werden dort festgelegt) sowie die bestandene Prüfung erforderlich.

Module: Implementiert das Modul CS B.inf.305 - Theoretische Informatik

Umfang: 2+1 SWS/4 ECTS

Termin/Ort: Vorlesung Di 08:30-10:00 (Achtung! Vorverlegt), IfI 0.101, Übung Mi 16-18, IfI 0.101 (genaue Zeit/Turnus werden noch festgelegt)

Sonstiges: Teilnahmeinteressenten melden sich bitte über Stud.IP (http://www.goettingen.studip.de) für diese Lehrveranstaltung an, um aktuelle Informationen zu erhalten.

Last modified: 2009-03-31, 18.54 - Carsten Damm