PrEDA

24 entradas

Algoritmos de programación para resolver problemas informáticos: divide y vencerás, voraz, programación dinámica, vuelta atrás y ramificación y poda.

Números

PrEDA: cálculo empírico del coste temporal de Binomial

El coeficiente binomial es una función muy utilizada en combinatoria. Sirve para saber el número de combinaciones de elementos que podemos hacer. Se utiliza mucho en computación para estudiar la estrategia de programación dinámica, porque ejemplifica muy bien la mejora que supone utilizar dicha estrategia. Por ejemplo, la forma de escoger de entre 6 elementos 2 de ellos, es igual al coeficiente binomial (6 2). Su definición es: Binomial(n, k) = 1, si k=0 o k=n Binomial(n, k) = Binomial(n-1, k-1) + Binomial(n-1, k), en otro casi Partiendo de esta definición tenemos en PHP el siguiente código: function binomialRecursive($n, $k) { if ($k == 0 or $k == $n) { return 1; } else { return binomialRecursive($n – 1, $k – 1) + binomialRecursive($n – 1, $k); } } Para números grandes se repiten cálculos muchas veces, con lo que reducimos su coste temporal aplicando programación dinámica: function binomialDynamic($n, $k) { $tablaNK = array(); if ($k <= 0 or $k == $n) { return 1; } else { for ($i = 0; $i <= $n; ++$i) { $tablaNK[$i][0] = 1; } for ($i = 1; $i <= $k; ++$i) { $tablaNK[$i][$i] = 1; } for ($i = 2; $i <= […]

Números

PrEDA: cálculo empírico del coste temporal de Fibonacci

Continuando con post anteriores sobre esquemas algorítmicos. Dejo aquí unas pruebas empíricas sobre cómo calcular el Número de Fibonacci de números grandes. Si vemos la definición de Fibonacci es la siguiente: Fibonacci(n) = 1, si n=0 o n=1 Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2), si n> 1 El código en PHP para resolverlo sería el siguiente: function fibonacciRecursive($n) { if ($n <= 1) { return 1; } else { return fibonacciRecursive($n – 1) + fibonacciRecursive($n – 2); } } Observamos que se repiten cálculos, con lo que aplicando programación dinámica tenemos el siguiente código: function fibonacciDynamic($n) { $tabla = array(); if ($n <= 1) { return 1; } else { $tabla[0] = $tabla[1] = 1; for ($i = 2; $i <= $n; ++$i) { $tabla[$i] = $tabla[$i – 1] + $tabla[$i – 2]; } return $tabla[$n]; } } Estas dos funciones, para compararlas empíricamente, las usamos en un bucle que vaya incrementando el número $n para obtener su coste temporal empírico. También en PHP con éste código: define(‘MAX_N’, 100); for ($i = 0; $i <= MAX_N; ++$i) { $timeStart = microtime(true); $theNumber = fibonacciRecursive($i); //echo ‘fibonacciRecursive(‘.$i.’) = ‘.$theNumber.PHP_EOL; $timeEnd = microtime(true); echo ‘RECURSIVE fibonacci(‘.$i.’): Calculated in ‘.number_format($timeEnd – $timeStart, 9).’ seconds.’.PHP_EOL; […]

PrEDA algoritmos genericos 16x9

PrEDA: esquemas de programación genéricos avanzados

Otro HOWTO, code-kata, a traer vengo hoy.. XDD vengo con este post cargado de esquemas algorítmicos para programar. Estos esquemas algorítmicos son los que nos ayudan a programar las mejores soluciones. Así conseguimos llegar a las soluciones que a veces tenemos que encontrar, pero quizá no vemos en un principio cómo. Quizá el problema lo tenemos en que tarda mucho, o necesitamos demasiado espacio de almacenamiento. La mayoría de las veces, podemos recorrer todas las posibles soluciones a lo bruto hasta encontrar la solución. Es decir, muchos problemas se pueden resolver de muchas formas, pero no todas las formas de resolver el mismo problema son la mejor forma. Sólo hay una mejor forma para cada problema. Es decir, algunas soluciones son eficaces porque simplemente encuentran la solución, pero quizás no son la forma más eficiente. Incluso podemos tener problemas, que por no resolverlos eficientemente, se convierten en imposibles de resolver. Se trata de estos esquemas: Voraz. Divide y vencerás. Programación dinámica. Vuelta atrás. Ramificación y poda. Vamos al grano hermano.. Esquema voraz Este esquema o estrategia se utiliza para optimizar el funcionamiento cuando tenemos una única solución, y además, podemos establecer un algoritmo de selección de los elementos que forman […]

Gantt

PrEDA: minimizando tiempo en el sistema con varios agentes

Continuando con el post anterior, y de nuevo a modo de code-kata, vengo a traer el siguiente paso al algoritmo. Si en el post anterior teníamos cómo minimizar el tiempo en el sistema de varias tareas con un sólo agente, ahora le añadimos la posibilidad de tener varios. Seguimos teniendo una estrategia voraz para resolver el órden en que se ejecutan las tareas. También voraz para asignar a los agentes dichas tareas, porque se seleccionan las tareas sin tener que volver atrás en la selección. La estrategia de selección es ordenar las tareas por orden creciente de tiempo necesario, y vamos alternando entre los agentes para distribuirles las tareas, distribuyendo también así la carga entre los agentes. Igual que en la versión anterior, suponemos que todas las tareas tienen el mismo beneficio o importancia, no habría ninguna razón para priorizar tareas de más tiempo. La prioridad la tendrán entonces las tareas de menos tiempo en este caso.. El código Un poco más elaborado que el anterior: <?php define(‘NUMBER_OF_TASKS’, 30); define(‘NUMBER_OF_AGENTS’, 3); $tasksTime = array(); for ($i = 0; $i < NUMBER_OF_TASKS; ++$i) { $tasksTime[$i] = rand(1, 10); } $totalTimeClientsWaiting = printTasks($tasksTime, $maxTimeWaiting); echo ‘TIME IN SYSTEM OF TASKS: ‘.$totalTimeClientsWaiting.’ WITH […]

Gantt

PrEDA: minimizando tiempo en el sistema

La gestión de los proyectos es la clave: puede marcar la diferencia entre el éxito o el desastre. La gestión de las tareas no se puede hacer de cualquier forma. Por esto que se han estudiado y se han establecido muchas estrategias. No cualquier software puede ser un buen gestor de proyectos. Por esto que existen estudios que lo integran, técnicas de programación.. y sobretodo en informática, que existen multitud de estrategias, ya que dentro de los ordenadores esto se aplica constantemente. Los pasos clásicos a seguir son los siguientes: Se establecen las tareas, fijando especificaciones. Se estudian bien los tiempos que va a llevar cada tarea. Se establece la estrategia para proceder. Se resuelve el órden, con lo cual, aquí se obtienen las fechas de finalización de cada tarea y el tiempo total. Se ejecuta el proyecto. Como es obvio, en el primer paso se cierran especificaciones y cualquier modificación posterior invalida el algoritmo, y hay que recalcular todo. A modo de code-kata traigo hoy una estrategia voraz para organizar un proyecto con el objetivo de minimizar el tiempo de espera de las tareas en el sistema. Suponiendo que todas las tareas son igual de importantes, se trata de […]

Grafos, mapas y matrices de adyacencia

PrEDA: grafos, el algoritmo de Dijkstra mejorado

Vengo a traer una revisión del post anterior. Sobre el algoritmo de Dijkstra para cálculo de caminos mínimos entre nodos de un grafo, a modo de code-kata. Son unas modificaciones para hacer que se pueda elegir el nodo inicial desde el que arrancamos. Y una sencilla ordenación de los nodos de la lista de adyacencia. Así de esta forma se puede poner en la variable global definida como INITIAL_NODE el nodo desde el que buscaremos los caminos mínimos. El código He marcado en negrita las modificaciones con respecto del anterior post. <?php define(‘NUMBER_OF_NODES’, 17); define(‘INITIAL_NODE’, 3); define(‘NUMBER_OF_EDGES_PER_NODE’, 3); define(‘IS_DIRECTED_GRAPH’, true); $adjacencyList = array(); fillRandomCosts($adjacencyList); printToScreen($adjacencyList); $special = $predecessor = array(); dijkstra($adjacencyList, $special, $predecessor); echo ‘FINAL> Special: ‘.implode(‘-‘, $special).PHP_EOL .’FINAL> Predecessor: ‘.implode(‘-‘, $predecessor).PHP_EOL; function dijkstra($adjacencyList, &$special, &$predecessor) { // Fill C with not used nodes. $C = array(); for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { if ($i != INITIAL_NODE) { $C[] = $i; } } // Fill special distances. for ($i = 0; $i < NUMBER_OF_NODES; ++$i) { if ($i != INITIAL_NODE) { $special[$i] = distanceFromTo($adjacencyList, INITIAL_NODE, $i); if ($special[$i] < INF) { $predecessor[$i] = INITIAL_NODE; } else { $predecessor[$i] = ‘#’; } } else { $special[$i] = ‘I’; […]

Grafos, mapas y matrices de adyacencia

PrEDA: grafos, el algoritmo de Dijkstra

Después de haber repasado los fundamentos de los grafos: cómo se almacenan mediante matrices o listas de adyacencia, cómo se mantienen conectados mediante el algoritmo de Prim o Kruskal.. llegamos al algoritmo de Dijkstra. Con este algoritmo, que nos sirve tanto para grafos dirigidos como no dirigidos, podemos saber cuál es el camino de menor coste desde un nodo origen a todos los demás. Usa la estrategia de programación voraz, mediante la cual, vamos construyendo la solución sin tener que volver atrás en cada decisión que vamos tomando. Las aplicaciones de este algorimo son muchas más que los algoritmos predecesores. Por ejemplo, para calcular rutas en un mapa de carreteras, para conectar llamadas telefónicas mediante circuitos virtuales, enrutamiento de paquetes de red, coger varios autobuses/trenes/aviones minimizando coste o tiempo, buscar el mejor camino hasta el punto de recarga de un robot aspiradora, y un largo etcétera.. Estructura del algoritmo Se basa en la selección arbitraria de un nodo origen, en el uso de un conjunto de nodos pendientes de estudiar, un vector especial que almacena el coste de llegar a cada nodo, y un vector de predecesores que guarda el nodo anterior para llegar a cada posición. Mediante estas estructuras […]

Grafos, mapas y matrices de adyacencia

PrEDA: grafos, el algoritmo de Kruskal

Otro code-kata que vengo a traer.. Siguiendo con la serie de los relacionados con los grafos, el algoritmo de Kruskal. Es parecido al algoritmo de Prim del post anterior pero con distinto rendimiento según el tipo de grafo que tengamos. Si tenemos un grafo denso es más eficiente el algoritmo de Prim, pero si es un grafo disperso el de Kruskal. Este algoritmo busca conseguir el árbol de recubrimiento mínimo de un grafo. Es decir, cada arista que une vértices del grafo tiene un coste. Entonces, se busca el árbol de coste mínimo que conecte a todos los nodos. Este algoritmo se puede aplicar para construcción de redes con coste mínimo, por ejemplo: Internet, redes locales, eléctricas, de agua, etc.. Se utiliza la estrategia de programación voraz. Se van eligiendo las siguientes aristas de forma que no hay que volver atrás en la construcción de la solución. Se basa en el concepto de componente conexa y en el ordenamiento previo de las aristas. Vamos a ver.. Los pasos del algoritmo Se ordenan todas las aristas en orden creciente de coste. Se parte de un vector de componentes conexas que inicialmente es 1 componente por nodo. Cada vez que se añade […]

Grafos, mapas y matrices de adyacencia

PrEDA: grafos, el algoritmo de Prim

Hoy vuelvo a traer otro code-kata, siguiendo con la serie de algoritmos de programación relacionados con los grafos. Esta vez se trata del algoritmo de Prim, que sirve para calcular el árbol de recubrimiento de mínimo coste de un grafo. Es decir, tenemos un grafo que se compone de nodos, que se interconectan mediante aristas. Dichas conexiones entre nodo y nodo, tienen un coste. Entonces queremos hallar la forma de interconectar todo con el mínimo coste. Una aplicación directa de esto puede ser para una red de ordenadores, eléctrica, tuberías, carreteras, etcétera.. mediante este algoritmo puedes obtener la forma de mantener conectados todos los nodos del grafo con el mínimo coste. Este algoritmo usa la estrategia de programación voraz. Mediante ésta se elige una forma de ir creando la solución sin rectificar volviendo atrás. Pasos del algoritmo de Prim Se divide en los siguientes: Se crean dos vectores, uno con los nodos que ya están en el árbol de recubrimiento mínimo (vector usados), y los que no (vector no usados). Se elige arbitrariamente el nodo raíz, se pone en el vector de los nodos del árbol usados. El resto de nodos en el vector de no usados. Se elige el […]

Grafos, mapas y matrices de adyacencia

PrEDA: grafos y mapas, ahora guardando en una lista de adyacencia..

Continuando con el post de ayer sobre cómo crear una matriz de adyacencia a partir de un mapa aleatorio, traigo otro code-kata. Es el mismo ejercicio de ayer, pero hoy para sacar en claro cómo almacenar un grafo en una lista de adyacencia. ¿Porqué una lista o matriz de adyacencia va a ser mejor o peor? Dependerá de cada grafo. Si el grafo es muy denso, porque tiene muchas aristas entre nodo y nodo, está demostrado que es mejor usar una matriz. Pero si el grafo es poco denso es mejor usar una lista de adyacencia. Igual que en el post de ayer, el escenario consiste en un mapa aleatorio, y nos podemos mover de casilla en casilla haciendo movimientos de peón de ajedrez. El coste de hacer cada movimiento, es el número que ponga en la casilla de destino. La interpretación de estos datos del mapa puede variar según lo que necesites. Al grano Un mapa generado aleatoriamente: | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ———————————————————————- 0 | 9 3 0 8 1 6 0 7 5 6 9 7 5 9 9 7 1 | 4 5 2 […]

Grafos, mapas y matrices de adyacencia

PrEDA: grafos, generando mapas aleatorios y su matriz de adyacencia..

Vuelvo de nuevo a traer otro code-kata. Esta vez estoy tratando de sacar en claro cómo generar matrices de adyacencia para trabajar con los grafos asociados a mapas. En este escenario tenemos un mapa, que se genera aleatoriamente. En cada casilla tenemos un coste de movernos a dicha casilla. Sólo podemos movernos a la casilla adyacente, como si se tratara del movimiento de un peón de ajedrez. Así pues, si estamos en la casilla (0,0) sólo podremos movernos a la (0,1), (1,1) y la de abajo, la (1,0). Así que ese coste de ese movimiento se representa por el valor del mapa generado. Y ese coste se guarda en la matriz de adyacencia como valor de la arista.

Números

PrEDA: el algoritmo de ordenamiento Mergesort

De nuevo con otro code-kata ya estoy por aquí de nuevo. Se trata ahora de un algoritmo más sencillo que los anteriores. El Heapsort se apoya en montículos para su ordenamiento. El Quicksort hace un pivotaje algo complejo para hacer la división del vector en dos más simples. En este caso, el Mergesort, hace un ordenamiento más simple. Mergesort aplica la estrategia de divide y vencerás para hacer el ordenamiento. Con esto, tenemos que un vector de números desordenado se divide en dos. Estos dos subvectores se ordenan por separado usando Mergesort recursivamente. Y al tenerlos ordenados, se fusionan en un vector final cogiendo elementos de uno u otro vector en orden creciente.