»Einführung in Berechenbarkeit, Komplexität
und formale Sprachen«
Wintersemester 2005/2006
Inhalt
Was können Computer berechnen? Sind alle Rechner gleichmächtig? Wie packt man ein Auto? Wie schwierig sind Kreuzworträtsel? Wie analysiert man Sätze, die von Personen, welche hier (soll heißen jetzt) ungenannt bleiben, kommen, die dazu neigen, Sätze immer tiefer zu schachteln? Warum können Automaten nicht zählen, aber die Teilbarkeit durch sieben feststellen? Das sind alles Fragen, die im Rahmen dieser Vorlesung beantwortet werden.
Die Theoretische Informatik ist das Fundament der Informatik und sie bildet ein wertvolles Basiswissen in der Arbeit jedes Informatikers.
Wir werden unter anderem folgende Teilgebiete kennen lernen:
- Berechenbarkeit
- Turingmaschinen
- entscheidbare und rekursiv aufzählbare Sprachen
- nicht entscheidbare Probleme
- Halteproblem
- nicht rekursiv aufzählbare Probleme
- Komplexitätstheorie
- Klassen P und NP, Zeitkomplexität
- NP-Vollständigkeit
- Satz von Cook
- Reduktion
- Algorithmen: Behandlung NP-vollständiger Probleme
- Heuristiken: Backtracking, Branch and Bound
- Approximationsalgorithmen
- Formale Sparchen
- reguläre Sprachen, reguläre Grammatiken
- deterministische und nicht-deterministische Automaten
- reguläre Ausdrücke
- Äquivalenzsatz
- Pumping Lemma
- kontextfreie Sprachen, kontextfreie Grammatiken
- Kellerautomaten
- Chomsky Normalform, Äquivalenzsatz
- CYK-Algorithmus
Organisation
Die Unterlagen finden Sie im Bereich Skript und weiterführende Literatur im gleichnamigen Abschnitt. Aufgaben, die Sie zur Übung lösen sollten und entsprechende Abgabezeiten werden ihnen im Bereich Übungen in verschiedenen Formaten zum Download angeboten. Informationen rund ums Thema "Mini-Klausuren" findet man unter dem Menüpunkt Klausur. Informationen zum zeitlichen Vorlesungsablauf und der Übungsgruppen finden sie im Bereich Termine. Kurzfristige Änderungen, wie Vorlesungs- oder Übungsausfall und noch nicht feststehende Termine, wie z.B. Prüfungstermine finden sie im Bereich News. Zum Informationsaustausch steht Ihnen außerdem noch ein Diskussionsforum zur Verfügung.
|
