Algorithmen und Datenstrukturen

Algorithmen

Game of life
Geburtstagsproblem

MinMax, AlphaBeta

* Syntaxbaum erstellen
* 8-Damen-Problem
* Sortieralgorithmen
  * Bubblesort, Insertsort, Mergesort, Quicksort (+ randomisiert), Median-of-three, Heapsort

* Datenstrukturen

Verkettete Listen
Stack
- umgekehrte polnische Notation
Queue
Dequeue
Binäre Bäume

Sonstiges
- Pipes auf der Bash
- Sierpinski-Sieb (Huhn)
- O-Notation

Klausur

Umwandlung Postfix/Infix
Lineare Rekursion
* Traversierung von Bäumen
Binärbäume
Komplexität von Algorithmen bestimmen, Laufzeitanalyse (quadratisch, kubisch etc.)
Codeoptimierung
Arrays mit Quicksort sortieren (C: qsort)
Heapsort, Countingsort, Radixsort
Backtracking (Was gibt vorgegebenes Programm aus?)

Postfix / Infix

mathematische Ausdrücke werden ublicherweise in der so genannten Infix-Schreibweise geschrieben:
```
(4 + 5) * (3 - 1) / 9
```
man kann solche Ausdrücke aber auch in der so genannten umgekehrten polnischen Notation angeben:
```
4 5 + 3 1 - * 9 /
```
Vorteile
- keine Berücksichtigung von Prioritäten der Operatoren nötig, es werden keine Klammern benötigt
```
* kann leicht mit Hilfe eines Stacks implementiert werden
```
  * Umwandlung Infix → Postfix (alle Ausdrücke müssen geklammert sein)
- Ausdruck von links nach rechts durchgehen
- Zahlen direkt ausgeben
- Operatoren auf den Stack legen
- bei schließender Klammer den obersten Operator ausgeben

Bäume

Ein Baum ist eine nicht-leere Menge von Knoten und Kanten, die gewisse Bedingungen erfüllen.
Ein Knoten ist ein Objekt, das einen Namen haben und weitere Informationen beinhalten kann.
Eine Kante ist eine Verbindung zwischen zwei Knoten.
Ein Pfad ist eine Folge von unterschiedlichen Knoten, die durch Kanten im Baum miteinander verbunden sind.
Die Wurzel eines Baums ist ein besonderer Knoten, der den Ursprung des Baums kennzeichnet. Es gilt immer, dass es zwischen der Wurzel und jedem beliebigen anderen Knoten eines Baums genau einen Pfad gibt.
Jeder Knoten (außer der Wurzel) hat genau einen Vorgänger, der sich direkt über ihm befindet und als sein direkter Vorgänger (parent) bezeichnet wird. Knoten, die sich direkt unter einem Knoten beﬁnden, werden als seine direkten Nachfolger (children) bezeichnet.
Entsprechend eines Familienstammbaums spricht man auch von einem Großelterknoten oder von Geschwisterknoten.
Blätter, Endknoten und äußere Knoten sind Knoten ohne Nachfolger.
Innere Knoten sind Knoten mit mindestens einem Nachfolger.
Jeder Knoten ist die Wurzel eines Unterbaums, der aus ihm und den Knoten unter ihm besteht.
Die Ebene eines Knotens ist die Anzahl der Knoten auf dem Pfad von diesem Knoten zur Wurzel, wobei der Knoten selbst nicht mitgezählt wird und die Höhe eines Baums ist seine höchste Ebenennummer. Die Pfadlänge eines Baums ist die Summe der Ebenen aller Knoten.
Ein Wald ist ein Menge von Bäumen.
Geordnete Bäume sind Bäume, bei denen die Reihenfolge der direkten Nachfolger bei jedem Knoten festgelegt ist. Ist diese Reihenfolge nicht fest vorgeschrieben, spricht man von ungeordneten Bäumen.
Falls jeder Knoten nur eine bestimmte Anzahl n von direkten Nachfolgern haben darf, die in einer bestimmten Reihenfolge vorliegen müssen, spricht man von einem n-ären Baum.

