GAD-Methodik

Ziel der Vorlesung: Grundstock an effizienten Algorithmen und Datenstrukturen für Standardprobleme, Methode zur Analyse von Problemen


0. Einführung
	0.1 Algorithmus: Ein Algorithmus ist eine deterministische Handlungsvorschrift, die auf eine bestimmte Klasse von Eingaben angewendet werden kann, und für jede dieser Eingaben eine 				 korrespondierende Ausgabe liefert
	0.2 Abstrakter Datentyp: legt fest, welche Operationen was tun(Semantik), aber nicht wie (konkrete Implementierung) → Kapselung/Abstraktion durch Definition einer Schnittstelle
	0.3 Datenstruktur: formalisiertes Objekt zur Speicherung, Verwaltung von, Zugriff auf Daten die dabei geeignet angeordnet, kodiert und verknüpft werden.
	0.4 Effizienz: Im Sinne
		0.4.1 Laufzeit, Speicheraufwand, Festplattenzugriffe, Energieverbrauch
		0.4.2 Kritische Beispiele: Riesige Datenmenge, Echtzeitanwendungen

	0.5 Sequenzen: lineare Struktur → Beim Anlegen ist nicht bekannt wieviele Elemente es enthalten wird, nur anlegen von statischen Feldern möglich → beschränkter Speicher
		0.5.1 statisches Feld Array: direkter Zugriff über s[i]; V
			0.5.1.1 Vorteil: Zugriff über direkten index, homogen im Speicher
			0.5.1.2 Nachteil: dynamische Größenänderung schwierig
		0.5.2 Liste: indirekter Zugriff über Nachfolger/Vorgänger
			0.5.2.1 Vorteil: Einfügen/Löschen von Teilsequenzen 
			0.5.2.2 Nachteil: kein Zugriff per Index, Elemente über Speicher verteilt

	0.6 Dynamisches Feld: 
		(0.6.1 Immer dann, wenn Feld s nicht mehr ausreicht wird ein neues Feld der Länge w+c für ein festes c → kopieren in ein größeres Feld)
		0.6.2 Immer dann, wenn Feld s nicht mehr ausreicht, wird ein neues Feld der Größe 2w generiert, Immer wenn Feld s zu groß(n<=w/4) ist generiere ein neues Feld der Größe w/2
		0.6.3 β = Wachstumsfaktor | α = max. Speicheroverhead | w = momentane Feldgroße  | n = momentane Elementanzahl | b = new ElementTyp[w]

		

