institut für medieninformatik und technische informatik Prof. Dr. H. W. Lang

---

Theoretische Informatik Bachelor-Studiengang Informatik 5. Sem.

Theorie ist wichtig für die Praxis

Um einen arithmetischen Ausdruck wie etwa 3*9-(3-(1-(-2)*2)) korrekt auszuwerten, braucht man Techniken aus dem Bereich des Übersetzerbaus.

Der Auftrag "Schreiben Sie bis übermorgen ein Programm zur Berechnung der kürzesten Rundreise durch 100 Städte" lässt sich nur durch den Hinweis "Chef, das Problem ist NP-vollständig", also durch Kenntnisse aus der Komplexitätstheorie, abwenden.

 

Themen

Die klassischen Themen der theoretischen Informatik sind die Definition von formalen Sprachen durch Grammatiken und die Erkennung von formalen Sprachen durch Automaten.

Im Zusammenhang damit steht die zentrale Frage, welche Sprachen überhaupt durch Automaten erkennbar sind. Allgemeiner formuliert lautet die Frage: Was ist überhaupt prinzipiell berechenbar und was nicht?

Daran schließen sich Fragen zur Komplexität an: Wenn etwas berechenbar ist, wie lange dauert es dann? Gibt es Probleme, die zwar prinzipiell lösbar, aber faktisch unlösbar sind, weil die Berechnung zu lange dauert?

Unmittelbare Anwendungen der theoretischen Informatik liegen in der Übersetzung von Programmier­sprachen und in der Kryptografie.

 

Inhalt

1. Alphabet, Wort, Sprache; regulärer Ausdruck und reguläre Sprache
2. Nicht­deterministischer endlicher Automat, Erkennung von regulären Sprachen, Konstruktion eines nicht­deterministischen endlichen Automaten aus einem regulären Ausdruck
3. Deterministischer endlicher Automat, Teilmengenkonstruktion, Pumping Lemma
4. Grammatik, Erzeugung einer Sprache durch eine Grammatik, kontextfreie Grammatik, Ableitungsbaum
5. Erkennung von kontextfreien Sprachen durch nicht­deterministische Stackautomaten, deterministische kontextfreie Sprachen
6. Recursive-Descent-Parser
7. Recursive-Descent-Übersetzer
8. Rechtslineare Grammatik, Normalformen kontextfreier Grammatiken, CYK-Algorithmus
9. Turingmaschine, Erkennung einer Sprache durch eine Turingmaschine
10. Entscheid­barkeit und Semi-Entscheid­barkeit, Konstruktion einer nicht entscheidbaren Sprache
11. Klassen P und NP, polynomielle Reduktion, NP-Voll­ständigkeit
12. NP-vollständige Probleme SAT, CLIQUE, TSP, HC und andere

 

Übungen

In den begleitenden Übungen im Computerlabor wird ein Recursive-Descent-Übersetzer für eine XML-Sprache programmiert.

 

Literatur

 

Für diese Vorlesung sind folgende Bücher besonders zu empfehlen:

[Hof 09]	D.W. Hoffmann: Theoretische Informatik. Hanser (2009)
[AB 02]	A. Asteroth, C. Baier: Theoretische Informatik. Pearson Studium (2002)
[HMU 02]	J.E. Hopcroft, R. Motwani, J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. Auflage, Pearson Studium (2002)
[Schö 92]	U. Schöning: Theoretische Informatik kurz gefasst. BI-Wissenschaftsverlag (1992)

 

Weitere geeignete Bücher finden sich in der Literaturliste theoretische Informatik.

 

 

 

Weiter:

 

H.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©