Binärbäume

Der einfachste Typ eines n-ären Baums ist der binäre Baum, für den Folgendes gilt:
- Es ist ein geordneter Baum mit zwei Typen von Knoten: inneren und äußeren Knoten. Innere Knoten haben immer maximal zwei direkte geordnete Nachfolger, die man auch als linker und rechter Nachfolger bezeichnet. Äußere Knoten sind Knoten ohne Nachfolger.
- Ein binärer Baum ist leer, wenn er nur aus einem äußeren Knoten besteht und keinen inneren Knoten besitzt.
- Ein voller binärer Baum ist ein binärer Baum, in dem sich in keiner Ebene, außer in der vorletzten, äußere Knoten befinden.
- Ein vollständiger binärer Baum ist ein voller binärer Baum, bei dem sich in der letzten Ebene nur äußere Knoten befinden.
- Für zwei Knoten in einem binären Baum gibt es immer nur genau einen Pfad, der sie verbindet.
- Ein binärer Baum mit n inneren Knoten hat n+1 äußere Knoten.
- Die äußere Pfadlänge eines binären Baums mit n inneren Knoten ist immer um 2n größer als die innere Pfadlänge.
- Ein Baum mit n Knoten hat immer n-1 Kanten.
- Die Höhe eines vollen binären Baums mit n inneren Knoten ist die nächste ganze Zahl zu log2(n).
Binärbäume vereinen die Vorteile von Arrays (schneller Zugriff auf ein Element) mit den Vorteilen von Listen (leichtes Einfügen/Löschen eines Elements).
Sie lassen sich am Besten mittels Rekursion verwalten.
nicht-binäre Bäume können einfach als binäre Bäume implementiert werden, indem jeder Knoten zwei Zeiger bekommt: einen auf sein erstes Kind (verkettete Liste aller Kinder) und einen auf seinen nächsten Geschwisterknoten
in balancierten Binärbäumen haben alle Knoten in etwa die gleiche Tiefe: bei n Knoten ist die Höhe log₂(n+1)
bei einem balancierten Binärbaum sind somit maximal log₂(n+1) Vergleiche (=Höhe des Binärbaums) notwendig, um ein Element in einem solchen balancierten Binärbaum zu ﬁnden

Heap

ein Heap ist ein Binärbaum, in dem alle Knoten Werte besitzen, die größer (oder gleich) sind als alle Werte ihrer Kindknoten
der größte Wert befindet sich somit im Wurzelknoten
Darstellung als Array: [0] = Wurzel, [1] und [2] 1. Ebene, [3], [4], [5], [6] 2. Ebene etc.
- Vorgänger des i. Knotens: i/2 (i » 1)
- linker Nachfolger des i. Knotens: 2i (i « 1)
- rechter Nachfolger des i. Knotens: 2i + 1 ( (i « 1) + 1)
Heap (= Binärbaum) mit n Knoten hat Höhe lg n, also können alle Operationen auf einem Heap mit O(lg n) durchgeführt werden
* Max-Heap: Nachfolger-Knoten haben kleinere Werte, Min-Heap: Nachfolger-Knoten haben größere Werte
Wiederherstellen der Heap-Eigenschaft mittels maxHeapify

Traversierung

Preorder: Bearbeite zuerst die Wurzel, dann bearbeite den vollständigen linken Unterbaum und anschließend den vollständigen rechten Unterbaum zu dieser Wurzel.
Inorder: Bearbeite zuerst den vollständigen linken Unterbaum, dann die Wurzel und anschließend den vollständigen rechten Unterbaum zu dieser Wurzel.
Postorder: Bearbeite zuerst den vollständigen linken Unterbaum, dann den vollständigen rechten Unterbaum und schließlich zuletzt die Wurzel zu diesen Unterbäumen.
Levelorder: Bei dieser Art der Traversierung wird von oben nach unten jede einzelne Ebene des binären Baums durchlaufen, wobei die einzelnen Ebenen von links nach rechts traversiert werden.

