Inhalt
Informatik III = Theoretische Informatik
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