From b5a681fd6b159a5aece7e318ce01637fff3965f8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Henrik=20J=C3=BCrges?= Date: Wed, 18 Oct 2017 18:20:12 +0200 Subject: dynamic programming de translation --- de-de/dynamic-programming-de.html.markdown | 54 ++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+) create mode 100644 de-de/dynamic-programming-de.html.markdown (limited to 'de-de/dynamic-programming-de.html.markdown') diff --git a/de-de/dynamic-programming-de.html.markdown b/de-de/dynamic-programming-de.html.markdown new file mode 100644 index 00000000..d663400f --- /dev/null +++ b/de-de/dynamic-programming-de.html.markdown @@ -0,0 +1,54 @@ +--- +category: Algorithms & Data Structures +name: Dynamic Programming +contributors: + - ["Akashdeep Goel", "http://github.com/akashdeepgoel"] +translators: + - ["Henrik Jürges", "http://github.com/santifa"] +lang: de-de +--- + +# Dynamische Programmierung + +## Einführung +Dynamische Programmierung ist eine leistungsfähige Technik, die zur Lösung einer bestimmten Klasse von Problemen verwendet wird. +Die Idee ist sehr einfach, wenn Sie ein Problem mit der gegebenen Eingabe gelöst haben, dann speichern Sie das Ergebnis für die spätere Referenz, um zu vermeiden, das gleiche Problem noch einmal zu lösen. + +Denken Sie immer daran! +"Diejenigen, die sich nicht an die Vergangenheit erinnern können, sind dazu verdammt, sie zu wiederholen." + +## Wege zur Lösung solcher Probleme + +1. *Top-Down*: Lösen Sie das gegebene Problem, indem Sie es aufteilen. Wenn Sie sehen, dass das Problem bereits gelöst ist, geben Sie einfach die gespeicherte Antwort zurück. Wenn es nicht gelöst wurde, lösen Sie es und speichern Sie die Antwort. Dieser Ansatz ist leicht zu verfolgen und sehr intuitiv. Er wird als Memoization bezeichnet. + +2. *Bottom-Up*: Analysieren Sie das Problem und beobachten Sie, in welcher Reihenfolge die Teilprobleme gelöst werden können. Beginnen Sie mit der Lösung vom trivialen Teilproblem bis zum gegebenen Problem. Dabei wird sichergestellt, dass die Teilprobleme vor der Problemlösung gelöst werden. Dies wird als Dynamische Programmierung bezeichnet. + +## Ein Beispiel für Dynamische Programmierung + +Das Problem mit der längsten ansteigenden Subsequenz besteht darin, die längste ansteigende Subsequenz einer gegebenen Sequenz zu finden. +Gegeben die Sequenz `S= {a1, a2, a3, a3, a4,..............., an-1, an }`, müssen wir die größte Teilmenge finden, so daß für alle `j` und `i`, `j a[j] and LS[i] Date: Wed, 18 Oct 2017 18:23:39 +0200 Subject: fixed line length --- de-de/dynamic-programming-de.html.markdown | 49 ++++++++++++++++++++++-------- 1 file changed, 36 insertions(+), 13 deletions(-) (limited to 'de-de/dynamic-programming-de.html.markdown') diff --git a/de-de/dynamic-programming-de.html.markdown b/de-de/dynamic-programming-de.html.markdown index d663400f..801d2514 100644 --- a/de-de/dynamic-programming-de.html.markdown +++ b/de-de/dynamic-programming-de.html.markdown @@ -11,28 +11,51 @@ lang: de-de # Dynamische Programmierung ## Einführung -Dynamische Programmierung ist eine leistungsfähige Technik, die zur Lösung einer bestimmten Klasse von Problemen verwendet wird. -Die Idee ist sehr einfach, wenn Sie ein Problem mit der gegebenen Eingabe gelöst haben, dann speichern Sie das Ergebnis für die spätere Referenz, um zu vermeiden, das gleiche Problem noch einmal zu lösen. +Dynamische Programmierung ist eine leistungsfähige Technik, die zur Lösung +einer bestimmten Klasse von Problemen verwendet wird. +Die Idee ist sehr einfach, wenn Sie ein Problem mit der gegebenen Eingabe +gelöst haben, dann speichern Sie das Ergebnis für die spätere Referenz, um zu +vermeiden, das gleiche Problem noch einmal zu lösen. Denken Sie immer daran! -"Diejenigen, die sich nicht an die Vergangenheit erinnern können, sind dazu verdammt, sie zu wiederholen." +"Diejenigen, die sich nicht an die Vergangenheit erinnern können, +sind dazu verdammt, sie zu wiederholen." ## Wege zur Lösung solcher Probleme -1. *Top-Down*: Lösen Sie das gegebene Problem, indem Sie es aufteilen. Wenn Sie sehen, dass das Problem bereits gelöst ist, geben Sie einfach die gespeicherte Antwort zurück. Wenn es nicht gelöst wurde, lösen Sie es und speichern Sie die Antwort. Dieser Ansatz ist leicht zu verfolgen und sehr intuitiv. Er wird als Memoization bezeichnet. +1. *Top-Down*: Lösen Sie das gegebene Problem, indem Sie es aufteilen. +Wenn Sie sehen, dass das Problem bereits gelöst ist, geben Sie einfach die +gespeicherte Antwort zurück. Wenn es nicht gelöst wurde, lösen Sie es und +speichern Sie die Antwort. Dieser Ansatz ist leicht zu verfolgen und sehr +intuitiv. Er wird als Memoization bezeichnet. -2. *Bottom-Up*: Analysieren Sie das Problem und beobachten Sie, in welcher Reihenfolge die Teilprobleme gelöst werden können. Beginnen Sie mit der Lösung vom trivialen Teilproblem bis zum gegebenen Problem. Dabei wird sichergestellt, dass die Teilprobleme vor der Problemlösung gelöst werden. Dies wird als Dynamische Programmierung bezeichnet. +2. *Bottom-Up*: Analysieren Sie das Problem und beobachten Sie, in welcher +Reihenfolge die Teilprobleme gelöst werden können. Beginnen Sie mit der +Lösung vom trivialen Teilproblem bis zum gegebenen Problem. Dabei wird +sichergestellt, dass die Teilprobleme vor der Problemlösung gelöst werden. +Dies wird als Dynamische Programmierung bezeichnet. ## Ein Beispiel für Dynamische Programmierung -Das Problem mit der längsten ansteigenden Subsequenz besteht darin, die längste ansteigende Subsequenz einer gegebenen Sequenz zu finden. -Gegeben die Sequenz `S= {a1, a2, a3, a3, a4,..............., an-1, an }`, müssen wir die größte Teilmenge finden, so daß für alle `j` und `i`, `j Date: Sun, 14 Oct 2018 06:02:26 +0530 Subject: Fix links --- de-de/dynamic-programming-de.html.markdown | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'de-de/dynamic-programming-de.html.markdown') diff --git a/de-de/dynamic-programming-de.html.markdown b/de-de/dynamic-programming-de.html.markdown index 801d2514..afa9a17c 100644 --- a/de-de/dynamic-programming-de.html.markdown +++ b/de-de/dynamic-programming-de.html.markdown @@ -68,9 +68,9 @@ for i=0 to n-1 ### Einige bekannte DP Probleme -- Floyd Warshall Algorithm - [Tutorial and C Program source code](http://www.thelearningpoint.net/computer-science/algorithms-all-to-all-shortest-paths-in-graphs---floyd-warshall-algorithm-with-c-program-source-code) -- Integer Knapsack Problem - [Tutorial and C Program source code](http://www.thelearningpoint.net/computer-science/algorithms-dynamic-programming---the-integer-knapsack-problem) -- Longest Common Subsequence - [Tutorial and C Program source code](http://www.thelearningpoint.net/computer-science/algorithms-dynamic-programming---longest-common-subsequence) +- Floyd Warshall Algorithm - Tutorial and C Program source code: [http://www.thelearningpoint.net/computer-science/algorithms-all-to-all-shortest-paths-in-graphs---floyd-warshall-algorithm-with-c-program-source-code]() +- Integer Knapsack Problem - Tutorial and C Program source code: [http://www.thelearningpoint.net/computer-science/algorithms-dynamic-programming---the-integer-knapsack-problem]() +- Longest Common Subsequence - Tutorial and C Program source code : [http://www.thelearningpoint.net/computer-science/algorithms-dynamic-programming---longest-common-subsequence]() ## Online Ressourcen -- cgit v1.2.3