Tarea Jueves 14/7/2011

Bibliografia:
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/grafos.pdf
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos
http://www.matediscreta.8k.com/grafos_y_arboles.htm

Grabado con:
Jing de Techsmith

Tarea Martes 12/7/11 (Arreglos, tablas y listas)

Bibliografia:
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/lindin.pdf
http://sistemas.itlp.edu.mx/tutoriales/progorientobjetos/t11.htm
http://es.wikipedia.org/wiki/Vector_%28programaci%C3%B3n%29
http://www.formatoweb.com.ar/blog/2008/03/05/pila-y-cola-en-c-c-mas-mas-con-punteros-un-par-de-ejemplos-practicos/
http://es.kioskea.net/faq/2885-las-pilas-en-lenguaje-c

Explicación Grafos y Arboles (Extra)

Video de el tema de Grafos y Arboles

Desde:http://www.youtube.com/watch?v=BmnOG37pPXQ

Tarea Viernes 8/7/2011 (Algoritmos recursivos)

Algoritmo de quicksort

View more presentations from JorgeVilla_9.

Algoritmos de Ordenamiento (Extra)

Un algoritmo de ordenamiento es aquel algoritmo que te ayuda a poner elementos de una lista en orden.
Estos son algunos de los algoritmos de ordenamiento:

Bubble sort
El ordenamiento por burbuja (Bubble Sort) es un algoritmo bastante simple. Empiesa al principio de los datos y compara los primeros dos datos para saber cual es mayor, despues repite el siguiente paso pero comparando el primer par de datos con el segundo.

Su rendimiento promedio y mas bajo es: O(n2), por lo tanto no es conveniente usarlo en cantidades largas de datos. Este método es: Iterativo

Codigo en C

