Asdasd
Enviado por Programa Chuletas y clasificado en Lengua y literatura
Escrito el en 
español con un tamaño de 4,13 KB
"DIV Y VEN" en que consiste esta tecnica en terminos informaticos?
resolver el problema a través de subproblemas , así hasta que los problemas sean lo bastante pequeños para encontrar mejores soluciones.
mecione y explique los 3 pasos que debe realizarese par aplicar esta tecnica.
1) se plantea el problema de forma que se pueda dividir en k subproblemas del mismo tipo pero de menor tamaño
2) cada subproblemas debe resolverse independientemente
3) conbinar las soluciones .
Explique como se aplica esta tecnicas en el algoritmo de busqueda binaria.
existe un elemento dado x en un vector de enteros “ordenados”. el valor x se compara con el termino central del vector , caso que coincida , hemos solucionado nuestro problema, de lo contrario se daran dos condiciones , que x sea mayor que el temino central o que sea menor, en cualquiera de los das casos podemos descartar uno de ellos, repitiendo el paso con el subvector elegido de forma recursiva, hasta encontrar el valor buscado.
De los ejemplos dados en el texto: expliqeu com se aplica esta técnica en al menos 2 algoritmos distintosa a busqueda binaria.
Búsqueda ternaria Consideremos un valor x que queremos comparar con el elemento de la posición n/3 del vector, si este elemento es menor al valor x entonces comparamos con el elemento en la posición 2n/3, y si no coincide con x busca recursivamente en el correspondiente subvector del tamaño 1/3 del original.
LA SUBSECUENCIA DE SUMA MÁXIMA
Dividiremos este problema en 3 subproblemas sobre cuyas soluciones constituiremos la solución final. En este caso la subsecuencia de suma máxima se puede encontrar en 3 partes, al principio del vector, en el medio, o en el final. Por esto dividiremos el problema en tres subproblemas. Los dos primeros casos pueden resolverse recursivamente. Respecto al tercero, podemos calcular la subsecuencia de suma máxima de la primera mitad que contenga al último elemento de esa primera mitad, y la subsecuencia de suma máxima de la segunda mitad que contenga al primer elemento de esa segunda mitad.
Programacion Dinamica
Es una técnica que parte del principio de no calcular dos veces la misma información, por lo tanto se utilizan estructuras de almacenamiento como vectores, tablas, arreglos, archivos, con el fin de almacenarlos resultados parciales, que contribuyan a la solución final.
Este algoritmo evita calcular dos veces la misma información, manteniendo una tabla de resultados conocidos, la cual se va llenando a medida que seresuelven los subcasos. Es una técnica ascendente que normalmente, empieza por los subcasosmás pequeños y más sencillos.Combinando sus soluciones, obtenemoslas respuestas para los subcasos cada vez mayores, hasta que llegamosa la solucióndel caso original.
La programación dinámica se aplica no solo por razones de eficiencia, sino porque permite resolver de manera eficiente problemas que no se pueden resolver por otras metodologías.
El mayor número de aplicaciones se encuentra en problemas que requieren optimización, ya que se pueden hallar múltiples soluciones y así evaluarlas para hallar la óptima.
Al contrario del método divide y venceras que es de tipo decendente ya que divide los problemas de grandes a pequeños, La programación dinámica es de tipo ascendente ya que soluciona los problemas chicos y los va guardando para solucionar los mas grandes.
FORMA GENERAL
La forma general de las soluciones desarrolladas mediante programación dinámica requiere de los siguientes pasos:
planteamiento de la solución, mediante una serie de decisiones que garanticen que la solución será óptima.
Encontrar una solución recursiva de la definición.
Calcular la solución teniendo en cuenta una tabla en la que se almacenen soluciones a problemas parciales para su reutilización y así evitar el nuevo cálculo.
resolver el problema a través de subproblemas , así hasta que los problemas sean lo bastante pequeños para encontrar mejores soluciones.
mecione y explique los 3 pasos que debe realizarese par aplicar esta tecnica.
1) se plantea el problema de forma que se pueda dividir en k subproblemas del mismo tipo pero de menor tamaño
2) cada subproblemas debe resolverse independientemente
3) conbinar las soluciones .
Explique como se aplica esta tecnicas en el algoritmo de busqueda binaria.
existe un elemento dado x en un vector de enteros “ordenados”. el valor x se compara con el termino central del vector , caso que coincida , hemos solucionado nuestro problema, de lo contrario se daran dos condiciones , que x sea mayor que el temino central o que sea menor, en cualquiera de los das casos podemos descartar uno de ellos, repitiendo el paso con el subvector elegido de forma recursiva, hasta encontrar el valor buscado.
De los ejemplos dados en el texto: expliqeu com se aplica esta técnica en al menos 2 algoritmos distintosa a busqueda binaria.
Búsqueda ternaria Consideremos un valor x que queremos comparar con el elemento de la posición n/3 del vector, si este elemento es menor al valor x entonces comparamos con el elemento en la posición 2n/3, y si no coincide con x busca recursivamente en el correspondiente subvector del tamaño 1/3 del original.
LA SUBSECUENCIA DE SUMA MÁXIMA
Dividiremos este problema en 3 subproblemas sobre cuyas soluciones constituiremos la solución final. En este caso la subsecuencia de suma máxima se puede encontrar en 3 partes, al principio del vector, en el medio, o en el final. Por esto dividiremos el problema en tres subproblemas. Los dos primeros casos pueden resolverse recursivamente. Respecto al tercero, podemos calcular la subsecuencia de suma máxima de la primera mitad que contenga al último elemento de esa primera mitad, y la subsecuencia de suma máxima de la segunda mitad que contenga al primer elemento de esa segunda mitad.
Programacion Dinamica
Es una técnica que parte del principio de no calcular dos veces la misma información, por lo tanto se utilizan estructuras de almacenamiento como vectores, tablas, arreglos, archivos, con el fin de almacenarlos resultados parciales, que contribuyan a la solución final.
Este algoritmo evita calcular dos veces la misma información, manteniendo una tabla de resultados conocidos, la cual se va llenando a medida que seresuelven los subcasos. Es una técnica ascendente que normalmente, empieza por los subcasosmás pequeños y más sencillos.Combinando sus soluciones, obtenemoslas respuestas para los subcasos cada vez mayores, hasta que llegamosa la solucióndel caso original.
La programación dinámica se aplica no solo por razones de eficiencia, sino porque permite resolver de manera eficiente problemas que no se pueden resolver por otras metodologías.
El mayor número de aplicaciones se encuentra en problemas que requieren optimización, ya que se pueden hallar múltiples soluciones y así evaluarlas para hallar la óptima.
Al contrario del método divide y venceras que es de tipo decendente ya que divide los problemas de grandes a pequeños, La programación dinámica es de tipo ascendente ya que soluciona los problemas chicos y los va guardando para solucionar los mas grandes.
FORMA GENERAL
La forma general de las soluciones desarrolladas mediante programación dinámica requiere de los siguientes pasos:
planteamiento de la solución, mediante una serie de decisiones que garanticen que la solución será óptima.
Encontrar una solución recursiva de la definición.
Calcular la solución teniendo en cuenta una tabla en la que se almacenen soluciones a problemas parciales para su reutilización y así evitar el nuevo cálculo.