Wikiversity

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

< Kurs:Algorithmen und Datenstrukturen‎ | Vorlesung



Startseite
Vorlesung


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:

  1.  
  2.  

"%" ist die Modulo 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.


     

Abgerufen von „https://de.wikiversity.org/w/index.php?title=Kurs:Algorithmen_und_Datenstrukturen/Vorlesung/Größter_gemeinsamer_Teiler&oldid=704835“