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