Download imd2 -- Sage - Emmanuel Briand
Transcript
http://localhost:8000/home/admin/48/print http://localhost:8000/home/admin/48/print imd2 Práctica 2 IMD-IC Complejidad de algoritmos Primer termino de L: 12 Segundo termino de L: 35 Tercer termino de L: esto es una cadena de caracteres Cuarto termino de L: 7 Si pedimos el termino de indice 4, que no existe, obtenemos un mensaje de error. print L[4] Traceback (click to the left of this block for traceback) ... IndexError: list index out of range Podemos modificar los terminos de la lista. En esta práctica examinamos la complejidad de una algoritmos, estimando el tiempo necesario a su ejecución en función del tamaño de su entrada. Empezamos familiarizandonos con unos comandos de SAGE. I. Listas en SAGE L=[12,35,"esto es una cadena de caracteres", 7] print L L[1]=60 print L [12, 35, 'esto es una cadena de caracteres', 7] [12, 60, 'esto es una cadena de caracteres', 7] print L L[3]=L[3]+1 print L [12, 60, 'esto es una cadena de caracteres', 7] [12, 60, 'esto es una cadena de caracteres', 8] La lista de longitud cero existe. (Pinchar en la ventana, y luego en el "evaluate" azul que aparece debajo, para ejecutar el comando) Acabamos de defiinir una Lista, que hemos llamado "L". Tiene cuatro terminos, tres de ellos son números, el otro es una cadena de caracteres. Podemos imprimir la lista L a la pantalla, y su longitud (length, en inglés), de la manera siguiente: print L [12, 35, 'esto es una cadena de caracteres', 7] len(L) 4 Como en otros lenguajes de programación, los terminos de una lista en SAGE son numerados a partir del 0. Como L tiene 4 terminos, sus indices van del 0 al 3. print print print print "Primer termino de L:", L[0] "Segundo termino de L:", L[1] "Tercer termino de L:", L[2] "Cuarto termino de L:", L[3] L1=[] print L1 print len(L1) [] 0 Ejercicio 1. Adivinar el efecto de las funciones "append" e "insert" sobre una lista, considerando ejemplos adecuados, como por ejemplo los siguientes L=[100,45,40,43,21,12,-5] L.append(55) print L [100, 45, 40, 43, 21, 12, -5, 55] L=[100,45,40,43,21,12,-5] L.insert(5,55) print L [100, 45, 40, 43, 21, 55, 12, -5] http://localhost:8000/home/admin/48/print Ejercicio 2 ¿ Cómo añadir un elemento inicial en una lista, para transformar, por ejemplo, [1,2,3] en [55,1,2,3] ? 2. Complejidad de un algoritmo 2.1. Un algoritmo misterioso Consideramos el algoritmo siguiente, que, a partir de una lista, produce otra lista. (No se pide por ahora entender el funcionamiento de este algoritmo). def mialgo(L): longitud=len(L) if longitud<=1: return(L) else: for k in [1,..,longitud-1]: clave=L[k] for j in [k-1,k-2,..,0]: if L[j]>clave: L[j+1]=L[j] L[j]=clave else: break # salida del bucle return(L) http://localhost:8000/home/admin/48/print para ordenar [1,2,4,3,5] hace falta 5 comparaciones para ordenar [5,3,1,2,4] hace falta 8 comparaciones ... El recuento del número de comparaciones para ordenar cada lista, lo hará la función mialgo2 siguiente. # Modificación del algoritmo "mialgo" # En vez de devolver la lista ordenada, # devuelve el número de comparaciones realizadas al ordenarla def mialgo2(L): longitud=len(L) comp=0 if longitud<=1: # no contaremos esta comparación return(comp) else: for k in [1,..,longitud-1]: clave=L[k] # la clave se desplaza tanto hasta la izquierda como posible # hasta encontrar un elemento menor. for j in [k-1,k-2,..,0]: comp=comp+1 #para la comparación que sigue: "L[j]>clave" if L[j]>clave: L[j+1]=L[j] L[j]=clave else: break # salida del bucle return(comp) Ejercicio 3 1. Adivinar lo que hace este algoritmo, cambiando L1 en el ejemplo siguiente y observando que resultados da mialgo para estas entradas. 2. Modificar mialgo, introduciendo la instrucción "print L" en el sitio adecuado, para observar como se modifica L durante la ejecución de la función. L1=[12,15,-34,64,11,10] L2=mialgo(L1) print L2 [-34, 10, 11, 12, 15, 64] 2.2. Estudio experimental de la complejidad del algoritmo Vamos a estudiar la complejidad de este algoritmo: estimar el tiempo que necesita en función del número de elementos de la lista dada en entrada. Para esto, contaremos el número de comparaciones realizadas al ejecutar mialgo, para todas las entradas posibles : mialgo2([1,2,4,3,5]) 5 mialgo2([5,3,1,2,4]) 8 Vamos a estudiar la complejidad del algoritmo en función de la longitud n de la lista dada en entrada. Estudiaremos solamente el caso de las permutaciones de {1, 2, .., n} (¿ por qué basta esto ?). para una longitud n dada, hay muchas permutaciones de longitud n. Hacemos la lista de TODAS estas permutaciones de longitud n (¿ Cuántas son ?). creamos una lista Ncomp que recuerda los números de comparaciones realizadas al ordenar con mialgo cada una de estas permutaciones. # Ejemplo para n=5 http://localhost:8000/home/admin/48/print http://localhost:8000/home/admin/48/print Ncomp=[] for sigma in Permutations(5): # sigma es una permutación c=mialgo2(list(sigma)) # c es el número de comparaciones necesarias para ordenarla Ncomp.append(c) # Ponemos el valor de c en la lista "Ncomp" # Ejemplo de uso de estas funciones L=[1,4,2] add(L) 7 factorial(5) 120 print(Ncomp) [4, 5, 5, 6, 6, 7, 5, 6, 6, 7, 7, 8, 6, 7, 7, 8, 8, 9, 7, 8, 8, 9, 9, 10, 4, 5, 5, 6, 6, 7, 5, 6, 6, 7, 7, 8, 6, 7, 7, 8, 8, 9, 7, 8, 8, 9, 9, 10, 5, 6, 6, 7, 7, 8, 5, 6, 6, 7, 7, 8, 7, 8, 7, 8, 9, 9, 8, 9, 8, 9, 10, 10, 6, 7, 7, 8, 8, 9, 6, 7, 7, 8, 8, 9, 7, 8, 7, 8, 9, 9, 9, 10, 9, 10, 10, 10, 7, 8, 8, 9, 9, 10, 7, 8, 8, 9, 9, 10, 8, 9, 8, 9, 10, 10, 9, 10, 9, 10, 10, 10] De esta lista Ncomp, podemos extraer dos datos particularmente interesantes: 1. El promedio de los números de comparaciones realizadas, para todas las permutaciones de {1, 2, ..., n}. Lo llamamos "complejidad media de mialgo para entradas de longitud n". 2. El máximo de los números de comparaciones realizadas, para todas las permutaciones de {1, 2, ..., n}. Lo llamamos "complejidad en peor caso de mialgo para entradas de longitud n". Si la complejidad media de mialgo para ordenar listas de longitud n = 1000 es, digamos, 30000, y tenemos que ordenar 2000 listas de longitud n = 1000, entonces podemos estimar el número de comparaciones realizadas al ordenar estas 2000 listas a: 2000 ! 30000 comparaciones. Y si la complejidad en peor caso es 50000, podemos garantizar que no se harán más de 2000 ! 50000 comparaciones. Ejercicio 4 A partir de la lista Ncomp, completar la tabla siguiente: Longitud n 1 2 3 4 5 Complejidad en peor caso para ordenar listas de longitud n Complejidad media para ordenar listas de longitud n Se podrá utilizar las funciones max, add, factorial y float. 6 7 8 max(L) 4 float(13/3) 4.333333333333333 2.3 Representación gráfica Representamos gráficamente todos los puntos: [n, número de comparaciones al ejecutar "mialgo" con una permutación de longitud n como entrada], para todos los n entre 1 y 8. (Ejecutar simplemente el bloque de instrucciones siguiente ... ser paciente ... ). Comparar con los cálculos de complejidad media y complejidad en peor caso hechos anteriormente. P=[] for n in [1,..,8]: NNN=[] for sigma in Permutations(n): c=mialgo2(list(sigma)) NNN.append(c) P.extend([(n,c) for c in NNN]) PP=points(P) show(PP) http://localhost:8000/home/admin/48/print http://localhost:8000/home/admin/48/print comparaciones posibles para todas las sucesiones de longitud n ? En general uno no paga atención excesiva a la formula exacta para la complejidad: guarda solamente el "término dominante" e incluso omite precisar las constantes multiplicativas. En el ejemplo del algoritmo mialgo, que la complejidad en peor caso es O(n2 ) ("en gran O de ene cuadrado"), en vez de la formula exacta. La significación exacta de O(n2 ) es: una función c de n, 2 tal que existe una constante k y un entero N , tal que para cualquier n ! N , c(n) " kn . Se puede demostrar que la complejidad media de mialgo también es en O(n2 ). Otros algoritmos (como por ejemplo Merge, utilizado en Java) tienen complejidad media y complejidad en peor caso en O(n log n). Podemos comprobar gráficamente que la complejidad de mialgo parece acotada por n2 . ¿ podrémos hallar mejores cotas ? F=plot(x^2,(x,0,8),color='red') show(F+PP) Ejercicio 5 1. Adivinar una formula (en función de n) para la complejidad en peor caso de "mialgo". 2. ¿ Cuáles son las permutaciones que necesitan efectivamente este peor número de comparaciones para ser ordenadas por mialgo ?, 3. ¿ Puedes demostrar que la formula adivinada da exactamente el mayor número de