Kurs:Algorithmen und Datenstrukturen/Vorlesung/Größter gemeinsamer Teiler

Aus Wikiversity
Zur Navigation springen Zur Suche springen




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

"%" ist die Modulu Funktion:

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.


R-0 Discussion R-3