El Tema que yo elegi para mi 5to proyecto y ultimo es Camino mas Largo: Programacion Dinámica.Principalmente
En teoría de los grafos [ grafos como nosotros ya sabemos es una representación mediante una serie de puntos (vértices) conectados por lineas (aristas) ], el problema de " El camino mas largo"
es dado un grafo, encontrar un camino simple de longitud maxima.
A diferencia de el problema camino mas corto que se puede solucionar en tiempo polinomial, pero este problema es NP- completo lo que quiere decir que la solución optima no se puede encontrar en tiempo polinomico.
Un problema Completo es aquel:
- Que todos los demas problemas de la clase se reducen.
- son los problemas más dificiles (en el hecho de que son mas largos)
El matemático Richard Bellman inventó la programacion dinamica en 1953.
Almacenar los resultados en una tabla, empezando por los tamaños pequeños y avanzando hacia los mas grandes.
Ademas es un metodo para reducir el tiempo de ejecucion de un algoritmo mediante la utilizacion de subproblemas superpuestos y subestructuras optimas (significa que se pueden usar soluciones optimas de subproblemas para encontrar la solucion optima de problema en su conjunto).
En general se pueden resolver problemas con subestructuras optimas siguiendo estos tres pasos:
- Dividir el problema en subproblemas mas pequeños
- Resolver estos problemas de manera optima usando este proceso de tres pasos recurrentes
- Usar estas soluciones optimas para construir una solucion optima al problema original.
La programacion dinamica es un metodo ascendente, se resuelven primero los sub ejemplares mas pequeños y por tanto mas simples. combinando las soluciones se obtienen las soluciones de ejemplares sucesivamente mas grande hasta llegar al ejemplar original.
Un ejemplo de camino largo puede ser
- Sucesion de Fibonacci
esta expresion puede expresarse mediante la siguiente recurrencia:
Fib(n)=
0 si n=0
1 si n=1
Fib(n-1)+ Fiib(n-2) si n>1
INICIO
SI n = 0 ENTONCES
DEVOLVER 0
SINOSI n = 1 ENTONCES
DEVOLVER 1
SINO
devolver fib(n-1) + fib(n-2)
FINSI
FIN
Si llamamos, por ejemplo, a fib(5), produciremos un árbol de llamadas que contendrá funciones con los mismos parámetros varias veces:
- fib(5)
- fib(4) + fib(3)
- (fib(3) + fib(2)) + (fib(2) + fib(1))
- ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
- (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
En particular, fib(2) se ha calculado dos veces desde cero. En ejemplos mayores, se recalculan muchos otros valores de fib.
Para evitar este inconveniente, podemos resolver el problema mediante programación dinámica, y en particular, utilizando el enfoque de memorización (guardar los valores que ya han sido calculados para utilizarlos posteriormente). Así, rellenaríamos una tabla con los resultados de los distintos subproblemas, para reutilizarlos cuando haga falta en lugar de volver a calcularlos. La tabla resultante sería una tabla unidimensional con los resultados desde 0 hasta n.Con programacion Dinamica
operacion fibonacci(n:entero): entero
T[1]:=1;T[2]:=1
para i:=3,......,n hacer
T[i]:= T[i-1]+T[i-2]
devolver T[n]
Cabe mencionar unos metodos como conclusión sobre este tema:
Metodo descentente
- Empezar con el problema original y descomponer recursivamente en problemas de menor tamaño.
- Partiendo del problema grande, descendemos hacia problemas más sencillos.
Metodo ascendente
- Resolvemos primero los problemas pequeños (guardando las soluciones en una tabla). Después los vamos combinando para resolver los problemas más grandes.
- Partiendo de los problemas pequeños avanzamos hacia los más grandes.
poniendo un grafo como el de la imagen poder realizar la tabla de la que les hable que se realiza con programacion dinamica
a continuacion la tabla
Bueno solo queria agregar eso para que quedara mas claro.
Autoevaluacion:
En mi opinion eh aprendido mucho de este curso puede que no me esta llendo perfecto pero se que tengo concimientos nuevos e interesantes, bueno anfocandome en este ultimo proyecto me puse muy nerviosa al exponer mi clase es por falta de seguridad y de saber el tema estoy de acuerdo en eso pero con todo y nervio pude exponerla. En esta clase aprendi a lo diferente de trabajar sola y en equipo y lo importante de eso, me falta poner mas de mi parte en cada punto de mis tareas es en lo que fallo.
Deseo la mejor de la suerte a todos.
cualquier duda con confianza pueden preguntarme :D
