Die Webseiten der Fachschaft Informatik am ERG Saalfeld


Algorithmus - Definition und Eigenschaften

Definition

Wikipedia: Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems.

Anmerkung:

Algorithmen bestehen aus endlich vielen, wohldefinierten(!) Einzelschritten. Somit können sie zur Ausführung in einem Computerprogramm implementiert, aber auch in menschlicher Sprache formuliert werden. Bei der Problemlösung wird eine bestimmte Eingabe in eine bestimmte Ausgabe überführt.

Eigenschaften:

  • Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
  • Jeder Schritt des Verfahrens muss tatsächlich ausführbar sein (Ausführbarkeit).
  • Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit).
  • Das Verfahren darf nur endlich viele Schritte benötigen (Terminierung).

Häufig werden noch folgende zusätzliche Anforderungen an einen Algorithmus gestellt:
  • Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
  • Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).

Beispiel - der euklidische Algorithmus

Man bildet von den beiden gegebenen Zahlen die Differenz, wobei von der größeren Zahl die kleinere Zahl abgezogen wird. Man streicht von den 3 Zahlen die größte und setzt das Verfahren fort bis die Differenz 0 ergibt. Der dazugehörige Minuend (oder auch Subtrahend) ist der ggT der beiden Zahlen.

     
       40
     - 24
     -----
       16
      
     
       24
     - 16
     -----
        8
      
     
       16
     -  8
     -----
        8
      
     
        8  <- ggT
     -  8
     -----
        0
      
        Hinweis: Um die Differenz bilden zu können, muss von der größeren die kleinere Zahl abgezogen werden. Dazu sind die beiden Zahlen zu sortieren. (alternativ arbeite man mit 2 Differenzen).

 

Programm

import sys

a = int(sys.argv[1])
b = int(sys.argv[2])

# da wir a-b rechnen wollen, muss a > b sein -> sonst tauschen
if a < b:
    help = a
    a = b
    b = help

# damit wir auf die Differenz testen können, bilden wir diese
differenz = a - b

#  solange wie die Differenz nicht 0 ist
while differenz != 0:
    a = b
    b = differenz
    # falls $a < $b dann müssen wir tauschen
    if a < b:
        help = a
        a = b
        b = help
    # wir bilden die Differenz
    differenz = a - b

# da der Abbruch ist, wenn differenz = 0   => haben wir den ggT
print("Der ggT ist ",a)

 

Screenshot:

 

Untersuchen der 4 Eigenschaften von Algorithmus an diesem Beispiel:

  1. Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
    • Die 3 Sätze direkt unter "Beispiel - der euklidische Algorithmus" => endlich und eindeutig
  2. Jeder Schritt des Verfahrens muss tatsächlich ausführbar sein (Ausführbarkeit).
    • Es kann immer eine größere der Zahlen gefunden werden, damit ist immer das sortieren möglich.
    • Die Differenz kann immer gebildet werden.
    • Von den 3 Zahlen kann immer die größte Zahl gestrichen werden.
  3. Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit).
    • das Verfahren braucht nur für die Variablen a, b und help und für den Programmcode Platz und ist damit endlich.
  4. Das Verfahren darf nur endlich viele Schritte benötigen (Terminierung).
    • Die Differenz wird immer kleiner
    • Da nur natürliche Zahlen als Differenz und diese immer kleiner, wird die Differenz auf jeden Fall mal 0 => endlich viele Schritte

 

Quellen

 

zurück


© ERG Saalfeld   -   Dustin Wiese   08.10.2020