AD - Algorithmen FS17

Teile und Herrsche

Ein Heap ist ein binärer Baum, der:

• eine strukturelle Bedingung erfüllt, d.h. voll ist
• eine inhaltliche Bedingung erfüllt, d.h. jeder innere Knoten ≥ als seine Söhne ist,
• in einem Array abgespeichert ist.

O(log₂ n)

Nein

• Best Case = O(n log n)
• Worst Case = O(n log n)
• Average Case = O(n log n)

Ein komplexes Problem durch Zerlegen in einfachere Teilprobleme lösen:

1. Problem in Teilprobleme zerlegen.
2. Teilprobleme lösen.
3. Teillösungen zur Gesamtlösung zusammensetzen.

• eine Lösungsfindung
• einen rekursiven Lösungsansatz
• parallelisierbare Lösungen (falls Teilprobleme unabhängig lösbar)
• eine Reduktion des Lösungsaufwandes

• boolean equals(Object obj)
• int hashCode()

• static void sort(int[] a)
• static void sort(Object[] a)
• static <T> void sort(T[] a, Comparator<? super T> c)

• static <T extends Comparable<? super T>> void sort(List<T> list)
• static <T> void sort(List<T> list, Comparator<? super T> c)

Collection in Array umwandeln:
Interface java.util.Collection<E>

• Object[ ] toArray()
• <T> T[ ] toArray(T[] a)

Array in Liste umwandeln:
Klasse java.util.Arrays

• static <T> List<T> asList(T... a)

für ungleiche Objekte, deshalb Set:
Klasse java.util.TreeSet<E>
 - TreeSet()
 - TreeSet(Comparator<? super E> comparator)
Klasse java.util.Collections
 - static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)

für Key/Value-Paare, deshalb Map:
Klasse java.util.TreeMap<K,V>
 - TreeMap()
 - TreeMap(Comparator<? super K> comparator)
Klasse java.util.Collections
 - static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m)

• Steuerungsautomaten (Ampelsteuerung, Billettautomat, Waschmaschine, Prozessor)
• Lexikalische Analyse (Gehört ein vorliegendes Wort zur Sprache?)
• Textsuche (Kommt ein bestimmtes Muster in einem Text vor?)
• Kommunikationsprotokolle
• Verarbeiten von Ereignisfolgen
• Verhaltensmodellierung (Steuerung, System, Dialog)

• Allgemeiner-Automat
• Mealy-Automat
• Moore-Automat

Ein Zustandswechsel ohne expliziete Ausgabe.

Ein Zustandswechsel (Zustandsübergang), der selber eine Ausgabe bewirkt.

Ein Zustandswechsel. Jeder Zustand bewirkt selber eine Ausgabe.

Verschachtelte Switch statements.

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

In diesem Speicherbereich werden die Objekte gespeichert, d.h. deren Instanzvariablen bzw. Zustände. Nicht mehr referenzierbare Objekte werden durch den Garbage Collector (GC) automatisch gelöscht.

Bei der Ausführung eines Programms «eine Kette» von Methoden abgearbeitet. Jeder Methodenaufruf bedingt gewissen Speicher, insbesondere für Parameter und lokalen Variablen. Dazu dient der Call Stack. Ein neuer Methodenaufruf bewirkt, dass der Call Stack wächst bzw. darauf ein zusätzlicher Stack Frame angelegt wird.

Sie sind gleich mächtig:

• Die Menge der berechenbaren Problemstellungen bei Verwendung der Rekursion und Verwendung der Iteration ist gleich.
• Eine rekursive Implementation lässt sich grundsätzlich immer in eine gleichwertige iterative Implementation umprogrammieren und umgekehrt.

• mächtiges Lösungskonzept
• häufig einfache und elegante Problemlösungen
• weniger Quellcode
• Korrektheit häufig einfacher zu zeigen
• Gewisse Programmiersprachen (zB Lisp, Prolog) kennen nur Rekursion!

• schnell sehr viele Methodenaufrufe
• tendenziell langsamere Programmausführung
• grosser Speicherbedarf auf dem Call Stack
• Gefahr eines Stack Overflow!

⇒ Bei Wahlmöglichkeit eine iterative Implementierung bevorzugen!

Schneller & Effizienter Zugriff auf gewünschte Daten.

Beispiele:

• Person mit bestimmter ID
• Prozess mit höchster Priorität
• Zugsverbindung mit Abfahrtszeit früher als x
• Taxi, das am nächsten ist

Eine Menge an Datenelementen die:

• eine Totale Ordnung haben (x ist kleiner/grösser/gleich y)
• vergleichbar sind (z.B. durch einen Key/Schlüssel)

• Interface Comparable<T> mit int compareTo(T o)
  → für die natürliche Ordnung
• Interface Comparator<T> mit int compare(T o1, T o2)
  → für jede spezielle Ordnung.

O(n * log n)

O(n)

• Daten liegen im Arbeitsspeicher vor.
• Direktes Vergleichen der Daten möglich.
• Internes Sortieren ist primär von Bedeutung.
• Beispiel: Sortieren von Arrays