Proyecto 5

Descripción

En la Ciencia de la computación y teoría de los grafos, el Algoritmo de Edmonds-Karp es una implementación del Algoritmo de Ford-Fulkerson para la resolución del problema de flujo máximo en una red de flujo. La característica que lo distingue es que el camino de aumento más corto es usado en cada interacción, lo que garantiza que lo calculo va a terminar. En la mayoría de las implementaciones, el camino de aumento más corto es encontrado usando una búsqueda en anchura, la cual rueda un tiempo de Lo(VE2). Es decir asintóticamente más lento que algoritmo remarcagem-para-frente, el cual rueda en Lo(V3), pero es frecuentemente más rápido para utilización en grafos esparsos. El algoritmo fue publicado por primera vez por el científico ruso Dinic, en 1970, y después, de forma independiente, por Edmonds y Karp que lo publicaron en 1972. El algoritmo de Dinic incluye técnicas adicionales para reducir el tiempo para la orden de Lo(V2Y)

Problema que resuelve

Este algoritmo es idéntico al Algoritmo de Ford-Fulkerson, excepto que la orden de búsqueda cuando encuentra que el camino de aumento de flujo definido. El camino encontrado debe ser el camino más corto con capacidad disponible. Esto lo podemos encontrar por una primera búsqueda de amplitud dejando que los bordes sean la unidad de longitud. El tiempo de duración de O(|V|*|E|^2) se encuentra mostrando que cada trayectoria de aumento se puede encontrar en O(|E|)tiempo, y que a su vez al menos uno de los bordes de E se satura, la distancia desde un borde saturado a la fuente de la trayectoria de aumento debe ser más larga que la última vez que estaba saturado y la distancia es en la mayoría de V de largo.

Ejemplo

Dato una red de siete nudos, y capacidad como mostrado abajo:

En el pares f / c escritos en los arcos, f es el flujo actual, y c es la capacidad. La capacidad residual de u para v es cf(u,v) = c(u,v) − f(u,v), la capacidad total, menos la que ya está siendo usada. Si el flujo de la red de u para v es negativo, esto contribuye para capacidad residual.



Pseudocodigo

