Download imd2 -- Sage - Emmanuel Briand

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