Algoritmo de prim

Check out this SlideShare Presentation:

Algoritmo de prim

View more presentations from Abraham.

Reporte del Proyecto 5 Algoritmo de Prim

Un poco acerca de esto:

El algoritmo de prim es un algoritmo perteneciente a la teoría de lo grafos para encontrar un árbol recubridor mínimo en un grafo conexo , no dirigido y cuyas aristas están etiquetadas.

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.

pero para no aburrirte tanto acerca de este, en pocas palabras lo que hace es que que ayuda a ahorrar recursos, llegando a cada una de sus aristas.

Problema que resuelve

El problema que resuelve es del camino mas corto o caminos minimos. El problema consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima.

Problema de decision:

Existe un camino mas corto que c?

Respuesta: La pregunta que se te hace es que si existe un camino mas corto, si la respues es que si, ya sea de que a o b sean mas cortos que c, y se vuelve a hacerse la misma pregunta pero ahora si hay uno de b, ya que puede haber un d o un e, cuando la respuesta sea no y haya recorrido todas las aristas, la solucion habra acabado.

Perteneciente a P

Este problem se puede resolver en timpo polinomial, por lo tanto esto se puede resolver con una maquina turing no determinsita en timpo polinomial

Algoritmo:

los pasos son:

1. Se marca un nodo cualquiera, será el nodo de partida.

2. Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente, y marcamos el otro nodo en el que incide.

3. Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.

4. El proceso termina cuando tenemos todos los nodos del grafo marcados.

Que es lo que viene haciendo esta algoritmo?

lo que viene haciedno este algoritmo es, recorrer todo el grafo dado, tocando cada una de sus aristas, utilizando el menor numero posible de reursos.

Pseudocodigo

// Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL

// Encolamos, en una cola de prioridad donde la prioridad es la distancia, todas las parejas del grafo

por cada u en V[G] hacer

distancia[u] = INFINITO

padre[u] = NULL

Añadir(cola,)

distancia[s]=0

mientras cola != 0 do

// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.

u = extraer_minimo(cola) //devuelve el minimo y lo elimina de la cola.

por cada v adyacente a 'u' hacer

si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces

padre[v] = u

distancia[v] = peso(u, v)

Actualizar(cola,)

Ejemplo paso a paso:

Siguiendo el algoritmo de Prim, tenemos:

o Elegimos, por ejemplo, el nodo 1 y lo marcamos.

o Elegimos la arista con menor valor incidente en 1, la (1, 3) = 1 la marcamos y marcamos el otro nodo en el que incide, el 3.

o Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (1, 2) = 3 la marcamos y marcamos el nodo no marcado, el 2.

o Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (2, 5) = 5 la marcamos y marcamos el nodo no marcado, el 5.

o Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 6) = 1 la marcamos y marcamos el nodo no marcado, el 6.

o Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 7) = 2 la marcamos y marcamos el nodo no marcado, el 7.

o Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 4) = 6 la marcamos y marcamos el nodo no marcado, el 4.

o FIN. Finalizamos dado que tenemos marcados los 7 nodos del grafo.

o Por tanto el árbol de mínima expansión resultante sería:

Estructura de datos:

El tipo de estrucura de datos, que este emlpea es el de cola de prioridad, ya que se van a indicando conforme a su prioridad.

Su complejidad:

Es O(n^2), porque se recorre cada nodo y se compara con cada uno de ellos, para marcarlos que ya los visito, y asi no usar mas recursos.

Aplicaciones

Este algoritmo tiene diversas aplicaciones, mas que nada es impementado, para ahorrar recursos como ya se habia mencionado, se puede usar en el cableado en poner postes de luz, cableados de redes, entre otros.

como viene funcionando esto?

imaginate, si cada poste de luz es un nodo junto tambien con las casas, y su cableado es un arista y a esta asignandole un valor, que viene siendo la distancia que hay en ellos, para esto hay que buscar la forma en ahorra cableado, para eso se emplea este algoritmo.

Bibliografia:

http://es.wikipedia.org/wiki/Algoritmo_de_Prim

http://algoritmoshade.blogspot.com/

http://www.cut-the-knot.org/Curriculum/Games/Mazes.shtml

http://www.youtube.com/results?search_query=algoritmo+de+prim&aq=0

http://www.mincel.com/java/prim.html

Reporte Proyecto 4

