Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Programación dinámica

Técnicas de diseño de algoritmos. Apuestas de la serie mundial de béisbol
by

Natalia Arvizu

on 4 December 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Programación dinámica

Apuestas en la serie mundial de béisbol. Programación dinámica Definición Es un método para reducir el
tiempo de ejecución de un algoritmo mediante
la utilización de subproblemas superpuestos y subestructuras óptimas. El diseño consta de los siguientes pasos: Apuestas en la
serie mundial de béisbol Competición entre dos equipos,
A y B, en la que el ganador
es el primer equipo que consiga
n victorias.
• No hay empates, los resultados de
todos los partidos son independientes.
A y B son igualmente competentes,
cada uno tiene un
50% de ganar Se rellena una tabla sin tener en cuenta si se necesita realmente un subproblema particular en la solución total. La formación de la tabla de subproblemas para alcanzar una solución a un problema dado se denomina programación dinámica, nombre procedente de la teoría de control. La forma de un
algoritmo de
programación dinámica
puede variar,
pero hay un esquema común:
una tabla a rellenar
y un orden en el cual
se hacen las entradas. 1. Planteamiento de la solución como una sucesión de decisiones y verificación de que ésta cumple el principio de óptimo.
2. Definición recursiva de la solución.
3. Cálculo del valor de la solución óptima mediante una tabla en donde se almacenan soluciones a problemas parciales para reutilizar los cálculos.
4. Construcción de la solución óptima haciendo uso de la información contenida en la tabla anterior. P(i, j) = probabilidad de que
A gane la competición si a A le faltan
i victorias para ganar
y a B le faltan j victorias. Definición recursiva:
P(i, j) = (P(i − 1, j) + P(i, j − 1))/2
i > 0 y j > 0
Los casos básicos son:
P(0, j) = 1 i = 0 y j > 0 A ya ha ganado
P(i, 0) = 0 j = 0 y i > 0 B ya ha ganado El problema con el cálculo
recursivo es que se calcula la misma
P(i,j) muchas veces. Una forma mejor de calcular P(i,j) es llenar
la tabla.
La fila inferior está llena de 0's y la columna más a la derecha está llena de 1's (debido a los casos básicos).
Cada una de las otras entradas es el promedio de la entrada de abajo y de la entrada de la derecha.
Una forma apropiada de llenar la tabla es proceder en diagonales a partir de la esquina inferior derecha, y procediendo hacia arriba y hacia la izquierda en diagonal que representan las posiciones con valor constante de i +j O(n^2) s = 1 P[0,1] = 1
P[1,0] = 0 k = 1 <= (s-1) s = 2 P[0,2] = 1
P[2,0] = 0

k = 1 <= 2 -1
P[1,1] = P[0,1] + P[1,0] / 2 =
1 + 0 / 2 = 1/2
k = 2 <= 1 x s = 3 P[0,3] = 1
P[3,0] = 0

k = 1 <= 2
P[1,2] = P[0,2] + P[1,1]/2 = (1 + 1/2) /2 = 3/4
k = 2
P[2,1] = P[1,1] + P[2,0]/2 = (1/2 + 0) /2 = 1/4 s = 4 P[0,4] = 1
P[4,0] = 0

k=1 <= 3
P[1,3] = P[0,3] + P[1,2]/2 = (1 + 3/4)/2 = 7/8
k=2
P[2,2] = P[1,2] + P[2,1]/2 = (3/4 + 1/4)/2 = 1/2
k=3
P[3,1] = P[2,1] + P[3,0]/2 = (1/4 + 0)/2 = 1/8 s = 5 P[0,5] = 1
P[5,0] = 0
k=1 <= 4
P[1,4] = P[0,4] + P[1,3]/2 =
(1 + 7/8)/2 = 15/16
k=2
P[2,3] = P[1,3] + P[2,2]/2 =
(7/8 + 1/2)/2 = 11/16
k=3
P[3,2] = P[2,2] + P[3,1]/2 =
(1/2 + 1/8)/2 = 5/16
k=4
P[4,1] = P[3,1] + P[4,0]/2 =
(1/8 + 0)/2 = 1/16 Arvizu Aranda, Natalia
Cárdenas Campos, Alejandro
Mora Quezada, Alejandro
Full transcript