2.1 Allgemeines und Anwendungen
	2.2 Abstrakte Datentypen (ADT)  Listen  Stapel  Schlangen  Binäre Bäume
	2.3 Komplexität von Algorithmen  Sortieralgorithmen  Suchalgorithmen  Graphenalgorithmen

Allgemeine Gedanken zum Suchen in Datenstrukturen:

Für ein erfolgreiches Suchen müssen folgende Voraussetzungen gesichert sein:

- Wir haben eine Ortsangabe für den Einstieg und für jedes Element.
- Datenelemente mit Nutzdaten
- Suchschlüssel
- geeignete Beschreibungsgrößen legen die Struktur fest
- ein Feststellungskriterium falls die Datenstruktur leer ist

Vorraussetzungen bei Suchbäumen:

- Zugänglichkeit, Zusammenhang und die Suchbaumeigenschaft
- Eingangsparameter der Schlüssel
- Durchgangsparameter des Suchbaums
- Ergebnisparameter der abgehängten Knoten
- teures Umordnen wenn die Elemente sehr gross
- Elemente über den Arrayzugriff erreichbar
- feste Elementzahl oder eine feste Maximalgrenze

Ziel: Speichereffizient und sequentieller/induzierter Zugriff.

---

2.1 Anwendungen

Graphenmarkierung:

Speicherbereinigung auf der Halde, um unerreichbare Speicherobjekte frei zu geben.

1. laufe über die Halde und entferne alle Markierungen
2. laufe über alle gültigen Pointer-Variablen, markiere das jeweils daran hängende Geflecht
3. laufe über die Halde und sammle alle unmarkierten Objekte ein

Man stelle sich das Problem vor, dass zu wenig Strukturinformationen über den Graphen vorliegen. Liegen beispielsweise nur die Informationen über Kanten vor

---

2.2 Abstrakte Datentypen (ADT)

Bezeichnungen in den Tabellen der ADTs:

SORTS	:= Liste der Sorten (=Typen), eine Menge von Werten eines Typs. Der Name des Datentyps muss hier stehen.
OPERATIONS	:= Liste der Operationen mit jeweils ihrer Funktionalität oder Arität. Konstanten lassen sich als nullstellige Funktionen mit unterbringen. Die wichtigsten Operationen sind die Konstruktoren Die anderen Operatoren sind dazu da, um auf den Elementen des Typs zu rechnen: die Observatoren, die Projektoren, die Selektoren und die Transformatoren.
RULES	:= Liste von Regeln oder Axiomen über bestehende Zusammenhänge zwischen den Operationen (beschreiben das Verhalten hinreichend)

schweres Beispiel:

