Dynamische Programmierung - Versionsgeschichte

Daniel5Ko: /* Musterbeispiel */ Nur zweimal.

2024-08-23T13:50:19Z

Musterbeispiel: Nur zweimal.

← Nächstältere Version		Version vom 23. August 2024, 15:50 Uhr
Zeile 25:		Zeile 25:
	# <code>((fib(1)+fib(0)) + fib(1)) + (fib(1) + fib(0))</code>		# <code>((fib(1)+fib(0)) + fib(1)) + (fib(1) + fib(0))</code>

	Die Berechnung für <code>fib(2)</code> wurde ~~dreifach~~ ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.		Die Berechnung für <code>fib(2)</code> wurde doppelt ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.

	In einem möglichen dynamischen Programm berechnen wir erst die kleineren Fibonacci-Zahlen und bauen aus diesen die größeren Fibonacci-Zahlen, indem wir jede Berechnung nur einmal durchführen.		In einem möglichen dynamischen Programm berechnen wir erst die kleineren Fibonacci-Zahlen und bauen aus diesen die größeren Fibonacci-Zahlen, indem wir jede Berechnung nur einmal durchführen.

ErichS8: Tippfehler dreifach doppelt -> dreifach

2024-07-21T16:16:11Z

Tippfehler dreifach doppelt -> dreifach

← Nächstältere Version		Version vom 21. Juli 2024, 18:16 Uhr
Zeile 25:		Zeile 25:
	# <code>((fib(1)+fib(0)) + fib(1)) + (fib(1) + fib(0))</code>		# <code>((fib(1)+fib(0)) + fib(1)) + (fib(1) + fib(0))</code>

	Die Berechnung für <code>fib(2)</code> wurde dreifach ~~doppelt~~ ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.		Die Berechnung für <code>fib(2)</code> wurde dreifach ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.

	In einem möglichen dynamischen Programm berechnen wir erst die kleineren Fibonacci-Zahlen und bauen aus diesen die größeren Fibonacci-Zahlen, indem wir jede Berechnung nur einmal durchführen.		In einem möglichen dynamischen Programm berechnen wir erst die kleineren Fibonacci-Zahlen und bauen aus diesen die größeren Fibonacci-Zahlen, indem wir jede Berechnung nur einmal durchführen.

ErichS8: 2x "function fib(n)" in den Codeblock verschoben; Low-level pseudocode Formatierung lt. MoS; erstmal -> erst; doppelt -> dreifach

2024-07-21T16:14:51Z

2x "function fib(n)" in den Codeblock verschoben; Low-level pseudocode Formatierung lt. MoS; erstmal -> erst; doppelt -> dreifach

@@ Zeile 12: / Zeile 12: @@
 Eine naive Implementation wäre:
-function fib(n)
+ '''function''' fib(n)
-    return fib(n − 1) + fib(n − 2)
+     '''if''' n <= 1 '''return''' n
 Ein Aufruf von fib(4) zur Berechnung der vierten Fibonacci-Zahl erstellt folgenden Aufrufbaum:
@@ Zeile 23: / Zeile 25: @@
 # <code>((fib(1)+fib(0)) + fib(1)) + (fib(1) + fib(0))</code>
-Die Berechnung für <code>fib(2)</code> wurde doppelt ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.
+Die Berechnung für <code>fib(2)</code> wurde dreifach doppelt ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.
 Da wir jede Berechnung nur einmal durchführen, hat dieses Programm eine Laufzeit von O(n).

Tsor: verlangt einen Pflichtparameter

2024-03-18T21:02:47Z

<syntaxhighlight> verlangt einen Pflichtparameter

← Nächstältere Version		Version vom 18. März 2024, 23:02 Uhr
Zeile 11:		Zeile 11:
	Durch die Nutzung von dynamischer Programmierung kann die Zeitkomplexität zur Berechnung der n-ten [[Fibonacci-Zahl]] drastisch verbessert werden.		Durch die Nutzung von dynamischer Programmierung kann die Zeitkomplexität zur Berechnung der n-ten [[Fibonacci-Zahl]] drastisch verbessert werden.

	Eine naive Implementation wäre:~~<syntaxhighlight>~~		Eine naive Implementation wäre:
	function fib(n)		function fib(n)
	if n <= 1 return n		if n <= 1 return n
	return fib(n − 1) + fib(n − 2)		return fib(n − 1) + fib(n − 2)
	~~</syntaxhighlight>~~Ein Aufruf von fib(4) zur Berechnung der vierten Fibonacci-Zahl erstellt folgenden Aufrufbaum:		Ein Aufruf von fib(4) zur Berechnung der vierten Fibonacci-Zahl erstellt folgenden Aufrufbaum:

	# <code>fib(4)</code>		# <code>fib(4)</code>
