Download Enunciado en pdf - Emmanuel Briand
Document related concepts
Transcript
IMD-IS 2011–2012. Sesión de laboratorio 3. La hoja de SAGE que corresponde a la práctica puede obtenerse de: http: // personal. us. es/ ebriand/ practica3. sws En esta práctica ilustramos, con unos ejemplos, la noción de complejidad de algoritmos (se estudiará más en detalle en la asignatura “Análisis y Diseño de Algoritmos” de segundo curso). Utilizaremos cómo ejemplos unos algoritmos de ordenación. Estos algoritmos toman, en entrada, una lista, y la devuelven ordenada. Por ejemplo: L=[5,3,4,2,1] insertionsort(L) L; [1,2,3,4,5] Un algoritmo de ordenación La función siguiente, que vamos a explicar más abajo, ordena una lista de números. def insertionsort(L): """ Devuelve una lista con los mismo términos que L, pero en orden creciente. """ longitud = len(L) ## la longitud de la lista R=copy(L) if longitud > 1: ## una lista de longitud 0 o 1 ya es ordenada, ## no hay que hacer nada. for k in [1,..,longitud-1]: ## paso numero k: clave=R[k] j=k ## j será la posición de la clave. ## Es decir: clave=R[j] a cada instante. while j > 0 and R[j] < R[j-1]: (R[j],R[j-1])=(R[j-1],R[j]) ## la clave y su predecesor R[j-1] ## intercambian sus posiciones. j=j-1 return(R) La idea del algoritmo es la siguiente: Para ordenar una lista de longitud n (con índices del 0 al n − 1) hay n − 1 pasos. Al final del paso k − 1, los k primeros elementos están ordenados. En el paso k intervienen solamente los k + 1 primeros elementos de la lista. • El elemento en posición k (si se empieza a contar las posiciones a partir de 0), lo llamamos clave del paso k. La clave se desplaza tan lejos hacia la izquierda como posible, hasta estar bloqueado por un elemento más pequeño. 2 • Cada paso de la clave hacia la izquierda se hace intercambiando su posición con la de un número mayor. Aquí esta un ejemplo. Ordenamos [5, 3, 4, 2, 1]. Estado inicial de la lista Paso 1 Paso 2 Paso 3 Paso 4 5 3421 53 421 La clave es 3. 35 421 Como 5 > 3, intercambiaron posiciones 35 421 354 21 Como la clave no puede ir más a la izquierda, se acaba el paso 1 La clave es 4. 345 21 Como 5 > 4, intercambiaron posiciones 345 21 Como 3 ≤ 4, se acaba el paso 2. 3452 1 La clave es 2. 3425 1 Como 5 > 2, intercambiaron posiciones 3245 1 Como 4 > 2, intercambiaron posiciones 2345 1 Como 3 > 2, intercambiaron posiciones 2345 1 Como la clave no puede ir más a la izquierda, se acaba el paso 3 23451 La clave es 1 2 3 4 15 Como 5 > 1, intercambiaron posiciones 23145 Como 4 > 1, intercambiaron posiciones 21345 Como 3 > 1, intercambiaron posiciones 12345 Como 2 > 1, intercambiaron posiciones 12345 Como la clave no puede ir más a la izquierda, se acaba el paso 4. Ejercicio 1. El código de la función insertionsort ya está copiado en la hoja de Sage. Ejecutar la ventana de comandos que contiene su definición y probarla en algunas ejemplos. Complejidad del algoritmo Nos interesa evaluar la eficiencia de los algoritmos, por ejemplo el tiempo de ejecución (el espacio de memoria utilizada es importante también, pero aquí no lo consideramos) en función del tamaño de las entradas (aquí, el tamaño será la longitud de la lista que se ordena). El tiempo de ejecución dependerá del lenguaje de programación utilizado para implementar el algoritmo, y del material utilizado ¿ Cómo evaluar la eficiencia del algoritmo de manera independientemente de estos parámetros ? Se hace contando el número de utilizaciones de alguna “instrucción crítica”, la que más se repite en la ejecución del algoritmo. Para los algoritmos de ordenación, la instrucción crítica será la comparación de términos de la lista (Para un algoritmo de álgebra lineal que resuelve sistemas de ecuaciones, las instrucciones críticas serian las operaciones 3 aritméticas: adición y multiplicación). La figura 1 representa, para un determinado algoritmo de ordenación (insertionsort) los números de comparaciones realizadas al ejecutar sobre todas las listas de no más que 8 elementos, en función de la longitud de la lista. Hay dos medidas de complejidad importantes: La complejidad en peor caso: asocia a cada n el mayor número de comparaciones realizadas entre todas las listas de longitud n. La complejidad media: asocia a cada n la media de los números de comparaciones realizadas para todas las listas de longitud n. La complejidad en peor caso es especialmente importante en informática teórica, para clasificar los problemas algorítmicos en clases de complejidad. La complejidad media es importante para evaluar la eficiencia “en práctica” de los algoritmos utilizados industrialmente. Sin embargo, el estudio matemático de la complejidad media es, en general, mucho más complicado que el estudio de la complejidad en peor caso. Figura 1: Números de comparaciones realizadas por insertionsort para ordenar todas las listas de longitud hasta 8, en función de la longitud. Cuadro 1: Complejidad para insertionsort n 1 2 3 4 5 6 7 8 Complejidad en peor caso 0 1 3 6 10 15 21 28 Complejidad media 0 1, 00 2, 67 4, 92 7, 72 11, 0 14, 9 19, 3 Ejercicio 2. A la vista de la tabla 1, ¿ Puedes adivinar una formula para la complejidad en peor caso de insertionsort en función de n ? (deberías encontrarla, pero si no puedes ayudarte de http: //oeis.org). Ejercicio 3. En tu opinión, ¿ Cuál permutación de {1, 2, . . . , n} necesita el mayor número de comparaciones para ser ordenada por insertionsort ? Ejercicio 4. (A hacer en casa) Demuestra por inducción que tu formula del ejercicio 2 es correcta. Observa que hay que demostrar dos cosas: en primer lugar, que la fórmula da una cota superior para todos los números de comparaciones realizados para las listas de longitud n; segundo, que para cualquier n hay una lista que se ordena con este número de comparaciones. Para el algoritmo insertionsort, se puede establecer la formula Figura 2: Complejidad en peor caso (curva de arriba) y complejidad media (curva de abajo) para insertionsort. 4 siguiente para la complejidad media: 1 1 1 n ( n − 1) +n− 1+ + +···+ 4 2 3 n En esta formula, un término se vuelve rápidamente mucho más grandes que otros. La formula para la complejidad media se puede resumir en: n2 + términos más pequeños (1) 4 Ejercicio 5. La fórmula (1) sugiere que el tiempo medio de ejecución de insertionsort para listas de longitud n es proporcional a n2 . Si, para una implementación dada y un ordenador dado, el tiempo medio para ordenar las listas de longitud 1000 es t ¿ cuál será el tiempo medio para ordenar las listas de longitud 2000 ? ¿ Y el tiempo medio para ordenar las listas de longitud 3000 ? Ejercicio 6. Comprobar experimentalmente que la estimación hecha en el ejercicio 5 es correcta. Para evaluar empíricamente el tiempo medio t para ordenar las listas de longitud n, se puede proceder así: Las instrucciones útiles son: Permutations(n).random_element() 1. se elije aleatoriamente una muestra de permutaciones de {1, 2, . . . , n}. para elegir aleatoriamente una permu2. para cada una de ellas, se mide el tiempo de ejecución de la función insertionsort y se lo guarda en memoria. 3. se calcula la media de los tiempos medidos. En la hoja de SAGE aparecen las instrucciones necesarias, en el ejemplo de la estimación del tiempo medio para ordenar las listas de 100 elementos. tación de {1, 2, . . . , n}; t=cputime() para medir el tiempo en un reloj del ordenador; y mean(T) para calcular la media de los valores de una lista T.