Theoretische Informatik

für Studierende der Angewandten Informatik

Sommersemester 2009

Beate Bollig

Termine

Wann? Wo? Wer?
Vorlesung: Di 8:15 - 9:45 OH 14, E 23 Beate Bollig
Vorlesung: Do 10:15 - 11:45 OH 14, E 23 Beate Bollig

Die erste Vorlesung findet am 14. April 2009 statt. Der Übungsbetrieb beginnt in der zweiten Vorlesungswoche.

Inhalt

Die Vorlesung „Theoretische Informatik für Studierende der Angewandten Informatik " bietet eine Einführung in die theoretische Informatik unter besonderer Berücksichtigung anwendungsbezogener Aspekte. Zentrale Teilgebiete der theoretischen Informatik werden behandelt: Komplexitätstheorie, Entscheidbarkeitstheorie, Automatentheorie, Grammatiken, Syntaxanalyse und lineare Programmierung.

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 folgenden Büchern:

  • Blum, N. (2004).
    Algorithmen und Datenstrukturen - eine anwendungsorientierte Einführung. (Kapitel 8, insbesondere Kapitel 8.1 und Kapitel 8.2)
    Oldenbourg.

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

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

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

    Für Kapitel 5 der Vorlesung, Lineare Programmierung, siehe auch:

  • Cormen, Th. H., Leiserson, C. E., Rivest, R., Stein, C. (2001).
    Introductions to algorithms. Second edition.
    (Kapitel 29)
    MIT Press.

    Zum Thema Randomisiertes Runden siehe auch:

  • Hromkovic, J. (2004).
    Randomisierte Algorithmen. (Kapitel 7.3 und 7.4)
    Teubner Verlag.

    Das folgende Buch ergänzt den Vorlesungsinhalt, indem die wesentlichen Ideen der Kapitel 2-4 der Vorlesung (Entscheidbarkeitstheorie, Endliche Automaten, Grammatiken und Syntaxanalyse) und teilweise des Kapitels 1 (Komplexitätstheorie) umgangssprachlich dargestellt werden:

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

    In dem Bereich Grundlagen der Theoretischen Informatik existieren eine Vielzahl weiterer guter Lehrbücher. 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.

    Einen gute Einführung in das Gebiet Automatentheorie und Formale Sprachen, die jedoch nicht den ganzen Vorlesungsinhalt abdeckt, findet sich auch in dem folgenden Buch.

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

    Weitere Literatur kann bei Bedarf bei der Dozentin nachgefragt werden.

    Inhalt der Vorlesung

    Die Vorlesung folgt den TIfAI-Vorlesungen SoSe 2006-2008 von Detlef Sieling und Beate Bollig. Die Folien der Vorlesung findet Ihr hier . Dort findet Ihr ebenfalls eine Liste der wichtigsten in der Vorlesung benutzten Abkürzungen, sowie Unterlagen zu den in der Vorlesung benötigten Grundlagen der Wahrscheinlichkeitstheorie.

    Für die Grundlagen der Wahrscheinlichkeitstheorie wie sie in der Vorlesung benötigt werden, verweisen wir auf Anhang A.2 in
    Wegener, I. (2003). Komplexitätstheorie - Grenzen der Effizienz von Algorithmen. Springer Verlag.


    Übungen

    Die aktuellen Übungsblätter werden jeweils bis Dienstag um 10 Uhr im Netz bereitgestellt und müssen bis zum darauffolgenden Montag um 12 Uhr abgegeben werden. Die Besprechung erfolgt in der Woche der Lösungsabgaben in den Übungen. Informationen zum Übungsbetrieb finden sich auf der Übungsseite.

    Studienleistungen

    Für Studierende des Bachelor-Studiengangs Angewandte Informatik ist die Erbringung von Studienleistungen Voraussetzung für die Teilnahme an der Modulprüfung (mündliche Prüfung). In TIfAI werden diese Studienleistungen durch regelmäßige aktive Teilnahme an den Übungen (nicht öfter als dreimaliges Fehlen) und Erreichen von jeweils mindestens 40% der Punkte der Übungsblätter 2-7 und 8-14 erbracht. Die Aufgaben dürfen in Gruppen von bis zu drei Personen bearbeitet werden, wobei jedes Gruppenmitglied alle bearbeiteten Aufgaben der Gruppe in der besuchten Übungsgruppe vorstellen können muß, um die jeweiligen Punkte zu erhalten.

    Prüfungen

    Prüfungsgrundlage ist der Inhalt der TIfAI-Veranstaltung des Sommersemesters 2009.

    Eine (unvollständige) Liste mit möglichen Prüfungsfragen hat Detlef Sieling hier bereitgestellt. Weitere mögliche Prüfungsfragen stehen im Kompendium der Theoretischen Informatik (siehe Literaturhinweise).

    PrüfungskandidatInnen bringen einen ausgefüllten und unterschriebenen Anmeldebogen mit. Dieser muss spätestens 14 Tage vor der geplanten Prüfung beim Dezernat 7.3 (Prüfungsverwaltung) eingegangen sein. Fernmündliche, sowie elektronische Anmeldungen sind leider nicht möglich. Prüfungstage in der vorlesungsfreien Zeit nach der Veranstaltung:

  • 29.7.2009
  • 4./5.8.2009
  • 26./27.8.2009
  • 6./7.10.2009

    (Bisher geplante) Prüfungstage in der Vorlesungszeit Wintersemester 2009/10:

  • 10.11.2009
  • 8.12.2009
  • 12.1.2010


    19.10.2009 - Beate Bollig