Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Algorithmusbegriff

Aus Wikiversity

Begriffserklärung Algorithmus[Bearbeiten]

Algorithmen im Alltag[Bearbeiten]

  • Bedienungsanleitungen
  • Gebrauchsanleitungen
  • Bauanleitungen
  • Kochrezepte
  • Berechnungsvorschriften (z.B. Berechnung der Fakultät)

Intuitive Begriffserklärung Algorithmus[Bearbeiten]

„Ein Algorithmus ist eine präzise (d.h. In einer festgelegten Sprache formulierten), endliche Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer Verarbeitungsschritte.“


Definitionen[Bearbeiten]

Algorithmus

  • „systematische Verarbeitung“
  • Eine eindeutige Beschreibung eines in mehreren Schritten durchgeführten Bearbeitungsvorgangs
  • Ein Algorithmus ist ein allgemeines Verfahren zur Lösung eines Problems ohne Bezug auf einen konkreten Prozessor.

Programm

  • Ein Programm ist eine konkrete Formulierung eines Algorithmus für eine konkrete Klasse von Prozessoren.

Prozessor

  • Ein Prozessor ist etwas, das die Fähigkeit hat, Programme auszuführen.

Datenstrukturen

  • „Ordnungsschema“
  • Eine Struktur zur Verwaltung von Daten
  • Darstellung von Informationen in maschinenverarbeitbarer Form
  • Charakterisieren Daten und mögliche Operationen auf Daten

Transformationelle Probleme[Bearbeiten]

Ein Algorithmus definiert eine Transformation auf dem gesamten, durch die Eingaben definierten Zustand, aus dem als Bedeutung dann die Werte der Ausgabevariablen ausgelesen werden. Das heißt, ein Algorithmus benutzt kein weiteres Wissen neben der Eingabe und hat keine Seiteneffekte!

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

Eigenschaften von Algorithmen[Bearbeiten]

Ein Algorithmus heißt …

  • terminierend, wenn er für alle zulässigen Schrittfolgen stets nach endlich vielen Schritten endet
  • deterministisch, wenn in der Auswahl der Verarbeitungsschritte keine Freiheit besteht
  • determiniert, wenn das Resultat eindeutig bestimmt ist
  • sequenziell, wenn die Schritte stets hintereinander ausgeführt werden
  • parallel oder neben läufig, wenn gewisse Verarbeitungsschritte nebeneinander (im Prinzip gleichzeitig) ausgeführt werden
  • korrekt, wenn das Resultat stets korrekt ist
  • effizient, wenn das Resultat in „annehmbarer“ Zeit geliefert wird

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


Algorithmenentwurf[Bearbeiten]

Dieses Kapitel behandelt die Vorgehensweise zum Algorithmenentwurf.

Vom Algorithmus zur Programmausführung[Bearbeiten]

  1. Der Algorithmus wird unabhängig von Programmiersprache und Rechnerhardware entworfen
  2. Der Algorithmus wird in einer höheren Programmiersprache, z.B. Java, programmiert
  3. Das Programm wird in Maschinensprache übersetzt
  4. Die CPU interpretiert den Maschinencode und das Programm wird ausgeführt


Vom Algorithmus zum Programm
Vom Algorithmus zum Programm


Vorgehensweise Algorithmus-Entwurf[Bearbeiten]

  • Hintergrundwissen erwerben: Derjenige der ein Problem beschreibt ist oft nicht derjenige, der den Algorithmus entwirft, dadurch kommt es zu unklaren Aufgabenstellungen, unterschiedlichem Vorwissen und verschiedenen Annahmen.
  • Problem definieren: Erfordert Hintergrundwissen und Übung in der Definition von Problemen
  • Algorithmus entwerfen: Erfordert Wissen zu Algorithmen und Datenstrukturen
  • Programm erstellen: Erfordert Wissen über Programmiersprache (Java) und Programmierung
  • Lösung überprüfen: Erfordert methodisches Wissen zu Termination, Korrektheit und Effizienz

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 2 und 8.1 zu finden.

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 Schri5. (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 tri5 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.

Berechenbarkeitsbegriff[Bearbeiten]

Ein Problem (z.B. eine mathematische Funktion) heißt berechenbar, falls dafür ein Algorithmus existiert.

  • Berechenbar: Algorithmus stoppt nach endlich vielen Schritten
  •   Funktion f: W → V ist
    • partiell: Def(f) ⊆ W (Beispiel: f: ℝ → ℝ, f(x)= 1/x)
    • total: Def(f) = W

Ausgangssituation: Wir entwerfen und programmieren einen Algorithmus und wir haben eine Vorstellung was berechenbar ist (intuitiver Berechenbarkeitsbegriff). Das Problem ist nun, wie man diese Berechenbarkeit nachweisen kann. Dazu bringen wir die intuitive Form in eine mathematische Form und können diese mit mathematischen Beweisen belegen.

Formale Definitionen des Berechenbarkeitsbegriff: Turing berechenbare Funktionen, while-Programme, µ-rekursive Funktionen

Church-Turing-These[Bearbeiten]

Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen. Wobei "intuitiv" nicht exakt formalisierbar ist.

Die durchführbaren Algorithmen sind eine Teilmenge der berechenbaren Funktionen, welche wiederum eine Teilmenge aller existierenden Funktionen sind.

Funktionen
Funktionen

Beispiele[Bearbeiten]

Durchführbare Algorithmen

  • ggT, Matrizenmultiplikation, Zinsberechnung,…

Berechenbare Funktionen, die nicht durchführbar sind

  • Harte Optimierungsprobleme mit Millionen von Variablen
  • Vollständige Eigenwertberechnung auf dem Facebook-Graphen

Nicht berechenbare Funktionen

  • Haltefunktion (gibt zu einem beliebigen Programm an, ob es hält)
  • Äquivalenzfunktion (gibt zu zwei beliebigen Programmen an, ob sie das gleiche Verhalten haben)

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 6.4 und 7.1 zu finden.