Download Enunciado en pdf - Emmanuel Briand

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.