Grundbegriffe der Theoretischen Informatik

Sommersemester 2006

Beate Bollig

Termine

Wann? Wo? Wer?
Vorlesungen: Di 10:15 - 12:00 HS 6 HG I Beate Bollig
Do 12:15 - 14:00 Audimax Beate Bollig

Die erste Vorlesung findet am 4. April 2006 statt.


Inhalt

Die Vorlesung „Grundbegriffe der Theoretischen Informatik " ist eine Einführung in zentrale Gebiete der theoretischen Informatik: Komplexitätstheorie, Entscheidbarkeitstheorie, Automatentheorie, Grammatiken und Syntaxanalyse.

Zunächst wird diskutiert, wie sich die algorithmische Komplexität eines Problems definieren lässt. Darunter verstehen wir die Mindestressourcen (wie Rechenzeit), um ein Problem zu lösen. Es müssen hier alle denkbaren Algorithmen für ein Problem betrachtet werden. Es zeigt sich, dass eine derartige Theorie unabhängig vom verwendeten Rechnertyp und von der verwendeten Programmiersprache möglich ist.

Für die meisten wichtigen Optimierungsprobleme gibt es einen trivialen Algorithmus mit exponentieller Laufzeit. Er probiert einfach alle möglichen Lösungen aus und wählt eine optimale Lösung. Für sehr viele dieser Probleme können wir zeigen, dass es entweder für sie alle effiziente Algorithmen gibt oder für sie alle keine effizienten Algorithmen gibt. Die Vermutung, dass die zweite Alternative wahr ist, beruht auf der NP-ungleich-P-Hypothese. Diese Hypothese stammt aus der NP-Vollständigkeitstheorie, dem wohl wichtigsten Teilgebiet der theoretischen Informatik. Diese Theorie wird vorgestellt, wobei ein neuer Zugang gewählt wird, in dem Randomisierung als Schlüsselkonzept aufgefasst wird.

In der Entscheidbarkeitstheorie wird untersucht, welche Probleme algorithmisch nicht lösbar sind. Dazu gehören so wichtige Probleme wie die Verifikation von Programmen und die Entscheidung, ob zwei Grammatiksysteme dieselbe Programmiersprache beschreiben. Für die Praxis ergibt sich die Konsequenz, nach Algorithmen für wichtige Spezialfälle zu suchen.

Endliche Automaten modellieren Schaltwerke, Rechnerkomponenten und Rechner mit beschränktem Speicher ebenso wie Cola-Automaten. Die Behandlung endlicher Automaten ist grundlegend für die Synthese und Analyse von Rechnern, die Verifikation von Hardwarekomponenten, den Entwurf von CAD-Werkzeugen und vieles andere.

Die Syntax von Programmiersprachen wird durch Grammatiken beschrieben. Grammatiken sollten einerseits komfortabel sein, um Programmkonstrukte elegant zu unterstützen. Andererseits ist es notwendig, dass der Test der syntaktischen Korrektheit, die syntaktische Zerlegung und die Compilierung effizient möglich sind. Dazu muss die Klasse der erlaubten Grammatiksysteme genügend eingeschränkt sein. Es wird gezeigt, warum kontextfreie Grammatiken und ihre Einschränkungen als Grundlage von Programmiersprachen geeignet sind.

In der theoretischen Informatik wird häufig von realen Problemen abstrahiert, um beweisbare Aussage zu erhalten. Viele der Aussagen in der Vorlesung sind negative Aussagen, etwa dass es für ein Problem keinen Algorithmus gibt. Auch eine solche Aussage ist für die Praxis relevant, da man sich die Zeit für die Suche nach einem Algorithmus, den es nicht gibt, sparen kann. Andererseits sind die Zwischenschritte, um zu solchen Aussagen zu kommen, an vielen Stellen abstrakter als in früheren Vorlesungen, was eine der neuen Schwierigkeiten beim Verständnis der Vorlesung ist. Eine andere Schwierigkeit besteht darin, dass für die exakte Formulierung von Aussagen formalere Schreibweisen erforderlich sind. Insbesondere die Übungen sollen dabei helfen, im Umgang mit diesen formalen Schreibweisen Routine zu bekommen.


Literatur zur Vorlesung

