lunes, 31 de mayo de 2010

PUNTOS EXTRAS

CICLO DE EULER


Un ciclo euleriano es aquel camino que recorre todos los vértices (nodos) de un grafo pasando una y sólo una vez por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde coinciden vértice inicial o de salida y vértice final o meta). Una definición más formal lo define como: "aquel ciclo que contiene todas las aristas de un grafo solamente una vez".




En la imagen, c= {1,2,3,4,6,3,5,4,1} es un ciclo euleriano, luego es un grafo euleriano.

Un grafo es una representación, un modelo, compuesto por un número determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo, como contrapartida un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo hamiltoniano.

Si un grafo admite un ciclo euleriano, se denomina grafo euleriano.

Determina el ciclo de Euler en la siguiente figura:

¿Para que es útil?

en la vida diaria lo usamos muy frecuentemente, cuando queremos visitar todos nuestros amigos y al final volver a la casa, o cuando estamos en un museo, queremos recorrer todas las salas y volver a salir por la misma entrada. es mas que nada para analizar todo el camino, y ver si hay algun error y mejorarlo.


PUNTOS EXTRAS

ALGORITMO DE DIJKSTRA

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.



















ALGORITMO

Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.

1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.
4. Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada, esto es:
si (Di > Da + d(a, vi)) entonces Di = Da + d(a, vi)
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
Una vez terminado al algoritmo, D estará completamente lleno.



¿ Para que es útil?

Muchas veces en la vida diaria queremos encontrar el camino mas eficiente para llegar a nuestro destino, este algoritmo es perfecto, ya que, evalúa todas las posibles rutas y escoje las mas corta para llegar al destino. Ciendo así la ruta mas eficiente. Ahora comparado con mi carrera es sumamente util, ya que hacer un programa que resuelva el problema en el menor tiempo, es el mejor. Poniendolo de otra forma, tu seras contratado, no el.

Calcular el camino mas corto de "1" a cualquier nodo









miércoles, 19 de mayo de 2010

Proyecto 5

Caminos de Hamilton

En el campo matemático de la teoría de grafos, un camino hamiltoniano en un grafo es un camino, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.
El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo.
Los caminos y ciclos hamiltonianos fueron nombrados después que William Rowan Hamilton, inventor del juego de Hamilton, lanzara un juguete que involucraba encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, pero esta solución no se generaliza a todos los grafos.



Un camino hamiltoniano es un camino que visita cada vértice exactamente una vez. Un grafo que contiene un camino hamiltoniano se denomina un ciclo hamiltoniano ó circuito hamiltoniano si es un ciclo que visita cada vértice exactamente una vez (excepto el vértice del que parte y al cual llega). Un grafo que contiene un ciclo hamiltoniano es llamado grafo hamiltoniano.
También se puede decir que los grafos hamiltonianos son cuando cumplen con :
-Circuito hamiltoniano -debe ser conexo -debe ser cerrado.

para resumir:: el camino de hamilton es un camino que recorre todas las aristas solo 1 vez, llegando al mismo punto de partida.

Ejercicio:
hay un problema famoso para este tipo de ejemplos:

en un tablero de ajedrez tratar de hacer el que caballo, recorra todas las casillas del tablero


Ninguno de los dos algoritmos garantiza una solución óptima. Sin embargo, normalmente ambos dan soluciones buenas, próximas a la óptima.


TEOREMA:

Sea K∗n un grafo dirigido completo, es decir K∗n tiene n v´ertices
y para cualquier par de v´ertices distintos x,y al menos la arista (x,y) o (y,x)
est´a en K∗n. Dicho grafo siempre contiene un camino de Hamilton.

DEMOSTRACIÓN:

Sea m≥2 con tm un camino simple que contiene las m−1 aristas: (v1,v2),(v2,v3),...,(vm−1,vm). Si m =n se ha terminado, en otro caso sea v un v´ertice que no aparece en tm.

Si (v,v1) es una arista de K∗n se puede ampliar tm añadiendo esta arista. En
otro caso(v1,v)debe ser una arista. Supongase ahora que(v,v2) esta en el grafo. Entonces se tiene la trayectoria mayor: (v1,v),(v,v2),(v2,v3),...,(vm−1,vm).Si

