AlgoDat an der NORDAKADEMIE Hochschule der Wirtschaft

Namensgeber:
Muhammed al-Chwarizmi

finit (statisch)
Die Beschreibung des Algorithmus besitzt eine endliche
Länge

finit (dynamisch)
Zu jedem Zeitpunkt wird nur endlich viel Speicher benötigt

effektiv
Jeder Schritt des Algorithmus muss tatsächlich („mechanisch“)
ausführbar sein

reproduzierbar
Der Algorithmus ist unabhängig von einer speziellen
Implementierung

terminierend
Der Algorithmus liefert für jede Eingabe nach endlich vielen
Schritten ein Ergebnis

korrekt
Der Algorithmus liefert für alle definierten Eingaben das
spezifizierte Ergebnis

deterministisch
Der Verfahrensablauf ist zu jedem Zeitpunkt fest
vorgeschrieben

determiniert
Gleiche Eingaben führen immer zum gleichen Ergebnis

effizient
Der Algorithmus geht sparsam mit den für die Lösung
des Problems benötigten Ressourcen (Rechenzeit und
Speicherplatz) um

Er fndet den ggT von n und m. Zwei nicht negativen ganzen Zahlen.

Sei m jeweils die nicht-kleinere der beiden Zahlen

Es gilt: ggT(m, n) = ggT(n, m mod n)

Wende die Formel an, bis n = 0. Dann ist m der
gesuchte ggT

Beispiel:
ggT(60,24) = ggT(24,12) = ggT(12,0) = 12

Schritt 1: Falls n = 0, gib m zurück und halte an. Anderenfalls gehe zu Schritt 2.

Schritt 2: Teile m durch n ganzzahlig und merke dir den Rest der Division in r.

Schritt 3: Weise m den Wert von n zu und n den Wert von r. Gehe zu Schritt 1.

Algorithmus Euklid(m, n)
// Berechnet den ggT(m, n) gemäß Euklids Algorithmus
// Eingabe: Zwei nicht-negative Ganzzahlen m und n,
// die nicht beide 0 sein dürfen
// Ausgabe: Größter gemeinsamer Teiler von m und n
while n≠ 0 do
r ← m mod n
m ← n
n ← r
return m

An Programmiersprachen angelehnte Notationsform von Algorithmen

Dient zur kurzen und präzisen Beschreibung des algorithmischen Kerns
• Keine Überprüfung von Eingaben
• Keine explizite Fehlerbehandlung

Soll ohne besondere Vorkenntnisse verständlich sein

Umfasst nur wenige, zentrale Konstrukte

Benutzt eine einfache, elementare Syntax

• Brute Force
• Decrease-and-Conquer
• Divide-and-Conquer
• Transform-and-Conquer
• Space andTime Tradeoffs
• Dynamic Programming
• Greedy Technique
• Iterative Improvement
• Backtracking
• Branch and Bound

• Lineare Datenstrukturen
  • Arrays
  • Einfach verkettete Listen
  • Doppelt verkettete Listen
• Graphen
  • als Adjazenzlisten
  • als Adjazenzmatrizen
• Bäume
  • Binärbäume
  • n-äre Bäume

• Pfad: Folge von adjazenten Ecken
  • Einfacher Pfad: Keine Ecke taucht mehrmals auf
  • Pfadlänge
    • Ungewichtete Graphen:
      Anzahl der Kanten im Pfad
    • Gewichtete Graphen:
      Summe der Gewichte der Kanten
• Verbundene Ecken:
  Zwei Ecken u und v heißen verbunden, wenn ein Pfad zwischen u und v existiert

• Wurzelbaum mit dem Grad 2 (2-ärer Baum)
• Benennung der direkten Knotennachfolger:
  • linkes Kind/linker Sohn (left child)
  • rechtes Kind/rechter Sohn (right child)
• Sortierter Binärbaum (= binärer Suchbaum)
  • Binärbaum und für alle Knoten gilt:
    • Wert aller linken Nachfolger ≤ Wert des Knotens
    • Wert aller rechten Nachfolger > Wert des Knotens

Bei manchen Algorithmen hängt die Effizienz von der
Beschaffenheit der Eingabe ab:
 Schlechtester Fall (worst case)
• Cworst(n): Maximum bei Eingaben der Größe n
 Bester Fall (best case)
• Cbest(n): Minimum bei Eingaben der Größe n
 Mittlerer Fall (average case)
• Cavg(n): „Mittel“ bei Eingaben der Größe n
• Annahmen über die Beschaffenheit und Wahrscheinlichkeit
von „typischen“ Eingaben notwendig
• NICHT Durchschnitt von bestem und schlechtestem Fall