14 jul. 2011

Fibonacci recursivo - Mala idea

Algoritmos Computacionales 

Ya sabemos que hacer Fibonacci en lenguaje C esta muy repetitivo, pero ahora vengo a intentar mostrarles el porque es muy mala idea querer hacer la serie en forma recursiva.

En la siguiente imagen muestro el código para la serie de Fibonacci en forma recursiva. Lo que he agregado es un contador dentro de la función "fibo" para conocer al final cuantas veces se manda a llamar y así tener un punto de comparación con la forma iterativa.


También en la forma iterativa agregue un contador, que en realidad no se necesitaba por el hecho de ser iterativo, pero lo pongo al igual que en recursivo para conocer las veces que se repite el proceso.


Los resultados son los siguientes:


Tenemos que Fibonacci recursivo con una instancia de 40, el contador nos da como resultado 331160281, esto quiere decir que se hace tal cantidad de llamadas.

En cambio con forma iterativa:


Tenemos que solamente se repite el proceso 39 veces para una instancia de 40.

Para esta demostración tomamos la instancia como la cantidad de números de la serie de Fibonacci que se desean obtener.

En cuanto a tiempo de ejecución también nos da en la forma recursiva, un tiempo mayor, esto se podría verificar colocando un contador de tiempo.

Conclusión:
Es muy mala idea hacer la serie de Fibonacci con fines prácticos.

Análisis asintótico

Algoritmos Computacionales 

Suponiendo que las siguientes funciones indican la complejidad asintótica de algunos algoritmos para resolver un problema, se tienen que ordenar en orden del peor algoritmo al mejor, donde el mejor sería aquél que tarde menos en resolver el problema.

En la imagen se muestran las ocho funciones a ordenar:


Tenemos que:

I. La función que implica mayor comlejidad es f2, porque al elevar una variable a una potencia igual a sí misma, incrementará rápidamente.

II. Parecido al caso anterior pero con la diferencia de que en la base tenemos una constante, tenemos que f1 es la que sigue a esta lista.

III. Ahora tenemos una base a la n elevada a la siete, esto nos daría en una gráfica que se encuentra más abajo de las dos anteriores esta es f3.

IV. Ahora tenemos una logarítmica un tanto engañosa f4, que sabemos de antemano que es mayor a f6 por el hecho de tener una n multiplicando al logaritmo.

V. Si aplicamos propiedades de los logaritmos y simplificamos, tenemos que f7 es la siguiente en nuestra escala.

VI. Una variable multiplicada a una constante grande f8, es menor a la constante elevada al logaritmo.

VII. Ya casi por terminar tenemos f5, porque una raíz es de los mejores casos que se puede tener.

VIII. Por regla vimos que f6, una función logarítmica es mejor a una polinomial.

Este orden lo obtuvimos en colaboración con todos los alumnos de la clase.

Gráfica aplicando escala logarítmica

Algoritmos Computacionales 

En una de nuestras primeras sesiones vimos lo que pasa cuando tenemos diferentes funciones y como se ven graficadas.

Esta es la tabla con datos y cada columna una función diferente.


Al graficar tenemos que aplicar la escala logaritmica para lograr observar como se disparan las líneas de la función exponencial.


12 jul. 2011

Lista enlazada simple

Algoritmos Computacionales 
Tarea 4 

Vídeo incrustado hablando de listas enlazadas simples y muestra de un ejemplo desde terminal.





El vídeo original dura aproximadamente 4 minutos, por más que intente Mencoder no convertía como debería.

8 jul. 2011

Problema de las 8 reinas

Algoritmos Computacionales 
Tarea 3 

Esta tarea corresponde al tema de algoritmos recursivos. El trabajo a entregar es una presentación en diapositivas.


Problema de las 8 reinas
Ver más presentaciones de Esteban González.


Esta animación muestra todos los cambios que se hacen al resolver por recursión el problema de las ocho reinas. Lo pongo aquí porque en la presentación no se pueden ver los cambios.





Obtenido de Wikipedia.

5 jul. 2011

Problema de Clique

Algoritmos Computacionales 
Tarea 2 

En complejidad computacional, el problema de la Clique o Problema de la liga de amigos, es un problema NP-completo según la Teoría de la complejidad computacional.

Problema

EL problema de clique es el siguiente:
Dado un grafo no dirigido G, y un número natural k, determinar si G posee un clique de tamaño k.


De nuevo:
Dado un grafo no dirigido cualquiera G= (V,E), en el cual V={1,2,…,n} es el conjunto
de los vértices del grafo y E es el conjunto de aristas. Un clique es un conjunto C de
vértices donde todo par de vértices de C esta conectado con una arista en G, es decir C
es un subgrafo completo.

Este problema se puede enunciar como un problema de decisión si la pregunta que se hace es saber si existe una clique de tamaño k en el grafo.

El correspondiente problema de optimización, consiste en encontrar una clique de tamaño máximo en un grafo.

Una vez que tenemos k o más vertices que forman una clique, es trivial verificar que lo son, por eso es un problema NP.