while (!done)

    {

done = TRUE;

numItems--;     /* one less item left to sort after each pass */

endItem = numItems * itemSize;

 for (i = 0; i < endItem; i += itemSize)

 {

if (compareFunc(VoidPtrOffset(list, (i + itemSize)),

 VoidPtrOffset(list, i)) < 0)

  {

 Swap(VoidPtrOffset(list, i),

VoidPtrOffset(list, (i + itemSize)), temp, itemSize);

    done = FALSE;

.

Selection sort
El algoritmo de seleccion (Selection Sort) Busca el valor minimo y lo pocisiona en el primer lugar de la cadena, repite este paso dependiendo de la cantidad de valores en la cadena.Tiene eficiencia de O(n2), por lo tanto no es conveniente usarlo en cantidades largas de datos.
Este método es : Iterativo

Codigo en C

void selection_sort(int list[], int n)
{
int i, j, min;
for (i = 0; i < n - 1; i++)
{
min = i;
 for (j = i+1; j < n; j++)
{
if (list[j] < list[min])
{
min = j;
}
}
 swap(&list[i], &list[min]);
 }
 }
void printlist(int list[],int n)
 {

int i;
 for(i=0;i<n;i++)
printf("%d\t",list[i]);





Insertion sort

El algoritmo de inserción (Insertion Sort) usa elementos de la cadena uno por uno ordenandolos e insertandolos en su posicion correcta en una nueva cadena.
Este método es: Iterativo

Codigo en C
temp = malloc(itemSize);
assert(temp != NULL);
endItem = numItems * itemSize;
for (i = itemSize; i < endItem; i += itemSize)
    {
        j = i;
        memcpy(temp, VoidPtrOffset(list, i), itemSize);
        while ((j > 0) &&
            (compareFunc(temp, VoidPtrOffset(list, (j - itemSize))) < 0))
        {
            memcpy(VoidPtrOffset(list, j),
                VoidPtrOffset(list, (j - itemSize)),
                itemSize);
            j -= itemSize;
        }

Shell sort
El allgoritmo Shell inventado por Donald Shell en el 59´ mueve mas de un elemento al mismo tiempo.
Este método es: Iterativo

Codigo en C

    temp = malloc(itemSize);

    assert(temp != NULL);

  for (increment = 1;

        increment <= numItems;

        increment = (increment * 3) + 1);

endItem = numItems * itemSize;

    for (increment /= 3; increment > 0; increment /= 3)

    {

        incrementItem = increment * itemSize;

        for (i = incrementItem; i < endItem; i += itemSize)

        {

            j = i;

            memcpy(temp, VoidPtrOffset(list, i), itemSize);

            while ((j >= incrementItem) &&

                (compareFunc(temp,

                    VoidPtrOffset(list, (j - incrementItem))) < 0))

            {

                memcpy(VoidPtrOffset(list, j),

                    VoidPtrOffset(list, (j - incrementItem)),

                    itemSize);

                j = j - incrementItem;

            }   memcpy(VoidPtrOffset(list, j), temp, itemSize);

Merge sort
El ordenamiento por mezcla (Merge Sort) empieza comparando cada dos elementos y cambiándolos si el segundo debe ir antes que el primero, y después repite este paso con todas las parejas de datos de la cadena y las ordena. En su peor caso: O(n log n).
Este método es: Recursivo

pivot = (numItems - 1) / 2;

    MergeSort(list, (pivot + 1), itemSize, compareFunc);

    MergeSort(VoidPtrOffset(list, ((pivot + 1) * itemSize)),

        numItems - pivot - 1, itemSize, compareFunc);

    merged = malloc(numItems * itemSize);

    assert(merged != NULL);

pivot *=  itemSize;

    numItems *= itemSize;

    lowPtr = 0;

    highPtr = pivot + itemSize;

    mergedPtr = 0;

while ((lowPtr <= pivot) && (highPtr < numItems))

    {

        if (compareFunc(VoidPtrOffset(list, lowPtr),

            VoidPtrOffset(list, highPtr)) < 0)

        {

            memcpy(VoidPtrOffset(merged, mergedPtr),

                VoidPtrOffset(list, lowPtr),

                itemSize);

            lowPtr += itemSize;

        }

        else

        {

            memcpy(VoidPtrOffset(merged, mergedPtr),

                VoidPtrOffset(list, highPtr),

                itemSize);

            highPtr += itemSize;

        }

  mergedPtr += itemSize;

    }

    if (lowPtr > pivot)

    {

        /* finish high half */

        while(highPtr < numItems)

        {

            memcpy(VoidPtrOffset(merged, mergedPtr),

                VoidPtrOffset(list, highPtr),

                itemSize);

            mergedPtr += itemSize;

            highPtr += itemSize;

        }

    }

    else

    {

        /* finish low half */

        while(lowPtr <= pivot)

        {

            memcpy(VoidPtrOffset(merged, mergedPtr),

                VoidPtrOffset(list, lowPtr),

                itemSize);

            mergedPtr += itemSize;

            lowPtr += itemSize;

        }

    }

Heapsort
El ordenamiento de montículos (Heapsort) funciona determinando cual es el elemento mas grande o mas chico de una cadena y posicionando lo al principio o a el final de esta y continua con el resto de la lista pero de una manera muy eficiente. En su peor caso O(n logn) .

Este metodo es: Recursivo

Codigo en C

int (*compareFunc) (const void *, const void *))

{

    size_t i;

    void *temp;

    if (numItems <= 1)

    { return;

    }

    /* create temporary swap variable */

    temp = malloc(itemSize);

    assert(temp != NULL);

    /* build a heap adding one element at a time */

    for (i = numItems / 2; i > 0; i--)

    {

        SiftDown(list, i, numItems - 1, itemSize, compareFunc, temp);

    }

    SiftDown(list, 0, numItems - 1, itemSize, compareFunc, temp);

    while (numItems > 1)

    {

        Swap(list, VoidPtrOffset(list, ((numItems - 1) * itemSize)) , temp,

            itemSize);

        numItems--;

        SiftDown(list, 0, numItems - 1, itemSize, compareFunc, temp);

    }

    free(temp);

    return;

Quicksort
El ordenamiento rapido (Quick Sort) hace una particion agarra a un elemento para hacer una particion y los elementos menores a este se mueven a una posición anterior y los mayores a una posición mas adelante.
Este método es : Recursivo

Codigo en C

if (numItems > 1)

    {

        temp = malloc(itemSize);

        assert(temp != NULL);

left = 0;

        right = (numItems  - 1) * itemSize;

while(TRUE)

        {

            while (left < right)

            {

                left += itemSize;

                if (compareFunc(VoidPtrOffset(list, left), list) > 0)

                {

                    break;    

                }

            }

            if (left > right)

            {

                break;

            }

            while (left <= right)

            {

                if (compareFunc(VoidPtrOffset(list, right), list) <= 0)

                {

                    break;     

                }

 right -= itemSize;

            }

 if (left >= right)

            {

                break;

            }

            Swap(VoidPtrOffset(list, left), VoidPtrOffset(list, right), temp,

                itemSize);

        }

        Swap(list, VoidPtrOffset(list, right), temp, itemSize);

        free(temp);

QuickSort(list, right / itemSize, itemSize, compareFunc);

        QuickSort(VoidPtrOffset(list, (right + itemSize)),

            numItems - ((right / itemSize) + 1), itemSize, compareFunc);

A continuación un vídeo que demuestra los diferentes sonidos que hacen estas cadenas al ser ordenadas por cada tipo de algoritmo.

Rendimiento

Esta tabla explica cuales son los peores y mejores casos de los rendimientos de la tabla.








Ejemplo graficado:Quicksort

Aquí se demuestra que el rendimiento de nlogn es superior que a el de n^2, demostrando que n^2 es el peor caso.






Bibliografia:
http://en.wikipedia.org/wiki/Sorting_algorithm#Shell_sort
http://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento
http://cprogramminglanguage.net/selection-sort-algorithm-c-souce-code.aspx
http://www.youtube.com/watch?v=t8g-iYGHpEA
http://www.monografias.com/trabajos32/algoritmos-de-ordenamiento/algoritmos-de-ordenamiento.shtml
http://ict.udlap.mx/people/ingrid/Clases/IS211/Ordenar.html
http://www.gratisblog.com/weblogs/juand/organizacion_1_.jpg

Codigos de:
http://michael.dipperstein.com/
Animaciones de:
http://www.sorting-algorithms.com/

Lista de 21 problemas NP-Completos. (Extra)

SAT (Problema de satisfacibilidad booleana, para fórmulas en forma normal conjuntiva)

• 0-1 INTEGER PROGRAMMING (Problema de la Programación lineal entera)
• CLIQUE (Problema del clique, véase también Problema del conjunto independiente)
  • SET PACKING (Problema del empaquetamiento de conjuntos)
  • VERTEX COVER (Problema de la cobertura de vértices)
    • SET COVERING (Problema del conjunto de cobertura)
    • FEEDBACK NODE SET
    • FEEDBACK ARC SET
    • DIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano dirigido)
      • UNDIRECTED HAMILTONIAN CIRCUIT (Problema del circuito hamiltoniano no dirigido)
• 3-SAT (Problema de satisfacibilidad booleana de 3 variables por cláusula)
• CHROMATIC NUMBER (Problema de la coloración de grafos)
• CLIQUE COVER (Problema de la cobertura de cliques)
• EXACT COVER (Problema de la cobertura exacta)
• HITTING SET
• STEINER TREE
• 3-DIMENSIONAL MATCHING (Problema del matching tridimensional)
• KNAPSACK (Problema de la mochila)
• JOB SEQUENCING (Problema de las secuencias de trabajo)
• PARTITION (Problema de la partición)
• MAX-CUT (Problema del corte máximo)

(Espero que esto les ayude con su tarea)

Bibliografia:
http://es.wikipedia.org/wiki/Lista_de_21_problemas_NP-completos_de_Karp

Tarea Miercoles 6/7/11 (Fundamentos de la complejidad computacional)

PROBLEMA NP-COMPLETO.
TSP: Travelling Salesman Problem (Problema del Vendedor Viajero)
El problema del viajante es uno de los problemas mas estudiados y analisados en el campo de la logica combinatoria. Consiste en encontrar un camino hacia las ciudades empezando y acavando en la misma , pero solo puede pasar una sola ves por cada ciudad y tiene que minimisar el tiempo de viaje.

Para poder resolver el problema tenemos que usar un algoritmo que repita todas las soluciones posibles y solo asi nos daremos cuenta de cual de las opciones due la mas eficiente, viendo cual fue la distancia minima que viajo.

"Ir seleccionando parejas de puntos que seránvisitados de forma consecutiva:
– se seleccionará primero aquella pareja de puntos entre los que la distancia sea mínima;
– a continuación, se selecciona la siguiente pareja separada con una distancia mínima siempre que esta nueva elección no haga que: u se visite un punto dos veces o más (es decir, que el punto aparezca tres o más veces en las parejas de puntos seleccionadas), ou se cierre un recorrido antes de haber visitado todos los puntos.De esta forma, si hay que visitar n puntos (incluido el origen), se selecciona un conjunto de n parejas de puntos (que serán visitados de forma consecutiva) y la solución consiste en reordenar todas esas parejas de forma que constituyan un recorrido"

El problema reside en el número de posibles combinaciones que viene dado por el factorial del número de ciudades (N!) y esto hace que la solución por fuerza bruta sea impracticable para valores de N incluso moderados con los medios computacionales actualmente a nuestro alcance. Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y 77.146 años en resolver el problema para sólo 20 ciudades.

El TSP está entre los problemas denominados NP-completos, esto es, los problemas que no se pueden resolver en tiempo polinomial en función del tamaño de la entrada (en este caso el número N de ciudades que el viajante debe recorrer). Sin embargo, algunos casos concretos del problema sí han sido resueltos hasta su optimización, lo que le convierte en un excelente banco de pruebas para algoritmos de optimización que pertenezcan a la misma familia

Algoritmo:

Aplicaciones:
Las aplicaciones para este problema varían desde logística hasta turismo, para optimizar la cantidad de dinero usada en viajes comerciales de una empresa en varias ciudades, entre otras.


Analisis Asintotico

Considerando n ciudades (tamaño de la entrada = n), la dimensión del espacio de búsqueda (permutaciones) es: (n-1)!/2.
Para n=10, hay 181.440 permutaciones posibles.
Para n=12 (caso del ejemplo para Alemania) hay 19.958.400 permutaciones posibles.
Para n=20 hay 60.822.550.204.416.000 permutaciones posibles.

Como todo algoritmo de optimisacion, el TSP es fácil de analizar pero difícil de optimizar, para esto hay diferentes métodos:


Método greedy .
Idea: tratar de construir una solución seleccionando iterativa-mente elementos componentes de menor costo.
Para algunos problemas con estructura particular, la solución construida es una solución óptima.

Imagen de:https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQOhd9jANJS-fDbzJ1KDkMEKG7Wa7bIIrgRiAErESJGK_pzi8y7GPYlbAAMZQOze3zarQAPOeg0no_Kv5JN2E_ul4A6Fh2iB9XGWgCE58Tdoi-ccq7DRcSdFRexwTecbhgmpv2oxBvBIwN/s1600-h/TSP+Voraz.bmp

Método Del vecino mas cercano:
Se comienzos eligiendo un vértice inicial (j1). Una ves elegido mediremos las distancias entre este vértice y los demás, después de eso viendo todas las distancias elijemos la mas corta y lo llamamos (j2) y seguimos midiendo distancias pero ahora en base a j2 y a la mas corta la llamamos j3, así repetimos hasta terminar los todos los vértices.

Link hacia la programacion:http://www.probcomp.com/cpp-programs/TSP-11/

Bibliografia:

http://www.fing.edu.uy/inco/seminarios/papi/web2009/PresentacionesPDF/Pres_Pedemonte.pdf

http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/probdec.pdf

http://webdiis.unizar.es/asignaturas/EDA/material/viajante%20de%20comercio.pdf

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

http://www.youtube.com/watch?v=-cLsEHP0qt0
https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQOhd9jANJS-fDbzJ1KDkMEKG7Wa7bIIrgRiAErESJGK_pzi8y7GPYlbAAMZQOze3zarQAPOeg0no_Kv5JN2E_ul4A6Fh2iB9XGWgCE58Tdoi-ccq7DRcSdFRexwTecbhgmpv2oxBvBIwN/s1600-h/TSP+Voraz.bmp
http://emmanuelgs.blogspot.com/2010/03/proyecto-2-problema-del-agente-vajero.html