HEINZ NIXDORF INSTITUT
Universität Paderborn
Algorithmen und Komplexität

Home
Übungen
Skript
Literatur
Klausur

Termine
News
Forum

Letzte Änderung:
15.11.2005
 

Orientierung:
 Heinz Nixdorf Institut
   Algorithmen und
   Komplexität


Webmaster
 

»Einführung in Berechenbarkeit, Komplexität
und formale Sprachen«

Hochschuldozent Dr. rer. nat. Christian Schindelhauer

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.