¿Qué es un clique?

El término proviene de la palabra inglesa clique, que define a un grupo de personas que comparten intereses en común.

En esta analogía, las personas serían los vértices y los intereses en común, las aristas. Cuando todas compartan un mismo interés, forman un grafo completo, es decir, forman un clique.

Un clique en un grafo no dirigido G es un conjunto de vértices V, tal que para todo par de vértices de V, existe una arista que las conecta, donde el tamaño de un clique es el número de vértices que contiene.

Ejemplo


El grafo G:
Tiene cliques {1,2,5} y {1,4,5} de tamaño 3.
Tiene cliques {2,3} y {3,4} de tamaño 2.

Aplicaciones al mundo real

Link Farm
Una granja de enlaces es un grupo de sitios web que enlazan a todos los sitios de un grupo entre sí. Esto es una forma de spamming para los indices de un motor de búsqueda.

Los motores de búsqueda necesitan una forma para encontrar la relevancia de una página. Un método para encontrarla es examinando todos los enlaces provenientes de páginas relevantes.

En otras palabras, crear una granja de enlaces tenía el propósito de incrementar la relevancia de un sitio web para aparecer en los primeros lugares de búsqueda. Para ello se creaban páginas que enlazaran unas a otras conteniendo los enlaces hacia aquellos sitios a los que se les deseaba dar popularidad.

Segmentación de imágenes y reconocimiento de patrones
Un problema muy común en computación gráfica es el de encontrar patrones dentro de una imagen. Hay una gran cantidad de problemas que entran dentro de esta categoría desde reconocimiento de bordes hasta búsqueda de figuras geométricas.

Un problema particular que se puede resolver utilizando una variación de Clique Máxima es la de reconocimiento de segmentos o regiones. Una región en una imagen es un conjunto de pixeles que comparten alguna característica.

Cálculo de probabilidades condicionales
El algoritmo general más común en redes bayesianas es el de agrupamiento "árbol cliques". El método de agrupamiento consiste en transformar la estructura de la red para obtener un árbol, mediante agrupación de nodos. Para ello, se hace una transformación de la red a un árbol de cliques máximas.

Biología
En el desarrollo evolutivo, una de las maneras de reconocer muchos de los procesos es mirar la expresión de genes en términos de las redes de la expresión de genes, que son los grafos. Los sistemas de regulación a menudo se revela como cliques en la red de expresión.

Al estudiar las estructuras de proteínas, una de las técnicas más importantes es analizar las proteínas similares, y encontrar cliques en común para las redes estructurales basados ​​en grafos de las proteínas.


Algoritmos para resolver este problema

Algoritmo de fuerza bruta
Un ejemplo de algoritmo de fuerza bruta para encontrar una clique en un grafo consiste en listar todos los subconjuntos de vértices V y verificar para cada uno de ellos si forma una clique.

Ese algoritmo es polinómico si k es una constante, pero como no lo es para este caso, tenemos un exponencial de n^k.

Algoritmo Bron-Kerbosch
Este algoritmo consiste en arrancar con cliques de un solo elemento e intentar mezclar cliques para obtener otras más grandes, hasta que no queden más mezclas por intentarse. Dos cliques pueden ser mezcladas si cada nodo de la primera es adyacente a cada nodo de la segunda.

Es eficiente en el peor de los casos por un resultado de Moon and Moser, donde un grafo de n vértices tiene a lo sumo 3^(n/3) cliques máximos, y el tiempo de ejecución del peor caso del algoritmo Bron-Kerbosch, con una estrategia dinámica que reduce al mínimo el número de llamadas recursivas realizadas en cada paso, es O(3^(n/3)), que coincidan con este límite.

Para estos dos algoritmos es fácil saber cuál es mejor que el otro. Tenemos que:
- El mejor es Bron-Kerbosch.
- El peor es Fuerza bruta.


En el siguiente pdf encontramos la reducción SAT para el problema de clique:
Time reduction

Bibliografía:
Problema de Clique Máximo
Clasificación de problemas
Clique problem - Wikipedia
Problema de la clique - Wikipedia
Complejidad computacional
Cliques and a bit of biology

1 jul. 2011

Algoritmo de Prim

Algoritmos Computacionales 
Tarea 1 

El Algoritmo de Prim es de los más conocidos en la teoría de grafos cuyo principal objetivo consiste en encontrar el árbol de expansión mínima en un cierto grafo, que debe ser conexo, no dirigido y cuyas aristas están etiquetadas.

Pero para entender esto, veamos que son estos conceptos:

Grafo - Se define como un conjunto de objetos llamados vértices o nodos y la unión de pares de vértices por líneas llamadas aristas, que pueden ser orientadas o no. Orientadas quiere decir si se indica la dirección en que se puede mover de vértice a vértice.

Conexo - Quiere decir que todos los pares de vértices deben de estar unidos por un camino o arista.


No dirigido - Es decir, que no se indica hacia dónde se mueve.

