Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Algorithmusbegriff

Begriffserklärung Algorithmus

Algorithmen im Alltag

Bedienungsanleitungen
Gebrauchsanleitungen
Bauanleitungen
Kochrezepte
Berechnungsvorschriften (z.B. Berechnung der Fakultät)

Intuitive Begriffserklärung Algorithmus

„Ein Algorithmus ist eine präzise (d.h. In einer festgelegten Sprache formulierten), endliche Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer Verarbeitungsschritte.“

Definitionen

Algorithmus

„systematische Verarbeitung“
Eine eindeutige Beschreibung eines in mehreren Schritten durchgeführten Bearbeitungsvorgangs
Ein Algorithmus ist ein allgemeines Verfahren zur Lösung eines Problems ohne Bezug auf einen konkreten Prozessor.

Programm

Ein Programm ist eine konkrete Formulierung eines Algorithmus für eine konkrete Klasse von Prozessoren.

Prozessor

Ein Prozessor ist etwas, das die Fähigkeit hat, Programme auszuführen.

Datenstrukturen

„Ordnungsschema“
Eine Struktur zur Verwaltung von Daten
Darstellung von Informationen in maschinenverarbeitbarer Form
Charakterisieren Daten und mögliche Operationen auf Daten

Transformationelle Probleme

Ein Algorithmus definiert eine Transformation auf dem gesamten, durch die Eingaben definierten Zustand, aus dem als Bedeutung dann die Werte der Ausgabevariablen ausgelesen werden. Das heißt, ein Algorithmus benutzt kein weiteres Wissen neben der Eingabe und hat keine Seiteneffekte!

Literatur

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 2.1 zu finden.

Eigenschaften von Algorithmen

Ein Algorithmus heißt …

terminierend, wenn er für alle zulässigen Schrittfolgen stets nach endlich vielen Schritten endet
deterministisch, wenn in der Auswahl der Verarbeitungsschritte keine Freiheit besteht
determiniert, wenn das Resultat eindeutig bestimmt ist
sequenziell, wenn die Schritte stets hintereinander ausgeführt werden
parallel oder neben läufig, wenn gewisse Verarbeitungsschritte nebeneinander (im Prinzip gleichzeitig) ausgeführt werden
korrekt, wenn das Resultat stets korrekt ist
effizient, wenn das Resultat in „annehmbarer“ Zeit geliefert wird

Literatur

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 2.1.1 zu finden.

Algorithmenentwurf

Dieses Kapitel behandelt die Vorgehensweise zum Algorithmenentwurf.

Vom Algorithmus zur Programmausführung

Der Algorithmus wird unabhängig von Programmiersprache und Rechnerhardware entworfen
Der Algorithmus wird in einer höheren Programmiersprache, z.B. Java, programmiert
Das Programm wird in Maschinensprache übersetzt
Die CPU interpretiert den Maschinencode und das Programm wird ausgeführt

Vom Algorithmus zum Programm

Vorgehensweise Algorithmus-Entwurf

Hintergrundwissen erwerben: Derjenige der ein Problem beschreibt ist oft nicht derjenige, der den Algorithmus entwirft, dadurch kommt es zu unklaren Aufgabenstellungen, unterschiedlichem Vorwissen und verschiedenen Annahmen.
Problem definieren: Erfordert Hintergrundwissen und Übung in der Definition von Problemen
Algorithmus entwerfen: Erfordert Wissen zu Algorithmen und Datenstrukturen
Programm erstellen: Erfordert Wissen über Programmiersprache (Java) und Programmierung
Lösung überprüfen: Erfordert methodisches Wissen zu Termination, Korrektheit und Effizienz

Literatur

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 2 und 8.1 zu finden.

Größter gemeinsamer Teiler

In diesem Kapitel wird die im vorherigen Kapitel vorgestellte Vorgehensweise zum Algorithmenentwurf am Beispiel des größten gemeinsamer Teilers gezeigt.

Hintergrundwissen

Gegeben zwei positive natürliche Zahlen a und b, welche ist die größte positive natürliche Zahl x, so dass x sowohl a also auch b teilt und es keine positive natürliche Zahl x’ gibt, so dass x’ > x und x’ teilt sowohl a als auch b.

Alle Variablen bezeichnen natürliche Zahlen größer 0
$x|a\iff \exists \alpha :a=\alpha \land x(x~teilt~a)$
$x=ggT(a,b)\iff x|a\wedge x|b\wedge \forall y:(y|a\wedge y|b\Rightarrow y|x)$
Anwendungsbeispiel Kürzen: 52/32 hat 4 als ggT, mit 4 gekürzt ergibt sich 13/8

Problem definieren

Wir betrachten (i. Allg.) hier transformationelle Probleme

Problem: ggT-Berechnung
Eingabe: zwei Zahlen a,b ∈ N 
Ausgabe: der größte gemeinsame Teiler von a und b

Algorithmus definiert also eine Transformation auf dem gesamten, durch die Eingaben definierten Zustand, aus dem als Bedeutung dann die Werte der Ausgabevariablen ausgelesen werden.

Algorithmus entwerfen

Verfahren von Euklid (300 v. Chr.) für natürliche Zahlen:

$b|a\Rightarrow b=ggT(a,b)$
$\lnot (b|a)\Rightarrow ggT(a,b)=ggT(b,a\%b)$

"%" ist die Modulu Funktion: $r=a\%b\iff 0\leq r\leq b\land \exists \alpha :a=\alpha *b+r$

