domingo, 21 de marzo de 2010

Proyecto # 3

Proyecto # 3
Secuencia de Fibonacci

Hola compañeros y profesora elisa este es mi 3er proyecto el cual realice con mis compañeros

Gerardo Ossio
Rocio Cecilia
Gustavo Chavana

Lo que yo entendi de este proyecto es, bueno principalmente cual es en si el seguimiento que se usa para la secuencia de Fibonacci y otra es que algoritmo emplear si el recursivo o el iterativo cual es el que mejor conviene.

A continuación voy a poner una explicación pequeña de que es algoritmo recursivo y algoritmo iterativo.

Algoritmo recursivo:
Este algoritmo es cuando un problema lo podemos dividir se puede decir en varias partes para asi resolverlo.

La recursividad forma parte del repertorio para resolver problemas en Computación y es de los métodos más poderosos y usados.
Los algoritmos recursivos ofrecen soluciones estructuradas, modulares y elegantes simples.


En toda situación en la cual la respuesta pueda ser expresada como una secuencia de movimientos, pasos o transformaciones gobernadas por un conjunto de reglas.


Los números de Fibonacci se definen como:
FN = FN-1 + FN-2 para N > 2
F0 = F1 = 1
que definen la secuencia:
1,1,2,3,5,8,13,21,34,55,89,144, .....
Por ejemplo, si quisiéramos encontrar Fibonacci de 5, entonces:
Fibonacci (5) = Fibonacci (4) + Fibonacci (3)
Fibonacci (4) = Fibonacci (3) + Fibonacci (2)
Fibonacci (3) = Fibonacci (2) + Fibonacci (1)
Fibonacci (2) = Fibonacci (1) + Fibonacci (0)

Algoritmo Iterativo:
Se caracterizan por ejecutarse mediante ciclos, son muy utiles para cuando se necesita hacer una repeticion de "n" veces algun caso.

De manera iterativa el algoritmo podría ser:
estática int Fibonacci (int n)
// versión iterativa
comienza
fibo [0] ß 1
fibo [1]ß 1
para i ß1 hasta n
fibo [i] ß fibo [i-1]+ fibo [i-2]
regresa fibo [n]
termina

Ahora como saber que algoritmo usar:


Ya que la solución recursiva tiene un coste de tiempo y memoria mayor
que la iterativa. Es decir, los programas recursivos en general son menos eficientes. Podríamos utilizar los siguientes consejos:
•Los algoritmos que por naturaleza son recursivos, y donde la solución iterativa es complicada y debe manejarse explícitamente una pila para enumerar las llamadas recursivas, deben resolverse por métodos recursivos.
•Cuando haya una solución obvia por iteración al problema, debe evitarse la recursividad.


Trabajo Grupal:
Pues la verdad me gusto trabajar con ellos al principio falto que nos pusieramos de acuerdo con el trabajo y lo dejamos para ultima fecha pero en si ya cuando nos pusimos a trabajar todos ayudamos en el proyecto cuando yo necesite ayuda pues ellos me ayudaron y asi.


Contribución al Trabajo:
En si todos contribuimos con lo que pudimos todos buscamos información y con la información de cada uno pudimos realizar el proyecto.


Que se podria mejorar en un futuro:
Yo digo que la distribución del tiempo solo eso porque ya nos vimos poco apurados cuando la isimos porque ya teniamos el tiempo encima.


bueno y por ultimo aqui queda el link para la descarga de nuestra clase =)

http://www.megaupload.com/?d=GM99HPNF

viernes, 5 de marzo de 2010

Proyecto # 2

Proyecto # 2

Camino Mínimo

El problema que yo escogí del proyecto número 2 es Camino Mínimo dicho problema es la determinación del camino más corto de cierto punto de origen como pasar por los vértices y llegar a un punto fin. Existen varios métodos para solucionar este problema, yo por ejemplo escogí el algoritmo de Dijkstra creado por (Edsger Wybe Dijkstra) y yo escogí este porque es una manera rápida de resolver el problema y encontré también un muy buen video que te explica dicho problema con ejemplos que logras entender muy fácil más adelante pondré la liga.

El problema de la ruta más corta involucra un conjunto de nodos que son los puntos y los caminos entre las flechas son los arcos. Un arco puede ser dirigido o no dirigido, si es dirigido significa que solo se puede ir del nodo inicial hasta el nodo terminal como en una calle de un solo sentido. En cambio si el arco es no dirigido significa que puede ser recorrido de los dos sentidos cada arco puede tener asociada la distancia entre los nodos.