Aristas etiquetadas - Que nos indiquen un peso, cuota o distancia entre vértices.

Sin embargo este no es el único algoritmo que existe para encontrar el árbol de expansión mínima, ya que existe otro como lo es el:

  • Algoritmo de Kruskal

Ejemplo de grafo conexo, no dirigido y con aristas etiquetadas


Cada punto negro es un vértice o nodo, y se le suele asignar una letra para hacer referencia a cada uno. También es posible encontrar grafos donde sus vértices se indican con números, esto no afecta en nada.

"Sea V el conjunto de nodos de un grafo pesado no dirigido. El algoritmo de Prim comienza cuando se asigna a un conjunto U de nodos un nodo inicial perteneciente a V, en el cual crece un árbol de expansión, arista por arista. En cada paso se localiza la arista más corta (u,v) que conecta a U con V-U, y después se agrega v, el vértice en V-U, a U. Este paso se repite hasta que V=U. El algoritmo de Prim es de O(N^2), donde |V| = N."

En otras palabras:

"Este algoritmo construye un árbol agregando aristas de manera iterativa hasta que se obtiene un árbol de expansión mínima. El algoritmo comienza con un solo vértice. Después, en cada iteración, agrega al árbol actual una arista de peso mínimo que no completa un ciclo."

Aplicaciones en la vida real

Este algoritmo puede ser utilizado en muchos campos como lo son las carreteras, vías férreas, aéreas o marítimas. También en redes eléctricas o de telefonía.

Actualmente empresas con servicios de cable e internet que necesitan expandirse lo más posible por toda una ciudad, hacen uso de estos algoritmos para seleccionar las rutas cuyos caminos sean los mas cortos y que generen un ahorro en el uso de cable como la fibra óptica.


En este caso el resultado de encontrar el camino de mínima expansión sería el siguiente:


Un ejemplo simple imaginable sería el querer viajar en auto por carretera a ciertas ciudades y buscar los caminos que generan distancias más cortas entre ciudades, en el menor tiempo posible o viajando la mínima cantidad de horas.

Ejemplo de ejecución

Obtenido de Wikipedia, al final se encuentra el enlace.
Image Descripción No visto En el grafo En el árbol
Prim Algorithm 0.svg Este es el grafo ponderado de partida. No es un árbol ya que requiere que no haya ciclos y en este grafo los hay. Los números cerca de las aristas indican el peso. Ninguna de las aristas está marcada, y el vértice D ha sido elegido arbitrariamente como el punto de partida. C, G A, B, E, F D
Prim Algorithm 1.svg El segundo vértice es el más cercano a D: A está a 5 de distancia, B a 9, E a 15 y F a 6. De estos, 5 es el valor más pequeño, así que marcamos la arista DA. C, G B, E, F A, D
Prim Algorithm 2.svg El próximo vértice a elegir es el más cercano a D o A. B está a 9 de distancia de D y a 7 de A, E está a 15, y F está a 6. 6 es el valor más pequeño, así que marcamos el vértice F y a la arista DF. C B, E, G A, D, F
Prim Algorithm 3.svg El algoritmo continua. El vértice B, que está a una distancia de 7 de A, es el siguiente marcado. En este punto la arista DB es marcada en rojo porque sus dos extremos ya están en el árbol y por lo tanto no podrá ser utilizado. null C, E, G A, D, F, B
Prim Algorithm 4.svg Aquí hay que elegir entre C, E y G. C está a 8 de distancia de B, E está a 7 de distancia de B, y G está a 11 de distancia de F. E está más cerca, entonces marcamos el vértice E y la arista EB. Otras dos aristas fueron marcadas en rojo porque ambos vértices que unen fueron agregados al árbol. null C, G A, D, F, B, E
Prim Algorithm 5.svg Sólo quedan disponibles C y G. C está a 5 de distancia de E, y G a 9 de distancia de E. Se elige C, y se marca con el arco EC. El arco BC también se marca con rojo. null G A, D, F, B, E, C
Prim Algorithm 6.svg G es el único vértice pendiente, y está más cerca de E que de F, así que se agrega EG al árbol. Todos los vértices están ya marcados, el árbol de expansión mínimo se muestra en verde. En este caso con un peso de 39. null null A, D, F, B, E, C, G

Código y ejecución



El código primero abre desde un archivo de texto los pares de vértices y la distancia entre ellos, para luego acomodar los valores en un arreglo.

Las iteraciones las logré gracias al ejemplo en C++ del blog de Ankit.

Esta es la captura de los datos de entrada, guardados en un archivo.


El grafo se ve de esta manera:


Ejecución:


El resultado obtenido como distancia mínima fue de 12.

El resultado obtenido fue:


Esto fue todo por hoy, para dudas o correcciones, dejen su comentario.

Bibliografía:
Libro: Matemáticas Discretas - Richard Johnsonbaugh (págs.398-401)
Algoritmos básicos de Grafos
Teoría de Grafos
Algoritmo de Prim

Blogs consultados:
Jonathan De La Rosa
Ankit Agrawal