add(x,nach(y))=nach(add(x,y))
mult(x,nach(y)=add(mult(x,y),x)

---

Listen

Bei der Arbeit mit sehr langen Ketten stehen in der Praxis Effizienzüberlegungen entgegen. Weil in der Regel mit
rekursiven Prozeduren gearbeitet wird kann es zu einem Überlauf des Kellerspeichers kommen, denn jedes
Listenelement wird an einer Prozedur-Inkarnation geheftet. Der Zeiger sollte als Referenzparameter übergeben
werden, ansonsten wird unter Verwendung "Zeiger als Wertparameter" unnötiegerweise kopiert.

Die Strukturinformation einer Liste basiert auf das Prinzip: "Verweis auf den Nachfolger" , und dass am Ende der Liste immer ein "null -Wert" steht. Die Liste als Ganzes wird angesprochen über einen Anker, der auf das erste Listenelement verweist; oder null bei einer leeren Liste.

	Listen	doppelt verkette Liste
ADT <x> IS	Lists(T)
SORTS	list, T, boolean
OPERATIONS	newlist:-> list cons: atom list -> list head: list -/-> atom tail: list -/-> list isempty: list -> boolean length: list -> natural	append: list × list -> list
RULES	isempty(newlist) = true isempty(cons(x, l)) = false head(cons(x, l)) = x tail(cons(x, l)) = l length(newliste)=0 length(cons(a,l))=length(l)+1 isequal(newlist, newlist) = true isequal(newlist, cons(a,x)) = false isequal(cons(a,x), newlist) = false isequal(cons(a,x), cons(b,y)) = ((a = b) ^ isequal(x,y)) <--rekursiv	append(newlist, l) = l append(cons(x, l1), l2) = cons(x, append(l1, l2))
	END Lists.

Bemerkungen:

Die Operationen newlist und cons sind Konstruktoren, allen anderen Operationen sind Selektoren!
Die Operationen head und tail sind partielle Funktionen und dürfen deswegen nicht auf leere Listen angwandt werden! Terme wie tail(newlist) lassen sich daher nicht auf Grundterme zurückführen. Sie bezeichnen demnach keine Objekte; in einer Implementierung ergeben sie keinen Sinn, und sie sollten möglichst als Fehler erkannt werden.

Die Funktion isequal liefert die Abfrage auf gleiche Wertefolgen, weil ein "normaler Vergleich" nur abfrägt, ob es sich um dasselbe konkrete Objekt handelt, anstatt die Information zu bringen, ob die beiden Listen dieselben Datenwerte in derselben Reihenfolge enthalten.

Die Liste <1,4,9,> wird durch den Aufruf cons( 1, cons (4, cons(9, newlist) erzeugt.
Satz: Wenn die Regel isempty(l) = false eintritt, dann ist l=cons( head(l), tail(l) )

Effiziente Operationen auf einer Liste:

am Anfang der Liste:

• Einfügen mit cons
• Entfernen mit tail

an gegebener Stelle:

• weiterschalten
• dahinter einfügen
• dahinter entfernen (falls der Nachfolger vorhanden ist)
• Inhalt mit Nachfolger vertauschen (falls vorhanden)

---

Stapel

Folgende Fehlerbehandlungen treten im Stack auf:

Überlauf: In einem vollen Stack ein Element mit PUSH drauflegen.
Unterlauf: Aus einem leeren Stack mit POP ein Element zu holen
Uninitialized: Eine Operation auf einem nicht initialiserten Stack ausführen.

ADT Stacks(T) IS
SORTS:	stack,T,boolean
OPERATIONS:	newstack -> stack
	push: T x stack -> stack
	top: stack -/-> T
	pop: stack -/-> stack
	isempty: stack -/-> boolean
RULES:	isempty(newstack)=true
	isempty(push(x,l))=false
	top(push(x,l)=x
	pop(push(x,l)=l
END Stacks.

---

Schlangen

Bei jeder Operation ("schreiben"/"lesen") wird überprüft, ob ein FIFO-Überlauf (full?) vorliegt oder ob die Queue leer (empty?) ist.


Zum Eintragen eines neuen Datenelements am Schwanz der Schlange hängen wir es hinten an den belegten Teil des Array an; und ebenso holen wir uns vorne das aktuelle Kopf-Element ab. Würden wir dabei über das Ende des Array hinauslaufen, so kommen wir von vorne wieder herein:

	Schlange	Doppelschlange
ADT <x>IS	Queues(T)
SORTS:	queue,T,boolean,cardinal
	newqueue: -> queue enqueue: T× queue -> queue isempty: queue -> boolean length: queue -> cardinal dequeue: queue -/->T × queue first: queue -/-> T rest: queue -/-> queue	Löschen des Knotens der Hilfszeiger p hat: v := p.vor; n := p.nach; v.nach := n; n.vor := v; danach erfolgt die Freigabe von p
OPERATIONS:	isempty(newqueue) = true isempty(enqueue(x, q)) = false length(newqueue) = 0 length(enqueue(x, q)) = length(q) + 1 dequeue(q) = <first(q), rest(q)> first(enqueue(x, q)) = IF isempty(q) THEN x ELSE first(q) rest(enqueue(x, q)) = IF isempty(q) THEN newqueue ELSE enqueue(x, rest(q))

Die algebraische Modellierung ist etwas mühsam und benötigt die Hilfsfunktionen first und rest.
Sonderfälle: Die leeren Schlange hat die Länge 0 (head=tail=NIL). Weiter ist zu beachten das der Fall einer einelementigen Schlange, bei der Kopf und Schwanz identisch sind, eintreten kann.

Ist die Maximallänge einer Schlange von Anfang an bekannt, so kann man sie in einem Array fester Länge unterbringen, den man zu einem logischen Ringpuffer schließt. Da im Allgemeinen nur ein Teil des Array belegt sein wird, müssen wir uns die Position von Kopf und Schwanz merken, und die aktuelle Länge mitzählen.

---

Binäre Bäume

ADT <x> IS
SORTS:
OPERATIONS:	newtree -> btree
	node: atom × btree × btree -> btree	Konstruktor
	isempty: btree -|-> boolean	Selektor
	root: btree -|-> atom
	left: btree -|-> btree
	right: btree -|-> btree
RULES:	isempty(newtree)=true
	isempty(node(x,l,r))=false
	root(node(x,l,r))=x
	left(node(x,l,r))=l
	right(node(x,l,r))=r
END Btrees.

---

2.3 Komplexität berühmter Algorithmen

Festlegung: Sei n die Anzahl der Knoten und m die Anzahl der Kanten.

Bei einer doppelten Rechnerleistung wird mit linearem Aufwand O(n) die Laufzeit des Algorithmus halbiert.
Bei exponentiellen Aufwand O(c^n) können wir in der selben Laufzeit nur ein Element mehr berechnen.
(z.B. anstatt 100 Elemente -> 101 Elemente) !

Def.: C := Compares, die Anzahl der nötigen Vergleiche und M := Movementes die Anzahl der zu bewegenden Elemente (Vertauschungen).

Ungeordnete Liste von Algorithmen

	Algorithmus	Einsatz	Zusatzinformationen	Aufwand
Matrixberechnungen	Wettervohersage		O(n³)
Dijkstra	kürzesten Wege zwischen allen Knoten berechnen
Prioritätssuche:	kürzesten Wegen von einem Knoten zu allen Knoten	|E| Kanten und |V| Knoten	O((|E|+|V|) * log|V|)
Prioritätssuche	wiederhole Algorithmus |V| - mal	für alle Knoten:
Topsort	Eingangsgrad beim topologischen Sortieren		O(n+m)
	Tiefensuchwald
	topologische Ordnung
Schachspiel		64 Züge -> 30^64 Möglichkeiten
	Gelenkpunkte des Graphen
	bestimme Zusammenhangskomponenten
Adjazenzliste	Finde Nachfolger eines bestimmten Knotens	gerichteter- / unger. Graph	O(n) / grosse Graphen
	Ist Knoten X direkter Nachfolger von Y ?	gerichteter- / unger. Graph	O(n) / doppelter Aufwand
Adjazenzmatrix	Finde Nachfolger eines bestimmten Knotens	gerichteter- / unger. Graph	O(n) / O(n²)
	Ist Knoten X direkter Nachfolger von Y ?	gerichteter- / unger. Graph	O(1) / O(1)

---

Sortieralgorithmen:

Nichtstabile Sortierverfahren sollten beim "mehrfachsortieren" nicht eingesetzt werden. Sonst kommt es zu
Vertauschungen in den Datensätzen.

	Algorithmus	Zusatzinformationen	Aufwand
Bubblesort	stabil, im besten Fall ist die Folge bereits sortiert und wir haben nur einen Durchlauf.	C: O(n²), M: O(n²), best case: C: O(n²), M: 0
Bucketsort	m Buckets und n verteilte Elemente	O(n+m)
Direktes Einfügen	stabil	C: O(n²), M: O(n²), best case: C: O(n²), M: O(n)
Direktes Aussuchen	2 geschachtelte FOR-Schleifen Anzahl der Vergleiche: C(n)=n*(n-1)/2 Anzahl der Zuweisungen: M(n)=3*(n-1), d.h. 3 Zuweisungen pro Tauschoperation	C: O(n²), M: O(n²), best case: C: O(n²), M: O(n)
Heapsort
Mergesort	n Vergleich beim Mischen einer Folge der Länge n Listenvariante ist stabil, die rekursive Variante nicht! - O(n) zusätzlicher Speicherplatz	C: O(n log n) garantiert, M: O(n log n) garantiert
Quicksort	best case: alle entstehenden Teilfolgen sind gleich lang wort case: Pivot wird immer der kleinste bzw. immer der größte Wert: - pro Aufruf nur eine Vertauschung - jedes Folgeelement ist einmal das Pivot	O(n log n) O(n²)

---

Suchalgorithmen:

	Algorithmus	Zusatzinformationen	Aufwand
Interpolationssuche	binäre Suche, Teilungsindex berechnen ist aufwendig. Aufwand bei zufälliger Schlüsselverteilung:	C: O( log (log n+1)) O( log (log n))
lineare Suche	im Mittel ist ein Wert nach n/2 Schritten gefunden. Nach n+1 Schritten ist das nicht vorhandene Element erkannt	O(n)
Suche im sortierten Feld	Zerlegung in Teilprobleme. "Logarithmisches Suchen"	O(log n)
Suche in einer rechteckigen Tabelle

---

Graphenalgorithmen:

	Algorithmus	Zusatzinformationen	Aufwand
Breitensuche	die Kanten mit ihrem Weg gewichten	O(V+E)
Dijkstra	sucht den kuerzesten Weg zwischen zwei Knoten	O(n2)
Floyd	Buttom-Up-Aufbau des Heaps erfolgt in O(n)	O(n log n)
Floyd-Warshall	loest „Kuerzeste-Wege-Problem“, arbeitet auch mit negativen Kantengewichten. Er bestimmt kuerzeste-Wege-Baeume fuer alle Startknoten.	O(n3)
Graphfärbung	Heuristik: färbe Kanten mit vielen Knoten zuerst	NP-vollständig
Heap	Prioritätswarteschlange + Adjazenzliste	O(log|V|)
Prim	findet den mimalen Spannbaum fuer einen ausgewaehlten Knoten.
Prioritätssuche	mit |E| Kanten und |V| Knoten.	O( (|E| + |V|) log|V|)
Traversierung	Strukturinformation eines Baums berechenen und die Numern der Knoten in einem Array hintereinander ablegen (Levelorder)	O(n log n)
Williams	insert: weniger als (ld n + 1) Vergleiche und wenger als ld n Tauschoperationen remove: weniger als 3(ld n + 1) Vergleiche und wenger als ld n Tauschoperationen nach n Schritten: weniger als 4n ( ld n + 1) Vergleiche und weniger als 2 ld n Tauschop.	C: O(n log n), M: O(n log n)
Zusammenhang	Feststellung ob der Graph 2-fach zusammenhängend ist: 1.) für Adjazenzlisten, jede ungerichtete Kante wird zweimal durchlaufen. 2.) für die Adjazenzmatrix Entspricht dem Aufwand der Tiefensuche in Adajazenzlisten und -matrix! weiterführend: Iterative Tiefensuche für zusammenhängende Graphen.	1.) O(|V| + |E|) 2.) O(|V|²)