Zeile 25:		Zeile 25:
	Die Berechnung für <code>fib(2)</code> wurde doppelt ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.		Die Berechnung für <code>fib(2)</code> wurde doppelt ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.

	In einem möglichen dynamischen Programm berechnen wir erstmal die kleineren Fibonacci-Zahlen und bauen aus diesen die größeren Fibonacci-Zahlen, indem wir jede Berechnung nur einmal durchführen.~~<syntaxhighlight>~~		In einem möglichen dynamischen Programm berechnen wir erstmal die kleineren Fibonacci-Zahlen und bauen aus diesen die größeren Fibonacci-Zahlen, indem wir jede Berechnung nur einmal durchführen.
	function fib(n)		function fib(n)
	if n = 0		if n = 0
Zeile 36:		Zeile 36:
	currentFib := newFib		currentFib := newFib
	return currentFib		return currentFib
	~~</syntaxhighlight>~~Da wir jede Berechnung nur einmal durchführen, hat dieses Programm eine Laufzeit von O(n).		Da wir jede Berechnung nur einmal durchführen, hat dieses Programm eine Laufzeit von O(n).

	== Weitere Beispiele ==		== Weitere Beispiele ==

Thomas Dresler: Komma vor „sondern“, „indem“, „wobei“ etc.

2024-03-16T09:13:53Z

Komma vor „sondern“, „indem“, „wobei“ etc.

← Nächstältere Version		Version vom 16. März 2024, 11:13 Uhr
Zeile 25:		Zeile 25:
	Die Berechnung für <code>fib(2)</code> wurde doppelt ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.		Die Berechnung für <code>fib(2)</code> wurde doppelt ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.

	In einem möglichen dynamischen Programm berechnen wir erstmal die kleineren Fibonacci-Zahlen und bauen aus diesen die größeren Fibonacci-Zahlen indem wir jede Berechnung nur einmal durchführen.<syntaxhighlight>		In einem möglichen dynamischen Programm berechnen wir erstmal die kleineren Fibonacci-Zahlen und bauen aus diesen die größeren Fibonacci-Zahlen, indem wir jede Berechnung nur einmal durchführen.<syntaxhighlight>
	function fib(n)		function fib(n)
	if n = 0		if n = 0

Invisigoth67: form

2024-03-12T12:28:08Z

form

← Nächstältere Version		Version vom 12. März 2024, 14:28 Uhr
Zeile 6:		Zeile 6:
	In der Regelungstheorie und verwandten Gebieten kann man das Prinzip der dynamischen Programmierung einsetzen, um etwa eine Gleichung herzuleiten (Hamilton-Jacobi-Bellman-Gleichung), deren Lösung den optimalen Wert ergibt. Die Argumentation ist dabei etwa folgende: Wenn das Problem zeitabhängig ist, kann man den optimalen Wert der Zielfunktion zu einem bestimmten Zeitpunkt betrachten. Man fragt sich dann, welche Gleichung die optimale Lösung erfüllen muss, damit das [[Funktional]] auch zu einem späteren Zeitpunkt optimal bleibt, dies führt zur [[Hamilton-Jacobi-Bellman-Gleichung]]. Damit kann man das Problem in Zeitschritte einteilen, anstatt es auf einmal lösen zu müssen.		In der Regelungstheorie und verwandten Gebieten kann man das Prinzip der dynamischen Programmierung einsetzen, um etwa eine Gleichung herzuleiten (Hamilton-Jacobi-Bellman-Gleichung), deren Lösung den optimalen Wert ergibt. Die Argumentation ist dabei etwa folgende: Wenn das Problem zeitabhängig ist, kann man den optimalen Wert der Zielfunktion zu einem bestimmten Zeitpunkt betrachten. Man fragt sich dann, welche Gleichung die optimale Lösung erfüllen muss, damit das [[Funktional]] auch zu einem späteren Zeitpunkt optimal bleibt, dies führt zur [[Hamilton-Jacobi-Bellman-Gleichung]]. Damit kann man das Problem in Zeitschritte einteilen, anstatt es auf einmal lösen zu müssen.

	In der [[Physik]] war dieses Prinzip schon seit Langem bekannt, allerdings nicht unter diesem Namen. Der Übergang von einer globalen (alle Zeitpunkte gleichzeitig) zu einer zeitabhängigen (dynamischen) Betrachtungsweise entspricht dort der Transformation der [[Lagrangefunktion\|Lagrange-Funktion]] in die [[Hamilton-Funktion]] mit Hilfe der [[Legendre-Transformation]].		In der [[Physik]] war dieses Prinzip schon seit Langem bekannt, allerdings nicht unter diesem Namen. Der Übergang von einer globalen (alle Zeitpunkte gleichzeitig) zu einer zeitabhängigen (dynamischen) Betrachtungsweise entspricht dort der Transformation der [[Lagrangefunktion\|Lagrange-Funktion]] in die [[Hamilton-Funktion]] mit Hilfe der [[Legendre-Transformation]].

	== Musterbeispiel ==		== Musterbeispiel ==