Die Vorlesung richtet sich im Wesentlichen nach den beiden folgenden Büchern:

  • Wegener, I. (2003).
    Komplexitätstheorie - Grenzen der Effizienz von Algorithmen.
    Springer Verlag.

    Die Kapitel 2-6 (ohne Kapitel 6.4, 6.5 und 6.6) werden in der Vorlesung behandelt.

  • Wegener, I. (1999).
    Theoretische Informatik - eine algorithmenorientierte Einführung.
    2. Auflage, Teubner Verlag.

    Die Kapitel 2 (ohne Registermaschinen und Techniken zur Programmierung von Turingmaschinen),
    4.1-4.4, 4.6, 5.1, 5.2, 5.3 bis 5.3.4, 5.4 (Kap. 5.4 ohne Beweise),
    6.1, 6.2 bis 6.2.2, 6.3-6.7, 7.1 bis 7.1.3, 7.2-7.4 werden in der Vorlesung behandelt.

    Anmerkung: Die 1. Auflage unterscheidet sich nicht wesentlich von der 2. Auflage.

    Das folgende Buch ergänzt den Vorlesungsinhalt, indem die wesentlichen Ideen umgangssprachlich dargestellt werden:

  • Wegener, I. (1996).
    Kompendium der Theoretischen Informatik - eine Ideensammlung.
    Teubner Verlag.

    In dem Bereich Grundlagen der Theoretischen Informatik existieren eine Vielzahl von weiteren guten Lehrbüchern. Ein gut geschriebenes Lehrbuch, in dem ähnlich wie in der Vorlesung eine algorithmenorientierte Sichtweise verfolgt wird, ist das folgende.

  • Hromkovic, J. (2001).
    Algorithmische Konzepte der Informatik - Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kryptographie.
    Teubner Verlag.

    Dieses Buch deckt jedoch nicht den ganzen Vorlesungsinhalt ab. Weitere Literatur kann bei Bedarf bei der Dozentin nachgefragt werden.

    Einen gute Einführung in das Gebiet Automatentheorie und Formale Sprachen findet sich auch in dem folgenden Buch.

  • Schöning, U. (1997).
    Theoretische Informatik - kurzgefasst.
    Spektrum Akademischer Verlag.


    Inhalt der Vorlesung

    Die Vorlesung folgt den GTI-Vorlesungen SoSe 2003 und SoSe 2004 von Ingo Wegener. Den Inhalt sowie die Folien der jeweils aktuellen Vorlesung sowie der vergangenen Vorlesungen findet Ihr hier .

    Übungen

    Der Übungsbetrieb beginnt in der zweiten Vorlesungswoche ab dem 10. April 2006. Die aktuellen Übungsblätter werden jeweils bis zur Vorlesung am Donnerstag im Netz bereitgestellt. Die Bearbeitungen können bis zur darauffolgenden Woche (bis Donnerstag 12:00 Uhr) abgegeben werden.
    Weitere Informationen finden sich hier .


    Prüfungen

    Prüfungsgrundlage ist der Inhalt der GTI-Veranstaltung des Sommersemesters 2006.

    An jedem Prüfungstag stehen maximal 10 Prüfungstermine zur Verfügung. Die Anmeldung für diese Prüfungstermine beginnt sechs Wochen vor dem jeweiligen Prüfungstermin bei mir persönlich. Fernmündliche, sowie elektronische Anmeldungen sind nicht möglich. Die Prüfungstermine werden bevorzugt an Hörerinnen und Hörer meiner Veranstaltung vergeben.

    Prüfungstage in der vorlesungsfreien Zeit:

  • 25.7.2006
  • 8.8.2006
  • 22./23.8.2006
  • 10./11.10.2006

    Prüfungstage im Wintersemester 2006/07:

  • 17.11.2006
  • 8./11.12.2006
  • 19.1./9.2.2007
  • 28.3.2007

    Prüfungstage im Sommersemester 2007:

  • 27.4.2007
  • 15.6.2007

    Die Termine werden sechs Wochen vorher freigegeben und können bei mir (ab 10 Uhr) persönlich vereinbart werden.

    Nach der Vorlesungszeit SoSe07 werden Prüfungstermine bei mir mit erster Priorität an Hörerinnen und Hörer meiner Veranstaltung TIfAI07 vergeben. Die Termine werden vier Wochen vorher für die HörerInnen meiner Veranstaltung TIfAI freigegeben und die freibleibenden Termine einen Tag später an alle anderen.


    20.6.2007 - Beate Bollig