ggT(46,18) = ggT(18,10)    (α=2, b=18, r=10) 
           = ggT(10,8)     (α=1, b=10, r=8)
           = ggT(8,2) = 2  (α=1, b=8, r=2)

In Worten erklärt:

Wie oft passt 18 in 46? → 2 mal (α)
2*18 ist 36, zur 46 fehlen somit noch 10 (r)
Wie oft passt 10 in 18? → 1 mal (α)
1*10 ist 10, zur 18 fehlen somit noch 8 (r)
Wie oft passt 8 in 10? → 1 mal (α)
1*8 ist 8, zur 10 fehlen somit noch 2 (r)
8 passt 0 mal in die 2, somit ist der ggT die 2

Idee: Führe die Berechnung von ggT(a,b) auf die Berechnung von ggT(b, a % b) zurück (falls b|a, ansonsten ist das Ergebnis b).

Vorbedingung: Eine Bedingung zur Ausführung des ggT(a,b) ist, dass a,b>0

Wie kann man dies sicherstellen?

Optimistische Strategie
- Man geht vom Erfüllt sein der Bedingung aus
  - z.B. Clients bekannt und zuverlässig, z.B. bei Rekursion
Pessimistische Strategie
- Man überprüft die Bedingung bei jedem Aufruf
  - z.B. Öffentliche APIs
Möglichkeiten bei nicht erfüllten Vorbedingungen
- Ausnahmen werfen
- Parameter auf Defaultwerte setzen (mit Meldung)
- Programm nicht ausführen und Defaultwert zurückgeben

Programm erstellen

Pseudocode

Algorithmus euklid
Eingabe: Ganze Zahlen a,b
Ausgabe: Ganze Zahl c=ggT(a,b)
  Setze r = a % b;
  Falls r = 0 gib b zurück;
    Ansonsten gib euklid(b,r) zurück;

Rekursiv, optimistisch

public int ggT(int a, int b){
   int r = a % b;
   if (r == 0)!
           return b;
   else
          return ggT(b,r);
}

Iterativ, pessimistisch – Version 1

public int ggT(int a, int b){
    if (a<=0 || b<=0)
          throw new ArithmeticError(“negative Daten bei ggt(“+a+“,“+b+“)“);
    else { 
          int r = a % b; 
          while (r!=0) { 
                  a = b;
                  b = r;
                  r = a % b;
          }
          return b;
     }
}

Iterativ, pessimistisch – Version 2

public int ggT(int a, int b){
    if (a<=0 || b<=0)
          then throw new ArithmeticError(“negative Daten bei ggt(“+a+“,“+b+“)“);
    else { 
          do{
             int r = a % b;
             a=b;
             b=r;
         } while (r!=0);
return a;
 }
}

Algorithmenanalyse

Ist unser ein Algorithmus ein guter Algorithmus?

Wichtige Fragen:

–  Terminiert der Algorithmus?

–  Ist der Algorithmus korrekt?

–  Welche Laufzeit hat der Algorithmus?

1. Theorem:

Für positive natürliche Zahlen a und b mit a > b, terminiert der Algorithmus Euklid nach endlich vielen Schritten.

Beweis:

(a) Falls b|a terminiert der Algorithmus in einem Schri5. (b) Andernfalls wird ein Parameter der Algorithmus um mindestens den Wert 1 verringert und der Algorithmus rekursiv aufgerufen. Spätestens wenn ein Parameter den Wert 1 erreicht tri5 Fall (a) ein und der Algorithmus terminiert. Für endliche Eingaben bedeutet dies eine endliche Laufzeit.

Was ist mit anderen Eingaben?

2. Theorem:

Der Algorithmus Euklid löst das Problem ggT.

Beweis:

Wir haben bereits festgestellt, dass für zwei positive natürliche Zahlen a, b gilt, dass ggT(a,b)=b (falls b|a) und ggT(a,b)=ggT(a%b) (falls b|a nicht gilt). Der Algorithmus Euklid vollzieht genau diese Fallunterscheidung nach.

3. Theorem:

Für positive natürliche Zahlen a und b mit a>b, benötigt der Algorithmus Euklid maximal max{a,b} viele rekursive Aufrufe.

Beweis:

Wir haben bereits festgestellt, dass Euklid stets terminiert, dass bei jedem Aufruf ein Parameter um mindestens den Wert 1 verringert wird und dass wenn der zweite (stets kleinere) Parameter den Wert 1 hat die Rekursion spätestens endet. Damit kann es maximal max{a,b} viele rekursive Aufrufe geben.

Anmerkung:

Die obige Laufzeit ist nur eine grobe obere Abschätzung. Die tatsächliche Worst‐case‐Laufzeit ist O(log(ab)) (mehr zur O‐Notation später)

Fazit

Welche Strategie (optimistisch, pessimistisch) und welches Verhalten man bei nicht‐erfüllten Vorbedingungen zeigt, hängt von vielen Faktoren ab:

–  Bei unkritischen oft aufzurufenden Algorithmen könnte die Überprüfung der Zulässigkeit zu viel Aufwand sein

–  Bei zeitintensiven Algorithmen kann durch eine Überprüfung Zeit gespart werden

Man sollte das Verhalten seines Algorithmus im Fehlerfall aber stets gut dokumentieren!

Literatur

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 8 zu finden.

Berechenbarkeitsbegriff

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

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

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

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.