Zeile 24:		Zeile 24:

	Die Berechnung für <code>fib(2)</code> wurde doppelt ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.		Die Berechnung für <code>fib(2)</code> wurde doppelt ausgeführt. Für die Berechnung von größeren Fibonacci-Zahlen nimmt die Anzahl an mehrfachen Berechnungen entsprechend exponentiell zu, woraus die exponentielle Laufzeit dieses Programmes resultiert.


	In einem möglichen dynamischen Programm berechnen wir erstmal die kleineren Fibonacci-Zahlen und bauen aus diesen die größeren Fibonacci-Zahlen indem wir jede Berechnung nur einmal durchführen.<syntaxhighlight>		In einem möglichen dynamischen Programm berechnen wir erstmal die kleineren Fibonacci-Zahlen und bauen aus diesen die größeren Fibonacci-Zahlen indem wir jede Berechnung nur einmal durchführen.<syntaxhighlight>

Thirain: Musterbeispiel für dynamische Programmierung einschliesslich Pseudocode angegeben

2024-03-04T21:57:35Z

Musterbeispiel für dynamische Programmierung einschliesslich Pseudocode angegeben

@@ Zeile 8: / Zeile 8: @@
 In der [[Physik]] war dieses Prinzip schon seit Langem bekannt, allerdings nicht unter diesem Namen. Der Übergang von einer globalen (alle Zeitpunkte gleichzeitig) zu einer zeitabhängigen (dynamischen) Betrachtungsweise entspricht dort der Transformation der  [[Lagrangefunktion|Lagrange-Funktion]] in die [[Hamilton-Funktion]] mit Hilfe der [[Legendre-Transformation]].
-== Beispiele ==
+== Musterbeispiel ==
 * [[Cocke-Younger-Kasami-Algorithmus|CYK-Algorithmus]]
 * [[Earley-Algorithmus]]

95.223.107.195: Linkfehler behoben

2023-07-06T19:53:23Z

Linkfehler behoben

