summaryrefslogtreecommitdiffhomepage
path: root/de-de
diff options
context:
space:
mode:
Diffstat (limited to 'de-de')
-rw-r--r--de-de/dynamic-programming-de.html.markdown77
-rw-r--r--de-de/go-de.html.markdown2
-rw-r--r--de-de/make-de.html.markdown7
3 files changed, 82 insertions, 4 deletions
diff --git a/de-de/dynamic-programming-de.html.markdown b/de-de/dynamic-programming-de.html.markdown
new file mode 100644
index 00000000..801d2514
--- /dev/null
+++ b/de-de/dynamic-programming-de.html.markdown
@@ -0,0 +1,77 @@
+---
+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<i`
+in der Teilmenge `aj<ai` gilt.
+Zuerst müssen wir bei jedem Index i den Wert der längsten Subsequenzen (LSi)
+finden, wobei das letzte Element der Sequenz ai ist. Dann wäre die größte LSi
+die längste Subsequenz in der gegebenen Sequenz. Am Anfang wird der LSi mit
+eins belegt, da ai ein Element der Sequenz (Letztes Element) ist.
+Dann ist für alle `j` mit `j<i` und `aj<ai`, so dass wir den größten LSj finden
+und zum LSi hinzufügen. Der Algorithmus hat eine Laufzeit von *O(n2)*.
+
+Pseudocode zur Bestimmung der Länge der am längsten ansteigenden Subsequenz:
+Die Komplexität des Algorithmus könnte durch eine bessere Datenstruktur anstelle
+von Arrays reduziert werden. Das Speichern von Vorgänger-Array's und Variablen
+wie `largest_sequences_so_far` und dessen Index würde eine Menge Zeit sparen.
+
+Ein ähnliches Konzept könnte auch bei der Suche nach dem längsten Weg
+in gerichteten azyklischen Graphen angewandt werden.
+```python
+for i=0 to n-1
+ LS[i]=1
+ for j=0 to i-1
+ if (a[i] > a[j] and LS[i]<LS[j])
+ LS[i] = LS[j]+1
+for i=0 to n-1
+ if (largest < LS[i])
+```
+
+### 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)
+
+## Online Ressourcen
+
+* [codechef](https://www.codechef.com/wiki/tutorial-dynamic-programming)
diff --git a/de-de/go-de.html.markdown b/de-de/go-de.html.markdown
index 817cb4ae..9409e181 100644
--- a/de-de/go-de.html.markdown
+++ b/de-de/go-de.html.markdown
@@ -94,7 +94,7 @@ Zeilenumbrüche beinhalten.` // Selber Zeichenketten-Typ
// Arrays haben bei Kompile-Zeit festgelegte Größen
var a4 [4]int // Ein Array mit 4 ints, alle mit Initialwert 0
- a3 := [...]int{3, 1, 5} // Ein Array mit 4 ints, Initialwerte wie angezeigt
+ a3 := [...]int{3, 1, 5} // Ein Array mit 3 ints, Initialwerte wie angezeigt
// "slices" haben eine dynamische Größe. Arrays und Slices haben beide ihre
// Vorzüge, aber slices werden viel häufiger verwendet
diff --git a/de-de/make-de.html.markdown b/de-de/make-de.html.markdown
index 22c14a69..bc5c7bcb 100644
--- a/de-de/make-de.html.markdown
+++ b/de-de/make-de.html.markdown
@@ -2,6 +2,7 @@
language: make
contributors:
- ["Robert Steed", "https://github.com/robochat"]
+ - ["Stephan Fuhrmann", "https://github.com/sfuhrm"]
translators:
- ["Martin Schimandl", "https://github.com/Git-Jiro"]
filename: Makefile-de
@@ -58,7 +59,7 @@ file2.txt file3.txt: file0.txt file1.txt
touch file3.txt
# Make wird sich beschweren wenn es mehrere Rezepte für die gleiche Regel gibt.
-# Leere Rezepte zählen nicht und können dazu verwendet werden weitere
+# Leere Rezepte zählen nicht und können dazu verwendet werden weitere
# Voraussetzungen hinzuzufügen.
#-----------------------------------------------------------------------
@@ -182,9 +183,9 @@ echo: name2 = Sara # Wahr innerhalb der passenden Regel und auch innerhalb
# Ein paar Variablen die von Make automatisch definiert werden.
echo_inbuilt:
echo $(CC)
- echo ${CXX)}
+ echo ${CXX}
echo $(FC)
- echo ${CFLAGS)}
+ echo ${CFLAGS}
echo $(CPPFLAGS)
echo ${CXXFLAGS}
echo $(LDFLAGS)