Ordenación por insercion

DEFINICIÓN

Este método consiste en insertar un elemento en el vector es una parte ya ordenada de este vector y comizas de nuevo con los elementos restantes. por ser utilizado generalmente por los jugadores de cartas se le conoce también por el nombre de método de baraja.
A si por ejemplo, suponga que tiene la lista desordenada.

para insertar el elemento 45, habrá que insertarlo entre 43 y 65, lo que supone desplazar a la derecha todos aquellos números de valor superiora 45, es decir, saltar sobre 65 y 84.

El metido se basa en comparaciones y desplazamientos sucesivos. el algoritmo de clasificación de un vector X para N elementos se realiza con un recorrido de todo el vector y la inserción del elemento correspondiente en el lugar adecuado. el recorrido se realiza desde el segundo elemento al n-ésimo.

CARACTERÍSTICAS

En el peor de los casos, el número de comparaciones que hay que realizar es de
N*(N+1)/2-1, lo que nos deja un tiempo de ejecución en O(n2). En el mejor caso
(cuando la lista ya estaba ordenada), el número de comparaciones es N-2. Todas
ellas son falsas, con lo que no se produce ningún intercambio. El tiempo de ejecución
está en O(n).

El caso medio dependerá de cómo están inicialmente distribuidos los elementos.
Vemos que cuanto más ordenada esté inicialmente más se acerca a O(n) y cuanto
más desordenada, más se acerca a O(n2).

El peor caso es igual que en los métodos de burbuja y selección, pero el mejor caso
es lineal, algo que no ocurría en éstos, con lo que para ciertas entradas podemos
tener ahorros en tiempo de ejecución.

PSEUDOCÓDIGO

Este es el código fuente, que mejor explica el método. si buscas bien y con paciencia todo encuentras ;).

Ejemplo en c.

void insertionSort(int numbers[], int array_size)
{
int i, j, index;
for (i=1; i < index =" numbers[i];" j =" i;" style="font-weight: bold;">while ((j > 0) && (numbers[j-1] > index)){
numbers[j] = numbers[j-1];
j = j - 1;
}//fin del while
numbers[j] = index;
}//fin del for
}//fin del ejemplo

Aqui un link de un ejemplo en lenguaje .c
http://rapidshare.com/files/449013398/barajamio.c


Espero que la información aquí mostrada le sirva, y sino se entiende o cometí un error, dejen un comentario para solucionar el problema, estoy abierto a los errores y dudas ;)

NOTA: Los libros tienen la respuesta

METODO BURBUJA.... ¿Que es?

Buen día, se que este tema ya esta saturado en Internet pero les pondré solo la información mas importante de este tema.

DEFINICIÓN

Este algoritmo de ordenamiento (descendente o ascendente) se basa en el principio de comparar pares de elementos adyacentes e intercambiar entre si hasta que estén todos ordenados.

EJEMPLO

Supogamos que se desea clasificar en orden ascedente el vector o lista

50 ---- 15 --- 56 --- 14 --- 35 --- 1 ---- 12 ---- 9
A[1] -A[2] -A[3] -A[4] -A[5] -A[6] -A[7] -A[8]

Los pasos para ordenarlo son:
1.- Comparar A[1] y A[2]; si estan en orden, se mantiene como estan; en caso contrario, se intercambian entre si.
2.- A continuacion se compara los elementos 2 y 3; de nuevo se intercambian si es necesario.
3.- El proceso continua hasta que cada elemento del vector ha sido comparada con sus elementos adyacentes y se han realizado los intercambios necesarios.

En pseudocodigo lo fundamental es (el metodo):

desde i=1 hasta 7 hacer
si elemento[i] > elemento [i+1] entonces
aux=A[i]
A[i]=A[i+1]
A[i+1]=aux
fin_si
fin_desde

NOTA: las palabras en negritas son propias del lenguaje.

DATOS IMPORTANTES DEL MÉTODO BURBUJA

Este es el método más simple y antiguo para ordenar un conjunto de datos, es
también el más lento.

El algoritmo burbuja tiene dos bucles for internos que recorren el vector
comparando el elemento j-esimo-1 con el elemento con el j-esimo elemento y en
caso de que este sea mayor hace un cambio de los elementos.

Al tener dos bucles internos el comportamiento es en general O(n^2), y en las mejores
condiciones se comporta como O(n).

Este es un link de un ejemplo en codigo en lenguaje c.
http://rapidshare.com/files/448851279/metodo_burbuja.c

Estoy abierto a cualquier duda o error que pude haber causado.

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

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

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