Lineare Rekursion

eine Funktion heißt rekursiv, wenn sie sich selbst oder ein von ihr aufgerufenes Programm sie selbst wieder aufruft
Rekursion ist eine Wiederholung durch Schachtelung → Schachtelmodell
jede Rekursion kann durch entsprechende Wiederholungen ausgedrückt werden und umgekehrt
Beispiele für Anwendung von Rekursion
- Quadratzahlen: n² = (n - 1)² + 2n - 1
- größter gemeinsamer Teiler: ggT(n, m) = 0, wenn m = 0, sonst ggT(m, n mod m)
- Dreieckszahlen: (k * (k + 1)) / 2
- Umwandlung von Dezimal- in Dualzahl: bis zahl = 0: rest = zahl % 2, zahl = zahl / 2; Reste umgekehrt ausgeben'
wenn eine Funktion sich mehrmals aufruft erhält man eine nicht-lineare Rekursion in Baumstruktur
- Fibonacci-Zahlen: F(0) = 1; F(1) = 1; F(n) = F(n - 2) + F(n - 1)
- Binomialkoeffizient: n über k = 1, wenn n oder k = 0, sonst (n - 1 über k) + (n - 1 über k - 1)
- Pascal'sches Dreieck

Analyse von Algorithmen

generell sollte darauf geachtet werden, performante Algorithmen zu verwenden, also z.B. lineare und nicht kubische
die einzelnen Operationen werden bei der Laufzeitanalyse nicht berücksichtigt, obwohl sie sich eigentlich in ihrer Laufzeit unterscheiden (z.B. Bitverschiebung und Potenz)
Laufzeit einiger Sortieralgorithmen
- Bubble-Sort: n²
- Select-Sort: n²
- Insert-Sort: WorstCase n², BestCase linear
bei der Ermittlung des Zeitbedarfs sollte immer vom WorstCase ausgegangen werden, da diese Grenze niemals überschritten werden kann und meist der AverageCase sich diesem annähert
* für die Analyse der Laufzeit ist eigentlich nur der Wachstumsgrad entscheidend, konstante Faktoren und Potenzen geringerer Ordnung werden bei großen n irrelevant
ein Algorithmus ist effizienter als ein anderer, wenn er im ungünstigsten Fall einen geringeren Wachstumsgrad hat
Überlegungen bei der Wahl eines Algorithmus
- Kosten-/Nutzenanalyse: effizientere Algorithmen benötigen vielleicht eine längere Entwicklungszeit, die bei seltener Nutzung des Algorithmus nicht gerechtfertigt ist
- bessere Algorithmen sind nicht immer deutlich komplizierter: vor der Entscheidung also erstmal schauen, wie einfach die Implementierung wirklich ist
- Flaschenhälse: bei langsamen Programmen muss evtl. nicht der komplette Algorithmus neu geschrieben werden, sondern evtl. nur die Flaschenhälse, die es hierfür natürlich zu identifizieren gilt
- Messung mit typischen Eingabedaten: die Entscheidung für einen Algorithmus sollte auf Basis von Messungen mit echten Daten erfolgen, da diese evtl. erheblich vom WorstCase abweichen

Codeoptimierungen

wo es geht Konstanten anstatt von Variablen verwenden (constant propagation)
einmalige Berechnung gleicher Ausdrücke (common subexpression elimination)
keine überflüssigen Funktionsaufrufe (Operatoren sind meist schneller)
Bitshifts beim Rechnen mit Zweierpotenzen verwenden (operator strength reducing)
keine überflüssigen oder doppelten Berechnungen (copy propagation)
Vermeiden überflüssiger Schleifendurchläufe durch Verwenden des passenden Inkrements (z.B. i += 10 anstatt i++) (loop strength reduction)
Entfernen invarianter Ausdrücke (Berechnungen mit immer gleichem Ergebnis in der Schleife oder dem Schleifenkopf) aus Schleifen (invariant code motion)
Zusammenfassen mehrerer Schleifen zu einer (loop jamming) und Vermeidung unnötiger Indexzugriffe auf Arrays

