Para este proyecto nuestro tema de cálculo de potencias altas lo que nosotros buscamos conseguir es calcular la potencia máxima pero en el menos tiempo posible
¿Qué es recursión?
Lo que yo entendí por recursión es cuando tienes un problema y es de gran tamaño lo divides en partes para que sea mucho más fácil resolverlo, al dividirlo de la función original llamas a una función llamada subrutina, haciendo los pasos dentro de esta funcion, un ejemplo sería el de las potencias se utilizaría el recursivo para no estar mismo número hasta que se termine el ciclo, y se recomienda a utilizarlo para cuando son demasiados y tienes que estar repitiiendo esos pasos muchas veses y el recursivo utiliza mas memoria que el iterativo .
El trabajo en equipo
Pues nos repartimos el trabajo y después lo juntamos y analizamos y relazamos los cambios necesarios para que se viera mejor ya con todo el trabajo.
Trabajo individual
Lo que yo hice fue acomodar la presentación con lo que le había tocado a cada quien y le hicieron algunos cambios convenientes , el pseudocódigo de recursión y un ejemplo de instancia , los códigos e investigar más a fondo de que se trataba el problema y las tablitas de análisis asintótico y también en buscar el lugar en donde subir la presentación.
Mi trabajo con los demás:
Pues trabajamos en equipo, debemos de organizarnos un poco más, pero pues todos trabajamos y hicimos nuestro mayor esfuerzo , no se puede comprar ya que cada quien hizo algo diferente pero al final aportamos nuestras ideas .
Que podría mejorar en el futuro
Como equipo pues tener un poco más de comunicación y organización, y también podría mejorar aprender a manejar bien lo del análisis asintótico ya que eso fue en lo que más batalle para entender ,y administrar bien el tiempo como fueron semanas de exámenes no hubo tanto tiempo para hacer el proyecto.
Ligas de los blog
Jonathan de la Rosa Gonzalez
Joel Ángel Escamilla Montemayor
Jorge Martínez Chavez
Liga para la presentación
Para ver la presentacion en linea
Presentacion-Potencias altas
Para descargar
Presentacion-Potencias altas
Para descargar
domingo, 21 de marzo de 2010
jueves, 4 de marzo de 2010
Proyecto #2 - Flujo máximo (maximum flow)
Flujo máximo (maximum flow)
Para representar el flujo que entra y que sale lo expresamos mediante las siguientes ecuaciones
La ecuación matemática para hallar x que se maximiza es:
Mi ejemplo de flujo máximo seria:
El problema es:
Una compañía de petróleo quiere trasportar galones de petróleo a los puntos de almacenamiento desde su refinería (fuente) hacia el punto 7 que es el pozo, lo que la compañía quiere es saber cuál es el flujo máximo que se puede trasportar.
Para representar y así analizar pondré esta imagen que representa toda la red, esto quiere decir el inicio (refinería) y hacia donde debe de llegar que en este caso sería al almacén 7.
En la siguiente tabla les muestro las trayectorisas posibles y en seguida cada trayectoria con sus pasos.
----------------------------------------------------------------------------------------
La primer trayectoria ,que pasa por los puntos 1-2-5-7 y la capacidad de flujo seria 3, para que se entienda entran 3 galones entonces como hay 6 se le restan 3 y sobran 3, en el segundo almacén como hay 3 se le restan 3 y quedan 0, en el 5 almacén hay 5 galones se le restan los 3 que entran y quedan 2. Y para interpretar esto está la imagen así se entenderá mejor los números que están en rojo representan los galones que quedan de la primer trayectoria.
----------------------------------------------------------------------------------------
Para la segunda trayectoria que pasa por los puntos 1-4-7, la capacidad de flujo que debe entrar seria de 2.Entonses para el almacén 1 se tienen 6 galones si entrar2 pues quedarían 4 galones, en el amasen 4 hay 2 galones y entrar 2 entonces quedan o galones .Los números que están de verde representan los galones que quedan de esta segunda trayectoria.
----------------------------------------------------------------------------------------
Para la tercera trayectoria que pasa por los puntos 1-4-3-6-7, la capacidad de flujo que debe entrar seria de 2 galones. En el almacen 1 hay 4 que fueron los que quedaron de la segunda trayectoria se le estan los 2 galones que entrar y quedarian 2 galones, en el almacen 4 hay 3 galones se le restan los 2 que entrar entonses quedaria 1 galon , para el almacen 3 hay 2 galones se le restan 2 y quedarian 0 galones ,para el almacen 6 hay 5 galones y se le restan 2 quedarian 3 .Los numeros que estan de morado representan los galones que quedan de esta tercer trayectoria.
----------------------------------------------------------------------------------------
Para la cuarta trayectoria que pasa por los puntos 1-4-3-5-7 , la capacidad de flujo que debe entrar es de 1 galón .En el almacén 1 de los galones que quedaban de la trayectoria 2 se le restan 1 galón que es el que entra y quedan 1 galón, en el almacén 4 de 1 galón que quedaba de la trayectoria 4 se le resta 1 y quedan 0 galones , del almacén 3 de los 2 galones que hay se le restan 1 que son los que entran y quedan 1 galón, del almacén 5 como quedaron dos de la trayectoria 1 se le está 1 que es lo que entra en esta trayectoria y queda 1.Los números que están de morado representan los números que quedan de esa trayectoria.
----------------------------------------------------------------------------------------
Para la quinta trayectoria que pasa por los puntos 1-4-6-7 , la capacidad de galones que debe entrar es de 1 galón. En el almacén 1 como quedo 1 galón en la trayectoria 4 y entra 1 galón pues quedan 0 galones, en el almacén 4 como hay 1 galón y entra 1 quedan o galones, en el almacén 6 como en la trayectoria 4 quedaron 3 se le resta 1 que es el de esta trayectoria y quedan 2 galones. Los números que están de amarillo representan los galones que quedan de esta trayectoria.
----------------------------------------------------------------------------------------
Para representar el flujo que entra y que sale lo expresamos mediante las siguientes ecuaciones
La ecuación matemática para hallar x que se maximiza es:
Mi ejemplo de flujo máximo seria:
El problema es:
Una compañía de petróleo quiere trasportar galones de petróleo a los puntos de almacenamiento desde su refinería (fuente) hacia el punto 7 que es el pozo, lo que la compañía quiere es saber cuál es el flujo máximo que se puede trasportar.
Para representar y así analizar pondré esta imagen que representa toda la red, esto quiere decir el inicio (refinería) y hacia donde debe de llegar que en este caso sería al almacén 7.
En la siguiente tabla les muestro las trayectorisas posibles y en seguida cada trayectoria con sus pasos.
----------------------------------------------------------------------------------------
La primer trayectoria ,que pasa por los puntos 1-2-5-7 y la capacidad de flujo seria 3, para que se entienda entran 3 galones entonces como hay 6 se le restan 3 y sobran 3, en el segundo almacén como hay 3 se le restan 3 y quedan 0, en el 5 almacén hay 5 galones se le restan los 3 que entran y quedan 2. Y para interpretar esto está la imagen así se entenderá mejor los números que están en rojo representan los galones que quedan de la primer trayectoria.
----------------------------------------------------------------------------------------
Para la segunda trayectoria que pasa por los puntos 1-4-7, la capacidad de flujo que debe entrar seria de 2.Entonses para el almacén 1 se tienen 6 galones si entrar2 pues quedarían 4 galones, en el amasen 4 hay 2 galones y entrar 2 entonces quedan o galones .Los números que están de verde representan los galones que quedan de esta segunda trayectoria.
----------------------------------------------------------------------------------------
Para la tercera trayectoria que pasa por los puntos 1-4-3-6-7, la capacidad de flujo que debe entrar seria de 2 galones. En el almacen 1 hay 4 que fueron los que quedaron de la segunda trayectoria se le estan los 2 galones que entrar y quedarian 2 galones, en el almacen 4 hay 3 galones se le restan los 2 que entrar entonses quedaria 1 galon , para el almacen 3 hay 2 galones se le restan 2 y quedarian 0 galones ,para el almacen 6 hay 5 galones y se le restan 2 quedarian 3 .Los numeros que estan de morado representan los galones que quedan de esta tercer trayectoria.
----------------------------------------------------------------------------------------
Para la cuarta trayectoria que pasa por los puntos 1-4-3-5-7 , la capacidad de flujo que debe entrar es de 1 galón .En el almacén 1 de los galones que quedaban de la trayectoria 2 se le restan 1 galón que es el que entra y quedan 1 galón, en el almacén 4 de 1 galón que quedaba de la trayectoria 4 se le resta 1 y quedan 0 galones , del almacén 3 de los 2 galones que hay se le restan 1 que son los que entran y quedan 1 galón, del almacén 5 como quedaron dos de la trayectoria 1 se le está 1 que es lo que entra en esta trayectoria y queda 1.Los números que están de morado representan los números que quedan de esa trayectoria.
----------------------------------------------------------------------------------------
Para la quinta trayectoria que pasa por los puntos 1-4-6-7 , la capacidad de galones que debe entrar es de 1 galón. En el almacén 1 como quedo 1 galón en la trayectoria 4 y entra 1 galón pues quedan 0 galones, en el almacén 4 como hay 1 galón y entra 1 quedan o galones, en el almacén 6 como en la trayectoria 4 quedaron 3 se le resta 1 que es el de esta trayectoria y quedan 2 galones. Los números que están de amarillo representan los galones que quedan de esta trayectoria.
----------------------------------------------------------------------------------------
Para la sexta trayectoria que pasa por los puntos 1-2-5-7, la capacidad de flujo que debe galones que debe entrar es de 1 galón .En el almacén 1 como quedaron 3 galones de la trayectoria 1 se le resta 1 y quedan 2 galones, en el almacén 2 como hay dos galones y entra 1 y queda 1 galón, en el almacén 5 como hay 1 galón de la trayectoria 5 se le resta el que entra y quedan 0 galones. Los números que están de celeste representan los galones que quedan de esta trayectoria.
----------------------------------------------------------------------------------------
Como se pueden dar cuenta esas son las trayectorias posibles ya que la fuente que es el inicio es el almacén 1 y hacia el almacén 2 si se puede trasportar un galón pero del almacén 2 hacia otro almacén no, y del almacén 1 que se dirige al almacén 4 no se puede ya que por así decirlo no hay espacio.
El flujo máximo seria de 10 ya que si suman los galones de cada trayectoria suman eso y ese el máximo flujo que se puede trasportar.
El problema de desión seria: Cual Cual es el camino que mas le convendria a la empresa de petroleo , es decir el camino mas corto y que trasporte la mayor cantidad de galones .
Pues como resolví el problema y analizando el camino para trasportar los galones sería el de la trayectoria primera que involucra a los caminos 1-2-5-7.Ya que es el camino mas corto y trasporta mayor cantidad de galones.
El algoritmo para el problema de decisión sería:
1. Inicio.
2. Analizar las trayectorias que resolví en el ejemplo de la compañía de petroleo.
3. Escoger la trayectoria que trasporta el máximo de galones.
4. Fin.
La complejidad de este algoritmo se haría en poco tiempo ya que solo son 12 almacenes, pero cuando la cantidad de almacenes es mucho mayor tardaríamos mucho tiempo en analizar cada camino para trasportar el máximo de galones.
Este problema es P ya que si existe método de solución, aunque dependiendo de los almacenes es el tiempo que nos vamos a tardar, pero eso no se quiere decir que no se pueda si no que cuando la cantidad de almacén es muy grande nos tardaríamos mucho tiempo , que podrían ser días, meses , años etc.
El problema no corresponde a NP-duro ya que no es NP no puede ser NP-duro.
Para el problema se debe considerar una red elegida, se tiene un inicio (fuente) y un fin (pozo), los nodos se utilizan para trasbordar y así llegar hacia donde queremos.
El algoritmo para el problema de optimización es:
1. Inicio.
2. Conocer los caminos posibles
3. Checar cuál camino tiene la capacidad que deseamos y debe ser mayor que 0.
4. Ya que checamos y elegimos el camino de mayor capacidad, elegir la rama de menor capacidad del camino que elegiste.
5. Reducuir la cantidad de capacidad de las ramas involucradas, pero aumentar la cantidad en el sentido contrario.
6. Seguir buscando caminos y se repite el mismo proceso de paso 4,5y6
7. Fin.
Este algoritmo funciona para saber el flujo máximo, pero depende los nodos que haiga es el tiempo que te tardarías, mas si se llega al resultado para saber el flujo máximo.
Puse este video ya que me fue muy útil para entender el concepto de flujo máximo
la pagina del video
http://www.youtube.com/watch?v=bu1BnW9H9V0
----------------------------------------------------------------------------------------
En las páginas en las que leí y estaba buscando información para así interpretar el concepto fue:
http://fc.uni.edu.pe/publicaciones/rev06-02/pdf/R%F3sulo%2ara
http://www.google.com.mx/#hl=es&source=hp&q=forumlar+un+problema+de+desicion+correspondiente&meta=&aq=f&oq=forumlar+un+problema+de+desicion+correspondiente%C3%A7&fp=d98d46c23d717632
http://www.virtual.unal.edu.co/cursos/sedes/manizales/4060015/Lecciones/Capitulo%20IV/problemas.htm
http://lear.inforg.uniovi.es/ioperativa/TutorialGrafos/flujomax/flujomax.htm
http://upcommons.upc.edu/revistes/bitstream/2099/4069/4/article.pdf
http://slirsredirect.search.aol.com/slirs_http/sredir?sredir=1692&query=el+problema+de+flujo+entero+m%C3%A1ximo+en+su+%C3%A7&invocationType=tb50hpcnnbie7-es-mx
">http://mit.ocw.universia.net/15.053/s02/pdf/s02-lec11.pdf
Suscribirse a:
Entradas (Atom)
