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

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Größter gemeinsamer Teiler - funktional

In folgendem Beispiel werden wir den größten gemeinsamen Teiler mit Hilfe eines funktionalen Algorithmus berechnen.

Hintergrundwissen

$Fuer~x,y>0~gilt:$
$ggT(x,y):=x$
$ggT(x,y):=ggT(y,x)$
$ggT(x,y):=ggT(x,y-x)~fuer~x\leq y$

Wir haben folgende funktionale Spezifikationen:

$ggt(x,y):=\left\{{\begin{array}{ll}if(x\leq 0)\lor (y\leq 0)&then~ggT(x,y)~else\\if~x==y&then~x~else\\if~x>y&then~ggT(y,x)~else\\&ggT(x,y-x)\end{array}}\right.$

Auswertung

Eine beispielhafte Auswertung sieht wie folgt aus:

$ggT(39,15)\to ggT(15,39)\to (15,24)$

$\to ggT(15,9)~~\to (9,15)$

$\to ggT(9,6)~~~\to (6,9)$

$\to ggT(6,3)~~~\to (3,3)$

$\to 3$

Abbruchbedingungen und Rekursion

Der ggT lässt sich nur korrekt berechnen, wenn positive Eingaben gemacht werden. Bei negativen Eingaben ist der ggT undefiniert und der Algorithmus terminiert nicht.

• Abbruchbedingungen:

$x\leq 0$

$y\leq 0$

$x==y$

Im Fall des Abbruchs wird eine Evaluierung oder Ausnahme angegeben.

• Bedingungen für rekursive Verwendung der Funktion, "einfachste" Rekursion zuerst

1. $x,y>0,~x\geq y$
2. $x,y>0,~y<x$

Im Fall der Rekursion wird eine Evaluierung angegeben.

Programm

public static int ggT(int x, int y)
{
     if  ((x <= 0) || (y <= 0))
         throw new ArithmeticError(“negative Daten bei ggt“));
     else   if  (x==y)  then return x;
               else   
                         if x > y  then return ggT(y,x);
                         else return ggT(x,y-x);
}

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