¿Que hice yo, Como me salio?
Mi objetivo principal, fue hacer la Explicación de aplicaciones reales, tarde un poco en buscarlos, pero ya despues de un tiempo de reflexion los encontré. Me salió bien las aplicaciones y se los mande a mis compañeros para que dieran su opinion y les parecio buena.

¿En qué aspectos estoy bien y en qué me hace falta mejorar?
Entendi el funcionamiento de las pilas, y sobre todo sus aplicaciones, el trabajo que se hizo en equipo y como nos lo distribuimos, Si acaso algo que no entendi fue el conteo por parentesis, pero ya despues de leerlo le entendi.

Ayudo a los demás o me apoyo en ellos
En mi opinión todos cooperamos por igual, trabajamos en equipo, si uno tenía duda, los demás buscaban la forma de apoyarlo, al dar o al compartir una idea, todos opinabamos la implementabamos o la mejorabamos.

¿Quién se encarga de coordinar el trabajo?
Como ya se habia mencionado antes, todos trabajamos por igual, al coordinar, nos poniamos de acuerdo para que el trabajo saliera por delante, cada uno de nosotros daba su opinion acerca de este.

¿Qué papel tomo yo?
Todos tomamos un papel importante en este proyecto, no creo que seria justo mencionar quien hizo mas o quien menos, porque entre los 4 se busco la forma de sacarlo, si acaso a mencionar sería de que cada uno dío su opiníon y se trabajaba con lo que se comentaba y se ponía a disposicion.

P4

Descargar Presentacion

Blog de mis Companeros:

http://emilio-salon4200.blogspot.com/

http://yeyohbk.wordpress.com/

http://emmanuelgs.blogspot.com/

Tercer Proyecto

14/mar/10

Hola a todos, este es mi proyecto de Algoritmos Computacionales realizado por mis compañeros Rodolfo, Christian, Erick y su servidor Abraham Silva,el proyecto que escogimos, fue el de Numeros de Catalan.

Muchos de ustedes se preguntaran para que sirven o cual es su utilidad, pero la realidad, esque este tipo de numeros los vemos muy seguidos. Nombrando algunos ejemplos seria: en las secuencias, estructuras de arboles, estructuras de figuras, combinaciones, etc...

La formula, para sacar estos numeros, es la siguiente:

Donde n, es todo cualquier numero positivo.

n

0 1

1 1

2 2

3 5

4 14

5 42

6 132

7 429

8 1430

Aqui se muestra una tabla con los primeros 8 numeros y como se realiza...

aaa y por cierto, disculpen mi dibujo feo, pero es para que me entiendan de como sacarlo.

Este metodo, es un tipo de recursion, ya que esta secuencia se va repitiendo en mucahs otras ya que el numero resultante simpre sera el mismo.

Ya teniendo la base y la idea de esto, lo que se hizo, pues fue el programa que es el siguente

#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();

}

Se tuvieron algunas complicaciones, ya que no se sabian algunas cosas de programacion, pero al fin se pudo, ya que nos apoyamos con uno...

http://es.wikipedia.org/wiki/Cálculo_de_los_números_de_Catalan

Considero, que parte de nuestro trabajo, nos falto un poco de organizacion, ya que conociendonos bien, como buenos estudiantes y mexicanos, lo dejamos todo a ultima hora y como salga, pero no, tenemos de excusa los examenesque le dedicamos horas y horas de estudio.

Pero si acaso lo que podria resaaltar fue la cooperacion de cada uno para que se pudiera realizar.

Y por cierto aqui pongo el link de las diapositivas:

http://rapidshare.com/files/363496541/PROYECTO.pptx1

Paginas hermanas:

http://algoritmoscomputacionalesras.blogspot.com/

http://cris-algoritmoscomputacionalesfime.blogspot.com/

Y ya para finalizar y no quitarles de su valioso tiempo les dejo unos links por si quieren estudiar mas acerca de los numeros de catalan:

http://es.wikipedia.org/wiki/Cálculo_de_los_números_de_Catalan/

http://gaussianos.com/los-numeros-de-catalan/

http://tiopetrus.blogia.com/2004/101101-los-numeros-de-catalan.php

Gracias y saludos...

Primer Proyecto

19/feb/10

Hola a todos, este es mi proyecto de Algoritmos Computacionales realizado por mi compañera Karla De la Torre y su servidor, Abraham Silva, el cual elegimos el buscar un número telefónico en una guía telefónica, se opto por este, ya que nos gusto la idea de desarrollarlo, además es útil y práctico.

