Bienvenido al Curso
Introducción al curso básico de algoritmos y estructuras de datos
Introducción a los algoritmos
¿Qué entiende una computadora?
Lenguajes de programación
Estructuras de datos
¿Qué es un algoritmo?
Metodología para la construcción de un algoritmo
Variables y tipos de datos
User defined data types
Instalando Ubuntu Bash en Windows
Creando nuestro user defined data type
Abstract Data Types básicos: Lists, Stacks, Queues
Explicación gráfica Data Types básicos
Glosario de funciones para Abstract Data Types
Clases y objetos
Creando tu primera Queue: Arrays
Creando tu primera Queue: implementación.
Creando tu primera Queue: implementar la función enQueue
Creando tu primera Queue: implementar la función deQueue
Creando tu primera Queue: main code
Algoritmos de ordenamiento
Algoritmos de ordenamiento
Bubble sort
Bubble sort: implementación
Bubble sort: main code
Insertion sort
Desafío: implementa un algoritmo de ordenamiento
Recursividad
Recursividad
La función Factorial, calculando el factorial recursivamente
Manejo de cadenas de caracteres
Arte: Generando arte recursivo
Divide and conquer y programación dinámica
Divide and Conquer (divide y vencerás)
Qué es la programación dinámica (divide y vencerás v2.0)
MergeSort
Desafío: Buscar el algortimo más rápido de sort
Implementando QuickSort con Python
Implementando QuickSort con Python: main code
Algoritmos 'Greedy'
Qué son los Greedy Algorithm
Ejercicio de programación greedy
Ejercio de programación greedy: main code
Grafos y árboles
Grafos y sus aplicaciones
Árboles
¿Cómo comparar Algoritmos?
Cómo comparar algoritmos y ritmo de crecimiento
¿Qué sigue?
Cierre del curso y siguientes pasos
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
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.
Aportes 36
Preguntas 0
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]
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.
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.
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
La programación dinámica es un método para resolver problemas complejos, ya que los divide en problemas más pequeños, los resuelve y conforme va resolviendo lo va acomodando para la resolución del problema final.
analizar un problema y descomponerlo en problemas mas pequeños
Programación dinámica: En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas.
Según este artículo en Wikipedia, Quick Sort no es un problema de de programación dinámica.
Resumen:
using System;
class SortingWithMerge{
static void Main() {
int[] arr = {47,-854,852,1,-99,0,-9999,9,10,8};
MergeSort(arr, 0, arr.Length-1);
foreach(int num in arr)
{
Console.WriteLine(num);
}
}
public static void MergeSort(int[] arr, int low, int high)
{
if( high > low)
{
int mid = (low + high) / 2;
MergeSort(arr, low, mid);
MergeSort(arr, (mid+1), high);
Merge(arr, low, mid, high);
}
}
public static void Merge(int[] arr, int low, int mid, int high)
{
int[] temp = new int[arr.Length];
int i = low;
int j = mid +1;
int k = low;
int elementNum = (high - low +1);
while(i <= mid && j <= high)
{
if(arr[i] <= arr[j])
{
temp[k] = arr[i];
i++;
}
else
{
temp[k] = arr[j];
j++;
}
k++;
}
while(i <= mid)
{
temp[k] = arr[i];
i++;
k++;
}
while(j <= high)
{
temp[k] = arr[j];
j++;
k++;
}
for( int n = 0; n<elementNum; n++ )
{
arr[high] = temp[high] ;
high--;
}
}
}
``
Se aplica mucho en programacion, excelente
gracias
function quickSort(array) {
if (array.length < 1) {
return [];
}
var left = [];
var right = [];
var pivot = array[0];
for (var i = 1; i < array.length; i++){
if (array[i] < pivot){
if (array[i] < pivot){
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return [].concat(quickSort(left), pivot, quickSort(right));
}
}
console.log(quickSort([4, 9, 2, 1, 6, 3, 8]));```
Interesante añadido al paradigma “divide y vencerás”, añadimos un concepto de memoria. Nos ahorramos la combinación.
Programación dinámica
Método para resolver problemas complejos, rompiéndolos en un conjunto de problemas simples.
Dividir, Conquistar y Combinar
Dividir: Tomar un problema grande en subproblemas
Conquistar: Resolver cada uno de los subproblemas
Combinar: Unir apropiadamente las respuestas
“Know your history or be doomed to repeat it”
Wuaooo me quedo muchísimo más claro!! gracias!!
Hace un tiempo vi la implementación del factorial de un número, usando este concepto, y hasta ahora me entero de que es programación dinámica D:. Excelente explicación.
“Problemas que solucionamos se van a ir guardando automáticamente y se va a ir acomodando automáticamente”
Cuando un profesor dice un concepto y se ríe lo mas probable es que eso vaya en el examen jejeje
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?