Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

 

Theoretische Informatik

für Studierende der Angewandten Informatik

Sommersemester 2011

Beate Bollig

Termine

Wann? Wo? Wer?
Vorlesung: Di 8:15 - 9:45 OH 14, E23 Beate Bollig
Vorlesung: Do 14:15 - 15:45 OH 14, E23 Beate Bollig

Die erste Vorlesung findet am 5. April 2011 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 mit den zentralen Teilgebieten: 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. Hier müssen 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 alle oder für keins effiziente Algorithmen gibt. Die Vermutung, dass die zweite Alternative wahr ist, beruht auf der NP-ungleich-P-Hypothese. Diese stammt aus der NP-Vollständigkeitstheorie, einem der wohl wichtigsten Teilgebiete der theoretischen Informatik. Diese Theorie wird mittels Randomisierung als Schlüsselkonzept vorgestellt.

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 daher grundlegend für die Synthese und Analyse von Rechnern, die Verifikation von Hardwarekomponenten, den Entwurf von CAD-Werkzeugen und vieles andere. Ein zentrales Thema in der Veranstaltung ist die Minimierung sogenannnter deterministischer endlicher Automaten.

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.

Der Simplexalgorithmus ist ein Verfahren, das sich in der Praxis im Bereich der Linearen Programmierung bewährt hat. Es wird die Fragestellung betrachtet, wie man verschiedene Optimierungsprobleme als lineares Programm formulieren kann und wie der Simplexalgorithmus arbeitet.

In der theoretischen Informatik wird häufig von realen Problemen abstrahiert, um beweisbare Aussage zu erhalten. Diese sind in der Vorlesung oftmals negativ, etwa dass es für ein Problem keinen Algorithmus mit bestimmten Eigenschaften gibt. Auch solche Aussagen können praxisrelevant sein, da man sich die Zeit für die Suche nach einem solchen Algorithmus, den es nicht gibt, sparen kann. Neben der höheren Abstraktionsstufe besteht eine weitere Herausforderung 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.
    (Kapitel 4.1-4.4, 4.6 bis einschl. 4.6.12, 5.1-5.3 bis einschl. 5.3.3, 6.1-6.6, 7.2-7.3, 8.2)
    Teubner Verlag.

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

Die oben genannten Kapitel aus den drei Lehrbüchern decken den Stoff der Vorlesung vollständig ab und entsprechen einem Skript zur Vorlesung.

Weiterführende Literatur

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. Bei Bedarf kann bei der Dozentin nachgefragt werden.


Inhalt der Vorlesung

