domingo, 21 de marzo de 2010

Proyecto #3

Hola profesora y compañeros de clase, aqui les muestro el proyecto # 3 donde a mi equipo nos toco el tema de la serie de fibonacci

Primero les explicare lo que significa
-Recursión
Una función es recursiva cuando se llama a sí misma,la llamada a sí mismo se conoce como llamada recursiva o recurrente.
Aunque por otra parte, la recursividad también puede ser indirecta, si tenemos un procedimiento P que llama a otro Q y éste a su vez llama a P.
La recursión nos sirve para experimentar con facilidad, resolver muchos problemas de manera sencilla y demostrar propiedades acerca de los algoritmos y un montón de cosas más.

-Cuando no usar la recursión:
La solución recursiva tiene un costo y memoria mayor que la iterativa, en otras palabras, los programas recursivos en ocaciones son menos eficientes.
Para ello podemos seguir los siguientes aspectos:
Los algoritmos que por naturaleza son recursivos y donde la solución iterativa es complicada deben 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.

Ejemplo del algoritmo de la serie de fibonacci en forma recursiva:


Ejemplo del algoritmo de la serie de fibonacci en forma iterativa:


como se daran cuenta en este problema es mas facil utilizar la forma iterativa porque requiere efectuar sólo n sumas para calcular fn, lo cual significa que este método es considerablemente más rápido, ya que en forma recursiva el algoritmo es mas lento y la sucecion crece mas rapido con un mayor margen de error.


El trabajo en equipo fue bueno ya que realmente pudimos ponernos de acuerdo para ver que podiamos contribuir cada quien con el proyecto, aunque al principio nos falto mas comunicacion para poder comenzar el proyecto con mayor anterioridad.
Lo que yo hize y mis compañeros tambien fue buscar informacion sobre la recursión, ver algunos ejemplos y recordar lo que la profesora nos habia explicado en el caso de la serie de fibonacci.
Lo que podriamos mejorar en un futuro seria juntarnos con aterioridad para analizar mas detalladamente los algoritmos y asi sacar mas conclusiones y detalles del proyecto.

Mi equipo :
Claudia Lozano
Rocio
Gustavo Chavanna


Este es el link donde se encuentra nuestra presentacion:
Fibonacci

jueves, 4 de marzo de 2010

Proyecto #2

Hola compañeros de clase y profesora aqui les dejo mi proyecto #2, el problema que escogi fue el de programacion de horario (sheduling) .

Es un problema muy amplio del cual se pueden derivar distintos subproblemas según sean las restricciones que se consideren en cada caso y según sean las del caso.

La mayoría de estos problemas son problemas NP Completos.

Considere un servidor (cajero de banco, una caja de supermercado ó procesador ) para atender a una secuencia de clientes ( tareas ). Además supongamos que conocemos por adelantado cuanto tiempo se necesita para atender a cada cliente. Si nuestro objetivo es minimizar el tiempo de espera de cada cliente, entonces una estrategia voraz consiste en atender a los clientes en orden no decreciente de tiempo de atención.

Este es un algoritmo voraz:

Supongamos que hay tres clientes etiquetados C1, C2, C3 que necesitan 8, 4
y 6 unidades de tiempo para ser atendidos, el tiempo total de atención para estos clientes 8 + 4 +6 = 18 unidades. En la siguiente tabla calculamos el tiempo medio que resulta para cada una de las seis secuencias de atención.




La solución óptima para este ejemplar del problema se obtiene atendiendo a C2 primero
luego a C3 y finalmente a C1 lo que arroja un tiempo medio de atención de 10.7 . Esta es la
secuencia que escoge la estrategia voraz

Fuente: http://chavez.gerenciadeproyectos.org/algoIII/sem10/UNMSM-AG3-PRD-10.pdf

Este es un ejemplo del problema en terminos matematicos:

Codificacion de problema de optimizacion
Dada una maquina y 5 trabajos que hay que realizar en ella, en cualquier orden, se dispone del tiempo de ejecucion de cada trabajo


y del tiempo de ajuste de la maquina para pasar de ejecutar el trabajo i(fila) a ejecutar el trabajo j (columna)


Resolver el problema para determinar cual es el menor tiempo posible para completar los 5 trabajos y como hacerlo. Se considera un ciclo de trabajo cerrado, que se repite y vuelve a comenzar.


*La segunda formulacion evita subciclos de parejas de trabajos
SETS
I trabajos que se van a ejecutar / TR1 * TR5 /
ALIAS (i,j)
TABLE C (i,j) tiempo de ajuste para pasar del trabajo i al trabajo j

VARIABLES
X(i,j) paso del trabajo i al trabajo j
TT tiempo total en completar los trabajos

BINARY VARIABLE X
EQUATIONS
TIEMPO tiempo total de trabajo
ANTERIOR(i) de cada trabajo se parte una vez
POSTERIOR(j) a cada trabajo se llega una vez
PAREJAS(i,j) suma de los trabajos por parejas ;

TIEMPO ..TT=E= SUM[(i,j) $(NOT SAME AS (i,j)), C(i,j)*X(i,j)] ;
ANTERIOR(i) ..SUM[j $(NOT SAME AS (i,j)), X(i,j)] =E= 1 ;
POSTERIOR(j) ..SUM[i $(NOT SAME AS (i,j)), X(i,j)] =E= 1 ;
PAREJAS(i,j) $(ORD(i) < l="1" href="http://www.gams.com/docs/contributed/modelado_en_gams.pdf">http://www.gams.com/docs/contributed/modelado_en_gams.pdf




Aqui otro tipo del problema donde se puede apreciar en forma matematica con su grafica:





Dado un conjunto de productos J=[1....n] y un conjunto de secadores M=[1.....m] en paralelo, se debe programar y secuenciar cada producto en el conjunto de secadores M, respetando las restricciones del probleama.





1): Un secador i ∈M puede procesar solo un producto j∈J a la vez.





2):En una hora de programacion, la suma de los consumos de vapor en cada secador i en paralelo no debe exceder el recurso de vapor maximo Vmax. Esto debe cumplirse para cada hora de programacion en la totalidad de los secadores y en toda la programacion.





3):Debido a condiciones tecnologicas del proceso del secado, algunos productos, j'∈J' siendo J⊂J
no pueden ser programados en ciertos secadores i∈M





4): Se debe cumplir con las fechas de entrega estipuladas para cada producto j∈J





Se define el vector vapor para cada producto i en cada secador j como:




Esta es la grafica del problema


fuente: http://redalyc.uaemex.mx/redalyc/pdf/299/29916103.pdf