La forma más común para seleccionar la trayectoria (o ruta), se basa en la formulación de la ruta más corta. En particular a cada arco se le asigna un escalar positivo el cual se puede ver como su longitud.



Un algoritmo de trayectoria más corta, rutea cada vehículo a lo largo de la trayectoria de longitud mínima (ruta más corta) entre los nodos origen y destino. Tienes que ir checando al sumar las trayectorias para al final la solución será encontrar la trayectoria más corta.


El algoritmo de Dijkstra para ruta más corta, en términos generales, encuentran la ruta más corta entre dos nodos, inicial a y final z, de la siguiente manera:

Los nodos de la red son etiquetados con números. Al principio, todos tienen la etiqueta 00 excepto el nodo inicial a que tiene la etiqueta 0. Los arcos tienen un peso wij que representa la distancia del enlace (i, j). El algoritmo de Dijkstra re numeran los nodos, de manera que cuando el nodo z tiene una etiqueta permanente, se ha obtenido la solución final.

Ejemplo de este tipo de caso de problema con un método de decisión:

Una persona tiene que desplazarse a diario de pueblo A al pueblo H. Está estudiando cual es el trayecto más corto usando un mapa de carreteras. Las carreteras y sus distancias están representadas en la figura siguiente:



Las distancias se encuentran en kilómetros y se asocian a los arcos correspondientes Observando que para llegar del pueblo A al pueblo H existen varios caminos con recorridos distintos ¿pero cómo encontrar el camino mínimo?

En este ejemplo podemos encontrar el camino mínimo luego de realizar una pequeña cantidad de inspecciones.

Aquí al checar bien los caminos existen una ruta te da a 25 km, otra a 18 km, otra a 22km y la ruta más corta al checar es en la que las flechas están resaltadas con rosa esa suma 17 km esto quiere decir que al señor le conviene ir por esa ruta porque es la más corta.

Pero qué pasa si es un lugar más grande una ciudad algo de mayor tamaño. Esto viene siendo el problema de optimización. A continuación doy el procedimiento:

En primer lugar etiquete el nodo de partida en una etiqueta permanente igual a cero, luego etiquete cada nodo que este conectado con el nodo de partida otra vez de un solo arco con una etiqueta temporal igual a la distancia entre los nodos. Etiquete los demás nodos con una etiqueta igual a infinito, se elige el nodo con la menor etiqueta temporal y se hace permanente para los nodos que tiene etiquetes temporal y están conectados con este nodo a través de un solo arco, se deben cambiar sus etiquetas por el mínimo entre su etiqueta temporal actual y la suma de la etiqueta permanente y la longitud del arco que los une, ahora debemos repetir este procedimiento hasta el nodo terminal tengo una etiqueta permanente el nodo C tiene una etiqueta temporal de menor valor luego se hace permanente esta etiqueta y se recalculan los valores de las etiquetas de los nodos D y F para eso será el mínimo de infinito y 10 para D será el mínimo entre el infinito y 6 ahora elegimos el nodo D y se calcula el valor de la etiqueta del nodo G como el mínimo de infinito y 14 ahora elegimos el nodo F y volvemos a calcular el valor de la etiqueta temporal del modo g que será el mínimo entre 14 y 15 elegimos ahora el modo B hacemos permanente su etiqueta calculamos el valor de etiqueta temporal del nodo E que será el mínimo entre infinito y 15 ahora elegimos el nodo c hacemos etiqueta permanente y calculamos el valor de la etiqueta temporal de H como el mínimo entre infinito y 17 luego elegimos el nodo E hacemos su etiqueta permanente y recalculamos la etiqueta del nodo H finalmente se elige el nodo H como permanente el nodo H es el nodo terminal así finaliza el procedimiento y se empieza a calcular el camino mínimo.

Para encontrar el camino mínimo trabajamos desde el nodo terminal al inicial seleccionando aquellos nodos que tengas etiquetas que difieran exactamente en la longitud del arco conector en este ejemplo empezaremos desde el nodo H seguiremos hacia el nodo G, D, C y finalmente había el nodo inicial A en este camino se recorren 17 km lo que coincide con lo que tenía anteriormente.

Bueno esto puede que no sea muy fácil de entender pero todo esto es un problema que saque de un video aquí está la liga viene el problema de decisión y este, con el video estoy segura que lo comprenderán.

Mi problema es P es un problema general y muy fácil de hacer (tratable). Puede solucionarse en un tiempo polinomial determinado el cual, dado una cadena, este solo depende de la longitud de la entrada.