← Nächstältere Version		Version vom 6. Juli 2023, 21:53 Uhr
Zeile 46:		Zeile 46:

	== Weblinks ==		== Weblinks ==
	* [https://bibiserv.cebitec.uni-bielefeld.de/adp/ ADP an der Uni Bielefeld]		* [https://bibiserv.cebitec.uni-bielefeld.de/adp/welcome.html ADP an der Uni Bielefeld]

	== Einzelnachweise ==		== Einzelnachweise ==

Aka: /* Weblinks */ https

2021-07-05T15:22:36Z

Weblinks: https

← Nächstältere Version		Version vom 5. Juli 2021, 17:22 Uhr
Zeile 46:		Zeile 46:

	== Weblinks ==		== Weblinks ==
	* [~~http~~://bibiserv.~~techfak~~.uni-bielefeld.de/adp/ ADP an der Uni Bielefeld]		* [https://bibiserv.cebitec.uni-bielefeld.de/adp/ ADP an der Uni Bielefeld]

	== Einzelnachweise ==		== Einzelnachweise ==

Hoss am 15. Mai 2021 um 12:08 Uhr

2021-05-15T12:08:05Z

← Nächstältere Version		Version vom 15. Mai 2021, 14:08 Uhr
Zeile 4:		Zeile 4:
	Dynamische Programmierung kann erfolgreich eingesetzt werden, wenn ein [[Optimierungsproblem]] aus vielen gleichartigen Teilproblemen besteht und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt. Dies nennt man [[Optimalitätsprinzip von Bellman]]. In der dynamischen Programmierung werden zuerst die optimalen Lösungen der kleinsten Teilprobleme direkt berechnet und dann geeignet zu einer Lösung eines nächstgrößeren Teilproblems zusammengesetzt. Dieses Verfahren setzt man fort, bis das ursprüngliche Problem gelöst wurde. Einmal berechnete Teilergebnisse werden in einer [[Tabelle]] gespeichert. Bei nachfolgenden Berechnungen gleichartiger Teilprobleme wird auf diese Zwischenlösungen zurückgegriffen, anstatt sie jedes Mal neu zu berechnen, was zu einer Senkung der Laufzeit führt. Wird die dynamische Programmierung konsequent eingesetzt, vermeidet sie kostspielige [[Rekursion]]en, weil bekannte Teilergebnisse wiederverwendet werden.		Dynamische Programmierung kann erfolgreich eingesetzt werden, wenn ein [[Optimierungsproblem]] aus vielen gleichartigen Teilproblemen besteht und eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt. Dies nennt man [[Optimalitätsprinzip von Bellman]]. In der dynamischen Programmierung werden zuerst die optimalen Lösungen der kleinsten Teilprobleme direkt berechnet und dann geeignet zu einer Lösung eines nächstgrößeren Teilproblems zusammengesetzt. Dieses Verfahren setzt man fort, bis das ursprüngliche Problem gelöst wurde. Einmal berechnete Teilergebnisse werden in einer [[Tabelle]] gespeichert. Bei nachfolgenden Berechnungen gleichartiger Teilprobleme wird auf diese Zwischenlösungen zurückgegriffen, anstatt sie jedes Mal neu zu berechnen, was zu einer Senkung der Laufzeit führt. Wird die dynamische Programmierung konsequent eingesetzt, vermeidet sie kostspielige [[Rekursion]]en, weil bekannte Teilergebnisse wiederverwendet werden.

	In der Regelungstheorie und verwandten Gebieten kann man das Prinzip der dynamischen Programmierung einsetzen, um etwa eine Gleichung herzuleiten (Hamilton-Jacobi-Bellman-Gleichung), deren Lösung den optimalen Wert ergibt. Die Argumentation ist dabei etwa folgende: Wenn das Problem zeitabhängig ist, kann man den optimalen Wert der ~~[[Funktional\|~~Zielfunktion]] zu einem bestimmten Zeitpunkt betrachten. Man fragt sich dann, welche Gleichung die optimale Lösung erfüllen muss, damit das ~~Zielfunktional~~ auch zu einem späteren Zeitpunkt optimal bleibt, dies führt zur [[Hamilton-Jacobi-Bellman-Gleichung]]. Damit kann man das Problem in Zeitschritte einteilen, anstatt es auf einmal lösen zu müssen.		In der Regelungstheorie und verwandten Gebieten kann man das Prinzip der dynamischen Programmierung einsetzen, um etwa eine Gleichung herzuleiten (Hamilton-Jacobi-Bellman-Gleichung), deren Lösung den optimalen Wert ergibt. Die Argumentation ist dabei etwa folgende: Wenn das Problem zeitabhängig ist, kann man den optimalen Wert der Zielfunktion zu einem bestimmten Zeitpunkt betrachten. Man fragt sich dann, welche Gleichung die optimale Lösung erfüllen muss, damit das [[Funktional]] auch zu einem späteren Zeitpunkt optimal bleibt, dies führt zur [[Hamilton-Jacobi-Bellman-Gleichung]]. Damit kann man das Problem in Zeitschritte einteilen, anstatt es auf einmal lösen zu müssen.

	In der [[Physik]] war dieses Prinzip schon seit Langem bekannt, allerdings nicht unter diesem Namen. Der Übergang von einer globalen (alle Zeitpunkte gleichzeitig) zu einer zeitabhängigen (dynamischen) Betrachtungsweise entspricht dort der Transformation der [[Lagrangefunktion\|Lagrange-Funktion]] in die [[Hamilton-Funktion]] mit Hilfe der [[Legendre-Transformation]].		In der [[Physik]] war dieses Prinzip schon seit Langem bekannt, allerdings nicht unter diesem Namen. Der Übergang von einer globalen (alle Zeitpunkte gleichzeitig) zu einer zeitabhängigen (dynamischen) Betrachtungsweise entspricht dort der Transformation der [[Lagrangefunktion\|Lagrange-Funktion]] in die [[Hamilton-Funktion]] mit Hilfe der [[Legendre-Transformation]].