Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
18 Cards in this Set
- Front
- Back
|
Mehrstufige Heransgehensweise (Zweistufig)
|
1. Stufe: Komplexität reduzieren - Datenmenge reduzieren - kritische Punkte identifizieren und vorab möglichst gut lösen - Lösung zuerst grob bestimmen 2. Stufe: Restproblem lösen |
|
|
Divide and Conquer + beispiel
|
Passt auf algo-Problemstellung, die sich in mehrere voneinander unabhängige Teilp robleme zerlegen lässt - merge/quick sort - konvexe hülle |
|
|
Dynamische Programmierung
|
Passt auf viele Probleme, die durch eine Rekursionsgleichung beschrieben werden können. -> Rekursion wird in iteration umgewandelt |
|
|
Fibonacci Zahlen iterativ
|
Falls n=1 oder 2, gib ein 1 sonst f1 = f2 = 1 Für i =2 -> n - f = f1+f2 - f1 = f2 - f2 = f return f |
|
|
Binomialkoeffizienten iterativ 1
|
Falls k = 0 oder k = n gib 1 aus M : matrix von 0 .. n 0...k int[][] a = new a[n][k] Für i = 0 -> n : M[i,0] = 1 Für j=1 -> k : M[j,j]=1 Für i = 0-> n und j=1 -> min(k,i-1): M[i,j] = M[i-1,j-1] + M[i-1,j] return M |
|
|
Binomialkoeffizienten iterativ 2
|
Falls k=1 oder n, gib 1 aus Falls k>floor(n/2) : k = n-k(Symmetrie des Binomialkoeffizienten) A: Array mit Indexbereich 0 .. k Für i = 0 -> k : A[i] = 1 Für i =1 -> n-k und j = 1->k : A[j]=A[j-1]+A[j] Gib A[k] aus |
|
|
Greedy Ansatz
|
Passt auf Probleme, in dem Lösungen (möglichst gute) Auswahlen sind -> Starte mit leeren Auswahl -> Füge das profitabelste Element hinzu, sodass das Element zusammen mit der bisherigen Auswahl weiterhin zu einer zulässigen Lösung erweiterbar ist. Invariante: vor /nach jeder It. ist de Auswahl eine zulässige Lösung oder ist zu einer zulässigen Lösung erweiterbar |
|
|
Greedy - Rucksackproblem
|
Invariante: maximales Gesamtgewicht ist nicht übershcritten In jeder Iteration wird das profitabelste Objekt eingefügt, dass zusammen mit der bisherigen Auswahl das Gesamtgewicht nicht überschritten wird. |
|
|
Greedy - TSP
|
Profit: negative kantenlänge Invarinate: Keine 2 kanten zeigen aus dem selben knoten hinein/hinaus, kein zykel auf Teilmenge geschlossen Variante: anhängen von neuem punkt, der noch nicht im pfad ist |
|
|
Greedy - Steinerbaum
|
Invariante: vor und nach jeder iteration bilden die kanten einen steineraum auf einer Teilmenge Variante: Teilmenge wird um 1 größer |
|
|
Greedy - Mengenpackung
|
|
|
|
Backtracking
|
Macht Entscheidungen bei Sackgasse bis zu bestimmtem punkt rückgängig
|
|
|
Lokale Suche
|
durchläuft Sequenz von vollständg konstruierten Lösungen anhand einer speziellen Nachbarschaftsregel, sodass die neue Lösung besser als die alte ist, hört auf, wenn keine Verbesserung mehr möglich ist.
|
|
|
Lokale Suche - TSP
|
Nachbarschaftsregel: 2 bel. Kanten werden herausgenommen, 2 neue Kanten werden eingefügt, die die 2 Pfade wieder zu einer neuen Lösung zusammen fügen (einer wird umgekehrt)
|
|
|
Lokale Suche - Rucksack
|
schlechte Nachbarschaft: tausche Objekt gegen besseres (Anz wir nicht verändert)
gute Nachbarschaft: Objekt kommt zusätzlich hinein oder/und wird gelöscht |
|
|
Spezielle Datenprofile
|
- Granulatität(Gesamtgewicht nicht reelle zahlen, sondern ganzzahlige vielfache einer auszureichen kleinen Gewichtseinheit) - Spezielle Strukturen ausnutzen (Straßen/ planare netzwerke -> erst kanten Richtung Ziel) - zusätzliche informationen |
|
|
Greedy dynamisch Rucksack |
M : Matrix von 0 ...n , 0 ... G Für i = 1 -> n : M[i,0] = 0 Für j = 1-> G : M[0,j] = 0 Für i = 1->n und j =1 ->G: M[i,j]=M[i-1,j] Falls gi<=j : M[i,j] = max(M[i,j],M[i-1,j-gi]+pi) Gib M[n,G] aus |
|
|
Rucksack rekursiv
|
entweder n ist in Auswahl: beste Auswahl gleich der Auswahl ohne noder n ist in Auswahl, dann n+ beste Auswahl für 1...n-1 für maximales Gewicht G-gn
|
