Kurs:Algorithmen und Datenstrukturen/Vorlesung/Berechenbarkeit

Aus Wikiversity
Zur Navigation springen Zur Suche springen




Berechenbarkeitsbegriff[Bearbeiten]

Ein 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[Bearbeiten]

Die 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.

Funktionen

Beispiele[Bearbeiten]

Durchfü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[Bearbeiten]

Da 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.


R-0 Discussion R-3