El algoritmo que se empleo es el siguiente:
1.- Inicio
2.- Imprime menú de opciones
3.- Introduce una opción del menú
4.- Procesa el dato introducido
5.- Imprime lista de contactos
6.- Fin

Ya hecho el algoritmo se inició el código fuente, está es la parte donde imprime el menú:



Así es como se vería una vez procesado:


Para que procesara el dato requerido, utilizamos el comando switch, el cual sirve para escoger una de las opciones indicadas, desarrollándolas con la información de los contactos.


Esta es la imagen ejecutada:


Estas serian otras de las opciones que puedes seleccionar:


Y por ultimo aquí les dejamos el código fuente del programa:


#include stdio.h
#include stdlib.h


main()

{
int grupo;

printf("|-------------------------------------|\n");
printf("| Mi Agenda |\n");
printf("| Lista de Contactos |\n");
printf("|-------------------------------------|\n");
printf("|1.Amigos |\n");
printf("|2.Servicios |\n");
printf("|3.Familiares |\n");
printf("|4.Restaurantes |\n");
printf("|5.Companeros de Escuela |\n");
printf("|6.Companeros de Trabajo |\n");
printf("|7.Emergencias |\n");
printf("|8.Salir |\n");
printf("|-------------------------------------|\n\n");
printf("\n\tElige a un grupo de Contactos: ");
scanf("%d", &grupo);
system("cls");


switch(grupo)
{
case 1:{
printf("Lista de Amigos:\n\n");
{
printf("\tAngel Paredez \n");
printf("\tMiravalle Sur 1546 \n");
printf("\tMonterrey, N.L. \n");
printf("\tTel.: 1122334455\n\n");

printf("\tAdriana Garcia \n");
printf("\tResidencial Anahuac 208A \n");
printf("\tSan Nicolas de Los Garza, N.L. \n");
printf("\tTel.: 2233445566\n\n");

printf("\tDaniel Cazarez \n");
printf("\tIturbide 204\n");
printf("\tSaltillo, Coah. \n");
printf("\tTel.: 3344556677\n\n");

printf("\n\nPresiona cualquier tecla para salir \n");
}
break; }

case 2: {
printf("Servicios:\n\n");
{
printf("\tTintoreria Wash \n");
printf("\tObrera Norte 1546 \n");
printf("\tMonterrey, N.L. \n");
printf("\tTel.: 1112223334\n\n");

printf("\tRadio Taxi \n");
printf("\t8372-4370 \n\n");

printf("\tInfotur Nuevo Leon \n");
printf("\t8152-3333 \n");

printf("\n\nPresiona cualquier tecla para salir \n");
}


break; }

case 3: {
printf("Lista de Familiares\n\n");
{
printf("\tClaudia Favela \n");
printf("\tBrisas del Valle \n");
printf("\tMonclova, Coahuila \n");
printf("\tTel.: 6668887771\n\n");

printf("\tJhon Guerra \n");
printf("\tCalle Chopo s/n \n");
printf("\tMonterey, N.L. \n");
printf("\tTel.: 9998877441\n\n");

printf("\tMinerva Orozco \n");
printf("\tFco. Glz. Boca Negra 1701 Col. Teocalli\n");
printf("\tMonclova, Coahuila \n");
printf("\tTel.: 6660571866\n\n");

printf("\n\nPresiona cualquier tecla para salir \n");
}
break; }

case 4: {
printf("Lista de Restaurantes:\n\n");
{
printf("\tJack & Ray \n");
printf("\tUniversidad101-1, Col. Anahuac \n");
printf("\tSan Nicolás de los Garza N.L. \n");
printf("\tTel.: 83329585\n\n");

printf("\tCarls Jr. \n");
printf("\tUniversidad 112, Anahuac \n");
printf("\tSan Nicolás de los Garza N.L. \n");
printf("\tTel.: 78945124\n\n");

printf("\tSirloin Stockade \n");
printf("\tAv. Alfonso Reyes #110 Nte Col. Anahuac \n");
printf("\tSan Nicolás de los Garza N.L. \n");
printf("\tTel.: 83529904\n\n");

printf("\n\nPresiona cualquier tecla para salir \n");
}
break; }

case 5:{
printf("Companeros de Escuela\n\n");
{
printf("\tOsvaldo Hinojosa \n");
printf("\tUniversidad 854, Col. Anahuac \n");
printf("\tSan Nicolás de los Garza N.L. \n");
printf("\tTel.: 84584575\n\n");

printf("\tOscar Rodriguez \n");
printf("\tCalle sexta, Residencial Anahuac 208 \n");
printf("\tSan Nicolás de los Garza N.L. \n");
printf("\tTel.: 81115454\n\n");

printf("\tMelisa Esparza \n");
printf("\tHaciedenda los Morales 854, \n");
printf("\tSan Nicolás de los Garza N.L. \n");
printf("\tTel.: 81154784\n\n");

printf("\n\nPresiona cualquier tecla para salir \n");

break; }
}

case 6: {
printf("Companeos de Trabajo\n\n");
{
printf("\tKarla Mendoza \n");
printf("\tUniversidad 845, Col. Anahuac \n");
printf("\tSan Nicolás de los Garza N.L. \n");
printf("\tTel.: 81122233\n\n");

printf("\tMartha De la Cerda \n");
printf("\tProgreso 200, Centro\n");
printf("\tCaderyta N.L. \n");
printf("\tTel.: 812223345\n\n");

printf("\tUribe Benavides \n");
printf("\tTel.: 82254845\n\n");

printf("\n\nPresiona cualquier tecla para salir \n");
break; }
}

case 7: {
printf("Emergencias\n\n");
{
printf("\tCruz Roja \n");
printf("\tTel.: 065\n\n");

printf("\tHospital Metropolitano \n");
printf("\tTel.: 8305-5900 y 8305-5904\n\n");

printf("\tCuerpo de Bomberos \n");
printf("\tTel.: 8342-0053 al 55\n\n");

printf("\tCentro Estatal de Emergencias \n");
printf("\tTel.: 066 o 01-800-712-4580\n\n");

printf("\tProteccio Civil\n");
printf("\tTel.: 8343-1116 y 8343-9530\n\n");

printf("\n\nPresiona cualquier tecla para salir \n");
break;}
}

case 8:{
exit (0); }
default: {
printf("Esa opcion no existe");
break; }


}
getch();
return 0;
}


