Achtung : Skript gibt den mündlichen Vortrag nur teilweise wieder !!!
                        

1. Die historischen Wurzeln und die Grundkonzepte der theoretischen Informatik

In den meisten Lehrbüchern der theoretischen Informatik beginnen die Autoren direkt mit Begriffen wie Automat, Entscheidungsproblem, Komplexitätsklasse usf. ohne zu zeigen, wie es zur Entstehung dieser Begriffe kam. In der heutigen Vorlesung soll dies in einem kurzen Abriss geschehen. Siehe dazu den Text aus der TI-Vorlesung vom WS02.

2. Glossar der wichtigsten Begriffe

Nach dieser ersten Einführung in die Entstehung und die Grundfragen der theoretischen Informatik hier eine erste Übersicht über alle wichtigen Begriffe anhand einer Themenlandkarte. Die weiteren Vorlesungen werden diese Begriffe dann weiter präzisieren.

• Berechenbarkeit - intuitiv:= den Begriff berechenbar intuitiv zu umschreiben, ist streng genommen schwierig bis unmöglich, da man in diesem Fall letztlich nur einzelne Beispiele anführen kann, die einen allgemeinen Sachverhalt illustrieren sollen. Eine mögliche intuitive Umschreibung des Begriffs berechenbar könnte sein: ein Prozess soll als berechenbar gelten, wenn man bei Angabe einer Startkonfiguration nach endlich vielen Aktionen zu einem definierten Ergebnis kommt.

Berechenbarkeit - präzise:= den Begriff berechenbar präzise zu fassen setzt voraus, dass man weiss, was eigentlich präzise heisst und wie man auf diese Weise den Begriff formuliert. In den formalen Wissenschaften herrscht heute Übereinkunft darin, dass sich präzise Formulierungen mithilfe von formalen Sprachen konstruieren lassen, bei denen der Begriff wohlgeformter Ausdruck sich mit endlichen Mitteln nach endlichen vielen Schritten überprüfen lässt. Beispiele für präzise Formulierungen des Begriffs berechenbar lassen sich z.B. mit den Begriffen Funktion, Automat oder Grammatik konstruieren.

• Funktionen:= sind im allgemeinen Fall Vorschriften, die Eingangswerten Ausgangswerte zuordnen. Berechenbare Funktionen sind nun solche, die nach endlich vielen Operationen bei einer bestimmten Eingabe ein definiertes Ergebnis liefern. Funktionen, die dafür bekannt sind, dass sie diese Eigenschaften haben, sind z.B. die primitiv rekursiven Funktioen und die my-rekursiven Funktionen (engl. oft auch "general recursive functions" oder einfach "recursive functions") (vgl. [MINSKY 1967:184f]). Sofern solche Funktionen für alle Eingangswerte definierte Ergebnisse liefern, nennt man sie auch totale Funktionen; andernfalls partielle Funktionen.

• Automat:= ein Automat ist ein formal definierte Struktur, bei der auf eine Eingabe eine endliche Menge von Operationen angewendet werden kann und zwar so, dass in jedem Augenblick klar ist, welche Operation als nächste folgt. Die Menge dieser Operationen nennt man eine Maschinentafel oder ein Programm. Der stärkste bekannte Automat ist die Turingmaschine. Man kann zeigen, dass man eine Turingmaschine in eine my-rekursive Funktionen übersetzen kann und umgekehrt (vgl. z.B. [MINSKY 1967:Kap.10]).

• Grammatik:= eine Grammatik definiert eine Menge wohlgeformter Ausdrücke, die eine (formale) Sprache darstellen. Die Ausdrücke setzen sich aus Elementen eines endlichen Zeichenvorrates (Alphabet) zusammen. Die Regeln der Grammatik legen fest, wie man einen gegebenen Ausdruck in einen anderen Ausdruck umformen darf. Im Gegensatz zu einem Automaten ist die Regelanwendung nicht notwendigerweise deterministisch. Man kann zeigen, dass die stärksten bekannten formalen Sprachen diejenigen sind, die von einer Turingmaschine erkannt werden können.

