AD - Algorithmen FS17

Ein Algorithmus ist ein präzise festgelegtes Verfahren zur Lösung eines Problems; genauer gesagt von einer Problem- Klasse beinhaltend (unendlich) viele gleichartige Probleme.

Algorithmus = Lösungsverfahren

Verschiedenen Algorithmen, die alle das problem einer Problemklasse lösen können.

Die Gleichwertigkeit von Algorithmen allgemein zu beweisen ist ein unlösbares Problem. Dies bedeutet, dass es kein Java-Programm geben kann, das den Quellcode von zwei Implementationen einliest und feststellt, ob sie gleichwertige Algorithmen repräsentieren oder nicht!

Algorithmen operieren auf Datenstrukturen und Datenstrukturen bedingen spezifische Algorithmen.

Wie hängt der Ressourcenbedarf von den Eingabedaten ab?

Ressourcenbedarf = f ( Eingabedaten )

Ressourcenbedarf:
- Rechenzeit → Zeitkomplexität
- Speicherbedarf → Speicherkomplexität
Eingabedaten:
- Grösse der Datenmenge
- Grösse eines Datenwertes

Konstant           O( 1 )              Hashing
Logarithmisch O( ln( n ) )      binäres Suchen
Linear                O( n )             Suchen in Texten
n log n               O( n · ln( n ) ) schlaues Sortieren
Polynomial      O( n m )          einfaches Sortieren
Exponential      O( d n )           Optimierungen
Fakultät           O( n ! )            Permutationen, TSP

• Die Ordnung ignoriert konstante Faktoren. Diese können aber praktisch relevant sein!
• Die Ordnung berücksichtigt das Verhalten bei kleinen n nicht. Langsamere Algorithmen sind aber bei kleinen n oft auch brauchbar oder gar die bessere Wahl!
• Die exakte mathematische Analyse von vielen Algorithmen ist schwierig oder sogar unmöglich!
• Häufig muss man bei der Analyse differenzieren (Best-, Worst-, Average Case). Häufig ist der mittlere Fall ein besseres Mass für die Leistung eines Algorithmus, als der schlimmste.

Viele Algorithmen und Datenstrukturen sind von Natur aus selbstähnlich bzw. selbstbezüglich:

• Der ggT von (21, 15) ist gleich dem ggT von (21-15, 15).
• Ein Verzeichnis enthält Dateien und andere Verzeichnisse.
• Ein Ausschnitt einer Matrix, einer Liste, eines Baumes, eines Graphen ist wieder eine Matrix, eine Liste, ein Baum, ein Graph.

⇒ Grundlage für Rekursion