1. Komplexitätsanalyse
	1.1 Effizienzmessung: Beschreibung der Performance von Algorithmen möglichst genau aber in kurzer und einfacher Forum
		1.1.1 Laufzeit eines Algorithmus: T: I→N (I = Menge der Instanzen | T meistens sehr schwer bestimmbar → Gruppierung der Instanzen)
		1.1.2 Worst Case: t(n) = max {T(i) : i ∈ In} →liefert Garantie für die Effizienz, aber sehr pessimistisch
		1.1.3 Average Case: t(n) = 1 / |In| * T(Summe aller i ∈ In) → beschrebit durchschnittliche Laufzeit, aber nicht unbedingt übereinstimmend mit den "typischen Fall" in der Praxis.
		1.1.4 Best Case: t(n) = min {T(i) : i ∈ In} → Vergleich mit worst case liefert Aussage über Abweichung innerhalb der Instanzen gleicher Größe, sehr optimistisch
	1.2 Asymptotische Notation:
		1.2.1 O(f(n)) = es gibt ein skalar * f(n) > 0, für das f schneller ist als g
		1.2.2 o(f(n)) = für alle skalare * f(n)) > 0, ist f schneller als g
	
		1.2.3 Ω(f(n)) = es gibt ein skalar * f(n) > 0, für das f langsamer ist als g
		1.2.4 ω(f(n)) = für alle skalare * f(n) > 0, ist f langsamer als g
		1.2.5 Θ(f(n)) = f und g sind gleich schnell
	1.3 Abstraktion von Maschinemodellen
	1.4 Laufzeitanalyse Worst-Case:
		→ T(I) sei die wort-case laufzeit
		→ T(Zuweisung) = O(1)
		→ T(Vergleich) = O(1)
		→ T(return) = O(1)
		→ T(Objekterstellung) = O(1) + O(T(Konstrukter der Klasse von der ein Objekt erstellt wurde))
		→ T(I1,I2) = T(I1) + T(I2)
		→ T(if-else) = O(T(Bedingung) + max{T(I1), T(I2)})
		→ T(for-schleife) = O(Summe für alle Durchläufe - 1(1 + T(Was in der for-Schleife passiert))
	1.5 Laufzeitanalyse Average-Case:
		→ 
	1.6 Erwartete Laufzeit
		1.6.1 Zufallsvariable: X: Ω→R; Wertebereich: Es gibt eine variable die eingesetzt in die Abbildung x ergibt.
		1.6.2 Erwartungswert: Der Erwartungswert einer Zufallsvariable ist x * die Summe des Wertebereichs der Zufallsvariable
	

		
Landau-Symbole 



2. Datenstrukturen für Sequenzen
Arrays, Listen, Stack und Queues

3. Hashing

	3.2 Universelles Hashing: 
		Es gibt eine Familie von Hashfunktionen bei der zufällig eine durch die Konstante c ausgewählt wird, um die Anzahl der Kollisionen klein zu halten.
	        Eine Familie von Hashfunktionen gilt als universell, wenn die Anzahl der Kollisionen <= (c / m) * Anzahl der Hashfunktionen 
	
		3.2.1 c-universelles Hashing: Eine Familie von Hashfunktionen gilt als c universell, wenn die Anzahl der Kollisionen <= (c / m)

	3.3 Hashing with Chaining: Gibt es eine Kollision so wird an der Kollisionstelle eine LinkedList instanziiert in der die kollidierenden Hashwerte gespeichert werden.
			
	3.4 Hashing with linear probing: Gibt es eine Kollison so wird der Hashwert einfach in der Stelle kollisionsstelle + 1 eingefügt.
	

Verkettung, universelles Hashing, Sondierverfahren, perfektes Hashing

4. Sortieren
Einfache Verfahren, MergeSort, QuickSort, untere Schranke, Rang-Selektion, Radix-Sort, externes Sortieren

5. Priority Queues
	5.2 Binäre Heaps: 
		
		5.2.1 MinHeaps: fast perfekte Binärbäume bei den die letzte eben bis auf den letzten rechten knoten erfüllt ist
			→ Build Methode: Elemente nach binomialier bedingung zeilenweise einfügen bis ein childknoten kleiner ist als ein Vaterknoten → siftup;
			→ deleteMax Methode: größtes Element an die letzte Stelle siften und dann löschen → anschließend die Heap-Invariante wieder herstellen
			→ Bei minheaps muss der vaterknoten immer den kleinsten schlüsselknoten haben, d.h. die wurzel hat den kleinsten wert
		5.2.2. MaxHeaps: 
			→ Build Methode: Elemente nach binomialier bedingung zeilenweise einfügen bis ein childknoten kleiner ist als ein Vaterknoten → siftup;
			→ Bei maxheaps muss der vaterknoten immer den größten Schlüsselknoten haben, d.h. die wurzel hat den größten wert
	
 	5.3 Binomialheaps:
		
		5.3.1 Werden gebuilded indem zwei heaps der größe k-1 gemerged werden
		5.3.2 Es gibt 2^k Elemente 
		5.3.3 Die Länge ist k-1

6. Suchstrukturen
Binäre Suchbäume
	6.0 Binäre Bäume
		6.1 Insert: Inserte kleineren Wert nach links, größeren nach rechts
		6.2 remove: 
			6.2.1 Leaf node: einfach löschen
			6.2.2 with 1 Child: hochziehen
			6.2.3 with 2 childs: größte Element im linken teilbaum des zu löschenden knotens

	6.1 AVL-Bäume
		Elemente nach binomialer Bedingung zeilenweise einfügen: Elemente < als der vaterknoten nach links, > nach rechts → Rotation immer, wenn die balancierung an einem knoten 2 oder - 2 beträgt
		Falls das Kind auf dem Konfliktpfad ein unterschiedliches Vorzeichen hat als der Vaterknoten eine doppelrotation ausführen

	6.2 (a,b)-Bäume
		a = minimale Kinder, b = maximale Kinder. 
		a,b kann nur existieren, wenn b >= 2*a - 1

7. Graphen
Repräsentation, Traversierung, Zusammenhang, kürzeste Wege, minimale Spannbäume

8. Pattern Matching
Naive Suche, KMP Algorithmus

9. Datenkompression
Huffman Codes, Lempel-Ziv Verfahren

 



























1. Asymptotische-Notation
	1.1 O(f(n)) = es gibt ein skalar * f(n) > 0, für das f schneller ist als g
	1.2 o(f(n)) = für alle skalare * f(n)) > 0, ist f schneller als g
	
	2.1 Ω(f(n)) = es gibt ein skalar * f(n) > 0, für das f langsamer ist als g
	2.2 ω(f(n)) = für alle skalare * f(n) > 0, ist f langsamer als g

	3.  Θ(f(n)) = f und g sind gleich schnell

	Rechen


2. Laufzeitanalyse	
	












x.Sortieralgorithmen
	x.1 BubbleSort:
		→Durchlaufen der Ergebnisse - i (ab i ist schon sortiert)
		→Das aktuelle Element wird mit seinem rechten Nachbar verglichen
		→Falls die beiden das Sortierkriterium verletzten, werden sie vertauchst
		→Das ganz wird list.length mal sortiert
		→Laufzeit n(log(n))
		→stabiler Sortieralgorithmus

	x.2 MergeSort(rekursiv):
		→1. wenn links==rechts return;
		→mitte feststellen (links+rechts/2)
		→mergeSort(array, links, mitte)
		→mergeSort(array, mitte+1, rechts)
		→Laufvariablen für linke(links)&rechte(m+1) Hälfte instanziieren
		→Von 0 bis r-l durchlaufen:
			→Wenn j größer als die hälfte ist, k in das neue array kopieren
			→Ansonsten: wenn rechts größer als der rechte Bound ist, links in das neue Array kopieren
			→Ansonsten: vergleiche, ist die Zahl an a[j] zu a[k] entsprechend dem Sortierkriterium?
				     Wenn ja,a[links] ist Kopierarry nehmen, ansonsten a[rechts]
			→Kopiere das Kopierarray in das neue zurück