Kapitel 3

• Genaue Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen

• Ein Algorithmus ist eine präzise, d.h. in einer festgelegten Sprache abgefasste, endliche Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer (Verarbeitungs-)Schritte

• Problembezogene Eigenschaften: nehmen immer Bezug auf entsprechende Spezifikation des Problems

  • Korrektheit

  • Effizienz

• Problemunabhängige Eigenschaften: beziehen sich ausschließlich auf betrachteten Algorithmus, nicht jedoch auf das Problem oder dessen Spezifikation

  • Endlichkeit

  • Terminiertheit

  • Determiniertheit & Determinismus

  • Rekursivität

  • Parallelität

• Ein Algorithmus ist korrekt, wenn er in allen denkbaren Fällen eine korrekte Lösung seiner Aufgabe liefert

• Verbunden mit der funktionalen Sicht (“Was?”), d.h. mit der Aufgabe, die durch einen Algorithmus bewältigt werden soll

• Ein Algorithmus ist effizient, wenn er seine Aufgabe unter Verwendung von möglichst wenig Ressourcen löst

• Ressourcen sind:

  • Anzahl der Berechnungsschritte

  • benötigter Speicherplatz

  • Netzwerk Bandbreite

• Ein Algorithmus muss endlich beschreibbar sein, d.h. er muss durch einen endlichen Text formulierbar sein

• Endlichkeit bezieht sich auf Beschreibung eines Algorithmus, nicht auf seine Ausführung

  • kann dazu führen, dass der Algorithmus zwar durch endlich viele Schritte beschrieben ist, aber nicht terminiert

• Ein Algorithmus ist terminierend, wenn er für jede erlaubte Eingabe von Parameterwerten nach einer endlichen Zahl von Schritten (endliche Laufzeit) zu einem Ergebnis kommt/ abbricht

• Ein Algorithmus muss nach endlicher Zeit kontrolliert enden

• Ein Algorithmus ist determiniert, wenn er bei gleichen Parametern und Startwert stets das gleiche Resultat liefert

• Bei vorgegebener Eingabe eindeutiges Ergebnis auch bei mehrfacher Durchführung

• Algorithmus ist nicht determiniert, wenn dessen Ausgabe zum Teil auf dem Zufall beruht

• Ein Algorithmus ist deterministisch, wenn zu jedem Zeitpunkt seiner Ausführung der nachfolgende Abarbeitungsschritt des Algorithmus eindeutig festgelegt ist

• Deterministische Algorithmen mit eindeutigen Vorgaben der Schrittfolgen

• 
  

• Determiniertheit

  • Bei Eingabe gleicher Parameter kann Schrittfolge anders sein, aber Ergebnis ist immer gleich

• Determinismus

  • Bei Eingabe gleicher Parameter, gleiche schrittfolge und somit auch gleiches Ergebnis

  • Jeder deterministische Algorithmus ist stets determiniert, wenn er terminiert

• Ein Algorithmus heißt rekursiv, wenn er sich selbst wieder benutzt

• Rekursionsanker (ohne Selbstbezug): wenn Rekursionsanker erreicht, dann wird das Ergebnis sofort zurückgegeben

• Rekursionsschirtt (mit Selbstbezug): definiert Funktion mit Hilfe rekursiver Aufrufe

• Direkte Rekursion: Algortihmus ruft sich selber wieder auf

• indirekte Rekursion: mehrere verschiedene Algorithmen rufen sich wechselseitig auf

• Ein Algorithmus heißt parallel, wenn er so in Teilaufgaben aufgeteilt ist, dass diese gleichzeitig durch verschiedene Prozessoren ausgeführt werden könenn

Die Laufzeitkomplexität bezeichnet die Betrachtung des Laufzeitverhalten eines Algorithmus in Abhängigkeit vom Umfang seiner Eingabedaten

• einfache lineare Suche

  • schlechtester Fall: Nummer ist am Ende des Feldes -> Schleife läuft “n”x durch -> Komplexität O(n)

• Binäre Suche

  • Schlechtester Fall: gesuchte Nummer ist am Rand bzw. nicht im Array

    • Das Feld ist n Felder lang. Es wird immer geteilt -> n -> n/2 -> n/4 etc. (n/2^x)

    • Das läuft so lange bis die Länge des Feldes nur noch 1 ist

    • Die Anzahl der Durchläufe x errechnet sich: n/2^x=1 -> x=log2(n) -> O(log(n))

• Bubblesort - Laufzeitkomplexität im Durchschnitt O(n^2)

  • Algorithmus vergleicht der Reihe nach zwei benachbarte Elemente; vertauscht sie, falls falsche Reihenfolge vorliegt

  • Wiederholung solange, bis keine Vertauschungen mehr nötig sind

• Mergesort - Laufzeitkomplexität O(nlog(n))

  • Betrachtung der zu sortierenden Daten als Liste, Zerlegung in kleinere Listen, die unabhängig voneinander sortiert werden

  • Zusammenfügen der sortierten kleinen Listen zu größeren Listen bis sortierte Gesamtliste erreicht ist

• Quicksort - Laufzeitkomplexität im Durchschnitt O(nlog(n))

  • Algortihmus teilt Liste von Elementen in zwei Teillisten aufgrund von Vergleichen mit speziellen Pivotwert

  • Elemente, die kleiner als das Pivotwert sind, kommen in die erste Liste, die anderen in die zweite

  • Beide Teillisten werden dann auf dieselbe Art und Weise getrennt voneinander sortiert