Por nuestra parte es todo, gracias.

Aaaah... Y por cierto, aqui les dejo unos videos acerca de como lo hicimos:

SOs(ayuda) en SO (Sistema Operativo)

Muchos de nosotros simpre buscamos tener lo mejor, ya sea en ropa, accesorios, tecnologias, computadoras, pero una de las cosas mas importantes y las que nos llama a algunos la atencion, es el SO (Sistema Operativo), que en este buscamos que sea elegante, facil, con buena interface, que lo podamos utilizar bien y facilmente.
Para ello les pongo los siguientes sistemas operativos que mas conocemos y podemos emplear que podemos emplear:


-WINDOWS: Es el que todos por general conocemos y lo tomamos que es facil, sencillo y con buenas interfaces, pero lo malo de este es que es costos (al rededor de $199dls.) y tiene muchas fallas, ya sean internas, problemas graficos, administrativas entre otras.


-MAC: Este sistema es muy elegante, facil de usar, ideal para aquellas personas que les gusta editar(videos, caciones, fotos, entre muchas otras) uno de los sistemas operativos mas potentes y por lo mismo que es muy caro ronda alrededor de unos $599dls y no cualquier computadora lo pude emplear.



-Linux alomejor emos oido hablar de este SO y de que tiene muchas distribuciones y alo que se refiere esto es de que tiene varios sistemas operativos hechos idealemtne para cada persona de como le guste trabajar, pero el mas conocido es...:
- Ubuntu este es la distribucion mas popular de linux, muy facil de usar, con muchas interfaces, ideal para las personas que les gusta la programacion. Algo que muchos no saben de este sistema es de que esta en "CODIGO ABIERTO" que quiere decir esto, pues bien quiere decir que cualquier persona puede meterse a su codigo y modificarlo de tal forma que lo hagas como tu quieras. Y resumido en todo sobre este SO esque es Libre,osea no tiene costo alguno, como los 2 anteriores asi que no pagarias nada para obtenerlo, lo puedes descargar de la web oficial o pedir un Cd sin costo alguno


Bueno, espero que eseta informacion les aya sido de mucha utilidad ya que muchos no sabemos que SO podemos utilizar.