Kurs:Algorithmen und Datenstrukturen/Vorlesung/Berechenbarkeit
Berechenbarkeitsbegriff
BearbeitenEin Problem (z.B. eine mathematische Funktion) heißt berechenbar, falls dafür ein Algorithmus existiert.
- Berechenbar: Algorithmus stoppt nach endlich vielen Schritten
- Funktion f: W → V ist
- partiell: Def(f) ⊆ W (Beispiel: f: ℝ → ℝ, f(x)= 1/x)
- total: Def(f) = W
Ausgangssituation: Wir entwerfen und programmieren einen Algorithmus und wir haben eine Vorstellung was berechenbar ist (intuitiver Berechenbarkeitsbegriff). Das Problem ist nun, wie man diese Berechenbarkeit nachweisen kann. Dazu bringen wir die intuitive Form in eine mathematische Form und können diese mit mathematischen Beweisen belegen.
Formale Definitionen des Berechenbarkeitsbegriff: Turing berechenbare Funktionen, while-Programme, µ-rekursive Funktionen
Church-Turing-These
BearbeitenDie Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen. Wobei "intuitiv" nicht exakt formalisierbar ist.
Die durchführbaren Algorithmen sind eine Teilmenge der berechenbaren Funktionen, welche wiederum eine Teilmenge aller existierenden Funktionen sind.
Beispiele
BearbeitenDurchführbare Algorithmen
- ggT, Matrizenmultiplikation, Zinsberechnung,…
Berechenbare Funktionen, die nicht durchführbar sind
- Harte Optimierungsprobleme mit Millionen von Variablen
- Vollständige Eigenwertberechnung auf dem Facebook-Graphen
Nicht berechenbare Funktionen
- Haltefunktion (gibt zu einem beliebigen Programm an, ob es hält)
- Äquivalenzfunktion (gibt zu zwei beliebigen Programmen an, ob sie das gleiche Verhalten haben)
- …
Literatur
BearbeitenDa die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 6.4 und 7.1 zu finden.