Sortieralgorithmen

Unterscheidung
- Speicherstelle der Daten
  - Intern: Daten im Arbeitsspeicher
  - Extern: Daten auf Peripheriegerät
  - Index-sequentiell: Daten mit Schlüssel, nach dem sie sortiert werden sollen
- Laufzeit (liegt zwischen n lg n und n²)
- Speicherplatz
  - in-place: kein zusätzlicher Speicherplatz (außer vielleicht kleines Array oder Stack)
  - zusätzlicher Speicher für n Zeiger
  - doppelter Speicherplatz für Kopie der Daten
```
* Stabilität: stabile Sortieralgorithmen behalten die relative Reihenfolge der Elemente bei, wenn das Sortierkriterium gleich ist
```
    * Quicksort
- Komplexität O(n lg n), WorstCase n²
- in-place mit kleinem Hilfsarray
- rekursiv
- WorstCase ist bereits sortiertes Array, kann mit Tricks optimiert werden
  - zufällige Auswahl des Pivotelements
  - Insertsort für kleine Teilarrays verwenden
```
  * Entrekursivierung: zweiten rekursiven Aufruf durch while ersetzen
  * Median-of-Three-Methode
  * Drei-Wege-Partitionierung
* Quicksort in C (''stdlib.h''): ''void qsort(void *array, size_t n, size_t length, int (*compare)(const void *val1, const void *val2))'' 	  	        
```
    * Heapsort
- Komplexität O(n lg n)
- in-place mittels Heap
  * Counting-Sort
- Komplexität O(n)
- verwendet ein Ausgabearray und ein Hilfsarray für die Häufigkeitsverteilung der Werte
```
* Sortierung über Häufigkeitsverteilung der Werte (z.B. 5 Werte kleiner als "g", also muss "g" Index 5 im neuen Array bekommen)  
```
  * Radix-Sort
- Partitionierung der Daten z.B. anhand von Anfangsbuchstaben und rekursives Sortieren
```
* Sortierung anhand des Bitmusters von Zahlen
* Radix Exchange Sort: Bitmuster von links nach rechts durchgehen, 0 vor 1 einsortieren    
* Straight Radix Sort: quasi ein Counting-Sort für Bitmuster von rechts nach links
```

Backtracking

Backtracking ist ein Lösungsverfahren nach dem Trial-and-Error-Verfahren
über Teillösungen soll zu einer Lösung des Gesamtproblems gefunden werden
wenn ein Teilproblem nicht mehr weiter lösbar ist ("Sackgasse"), werden die vorherigen Teilschritte soweit rückgängig gemacht, dass ein anderer Weg ausprobiert werden kann
Beispiele
- Wegfindung im Labyrinth (Maus sucht Käse)
- Teilsummenermittlung
- Acht-Damen-Problem
- Sudoku

ToDo

Wichtige Bereiche im Skript mit Klebi kennzeichnen
~~Umwandlung Postfix/Infix~~
~~Lineare Rekursion~~
~~Binärbäume~~
- ~~Traversierung von Binärbäumen implementieren~~
~~Komplexität von Algorithmen bestimmen, Laufzeitanalyse (quadratisch, kubisch etc.)~~
~~Codeoptimierung~~
~~Arrays mit Quicksort sortieren (C: qsort)~~
~~Heapsort, Countingsort, Radixsort~~
~~Backtracking (Was gibt vorgegebenes Programm aus?)~~
Beispiele für Ermittlung der benötigten Zeit nachrechnen
~~Codeoptimierungen ins Wiki eintragen~~