Study your flashcards anywhere!

Download the official Cram app for free >

  • Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

How to study your flashcards.

Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key

Up/Down arrow keys: Flip the card between the front and back.down keyup key

H key: Show hint (3rd side).h key

A key: Read text to speech.a key

image

Play button

image

Play button

image

Progress

1/18

Click to flip

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