Die Vorlesung folgt den TIfAI-Vorlesungen SoSe 2006-2010 von Detlef Sieling und Beate Bollig. Die aktuellen Folien der Vorlesung findet Ihr hier .

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.

  • 5.4.2011:
    Überblick über die Vorlesung, Beispielproblem Partition, Entscheidungs- und Suchprobleme, Begriffe Problem und Sprache
  • 7.4.2011:
    Registermaschinen, algorithmische Komplexität, Turingmaschinen
  • 12.4.2011:
    Sonderrolle polynomieller Rechenzeiten und die Komplexitätsklasse P, Einführung randomisierter Algorithmen, Beispielalgorithmus ÄMA, BPM
  • 14.4.2011:
    Komplexitätsklassen für randomisierte Algorithmen, Probability Amplification
  • 19.4.2011:
    Zusammenhang zwischen den Komplexitätsklassen Nichtdeterminismus, Komplexitätsklasse NP
  • 21.4.2011:
    Algorithmische Ähnlichkeit von Problemen, Turing-Reduktionen, Entscheidungsvariante eines Problems versus Optimierungsvariante
  • 26.4.2011:
    Turing-Reduktionen zwischen verwandten Problemen, polynomielle Reduktionen als Spezialfall von Turing-Reduktionen, Turing-Reduktionen zwischen nicht verwandten Problemen
  • 28.4.2011:
    Turing-Reduktionen (polynomielle Reduktionen) zwischen nicht verwandten Problemen, Eigenschaften der polynomiellen Reduktion, NP-Vollständigkeit
  • 3.5.2011:
    Charakterisierung von NP und co-NP, Rate-Verifikationsmodus, stereotype Turingmaschinen, Satz von Cook
  • 5.5.2011:
    Beweis Satz von Cook, NP-Vollständigkeitsbeweise
  • 10.5.2011:
    weitere NP-Vollständigkeitsbeweise
  • 12.5.2011:
    weitere NP-Vollständigkeitsbeweise, Einführung Entscheidbarkeitstheorie: universelle Turingmaschine, Turing-Berechenbarkeit rekursive und rekursiv aufzählbare Sprachen, Churche These
  • 17.5.2011:
    Diagonalsprache, Diagonalisierung, Halteproblem, Reduktionen, spezielles Halteproblem, Satz von Rice
  • 19.5.2011:
    Abschlusseigenschaften rekursiver und rekursiv aufzählbarer Sprachen, Unentscheidbarkeit (modifiziertes) Postsches Korrepondenzproblem
  • 24.5.2011:
    Beweis der Korrektheit der Reduktion des Halteproblems auf das (modifizierte) Postsche Korrepondenzproblem, Einführung Automatentheorie
  • 26.5.2011:
    Pumping-Lemma für reguläre Sprachen, äquivalente Zustände in einem Automaten, Äquivalenzklassenautomat
  • 31.5.2011:
    Minimierung deterministischer endlicher Automaten, rechtsinvariante Äquivalenzrelationen, Satz von Nerode
  • 7.6.2011:
    NFAs, Umwandlung NFAs in DFAs: Potenzmengenkonstruktion
  • 9.6.2011:
    Algorithmen für FAs, Vollständigkeitsproblem für DFAs und NFAs, Abschlusseigenschaften für DFAs und NFAs, reguläre Ausdrücke
  • 14.6.2011:
    Fortsetzung reguläre Ausdrücke, Grammatiken, rekursiv aufzählbare Sprachen und die Chomsky-Hierarchie
  • 16.6.2011:
    Fortsetzung Chomsky-Hierarchie, reguläre Sprachen und Chomsky-3-Grammatiken, kontextfreie Sprachen
  • 21.6.2011:
    Umwandlung kontextfreier Grammatiken in Chomsky-Normalform, CYK-Algorithmus (Wortproblem)
  • 28.6.2011:
    Pumping-Lemma für kontextfreie Sprachen, Ogdens Lemma, Algorithmen für kontextfreie Sprachen, Abschlusseigenschaften für kontextfreie Sprachen
  • 30.6.2011:
    unentscheidbare Probleme für kontextfreie Sprachen, kontextsensitive Sprachen, Greibachnormalform und Kellerautomaten, Akzeptanz mit akzeptierenden Zuständen, Akzeptanz mit leerem Stack
  • 5.7.2011:
    Tripelkonstruktion, LR(k)-Grammatiken
  • 7.7.2011:
    Shift-Reduce-Parser, Einführung lineare Optimierung
  • 12.7.2011:
    Grundlagen aus der linearen Algebra, Arbeitsweise Simplex-Algorithmus
  • 14.7.2011:
    Simplex-Algorithmus, Randomisiertes Runden


Übungen

Die aktuellen Übungsblätter werden jeweils bis Dienstag um 10 Uhr im Netz bereitgestellt und müssen bis zum darauffolgenden Montag um 14 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 (höchstens zweimaliges unentschuldigtes Fehlen) und Erreichen von jeweils mindestens 40% der Punkte in den jeweiligen Übungsblöcken 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

Die Prüfung findet mündlich statt, Prüfungsgrundlage ist der Inhalt der TIfAI-Veranstaltung des Sommersemesters 2011.

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 in die Sprechstunde der Dozentin (Do 13:00-14:00 Uhr während der Vorlesungszeit, ansonsten nach Vereinbarung). 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üfungsblock in der vorlesungsfreien Zeit nach der Veranstaltung:

  • 31. KW
Zweiter Prüfungsblock:
  • 41. KW

Studierende, die bereits im Sommersemester 2010 ihre Studienleistungen für das Modul TIfAI erworben haben, können auf Wunsch auch während der Vorlesungszeit Sommersemester 2011 geprüft werden. Entsprechende Termine können mit mir in meiner Sprechstunde vereinbart werden.


14.7.2011 - Beate Bollig