1 - Algorithmen

• löst Problemklasse

Problemklasse: Allgemein auf mehrere Probleme der gleichen Art anwendbar

• Größter gemeinsamer Teiler zweier ganzer Zahlen

Probleminstanz: Nur auf ein bestimmtes Problem anwendbar

• Größter gemeinsamer Teiler von 84 und 231

Alle Algorithmen bestehen aus grundlegenden Bestandteilen und verwenden wiederkehrende Prinzipien

• elementare Operationen

• bedingte Ausführung

• sequenzielle Ausführung

• Iteration

• Rekursion

• Brut-Force

• Teile-und-herrsche

• Greedy

• Rekusion

• “rohe Gewalt”

• Lösung durch Ausprobieren aller möglichen Lösungen

• einfach zu implementieren

• finden theoretisch immer Lösung

• ineffizient & langsam

• praktisch selten anwendbar

  • Bsp.: Erraten einer Pin

  • Je größer Zahl, desto längere Dauer

1. Divide - Zerlegung in Teilprobleme

2. Conquer - Conquer

3. Merge - Zusammensetzen der Gesamtlösung

• verwenden häufig Rekursion

  • Bsp.: MergeSort, QuickSort

  • keine Aussage über Zusammenhänge treffbar

• schrittweises Vorgehen

• Beurteilung aller möglichen Folgezustände in jedem Schritt

• Auswahl des zu diesem Zeitpunkts besten Schritts

• schnelle Lösung (lokales Optimum, nicht beste Lösung (globales Optimum)

  • Bsp.: Gradientenverfahren zur Nullstellensuche

• direkte oder indirekte Selbstbezüglichkeit

• Abbruchbedingung benötigt

• Phasen

  • Abstieg/Aufwicklung

  • Aufstieg/Abwicklung

• jeder Rekursionsaufruf erzeugt neue Version der Variablen

• Speicherprobleme, weil ursprüngliche Werte zwischengespeichert werden müssen

  • Bsp.: Fakultät, Türme von Hanoi

• Komplexität - Maß für Effizienz eines Algorithmus

  • wird in Abhängigkeit des Umfangs des Problems gemessen (Problemgröße n)

• Problem kann n unterschiedliche Bedeutungen annehmen

  • Anzahl der zu sortierenden Elemente

  • Länge einer Zeichenkette bei Suchen eines Wortes

• Prozesse verbauchen zwei Ressourcen

  • Rechen-/Laufzeit - Zeitkomplexität

  • Speicherplatz - Platzkomplexität

• Laufzeitmessung einfach, aber Ergebnis abhängig von

  • Problemgröße

  • Probleminstanz

  • Hardware

• nicht geeignet, um Zeitkomplexität systematisch zu vergleichen, sondern nur auf ein und demselben Chip

  
  

• Abschätzung der Anzahl der Rechenschritte

• Untersuchung des Wachstums der Anzahl der Rechenschritte bei steigender Problemgröße

• Verwendung Landau-Notation

• Unterscheidung Best-, Average- und Worst-Case

1. Elementare Operationen haben die Komplexitätsklasse 0(1)

   • konstante Laufzeit

2. Bei iterativer Ausführung eines inneren Programmteils durch einen äußeren, multiplizieren sich die Laufzeiten

3. Konstanten werden nicht berücksichtigt

4. Bei sequentieller Ausführung zweier Programmteile, wird die Laufzeit von der schneller wachsenden Komplexitätsklasse bestimmt