Reporte 5: Árboles binarios

Referencias:
Árboles binarios en Python
Árbol binario
Universidad Central de Venezuela -  árbol binario
Standford University - Binary tree
Animación de un árbol binario

-

Reporte 4: Lista simplemente enlazada

Reporte 3: DFS búsqueda de profundidad

Reporte 2: Problema de la mochila.

El problema de la mochila, tambien llamado knapsack problem, es un problema que modela la situación de llenar una mochila, limitada a cierta capacidad de peso y con cierta cantidad de objetos con diferentes pesos y valores cada uno. Los objetos que se pongan en la mochila deben de maximizar el valor total, sin superar el peso máximo permitido. Es uno de los 21 problemas NP-completos de Richard Karp.

El problema de la mochila: ¿Que cubos debemos elegir
 para maximizar la cantidad sin sobrepasar los 15 kg permitidos?

El problema de la mochila tiene sus puntos relevantes:

• Hay un algoritmo pseudo-polinomial (ya que ahora la salida es polinomial), con programación dinamica.
• Hay un aproximación de tiempo polinomial completo, utilizando el algoritmo anterior como subrutina
• El problema es NP-completo, por lo que se espera que ningún algoritmo puede ser rapido y correcto (en tiempo polinomial) en todos los casos.

Los datos del problema se pueden expresar en términos matemáticos. 

• Los objetos están numerados por el índice i variando de 1 a n. 
• Los números wi y pi representan el peso y el valor del número i. 
• La capacidad de la bolsa se denomina en esta formula W.

Existen muchas manera de llenar la mochila, para decidir a cada uno de ellos debemos de decir para cada objeto si lo metemos a la mochila o no, pudiendo utilizar el código binario que cuando xi = 1, metemos el objeto a la mochila, o xi = 0, se pone afuera, y para ir llenando esta mochila podemos utilizar un vector de contenido, que comprende: X = (x1, x2, ..., xn), entonces podemos expresar una función del contenido del vector.

Para un contenido dado X, el valor total de la bolsa es:

De la misma manera, la suma de los pesos de los objetos es:

El problema entonces lo podemos enunciar como un contenido de vectores X = (x1, x2, ..., xn), que tienen componentes de ceros y unos, teniendo como máximo la restricción de la función z(X).

Esto quiere decir que la suma de los pesos (o sea, la función w(X)), de los objetos que pusimos en la mochila no deben de superar la capacidad de esta, (o sea, la W).

Podemos decir que:

• z(X) es una función objetivo (como su nombre lo dice, representa el objetivo del problema, esta expresión se maximiza o se minimiza.
• Un vector X que cumple con la restricción W en la tercera formula se le nombra factible (o sea, que se pude hacer).
• Si tenemos un resultado máximo en z(X), entonces X es óptimo.

Se le pueden agregar otras restricciones según tengamos un caso, en esta liga, encontramos diferentes casos singulares.

Con esto podemos argumentar que tenemos un problema de decisión cuando para decidir a cada uno de ellos debemos de decir para cada objeto si lo metemos a la mochila o no, que cuando xi = 1, metemos el objeto a la mochila, o xi = 0, se pone afuera y podemos decir que es un problema de optimización porque podemos encontrar funciones objetivo, valores óptimos utilizando las declaraciones matemáticas.

El problema es NP-completo porque se puede representar como una toma de decisiones mediante el reemplazo del máximo, utilizando la siguiente pregunta: 

Dado el número k, existe un valor xi para el cual  

Existe un vinculo entre la version de decisión y la version de optimización del problema en que si existe un algoritmo polinomial que resuelve la versión de decisión,  por lo tanto, las dos versiones del problema son de dificultad similar.

El problema de optimización es NP-hard, su resolución es al menos tan difícil como el problema de decisión.

La prueba de que el problema es NP-completo fue presentado por Michail G. Lagoudakis, se puede encontrar en la misma liga

Algoritmos existentes:
Algoritmo Greddy o voraz: La idea es añadir un objeto prioritario mas efectivo hasta la saturación de la mochila. La complejidad de estos algoritmos se basa en la inversa de la calidad esperada.

Las dos fases del algoritmo voraz

Podemos ver las dos fases del algoritmo voraz.
      A) el ordenamiento de las cajas según un interes (en este caso en peso en $/kg)
      B) si es posible la entrar a la mochila.  




Algoritmo genético: se utiliza a menudo en problemas de optimización difíciles, como este, facil de implementar y obtener rapidamente una solución.

 

Ejemplo de la evolución de una población con
un algoritmo genetico.

Los objetos son utilizados para el algoritmo voraz, por ejemplo el genoma (0,1,0,0,0) corresponde a un cuadro de selección de 12 kg de peso 7.




Programación dinámica: El problema de la mochila tiene la propiedad que le permite utilizar el metodo de resolución de programación dinámica.
Este algoritmo tiene una complejidad en tiempo y espacio que tiene como ventajas la velocidad y no hay necesidad de ordenar las variables, pero como desventajas es que gasta mucha memoria, por lo tanto no puede ser solución para problemas grandes.

