Dynamische Programmierung Flashcards
1
Q
Was ist das Prinzip der Dynamischen Programmierung?
A
- Es ist eine Methode zum Lösen von Optimierungsproblemen
- das Problem in kleinere Teilprobleme zerlegen und diese Teilprobleme systematisch lösen
- Die Lösungen der Teilprobleme werden dann in einer Tabelle gespeichert
- Diese werden dann später wiederverwendet um urspüngliches Problem zu lösen
- oft rekusriv
2
Q
wie funktioniert LCS?
A
- Erstelle Tabelle mit leerer Menge und beiden Wörtern
- Gehe spalten Weise voran
- Stimmen die buchstaben überein, nehme die Zahl von Diagonal links oben und addiere 1
- Stimmen sie nicht überein nehme das Maximum vom linken und oberen Nachbarn
- Ist man fertig startet man wieder unten rechts
- Stimmen die buchstaben überein markiere die Zelle und geh Diagonal links nach oben
- Stimmen sie nicht überein gehe zum maximum vom linken oder oberen nachbarn
* Sind beide gleich ist es egal zu welchem man geht - Kommt man bei 0 an ist man fertig und alle markierten Zellen ergeben die LCS
* Laufzeit: O(n1 * n2), O(n^2) wenn beide gleich lang