miércoles, 13 de julio de 2011

Tarea Jueves 14/7/2011

Unable to display content. Adobe Flash is required.

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
Publicado por en 1 comentario:

lunes, 11 de julio de 2011

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

Unable to display content. Adobe Flash is required.


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
Publicado por en 1 comentario:

Explicación Grafos y Arboles (Extra)

Video de el tema de Grafos y Arboles

Desde:http://www.youtube.com/watch?v=BmnOG37pPXQ
Publicado por en 1 comentario:

jueves, 7 de julio de 2011

Tarea Viernes 8/7/2011 (Algoritmos recursivos)

Algoritmo de quicksort
View more presentations from JorgeVilla_9.
Publicado por en 1 comentario:

miércoles, 6 de julio de 2011

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/
Publicado por en No hay comentarios:

domingo, 3 de julio de 2011

Lista de 21 problemas NP-Completos. (Extra)

SAT (Problema de satisfacibilidad booleana, para fórmulas en forma normal conjuntiva)
(Espero que esto les ayude con su tarea)

Publicado por en 1 comentario:

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
Publicado por en 3 comentarios:

Tutorial Operaciones Binarias (Extra)

como visto en http://www.youtube.com/watch?v=Bcs9gEc8kbo&feature=player_embedded
Publicado por en 1 comentario:
Etiquetas:

jueves, 30 de junio de 2011

Algoritmo de Dios (Extra)



Algoritmos de Dios

Consiste básicamente en resolver un cubo de Rubik en mas 0 menos 20 movidas.

El cubo de Rubik usa un algoritmo que se separa en varias partes dependiendo de que lado se valla a resolver; existen muchos tipos de variaciones para demostrar cual es el algoritmo de Dios, pero muchos de estos ocupan mas de 40 movimientos.

El algoritmo tiene que ser mas simple que 40 movidas, a el método de resolución mas rápido se le llama el algoritmo de Dios.


Para poder resolver el algoritmo Google dono una computadora que estuviera processando el algoritmo el tiempo nesesario, y esto fue 35 años.

Se dice que este algoritmo esta dentro de la categoria de los mas dificiles de calcular.

Esta dentro de la categoria NP-Difficil no determinista.

Bibliografia:
http://en.wikipedia.org/wiki/God%27s_algorithm
http://www.cube20.org/
http://www.neoteo.com/descubierto-el-algoritmo-de-dios-para-el-cubo-de
.
Publicado por en 1 comentario:

Tarea Viernes 1/07/11 ( Algoritmo Simple)

Algoritmo Simple: 
Ordenacion por metodo de burbuja

El metodo burbuja consiste en ordenar de manera secuencial una cadena de caracteres al ir remplazando los caracteres dependiendo de su valor en la cadena.

Este algoritmo es muy sencillo por lo cual lo considere para mi ejemplo:
Diagrama



















Programa
void ordenamientoBurbuja(int v[], int util_v) { int temp, i, j; for (i = 0; i < util_v -1 ; i++) { for (j = i + 1; j < util_v ; j++) { if (v[i] > v[j]) { temp = v[i]; v[i] = v[j]; v[j] = temp; } } }}
Como visto en :
http://es.wikipedia.org/wiki/Ordenamiento_de_burbuja 






Rendimiento del Algoritmo

Rendimiento del algoritmo
Para poder ordenar satisfactoriamente tenemos que usar el mismo numero de comparaciones.

Esto es, el número de comparaciones c(n) no depende del orden de los términos, si no del número de términos.

Por lo tanto la cota ajustada asintótica del numero de comparaciones pertenece al orden de n cuadrado.

El numero de intercambios i(n), que hay que realizar depende del orden de los términos y podemos diferencia, el caso mejor, si el vector esta previamente ordenado, y el caso peor, si el vector esta ordenado en orden inverso.
Por lo que no se puede determinar una cota ajustada asintótica del número de intercambios, dado que este dependerá del orden del vector en cuestión.
[editar]Rendimiento en el caso desfavorable
Artículo principal: Cota superior asintótica

Si pasamos al algoritmo un vector ordenado en orden inverso realizara un numero de comparaciones:

Como ya hemos dicho anteriormente, y tendrá que realizar un número igual de intercambios entre los términos del vector, dado que en cada comparación los términos estarán desordenados, y se realizara el intercambio.
Por lo tanto en el caso más desfavorable tanto el numero de comparaciones como el de intercambios coinciden:

El numero de comparaciones o de intercambios en el caso más desfavorable pertenece al orden de n cuadrado.

Rendimiento en casos óptimos
Artículo principal: Cota inferior asintótica
En el caso optimo, el más favorable, es la ordenación que un vector ya ordenado, en este caso el número de comparaciones será el mismo que en cualquier otro caso:

La cota inferior asintótica del número de comparaciones pertenece al orden de n cuadrado, como en los demás casos, pero en todas las comparaciones el orden es el correcto y por tanto no se realiza ningún intercambio:

Por lo tanto el coste de intercambios no depende de n, y es constante:
El ordenamiento de burbuja tiene una complejidad Ω(n²) igual que ordenamiento por selección. Cuando una lista ya está ordenada, a diferencia del ordenamiento por inserción que pasará por la lista una vez y encontrará que no hay necesidad de intercambiar las posiciones de los elementos, el método de ordenación por burbuja está forzado a pasar por dichas comparaciones, lo que hace que su complejidad sea cuadrática en el mejor de los casos. Esto lo cataloga como el algoritmo mas ineficiente que existe, aunque para muchos programadores sea el más sencillo de implementar.

Bibliografia:

Publicado por en 1 comentario:

Complejidad Asintotica (Eficiencia de Algoritmos) (Extra)

Complejidad Asintótica
Para calcular la complejidad asintotica de un algoritmo es necesario denotar las instancias (entrada y salida de datos) con una variable n, Calculamos el numero de operaciones necesarias para efectuar el algoritmo usando los valores de n. Podemos gráfica todos los valores de n para crear una gráfica. 
Después de eso podemos buscar cual es el valor asintotico de la gráfica.

En clase vimos un ejemplo de como ordenar por complejidad los asintotas de un algoritmo.
Teníamos esta tabla:
f1 = 7n
f5 =(raíz)n
f2 = nn
f6 = log7n
f3 = n7
f7 = 7log7n
f4 = n log7n
f8 = 700n

Después de hacer una prueba calculando la n con valores simples del 1 al 15 coincidí que:
y al gráficar:

Entonces  descubrí el orden de la eficiencia de el algoritmo, y dado lo visto en clase el orden es el siguiente:
F2
F1
F3
F4
F7-F8
F5
F6


Bibliografia:

Publicado por en No hay comentarios:

Trabajo en Clase (Grafica Logaritmo)

Publicado por en No hay comentarios:

miércoles, 29 de junio de 2011

Maquina de Turing Resta (Extra)

Como visto en: http://w0oh0o.blogspot.com/2010/02/problema-31-maquina-de-turing-que-resta.html

PЄΚ
σЄ∑
ℓ(Ρ,σ)
S
►
s,►,->
S
0
s,0,->
S
1
q,1,->
S
I_I
r,|_|,<-
Q
0
q,0,->
Q
1
q,1,->
Q
I_L
t,|_|,<-
T
0
t,-1,-
R
0
r,1,<-
r
1
r,0,-




Publicado por en No hay comentarios:
Suscribirse a: Entradas (Atom)