Größter gemeinsamer Teiler[Bearbeiten]

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

Hintergrundwissen[Bearbeiten]

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

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

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

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

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 Schritt. (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 tritt 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[Bearbeiten]

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