miércoles, 13 de julio de 2011
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
lunes, 11 de julio de 2011
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
jueves, 7 de julio de 2011
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: IterativoCodigo 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
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;
}
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/
for(i=0;i<n;i++)
printf("%d\t",list[i]);
Insertion sortEl 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
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
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/
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)
- 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)
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 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.
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/
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:http://2.bp.blogspot.com/_Yr9ozXlqA6Y/S5B2AS8SUDI/AAAAAAAAAA4/YnFFSjw1lz4/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:
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
.
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
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.
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:
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/anasin.pdf
http://es.wikipedia.org/wiki/Ordenamiento_de_burbuja
http://es.wikipedia.org/wiki/Ordenamiento_de_burbuja
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:
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:
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:
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,- |
Lenguaje Recursivo (Extra)
Un lenguaje recursivo en la informática es aquel lenguaje que acepta cualquier letra o símbolo y se puede utilizar en una maquina de Turing y acepta cualquier numero de símbolos.
Su definicion viene de la palabra recursividad la cual en la informatica significa la propiedad que tiene un programa de solicitar su propia ejecucion en su desarollo.
Propiedades de las definiciones o algoritmos recursivos:
Un requisito importante para que sea correcto un algoritmo recursivo es que no genere una secuencia infinita de llamadas así mismo. Claro que cualquier algoritmo que genere tal secuencia no termina nunca. Una función recursiva f debe definirse en términos que no impliquen a f al menos en un argumento o grupo de argumentos. Debe existir una "salida" de la secuencia de llamadas recursivas.
Si en esta salida no puede calcularse ninguna función recursiva. Cualquier caso de definición recursiva o invocación de un algoritmo recursivo tiene que reducirse a la larga a alguna manipulación de uno o casos mas simples no recursivos.
Su definicion viene de la palabra recursividad la cual en la informatica significa la propiedad que tiene un programa de solicitar su propia ejecucion en su desarollo.
Propiedades de las definiciones o algoritmos recursivos:
Un requisito importante para que sea correcto un algoritmo recursivo es que no genere una secuencia infinita de llamadas así mismo. Claro que cualquier algoritmo que genere tal secuencia no termina nunca. Una función recursiva f debe definirse en términos que no impliquen a f al menos en un argumento o grupo de argumentos. Debe existir una "salida" de la secuencia de llamadas recursivas.
Si en esta salida no puede calcularse ninguna función recursiva. Cualquier caso de definición recursiva o invocación de un algoritmo recursivo tiene que reducirse a la larga a alguna manipulación de uno o casos mas simples no recursivos.
Teoria de Conjuntos (Extra)
La teoria de conjuntos consiste en comparar 2 o mas grupos de elementos, viendo si los elementos de esos conjuntos se repiten, no estan en otros conjunto, dependiendo de lo que te pida.
Los conjuntos elemenots de los conjuntos se ponen dentro de llaves y se separan con coma porejemplo:
A={1,2,4,5}
B={1,3,5,7}
Para demostrar si un elemento esta o no en un conjunto se usan los simbolos Î Ï
Para representar el Universo de los conjuntos, es decir todos los elementos en los conjuntos se usa la U
Existen varias operaciones que se pueden realizar con los conjuntos, porejemplo
Union: La union de los elementos de ambos conjuntos.
Los conjuntos elemenots de los conjuntos se ponen dentro de llaves y se separan con coma porejemplo:
A={1,2,4,5}
B={1,3,5,7}
Para demostrar si un elemento esta o no en un conjunto se usan los simbolos Î Ï
Para representar el Universo de los conjuntos, es decir todos los elementos en los conjuntos se usa la U
Existen varias operaciones que se pueden realizar con los conjuntos, porejemplo
Union: La union de los elementos de ambos conjuntos.
Interseccion: Los elementos que se comparten entre los conjuntos.
Complemento: Todos los elementos del universo que no estan en cierto conjunto.
Diferencia: Como realizar una resta entre conjuntos, se quitan los que estan en ambos conjuntos.
Los conjuntos se pueden representar facilmente con diagramas de Venn.
AUB={1,5}
Bibliografia:
Que es una función y sus propiedades. (Extra)
En matemáticas, una función,1 aplicación o mapeo f es una relación entre un conjunto dado X (el dominio) y otro conjunto de elementos Y(el codominio) de forma que a cada elemento x del dominio le corresponde un único elemento del codominio f(x). Se denota por:
Comúnmente, el término función se utiliza cuando el codominio son valores numéricos, reales o complejos. Entonces se habla de función realo función compleja mientras que a las funciones entre conjuntos cualesquiera se las denomina aplicaciones.
Clasificaciones
Dados dos conjuntos X, Y, consideremos a todas las posibles aplicaciones (funciones) que pueden formarse entre estos dos conjuntos. Podemos diferenciar los siguientes casos:- Si a cada imagen le corresponde una única preimagen, inyectiva.
- Si la imagen de la función es igual al codominio, sobreyectiva o suprayectiva.
- Una función que sea inyectiva y sobreyectiva simultáneamente, se denomina biyectiva .
Puede haber funciones que sean biyectivas, inyectivas pero no suprayectivas, supreyectiva pero no inyectiva o que no se cumple ninguna de esas condiciones, en cuyo caso no tiene un nombre específico.
'Definiciones alternas: sea 
dada y sea b un elemento cualquiera del codominio Y. Consideremos la ecuación
dada y sea b un elemento cualquiera del codominio Y. Consideremos la ecuación
.- la función es suprayectiva o sobreyectiva si, y sólo si, la ecuación (*) siempre tiene al menos una solución.
- la función es inyectiva si, y sólo si, la ecuación (*) tiene a lo más una solución.
- la función es biyectiva cuando, y sólo cuando, es inyectiva y suprayectiva a la vez.
Bibliografia:
Suscribirse a:
Entradas (Atom)