//Edmonds-Karp
//return the largest flow;flow[] will record every edge's flow
//n, the number of nodes in the graph;cap, the capacity
//O(VE^2)
#define N 100
#define inf 0x3f3f3f3f
int Edmonds_Karp(int n,int cap[][N],int source,int sink){
int flow[N][N];
int pre[N],que[N],d[N],p,q,t,i,j;
if (source==sink) return inf;
memset(flow,0,sizeof(flow));
while (true){
memset(pre,-1,sizeof(pre));
d[source]=inf;p=q=0,que[q++]=source;
while(p<0){ t="que[p++];" i="0;i
if (pre[i]<0&&(j=cap[t][i]-flow[t][i])) i="sink;i!=" i="pre[i])" j="i=">
return j;
}





Bibliografia
ww.cse.ohio-state.edu/~tamaldey/course/794/ek-algo.pdf
www.cs.umass.edu/~barring/cs611/lecture/11.pdf

Algoritmo de edmonds karp

View more presentations from ras2043.

Proyecto 4(Listas simplemente enlazadas)

El proyecto 4 trato de listas enlazadas a nosotros nos toco las listas enlazadas las listas simplemente enlazadas.

Una lista lineal simplemente enlazada es una estructura en la que el cada elemento enlaza con el siguiente. El recorrido se inicia a partir de un puntero ubicado al comienzo de la lista. El último elemento (nodo) de la lista apunta a una dirección vacía que indica el fin de la estructura.


Cabe destacar que en una lista lineal enlazada, sólo es posible acceder a los elementos sucesores pero no antecesores, además, siempre es necesario mantener un puntero a la cabeza de la lista para acceder a los demás elementos

Mi colaboración en el trabajo fue en el código donde modifique un código ya hecho para ajustarlo a un ejemplo real donde podría ser utilizado en un hotel para el registro de sus huéspedes. Creo que me hace falta mejorar en algunos temas de la clase para así poder comprender mejor lo que se está haciendo, creo que me apoyo en mis compañeros de equipo pero a la vez si ellos necesitan ayuda en algo que yo comprendo los puedo apoyar.

Links a los blogs del equipo
http://cris-algoritmoscomputacionalesfime.blogspot.com/
http://pelon-algoriitmos.blogspot.com/
http://ati5.jimdo.com/

Proyecto 3 Numeros de Catalan

Los números de Catalán forman una secuencia de números naturales que aparece en varios problemas de conteo que habitualmente son recursivos. Obtienen su nombre del matemático belga Eugene Charles Catalán (1814–1894).

#include

long*numero;
int n,i;

main()
{

printf("Ingrese el numero deseado de la serie:");
scanf("%d", &n);
numero = new long[n+1];
numero[0] = 1;

for (i = 1; i <= n; i++)
{
numero[i] = (numero[i-1]*2*(2*i-1))/(i+1);
}
printf("\nEl numero de Catalan para el numero %d es %d",n,numero[n]);

getchar();
getchar();
getchar();
}


Reporte

Recursion
La recursion es una tecnica utilizada para resolver problemas complejos sirve para se podria decir simplificarlos ya que
se dividen en partes haciendolos mas sencillos. Un Algoritmo recursivo es aquel que en una funcion se encuentra definido
en terminos de si mismo esto quiere decir que el valor que se devuelve al final es el mismo del inicio.
Un ejemplo puede ser en un programa cuando se pide un valor entero y el algoritmo como resultado debe escribir
los numeros de una forma vertical este vendria siendo el algoritmo
// ALGORITMO: escribaVerticalmenteDígitos(númeroEntero)
if (númeroEntero tiene un solo dígito)
print(númeroEntero)
else { escribaVerticalmenteDígitos(númeroEntero/10)
print(númeroEntero % 10)
}

Considero que el trabajo que hicimos como equipo fue bueno talvez lo unico que nos falto fue un poco mas de organizacion
para ponernos de acuerdo con lo que haciamos.Mi contribucion en el trabajo fue a ayudar en el pseudocodigo en el cual nos basamos
en un codigo ya hecho y despues de entender el programa modificarlo quitando lo que creiamos que no era necesario y agregando algunas cosas,
ademas de ayudar con algunos diapositivas de la presentacion.
Creo que no podria comparar mi trabajo con el de los demas ya que todos trabajamos por igual y todos participamos
en cada una de las partes del proyecto. Para el futuro talvez lo mejor seria planear con mas tiempo las cosas
la organizacion.

Links a los blogs de los miembros del equipo
http://technolifeandmore.blogspot.com
http://cris-algoritmoscomputacionalesfime.blogspot.com

Link a la presentacion
http://rapidshare.com/files/363496541/PROYECTO.pptx

1º PROYECTO DE ALGORITMOS COMPUTACIONALES

El primer proyecto fue realizado por los alumnos Rodolfo Aguirre Silva con numero de matricula 1535346 y por Cristhian Vladimir Estrada Guardado con numero de matricula 1377870.

El programa fue creado para facilitar al consumidor, la localizacion de algunos establecimientos.

Se utilizo el compilador DEVC++, para realizar el pseudocodigo.

/*Programa para buscar la direccion y el telefono de un establecimiento en monterrey*/

#include stdio.h

main()
{
int opcion,pregunta,opcion2,opcion3,opcion4,opcion5,opcion6,opcion7,respuesta,volver;
volver=1;
while (volver==1)/*ciclo para repetir programa*/
{
printf("\nIngrese el numero de la opcion a elejir:\n");
printf("********************");
printf("\n* 1.Pizzerias *\n********************\n* 2.Hoteles *\n********************\n* 3.Bares *\n********************\n* 4.Zapaterias *\n********************\n* 5.Sears *\n********************\n* 6.Liverpool *\n********************\nOpcion#:");
scanf("%d",&opcion);
while (opcion>6 || opcion<1) /*ciclo para evitar ingreso de opciones no disponibles*/
{
printf("\nEsa opcion no esta disponible\n");
printf("********************");
printf("\n* 1.Pizzerias *\n********************\n* 2.Hoteles *\n********************\n* 3.Bares *\n********************\n* 4.Zapaterias *\n********************\n* 5.Sears *\n********************\n* 6.Liverpool *\n********************\nOpcion#:");
scanf("%d",&opcion);
}
if (opcion==1)/*Opciones y impresion de cada una*/
{
printf("\nSeleccione un establecimiento:\n");
printf("********************");
printf("\n* 1.DOMINO S PIZZA *\n* 2.JOSEPHINO'S *\n* 3.LUIGIS PIZZA *\n* 4.PIZZA HUT *\n********************\nOpcion#:");
scanf("%d",&opcion2);
while (opcion2>4 || opcion2<1)/*ciclo para evitar ingreso de opciones no disponibles*/
{
printf("\nEsa opcion no esta disponible\n");
printf("\nSeleccione un establecimiento:\n");
printf("********************");
printf("\n* 1.DOMINO S PIZZA *\n* 2.JOSEPHINO'S *\n* 3.LUIGIS PIZZA *\n* 4.PIZZA HUT *\n********************\nOpcion#:");
scanf("%d",&opcion2);
}
if (opcion2==1)
{
printf("**********************************************************************");
printf("\nDOMINO S PIZZA\nUbicación:\nAVE UNIVERSIDAD 111 , MONTERREY CENTRO , C.P 64000\nTel:(81)8370-9586\n");
printf("**********************************************************************");
}
if (opcion2==2)
{
printf("**********************************************************************");
printf("\nJOSEPHINO'S Ubicación:\nPADRE MIER 276 , C.P 64720 , MONTERREY , NL\nTel:(81)8342-6790\n");
printf("**********************************************************************");
}
if (opcion2==3)
{
printf("**********************************************************************");
printf("\nLUIGIS PIZZA & MORE\nUbicación:\nBLVD ACAPULCO 3964 , VALLE DE LAS BRISAS , C.P 64790 , MONTERREY , NL\nTel:(81)8349-2623\n");
printf("**********************************************************************");
}
if (opcion2==4)
{
printf("**********************************************************************");
printf("\nPIZZA HUT\nUbicación:\nUNIVERSIDAD 139 LOC 1 , ANAHUAC , C.P 66450 , MONTERREY , NL\nTel:(81)8343-8652\n");
printf("**********************************************************************");
}
}


if (opcion==2)/*Opciones y impresion de cada una*/
{
printf("\nSeleccione un establecimiento:\n");
printf("***********************************************");
printf("\n* 1.HOTEL FIESTA *\n* 2.BEST WESTERN *\n* 3.HOTEL CITY EXPRESS MONTERREY AEROPUERTO *\n***********************************************\nOpcion#:");
scanf("%d",&opcion3);
while (opcion3>3 || opcion3<1)/*ciclo para evitar ingreso de opciones no disponibles*/
{
printf("\nEsa opcion no esta disponible\n");
printf("\nSeleccione un establecimiento:\n");
printf("***********************************************");
printf("\n* 1.HOTEL FIESTA *\n* 2.BEST WESTERN *\n* 3.HOTEL CITY EXPRESS MONTERREY AEROPUERTO *\n***********************************************\nOpcion#:");
scanf("%d",&opcion3);
}
if (opcion3==1)
{
printf("**********************************************************************");
printf("\nHOTEL FIESTA PLAZA\nUbicación:\nLAZARO CARDENAS 340 , ALAMO ORIENTE , C.P 45560 , TLAQUEPAQUE , JAL\nTel:(33)3657-8808\n");
printf("**********************************************************************");
}
if (opcion3==2)
{
printf("**********************************************************************");
printf("\nBEST WESTERN\nUbicación:\nDE LA REFORMA 308 2 , JUAREZ , C.P 06600 , CUAUHTEMOC , DF\nTel:(55)5580-5030\n");
printf("**********************************************************************");
}
if (opcion3==3)
{
printf("**********************************************************************");
printf("\nHOTEL CITY EXPRESS MONTERREY AEROPUERTO\nUbicación:\nBLVD AEROPUERTO 5028 , PARQUE INDUSTRIAL REGIOMONTANO , C.P 64540 , MONTERREY , NL\nTel:(81)8196-6100\n");
printf("**********************************************************************");
}
}


if (opcion==3)/*Opciones y impresion de cada una*/
{
printf("\nSeleccione un establecimiento:\n");
printf("*****************");
printf("\n* 1.BAR RIO *\n* 2.BAR LA ZOTA *\n* 3.BAR DE MAX *\n* 4.OPAS *\n*****************\nOpcion#:");
scanf("%d",&opcion4);
while (opcion4>4 || opcion4<1)/*ciclo para evitar ingreso de opciones no disponibles*/
{
printf("\nEsa opcion no esta disponible\n");
printf("\nSeleccione un establecimiento:\n");
printf("*****************");
printf("\n* 1.BAR RIO *\n* 2.BAR LA ZOTA *\n* 3.BAR DE MAX *\n* 4.OPAS *\n*****************\nOpcion#:");
scanf("%d",&opcion4);
}
if (opcion4==1)
{
printf("**********************************************************************");
printf("\nBAR RIO\nUbicación:\nPADRE MIER NO. 1094 , BARRIO ANTIGUO , C.P 64000 , MONTERREY , NL Tel:(81)8345-1556\n");
printf("**********************************************************************");
}
if (opcion4==2)
{
printf("**********************************************************************");
printf("\nBAR LA ZOTA\nUbicación:\nCLL CRISTOBAL COLON 606 , CENTRO , C.P 64720 Tel:(81)8372-8799\n");
printf("**********************************************************************");
}
if (opcion4==3)
{
printf("**********************************************************************");
printf("\nBAR DE MAX\nUbicación:\nCLLE JUAN ZUAZUA 952 , MONTERREY CENTRO , C.P 64000, Tel:(81)8374-1220\n");
printf("**********************************************************************");
}
if (opcion4==4)
{
printf("**********************************************************************");
printf("\nOPAS\nUbicación:\nVASCONCELOS OTE 1922 , DEL VALLE , C.P 66220 , SAN PEDRO GARZA GARCIA , NL Tel:(81)8128-8140\n");
printf("**********************************************************************");
}
}
if (opcion==4)/*Opciones y impresion de cada una*/
{
printf("\nSeleccione un establecimiento:\n");
printf("*************************************");
printf("\n* 1.CALZATRENDS S DE RL *\n* 2.PIRMA BRASIL *\n* 3.0GI REPARACION DE CALZADO GAVEU *\n* 4.ACCESORIOS PARA CALZADO *\n*************************************\nOpcion#:");
scanf("%d",&opcion5);
while (opcion5>4 || opcion5<1)/*ciclo para evitar ingreso de opciones no disponibles*/
{
printf("\nEsa opcion no esta disponible\n");
printf("\nSeleccione un establecimiento:\n");
printf("*************************************");
printf("\n* 1.CALZATRENDS S DE RL *\n* 2.PIRMA BRASIL *\n* 3.0GI REPARACION DE CALZADO GAVEU *\n* 4.ACCESORIOS PARA CALZADO *\n*************************************\nOpcion#:");
scanf("%d",&opcion5);
}
if (opcion5==1)
{
printf("**********************************************************************");
printf("\nCALZATRENDS S DE RL\nUbicación:\nCALLE ARTURO DE LA GARZA 410 , ROBLE SAN NICOLAS , C.P 66420 , SAN NICOLAS DE LOS GARZA , NL Tel:(81)8353-5611\n");
printf("**********************************************************************");
}
if (opcion5==2)
{
printf("**********************************************************************");
printf("\nPIRMA BRASIL\nUbicación:\nUNIVERSIDAD 101 L-2 , ANAHUAC , C.P 66450 , MONTERREY , NL, Tel:(81)8332-2188\n");
printf("**********************************************************************");
}
if (opcion5==3)
{
printf("**********************************************************************");
printf("\n0GI REPARACION DE CALZADO GAVEU\nbicación:\nJULIAN VILLAGRAN 305 , CENTRO , C.P 64720, Tel:(81)8344-5778\n");
printf("**********************************************************************");
}
if (opcion5==4)
{
printf("**********************************************************************");
printf("\nACCESORIOS PARA CALZADO\nUbicación:\nEMILIO CARRANZA 3533 , DEL NORTE , C.P 64500, Tel:(81)8331-1362\n");
printf("**********************************************************************");
}
}
if(opcion==5)/*Opciones y impresion de cada una*/
{
printf("\nSeleccione una ubicacion:\n");
printf("***********************");
printf("\n* 1.PADRE MIER *\n* 2.ROMULO GARZA *\n* 3.SAN AGUSTIN *\n* 4.RAMIRO E MARTINEZ *\n* 5.REGINA *\n* 6.VALLE *\n***********************\nOpcion#:");
scanf("%d",&opcion6);
while (opcion6>6 || opcion6<1)/*ciclo para evitar ingreso de opciones no disponibles*/
{
printf("\nEsa opcion no esta disponible\n");
printf("\nSeleccione una ubicacion:\n");
printf("***********************");
printf("\n* 1.PADRE MIER *\n* 2.ROMULO GARZA *\n* 3.SAN AGUSTIN *\n* 4.RAMIRO E MARTINEZ *\n* 5.REGINA *\n* 6.VALLE *\n***********************\nOpcion#:");
scanf("%d",&opcion6);
}
if (opcion6==1)
{
printf("**********************************************************************");
printf("\nSEARS\nUbicación:\nPADRE MIER 143 , CENTRO , C.P 64000 , MONTERREY , NL, Tel:(81)8318-0100\n");
printf("**********************************************************************");
}
if (opcion6==2)
{
printf("**********************************************************************");
printf("\nSEARS\nUbicación:\nAVE ROMULO GARZA 410 , DEL LAGO , C.P 05109, Tel:(81)2456-0154\n");
printf("**********************************************************************");
}
if (opcion6==3)
{
printf("**********************************************************************");
printf("\nSEARS\nUbicación:\nAVE BATALLON DE SN PATRICIO 1000 , RESIDENCIAL SAN AGUSTIN 1 SECTOR , C.P 37950, Tel:(81)8363-4893\n");
printf("**********************************************************************");
}
if (opcion6==4)
{
printf("**********************************************************************");
printf("\nSEARS\nUbicación:\nRAMIRO E MARTINEZ 1924 , RESIDENCIAL SAN AGUSTIN 1 SECTOR , C.P 64250, Tel:(81)8373-6929\n");
printf("**********************************************************************");
}
if (opcion6==5)
{
printf("**********************************************************************");
printf("\nSEARS\nUbicación:\nAVE ALFONSO REYES 3339 , REGINA , C.P 64290, Tel:(81)8331-3034\n");
printf("**********************************************************************");
}
if (opcion6==6)
{
printf("**********************************************************************");
printf("\nSEARS\nUbicación:\nAVE JOSE VASCONCELOS 402 212 , DEL VALLE , C.P 66268, Tel:(81)8356-5077\n");
printf("**********************************************************************");
}
}
if(opcion==6)/*Opciones y impresion de cada una*/
{
printf("\nSeleccione una ubicacion:\n");
printf("******************************");
printf("\n* 1.MITRAS CENTRO *\n* 2.RESIDENCIAL SAN JERONIMO *\n* 3.INSURGENTES *\n* 4.VISTA HERMOSA *\n******************************\nOpcion#:");
scanf("%d",&opcion7);
while (opcion7>4 || opcion7<1)/*ciclo para evitar ingreso de opciones no disponibles*/
{
printf("\nEsa opcion no esta disponible\n");
printf("\nSeleccione una ubicacion:\n");
printf("******************************");
printf("\n* 1.MITRAS CENTRO *\n* 2.RESIDENCIAL SAN JERONIMO *\n* 3.INSURGENTES *\n* 4.VISTA HERMOSA *\n******************************\nOpcion#:");
scanf("%d",&opcion7);
}
if (opcion7==1)
{
printf("**********************************************************************");
printf("\nLIVERPOOL MONTERREY\nUbicación:\nCLL JOSE JOSE ELEUTERIO GONZALEZ 500 , MITRAS CENTRO , C.P 64460, Tel:(81)8348-4482\n");
printf("**********************************************************************");
}
if (opcion7==2)
{
printf("**********************************************************************");
printf("\nLIVERPOOL MONTERREY\nUbicación:\nCLL JOSE JOSE ELEUTERIO GONZALEZ 550 L 232 S/N L 232 , RESIDENCIAL SAN JERONIMO , C.P 64635, Tel:(81)8348-9418\n");
printf("**********************************************************************");
}
if (opcion7==3)
{
printf("**********************************************************************");
printf("\nLIVERPOOL PROVINCIA\nUbicación:\nCLL INSURGENTES 2500 L 103 , C.P 64620, Tel:(81)8333-8114\n");
printf("**********************************************************************");
}
if (opcion7==4)
{
printf("**********************************************************************");
printf("\nSERVICIOS LIVERPOOL\nUbicación:\nCLL INSURGENTES 2500 L 103 , VISTA HERMOSA , C.P 64620, Tel:(81)8333-7934\n");
printf("**********************************************************************");
}
}
printf("\n\nDesea elejir otra opcion?\nIngrese 1 para Si, 2 para No:");
scanf("%d",&respuesta);
if(respuesta==1)volver=(1);
else if (respuesta!=1)volver=(2);
}
printf("\nPresione cualquier tecla para salir");
getch();
}
Acontinuacion se muestra una serie de imagenes, mostrando el funcionamiento del programa:

1. Seleccionar el establecimiento que deseas.












2. Elegir la tienda de preferencia.












3. Se mustran la direccion y el telefono del lugar.












4. Se te da nuevamente la opcion de poder elegir otro establecimiento, o salir del programa.






















Agradecemos el asesoraminto del Ing. Ismael Gutierrez.

Fuente de consulta:
Cairo, Osvaldo. (2006). "Fundamentos de Programacion. Piensa en C". Mexico. Pearson Educacion.