André Vratislavsky
Übungsgruppe vom 26.10.99
Einführung: Wozu Theoretische Informatik?
Berechenbarkeit und Effizienz
Es geht um die Frage, ob ein Problem berechenbar ist, bzw. ob die Lösung
effizient, also in vertretbarer Zeit berechenbar ist.
Dabei geht es nicht um Lottozahlen oder Weissagungen, vielmehr werden
sich ganz einfach anmutende Fragen als unlösbar bzw. sehr aufwendig
herausstellen.
Formalisierung:
Ein Problem kann als Frage aufgefaßt werden.
z.B.: Ist ein gegebener Text ein syntaktisch korrektes Java-Programm?
Formal betrachtet bilden alle korrekten Java-Programme eine Menge. Jedes
Element dieser Menge, d.h. jede Zeichenkette, die ein korrekte
Java-Programm darstellt, wird als Wort bezeichnet, die Menge von
Zeichenketten
selbst als Sprache.
Die Frage lautet also: Ist eine gegebene Zeichenkette Element dieser
Menge?
Oder allgemein: Ist ein beliebiges Wort Element einer beliebigen
Sprache?
Uns interessieren im folgenden nur Probleme, die auf diese Weise formuliert
werden können.
Daraus ergeben sich folgende Themen:
-
Die formale Beschreibung einer Sprache, die Grammatik.
Darunter versteht man ein Regelwerk zur Erzeugung der Wörter einer
Sprache.
Im Fall einer Programmiersprache soll die Grammatik mächtig genug
sein, eine ausdrucksstarke Programmiersprache zuzulassen. Andererseits
aber soll die Entscheidbarkeit, ob eine Zeichenkette ein sysntaktisch korrektes
Programm darstellt, das sogenannte Wortproblem effizient lösbar
sein. Für Programmiersprachen werden daher die sogenannten deterministisch-kontextfreien
Sprachen verwendet.
-
Die Rechnermodelle zur Berechnung des Wortproblems einer
Sprache.
Es werden Rechnermodelle gesucht, mit denen man berechnen kann, ob
ein Wort Element einer Sprache ist. Für deterministisch-kontextfreien
Sprachen sind das z.B. die sog. deterministischen Kellerautomaten.
-
Wichtige Sprachklassen und ihre zugehörigen Rechnermodelle:
Es ist sinnvoll, je nach Größe des Problems eine passende
Sprachklasse und das dazugehörige Rechnermodell zu verwenden.
| Rechnermodell |
Sprachklasse |
Effizienz / Mächtigkeit der Sprache |
| endliche Automaten |
reguläre Sprachen |
linear / gering |
| Kellerautomaten |
kontextfreie Sprachen |
effizient bis uneffizient / größer |
| Turingmaschinen |
rekursiv aufzählbare Sprachen |
beliebig uneffizient / berechnen dafür alles, was berechenbar
ist |
Turingmaschinen können mit den nicht berechenbaren rekursiv aufzählbaren
Sprachen rechnen, berechnen aber auch das Wortproblem der weniger mächtigen
Sprachklassen der regulären und kontextfreien Sprachen.
Rekursiv aufzählbare Sprachen sind nicht berechenbar, da
die Turingmaschine unendlich lange laufen müßte, um das Nichtenthalten
eines Wortes nachzuweisen (Halteproblem), also nicht in endlicher
Zeit zu einem Ergebnis kommt.
Beispiel für das Halteproblem:
Es gibt keine Maschine/Programm, das für ein beliebiges Programm
berechnen kann, ob es auf einer beliebigen Eingabe determiniert. Es ist
also im allgemeinen nicht voraussagbar, ob ein Programm in eine Endlosschleife
gerät.
Dem gegenüber ist das Traveling Salesman Problem zur Berechnung
des günstigsten Weges durch vorgegebene Punkte wohl berechenbar, jedoch
wahrscheinlich nicht in polynomieller Zeit, das heißt nicht effizient,
also steigt die Rechenzeit mit der Eingabegröße unverhältnismäßig
stark an.
Quicksort ist ein Beispiel für ein effizient berechenbares
Problem.
Gibt es unentscheidbare Probleme?
Die Menge der Sprachen über dem Alphabet {0,1}, also eine Teilmenge
aller Probleme, ist bereits gleichmächtig zur Menge der reellen Zahlen.
Dagegen ist die Menge der Programme eine
Teilmenge der endlichen Zeichenketten über einem endlichen Zeichenvorrat,
also nur gleichmächtig zur Menge der natürlichen Zahlen. (Da
die Zeichenketten endlich sind, lassen sie sich aufzählen.)
Es
gibt also viel mehr Sprachen/Probleme als Programme. Aus der Mathematik
ist bekannt, daß es keine bijektive Abbildung von der Menge der natürlichen
Zahlen in die Menge der reellen Zahlen gibt. Da aber jedes Programm nur
ein Problem löst, gibt es unlösbare Probleme.
Vollständige Induktion
Beweismethode für Aussagen über den Natürlichen Zahlen.
Prinzip:
-
Induktionsanfang:
Beweise die Aussage für die kleinste nat. Zahl, für die die
Aussage gilt, oft ist dies 0 oder 1.
-
Induktionsvoraussetzung:
Formuliere die Aussage für n.
-
Induktionsbehauptung:
Formuliere die Aussage für n+1.
-
Induktionsschritt:
Beweise die Induktionsbehauptung unter der Voraussetzung und Benutzung
der Induktionsvoraussetzung.
O-Notation
Def:
f(n) = O(g(n)) :<=> es gibt c, n0 > 0 : 0 <=
f(n) <= c*g(n) für alle n >= n0
Satz: [lim(n->unendl) (f(n)/g(n))] existiert
=> f(n)=O(g(n))
Es gilt:
log n < Wurzel(n) < n < nc < cn
für Konstante c,
wobei '<' die Größenordnung angibt ( f(n)=O(g(n)) )