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

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

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.