Aplicaciones en la vida real:

En la vida real, se utiliza para modelar diferentes situaciones:

• en los sistemas de apoyo a las fianzas: para encontrar el mejor equilibrio entre el capital y rendimiento financiero.
• en la carga del barco o avión: todo el equipaje debe ser llevado, sin ser sobrecargado.
• en el corte de materiales: para minimizar las caídas.
• entre otras...

Reducción:

El problema de la mochila, es un caso especial del SUBSET SUM, que viene de la reducción de 3-SAT, VERTEX COVER, en este PDF, vienen las reducciones hechas por Richard M. Karp de los 21 problemas, de la Universidad de Berkeley en los que se encuentra el problema de la mochila (knapsack). 

Referencias:

El Problema de la mochila, Universidad de Murcia. aqui.
Diapositivas de la clase: Optimización combinatoria. aqui.
Lecture: The knapsack problem. Technische Universiteit Eindhoven. aqui.
Reducibility among combinatorial problems de Richard M. Karp. aqui.
Encontré mucha información. aqui.

Este video me ayudó a entender la matemática, tiene subtítulos en español es del MIT.

Reporte 1: Algoritmo euclidiano.

El Algoritmo euclidiano es un algoritmo eficiente y popular para hallar el máximo común divisor de dos enteros.

El máximo común divisor de dos enteros (positivos y no sean 0) es el entero positivo más grande que divide a estos dos números, sin tener un residuo. Esto se utiliza, por ejemplo, para simplificar fracciones.

En la escuela nos enseñan un metodo para calcular el MCD, es descomponiendo los dos números en factores primos, esto quiere decir, sacando mitades o tercias etc...., luego marcamos cuando sean comunes divisores y estos al final se multiplican, esto es, por ejemplo:

Cuando nosotros dividimos entre a y b(números enteros positivos), nos dará como un resultados un cociente q y un residuo r, entonces como sabemos, r = a % b, por lo tanto mcd(a,b) = mcd(b,r); por ejemplo:

• Como 18 % 12 = 6, utilizando mcd(a,b) = mcd(b,r):
• mcd(18,12) = mcd(12,6)
• Como 60 % 48 = 12, utilizando mcd(a,b) = mcd(b,r):
• mcd(60,48) = mcd(48,12)

Algo importante que debemos considerar es que para obtener el MCD correcto tenemos que sacar el residuo dividiendo el mas grande entre el mas pequeño.

Considerando también que el máximo común divisor de cualquier numero y 0 es ese mismo numero, esto quiere decir:

• Como 80 % 40 = 0, utilizando mcd(a,b) = mcd(b,r):
• mcd(80,40) = mcd(40,0) = 40

Podemos ver que los resultados que obtuvimos con nuestro metodo que vimos en la escuela y el algoritmo euclidiano, en ambos obtuvimos el máximo común divisor.

Si a es un entero no negativo, b es un entero positivo y r = a mod b, entonces mcd(a,b) = mcd(b,r), decimos que, por el teorema de cociente-residuo: a = bq + r  y  0 <= r < b, este teorema es demostrado, donde a y b son los números dados, q es el cociente, r es el residuo.

El pseudocódigo de este algoritmo lo hice de esta manera:

Teniendo como entrada dos enteros no negativos, diferentes a cero y obteniendo como salida, el máximo común divisor de ellos.

El Diagrama de flujo para este algoritmo, es el siguiente:

Hay que notar se en este procedimiento utilizo las funciones XOR para intercambiar los datos dados por si en alguna ocasión se ingresa el menor y el mayor invertidos, también ver que los valores en el bucle while (mientras), se van actualizando con valores cada vez mas chicos, hasta que en algún momento b se vuelve 0, cuando en este punto mcd(a,0) por lo tanto es igual a a, que es el mcd.

Ahora mostraré como funciona por pasos este algoritmo en diferentes ocasiones.

Sean a = 48 y b = 60, entra a la condición ya que 48 < 60, pasamos a la siguiente linea numero 3 en donde con 3 XOR intercambio el orden para que a sea 60 y b sea 48, se hace lo siguiente.

• a = 48 XOR 60
• a = 12
• b = 12 XOR 60
• b = 48
• a = 12 XOR 48
• a = 60

Ahora estamos preparados para entrar el mientras, como b != 0, se hace lo siguiente.

• r = 60 % 48
• a = b
• a = 48
• b = r
• b = 12

Volvemos a entrar a el mientras y tenemos.

• r = 48 % 12
• a = b
• a = 12
• b = r
• b = 0

No entra al mientras y vamos a la linea 13 en donde regresa a a, que viene siendo el correcto MCD.

Hice un programa pequeño en C,  implementando el algoritmo:

Bibliografia:

MATEMATICAS DISCRETAS. Sexta edición.

Johnsonbaugh, Richard

PEARSON EDUCACION, México, 2005

Área: Universitarios.

PD. es el libro que utilizamos en la materia de Mates discretas, la pagina donde viene esta información es en la 205. Lo pueden conseguir en google books. en este link