(v,v2) no es una arista de K∗n entonces (v2,v) debe serlo. Según continua este

proceso hay solo dos posibilidades:

1. para 1 ≤k ≤m−1 las aristas (vk,v),(v,vk+1) están en K∗n y se sustituye (vk,vk+1) por este par de aristas

2. (vm,v) esta en K∗n y se añade esta arista a tm.

En cualquier caso, obtenemos como resultado un camino simple tm+1 que incluye m+1 vértices y tiene m aristas. Este proceso puede repetirse hasta que se tenga un camino de n vértices.


BIBLIOGRAFIA:
http://es.wikipedia.org/wiki/Camino_hamiltoniano
http://docs.google.com/viewer?a=v&q=cache:JNDPlNjUeggJ:www.matap.uma.es/profesor/magalan/MatDis/material/GrafosTema5_1_MatDiscreta.pdf+caminos+de+hamilton&hl=es&gl=mx&pid=bl&srcid=ADGEESjhF5pcBVaMbrj8kWCfuPdH4CVND5lKIyifHirJg6Wi48mGQJPdZAnrvC3y5aU6zwOJstFridndiLhVsNnEZmHNiT4Dq8eyp4XnqA6tEjWcK9wj3hffTsTdMiynAwAKVx1boWKm&sig=AHIEtbTAHM1-WypcKHRi25gFE92alt3ofQ
http://docs.google.com/viewer?a=v&q=cache:7CjbQrO-eUIJ:www.fing.edu.uy/tecnoinf/cursos/mdl2/material/teo/teorico2.pdf+caminos+de+hamilton&hl=es&gl=mx&pid=bl&srcid=ADGEESgw7LRDpcJCpSyzGyrAJuGasfz72trbe0_BF6Og_cA9O-tIqipWnMUho-aEnjfg5C0ev4FPu3B2OvQJ__szzb8icdE-K4e-QOxk-idphdOji1T_hOiEzTHd9USgf8ysHBTyDU7s&sig=AHIEtbRANt1P1qlH2c9kBAV0a2ck182FtA







domingo, 9 de mayo de 2010

domingo, 25 de abril de 2010

PROYECTO 4

El proyecto 4

¿Que hice yo?
Mi trabajo consistió mas que nada en teoría, busque definiciones, ejemplos.
Al terminar de buscar la información, decidimos la información que teníamos que subir.

¿Como me salio?
Creo que la verdad todo salio todo bien, la información recabada sirvió y fue muy poco lo que tibimos que hacer molificaciones, el trabajo tiene la información necesaria.

¿En que aspectos estoy bien y en que aspectos puedo mejorar?
Soy bueno buscando información, pero no me va a servir de nada. Aun tengo mucho que aprender, necesito dominar el código, y a la retención de información.

Ayudo a los demás o me apoyo en ellos?
Ambos pero en mi opinión siento que soy mas ayudado.

¿Quien se encarga de coordinar el trabajo? ¿Que papel tomo yo?
el trabajo los coordinamos todos pero hubo, como siempre el líder, dábamos ideas de como y que iba ir primero y que iba ir después, todos estábamos de acuerdo de lo que se iba a subir y quien lo iba a exponer.


aca esta el link para verla: http://www.slideshare.net/jlvaldes/proyecto-4-3863055

domingo, 14 de marzo de 2010

Computo de Factoriales



Interación






Se refiere a la acción de repetir una serie de pasos un cierto número de veces.








RECURSION




Es una instrucción que se le da a un problema que aparentemente es infinito, para limitarlo y ser mas precisos.

COMO NO USARLO
No es necesario cuando el algoritmo se puede resolver sin simplificarlo.


COMO TRABAJARON EN GRUPO

Nosotros nos dividimos el trabajo, para que no se nos fasilitara la búsqueda, si por alguna razón alguien no podía le ayudabamos.

CONTRIBUCIÓN AL TRABAJO

Investigue definiciones, pero en si, todos terminamos ayudando a alguien.




PRESENTACIÓN

http://www.slideshare.net/jlvaldes/proyecto-3-computo-del-factorial-3432889 para observarla
http://www.megaupload.com/?d=IDKWBT0W para descargarla