• (Semi-)Entscheidbarkeit:= der Begriff entscheidbar beschreibt den Fall, dass man eine (formale) Sprache L über einem Alphabet A* hat und man fragt, ob es eine Funktion gibt, die für ein beliebiges Wort w über dem Alphabet A* feststellen kann, ob w Element der Sprache L ist oder nicht (JA oder NEIN). Gibt es eine totale Funktion, also eine solche, die diese Frage ffür alle Worte über A* entscheiden kann, spricht man von einem (vollständigen) Entscheidungsverfahren; gelingt dies nicht für alle, ligt also eine partielle funktion vor, dann spricht man von einem Semi-Entscheidungsverfahren bzw. man nennt dann die sprache L semi-entscheidbar, sond entscheidbar.

• Effizient:= Probleme, die entscheidbar sind, können für die "Praxis" möglicherweise dennoch uninteressant sein, da sie nicht effizient lösbar sind. Die Effizienz eines Verfahrens hat mit seinen Kosten zu tun: wieviel Speicher benötigt das Verfahren oder wieviele Rechenschritte, wobei man einen Rechenschritt mit einer Ausführungszeit in Beziehung setzt. Kann man die benötigte Rechenzeit mit einem Polynom ausdrücken, dann spricht man von polynomieller Laufzeit. Verfahren mit polynomieller Laufzeit gelten als effizient, obgleich auch dies für reale Computer u.U. noch unakzeptabel lang sein kann.

• Kostenmass - uniform/ logarithmisch:= werden bei der Feststellung der Kosten eines Entscheidungsverfahrens für alle anfallenden Leistungen immer nur gleiche (:= uniforme) Kosten angesetzt, spricht man von einem uniformen Kostenmass. Werden hingegen anfallende Leistungen unterschiedlicher Grösse (Speicher/ Zeit) mit einem logarithmischen Wert gemessen, spricht man von einem logarithmischen Kostenmass.

3. Testfragen und Übungen

1. Was würden Sie jemandem antworten, der Sie fragt, wofür das Fach theoretische Informatik gut ist?

2. Wie würden Sie den Zusammenhang der folgenden Begriffe erklären: Mathematik, mengentheoretische Sprache, formale Theorie, Vollständigkeit und Widerspruchsfreiheit, effektives Verfahren, Turingmaschine, formale Sprachen, Programm/ Algorithmus, Funktion, Komplexität?

3. Wie hängen die folgenden Themen zusammen: Boolsche Algebra, Logizismus, Hilbert Programm, Beweistheorie, Gödels Unvollständigkeitsbeweis, Church's und Turing's Unentscheidbarkeitsbeweise?

4. Was ist eine formale Theorie?

5. Wie würden Sie die Begriffe 'Widerspruchsfreiheit', 'Vollständigkeit' und 'Unabhängigkeit' für formale Theorien erklären?

6. Geben Sie ein Beispiel einer möglichst einfachen formalen Theorie

7. Wie könnte man ein Theorem für diese Theorie beweisen?

8. Was bedeutet es, wenn man verlangt, dass ein Beweis mit 'finiten Mitteln' geführt werden soll?

9. Was verstehen Sie unter einer Grammatik?

10. Versuchen Sie beispiele für den intuitiven Begriff der Berechenbarkeit zu konstruieren.

11. Wie soll man das Verhältnis zwischen einem Automaten und einer formalen Grammatik verstehen?

12. Was sind die wichtigsten Automatentypen?

13. Was sind die wichtigsten Grammatiktypen?

14. Was sind Funktionen/ totale Funktionen/ partielle Funktionen?

15. Was verbirgt sich hinter dem Begriff entscheidbar?

16. Was versteht man unter einem effizienten Verfahren?

17. Was ist der Unterschied zwischen einem uniformen und einem logarithmischen Kostenmass?