Claudia Johana Herrera Torres
Company_adminRicardo Celis
ProfesorManuel Alejandro Aguilar Téllez Girón
Antes de implementar nuestro algoritmo quicksort tenemos que ver otro concepto súper importante, la programación dinámica.
La programación dinámica es el método para resolver problemas complejos, rompiéndolos en un conjunto de problemas simples
La diferencia con el divide y vencerás que aprendimos anteriormente es que cada uno de los problemas que solucionamos se van a ir guardando automáticamente y se va a ir acomodando automáticamente.
Claudia Johana Herrera Torres
Company_adminRicardo Celis
ProfesorManuel Alejandro Aguilar Téllez Girón
Juan Camilo Alvarez Jurado
Moisés Manuel Morín Hevia
Aldo Yedro
Danelia Sanchez Sanchez
Walter Alvarado
Karen Paola Diaz Duarte
Bernardo Aguayo Ortega
Rodolfo Christian Catunta Uturunco
Moisés Manuel Morín Hevia
Efraín Hernández García
Oliver Jesus Tuesta Yoplac
Wandy Rafael Santana Evangelista
Gibrán Pelayo Miranda
Gibrán Pelayo Miranda
Jakson Duvan Zambrano
Angie Garcia
Adriana del Pilar Martinez Bautista
Mayerly Prieto Muñoz
Leisy Karina Algarra Fernandez
Carlos Nassif Trejo Garcia
Bernardo Aguayo Ortega
MELVIN EMMANUEL HERNÁNDEZ AYALA
Gabriel Obregón
Nicolas Alpargatero
gran frase gracias!
Jajaja qué cool!
La programación dinámica es una técnica de diseño de algoritmos que busca mejorar la complejidad en tiempo de la solución de un problema que se pueda plantear desde una filosofía recursiva, empleando la reutilización de las soluciones ya obtenidas con una estructura de datos auxiliar, cuyos elementos representan sub-problemas específicos (según cómo se determine). Puede ser top-down (desde lo más general hacia abajo, requiere un manejo recursivo empleando "memoization"), o bien bottom-up (iterativo, partiendo del problema trivial hasta el problema más general)
El procedimiento que se sigue para plantear la solución de programación dinámica a un problema es el siguiente:
1. Identificar los problemas triviales del problema, a partir de los cuales se puedan generalizar luego problemas más complejos 2. Verificar cuáles problemaas están apenas un nivel más alto que el trivial, e inducir una generalización recursiva (y de optimización, si es el caso) para éstos 3. Determinar finalmente la respuesta de los problemas generalizados a partir de la estructura de datos que contiene las soluciones calculadas
En problemas de optimización, la estructura de datos de apoyo almacena las soluciones óptimas a los problemas de decisión (de los problemas triviales a los más generales); de este modo, para establecer la solución general hay que basarse en las decisiones de optimización que quedan reflejadas en dicha estructura (recorriendo desde los problemas triviales hasta el más general, tomando nota de los elementos a los que corresponden los valores óptimos, información que es proporcionada por los índices de las casillas a los que corresponden los problemas particulares)
Ejemplo 1: Factorial
Primero se identifican los problemas triviales:
factorial de 0 = 1 factorial de 1 = 1
Luego se induce una generalización partiendo de problemas apenas mayores a los triviales:
factorial de 2 = 2 * factorial de 1 factorial de 3 = 3 * factorial de 2 ... factorial de N = N * factorial de N-1
Se define la estructura solución:
solucion[i] = factorial de i
El algoritmo queda:
funcion factorial(N : entero) : entero soluciones <- Nuevo arreglo de enteros tamaño N solucion[0] <- 0 // Solucion trivial solucion[1] <- 1 // Solucion trivial para i <- 2 hasta N solucion[i] <- i * solucion[i-1] // Solucion general retorna solucion[N] // Solucion final
Ejemplo 2: Elemento de la secuencia de Fibonacci
Problemas triviales:
Fibonacci de 0 = 1 Fibonacci de 1 = 1
Generalización:
Fibonacci de 2 = Fibonacci de 1 + Fibonacci de 0 Fibonacci de 3 = Fibonacci de 2 + Fibonacci de 1 ... Fibonacci de N = Fibonacci de N-1 + Fibonacci de N-2
Se define la estructura solución:
solucion[i] = Fibonacci de i
Algoritmo:
funcion fibonacci(N : entero) : entero solucion <- Nuevo arreglo de tamaño N solucion[0] <- 1 solucion[1] <- 1 para i <-2 hasta N solucion[i] <- solucion[i-1] + solucion[i-2] return solucion[N]
Buen resumen !
Muy bueno!
Aprendiendo Dynamic Programming con JS porque el entrevistador me lo ordenó -parte 1
para que calcular algo muchas veces si ya lo calcule una vez ?? programación dinámica = recursividad + memorización simple y muy eficiente
LA PROGRAMACIÓN DINÁMICA: Es un concepto importante, es un método para resolver problemas grandes y complejos esta programación dinámica agrega una cosa mas y es cada uno de los subproblemas que se van resolviendo, se va a ir guardando automáticamente y ahí esta lo dinámico. El programa lleva la cuenta de todos los cálculos o ordenamientos y cuando le agregas una nueva operación simplemente la acumula dinamicamente.
básicamente Divide and Conuqer mejorado
La principal ventaja que tiene la programación dinámica contra el paradigma de Divide y Venceras es que memoiza los resultados, memoizar, significa que guarda en memoria un resultado calculado previamente, lo que hace que por ejemplo si existen sub problemas "solapados" es decir sub problemas que ya hemos calculado antes, pues no los vuelve a calcular, lo que lo hace mas eficiente.
Buen resumen !
En pocas palabras la programación dinamica es un método de otpimización matematica en el que se pueden seguir agregando datos.
Acá un ejemplo con de las serie fibonacci con programación dinámica en Java
public class Fibonacci { Map<Integer, Integer> memory = new HashMap<Integer, Integer>(); public int fibonacci(int n){ if (n == 0) return 0; if (n == 1) return 1; if (memory.get(n) != null){ return memory.get(n); } memory.put(n, fibonacci(n-1) + fibonacci(n-2)); return memory.get(n); } }
Merge Sort en JS:
function merge(leftArr, rightArr) { var sortedArr = []; while (leftArr.length && rightArr.length) { if (leftArr[0] <= rightArr[0]) { sortedArr.push(leftArr[0]); leftArr = leftArr.slice(1) } else { sortedArr.push(rightArr[0]); rightArr = rightArr.slice(1) } } while (leftArr.length) sortedArr.push(leftArr.shift()); while (rightArr.length) sortedArr.push(rightArr.shift()); return sortedArr; } function mergesort(arr) { if (arr.length < 2) { return arr; } else { var midpoint = parseInt(arr.length / 2); var leftArr = arr.slice(0, midpoint); var rightArr = arr.slice(midpoint, arr.length); return merge(mergesort(leftArr), mergesort(rightArr)); } } let unsortedArr = [340, 1, 3, 3, 76, 23, 4, 12, 122, 7642, 646]; console.log('This should be the sorted array!') console.log(mergesort(unsortedArr));```
Tratando de entender programación dinámica, encontré esta liga que puede servir: No memoización
Y bueno, adjunto código del Merge Sort para C, antes de pasar a la propia clase:
#include <stdio.h> void merge(int izq[], int c_izq, int der[], int c_der, int original[]) { int i, j, k; i = j = k = 0; while(i < c_izq && j < c_der) { if(izq[i] <= der[j]) { original[k] = izq[i]; i++; } else { original[k] = der[j]; j++; } k++; } while(i < c_izq) { original[k] = izq[i]; i++; k++; } while(j < c_der) { original[k] = der[j]; j++; k++; } } void mergeSort(int original[], int tam) { if(tam < 2) return; else { int mitad = tam/2; int izq[mitad], der[tam-mitad]; for(int i=0; i<mitad; i++) izq[i] = original[i]; for(int i=mitad; i<tam; i++) der[i-mitad] = original[i]; int tam_izq = sizeof(izq)/sizeof(izq[0]); int tam_der = sizeof(der)/sizeof(der[0]); mergeSort(izq, mitad); mergeSort(der, tam-mitad); merge(izq, tam_izq, der, tam_der, original); } } void main() { int original[]={9000, 8888, 6677, 5544, 5500, 3333, 222, 11, 0}; int e = sizeof(original)/sizeof(original[0]); printf("\nArreglo desordenado: \n"); for(int i=0; i<e; i++) printf("%d ", original[i]); mergeSort(original, e); printf("\n\nArreglo ordenado (ascendente): \n"); for(int i=0; i<e; i++) printf("%d ", original[i]); printf("\n\nFin."); }
Aquí lo puedes ver funcionando.
let array = [100, 4, 3, 5, 6, 5, 7, 7, 10, 13, 25] let parte1 = array.splice(0, (array.length/2)) let parte2 = array.splice(0, array.length) for(i = 0; i < parte1.length; i++){ if(parte1[i] > parte1[i+1]){ let temp = parte1[i] parte1[i] = parte1[i+1] parte1[i+1] = temp } } for(i = 0; i < parte2.length; i++){ if(parte2[i] > parte2[i+1]){ let temp = parte2[i] parte2[i] = parte2[i+1] parte2[i+1] = temp } } let merge = parte1.concat(parte2) for(i = 0; i < merge.length; i++){ if(merge[i] > merge[i+1]){ let temp = merge[i] merge[i] = merge[i+1] merge[i+1] = temp } } document.write(merge)```
interesante, me gustaria aplicarlo y praticar mas
Gran método de optimización en el programa que lo hace ser dinámico.
Es esta version 2.0, cada uno de los subproblemas, se van guardando y acomodando automátcamente.
Divide and conquer: (divide y vencerás) divide, vence y combina. programación dinámica: cada vez que desarrollamos o resolvemos un problema se irá implementando automáticamente.
Programación dinámica es como divide and conquer, pero sin el paso de combinar ya que esta lo hace automáticamente
más claro no se puede, gracias Carlos
¿Cuándo debo usar Quicksort en lugar de MergeSort?
Debes optar por Quicksort cuando necesites optimizar el uso de la memoria RAM y estés trabajando con conjuntos de datos masivos en sistemas con recursos limitados. A diferencia de otros métodos, Quicksort ordena los elementos in-place (en su mismo lugar).
Imagina que estás organizando una biblioteca. Con MergeSort, necesitarías una habitación vacía adicional del mismo tamaño para ir colocando los libros ordenados antes de devolverlos a su estante original (esto representa el paso de combinación que consume memoria extra). Con Quicksort, simplemente intercambias los libros de posición directamente en el estante actual utilizando un punto de referencia o pivote. Al no requerir esa habitación extra para combinar resultados, Quicksort es increíblemente rápido y eficiente en la práctica, siendo el algoritmo de ordenamiento por defecto en las librerías estándar de lenguajes como C, C++ y Java para tipos primitivos.
🧾Programación Dinámica
📌 ¿Qué es?
🔹 Método para resolver problemas complejos.
🔹 Se dividen en subproblemas más simples.
🔹 Diferencia con divide y vencerás:
💡 Idea central
⚡ No recalcular lo mismo.
⚡ Guardar (“memorizar”) resultados previos.
⚡ Cuando reaparece el cálculo, usas lo guardado → avanzas más rápido.
🧮 Ejemplo claro
1️⃣ Primero:
👉 1 + 1 + 1 + 1 + 1 + 1 = 6
2️⃣ Después:
👉 (1+1+1+1+1+1) + 1
👉 En vez de repetir todo, haces: 6 + 1 = 7
✅ Ahorro de tiempo y esfuerzo.
🗂️ Cómo funciona en programación
🔸 Resolver un subproblema → haces un cálculo inicial.
🔸 Guardar el resultado → lo almacenas en memoria.
🔸 Nueva solución → construyes usando lo guardado.