MIEMBROS DE EQUIPO
Jose Luis Valdes Farias; matricula 1366674 http://algoritmoscomp.blogspot.com/
Ricardo Tovar Briones; matricula 1463439 http://acrtb7.blogspot.com/
Osvaldo Javier Hinojosa Rodriguez; matricula 1452344 http://3imedio.blogspot.com/
Raul Guerrero Valdez; matricula 1330260 http://raulelchupete.blogspot.com/






martes, 2 de marzo de 2010

viernes, 19 de febrero de 2010

Proyecto 1

FELICIDADES

acabas de ganas un viaje de una semana todo pagado a la hermosa playa de Cancun,
solo hay una condición, tienes que llevar una sola mochila
que pese menos de 15 kg.



¿que artículos vas a llevar?


Aquí tenemos el algoritmo del problema para que todo salga bien.

esta explicado que es lo que debes hacer.


ALGORITMO
1. Inicio
2. Declarar variables(ropa, artículos personales, dinero, mochila=15,tot)
3. Preguntar la cantidad de ropa a llevar
4. Asignárcelo a la variable (rop)
5. Preguntar la cantidad de artículos personales
6. Asignárcelo a la variable (art)
7. Preguntar la cantidad de dinero
8. Asignárselo ala variable (din)
9. Realizar la operación (rop+art+din)
10.Usar if (tot<=15)
11. Imprimir “listo”
12. Usar else
13. Imprimir “se pasa de equipaje”
14. 11.Fin


-----RAPTOR----

Este es el algoritmo en diagrama de flujo. Para dicho problema


la calidad no es lo suficiente para poder observar con detalle el programa,

El funcionamiento del programa es
al empezar te pedirá el nombre del articulo, como cuanto pesa.
este proceso lo va hacer hasta que la mochila alcancé su limite.
el programa termina cuando la mochila alcanza o sobrepasa la capacidad de 15 kg,
y te imprime los articulos que ingresaste.



http://raulelchupete.blogspot.com/ <--------------------------- mi compañero

lunes, 1 de febrero de 2010

Conversión de Números Binarios a Decimales

* para practicar este ejercicio es recomendable empezar con Números pequeños e ir incrementando poco a poco

Primero escribimos un numero, (este puede ser corto, para entender el concepto)

1010011, empieza ahora ejercicio:::
La regla dice:
"El valor de cada Posición es el de una potencia de base 2, Elevada A UN exponente igual a la Posición del dígito menos uno "

1*2^ 6 + 0*2^ 5 + 1*2^ 4 + 0*2^ 3 + 0*2^ 2 + 1*2^ 1 + 1*2^ 0

(Los Números en negritas, son los Números Qué queremos convertir)
(Los Números 2 que esta en cursiva Representan la base numero 2, la base nunca va a cambiar)
(EL Símbolo es "un elevado exponente")
(el numero al lado derecho del Símbolo es el exponente)
Características:::
El primer "1" esta en la Posición 7 de la cifra (contando de der. un izq.). La regla dice "elevada A UN exponente igual a la Posición del dígito uno menos", Que si esta en la Posición 7 Le vamos a restar 1 y el resultado es el numero del exponente.

ahora solo queda resolver:

1*2^6 + 0*2^5 + 1*2^4 + 0*2^3 + 0*2^2 + 1*2^1 + 1*2^0
64 + 0 + 16 + 0 + 0 + 2 + 1
= 83


1010011 = 83

para practicar expresen los sig. Numeros:
110111
111000
010101
101010
1111110

espero que allan entendido un poco,
Sino me buscan en clase para que les explique mejor.

saludos
que esten bien

domingo, 31 de enero de 2010

hola
mi nombre es osvaldo, zoe de la calse del jueves v1-v3,
esto del blog... es algo complicado, pero interesante,
me gusta que lo que vemos en clase este en internet :),, asi la puedo checar cuando yo quiera, y no apuntar nda en clase xD, ademas hacer la tarea desde la cama, es genial :D

les dejo mi correo para estar ayudandonos:::
porque la clase, se complicara si se nos olvida
algun detalle
osvaldo_javier14@hot...

que esten bien,,,
saludos..