Introducción al análisis de algoritmosasanchez/Ada/introduccionADA.pdf · Procedure...
Transcript of Introducción al análisis de algoritmosasanchez/Ada/introduccionADA.pdf · Procedure...
Introducción al análisis de
algoritmos
Abraham Sánchez López
FCC/BUAP
Grupo MOVIS
(C) A. Sánchez L. 2017
Porque necesitamos estudiar algoritmos?
Teoría: El estudio de los algoritmos, la algoritmia se reconoce como la piedra angular de las ciencias computacionales.
Práctica: Es necesario conocer un conjunto estándar de algoritmos importantes, de diferentes áreas de la computación. Debemos ser capaces de diseñar nuevos algoritmos y analizar su eficiencia.
La algoritmia es más que una rama de las ciencias computacionales. Es el núcleo de la computación, y con toda imparcialidad, se puede decir que es relevante a muchas otras ciencias (negocios y tecnología).
Dado un problema y un dispositivo donde resolverlo, es necesario contar con un método que lo resuelva.
Diseño
Algoritmos
Estudio de su eficiencia
(C) A. Sánchez L. 2017
Diseño y eficiencia Diseño: Búsqueda de métodos o procedimientos, secuencias finitas de
instrucciones adecuadas al dispositivo que disponemos, que permitan resolver el problema.
Eficiencia: Medir de alguna forma el costo (en tiempo y recursos) que consume un algoritmo para encontrar la solución. Podemos comparar distintos algoritmos que resuelvan un mismo problema.
Qué es un algoritmo? Un algoritmo es una secuencia de instrucciones no ambiguas para resolver un problema, es decir, para obtener una salida requerida para cualquier entrada “correcta” en una cantidad finita de tiempo.
Problema
Algoritmo
Entrada Salida
“Computadora”
(C) A. Sánchez L. 2017
Cálculo del máximo común divisor
Por descomposición en factores primos
Usando el algoritmo de Euclides
Usando el mínimo común múltiplo
(C) A. Sánchez L. 2017
Representación de un algoritmo, I La representación de un algoritmo se puede hacer en lenguaje natural,
en pseudo lenguaje y en un lenguaje de programación.
La evolución del algoritmo hasta su representación como programa, se puede representar como sigue:
Problema real
Modelo
matemático
Algoritmo en
lenguaje natural
Tipo abstracto de
datos
Programa en
pseudo lenguaje
Estructura de
datos
Programa
ejecutable
Modelización
Estructura
de datos
Algoritmia
(C) A. Sánchez L. 2017
Representación de un algoritmo, II El algoritmo y la estructura de datos evolucionan al mismo tiempo
hasta llegar al programa ejecutable y a la estructura de datos sobre la que actúa el programa.
La siguiente figura muestra la secuencia de pasos en el análisis y diseño de algoritmos.
Analizar el algoritmo
Codificar el algoritmo
Entender el problema
Decidir: medios computacionales,
soluciones exactas vs aproximadas,
estructura(s) de datos, técnica de
diseño del algoritmo.
Diseñar un algoritmo
Probar correctez
(C) A. Sánchez L. 2017
Pasos en el análisis y diseño, I Entender el problema: Entender el problema completamente. Una
entrada a un algoritmo especifica una instancia del problema que el algoritmo resuelve. Es muy importante especificar exactamente el rango de instancias que el algoritmo necesita manejar.
Capacidades del dispositivo computacional:
Arquitectura Von Neumann algoritmos secuenciales
Algoritmos paralelos!!
Resolución completa vs. Resolución aproximada
(raíces cuadradas, sol. (Complejidad intrínseca, TSP,
de ecs no lineales, …) mochila, …)
Decisión de una estructura de datos apropiada.
Algoritmos + Estructura de Datos = Programas
POO
Técnicas de diseño de algoritmos: Una técnica de diseño de algoritmos (estrategia o paradigma) es un enfoque general para resolver problemas algorítmicamente, que es aplicable a una variedad de problemas de diferentes áreas de la computación.
(C) A. Sánchez L. 2017
Pasos en el análisis y diseño, II Métodos para especificar algoritmos
Dado un algoritmo diseñado se necesita especificar
Primeras técnicas: diagramas de flujo, pseudocódigo, lenguaje natural
Pruebas de correctez: Probar que el algoritmo nos lleve al resultado requerido para cada entrada correcta en una cantidad finita de tiempo.
algoritmo probar su
especificado correctez!!!
Análisis de un algoritmo: Disponemos de un algoritmo que funciona correctamente.
se definen varios criterios para medir su rendimiento o comportamiento (se centran en su simplicidad y el uso eficiente de recursos)
La sencillez es una característica muy interesante a la hora de diseñar un algoritmo.
facilita la verificación (estudio de la eficiencia y mantenimiento)
(C) A. Sánchez L. 2017
Pasos en el análisis y diseño, III uso eficiente de los recursos
el espacio el tiempo
(memoria que utiliza) (lo que tarda en ejecutarse)
El tiempo de ejecución depende de diversos factores:
Datos de entrada que suministramos
Calidad del código generado por el compilador
Naturaleza y rapidez de las instrucciones máquina
Complejidad intrínseca del algoritmo
Estudios o consideraciones sobre el tiempo
Uno que proporciona una medida técnica (a priori), que consiste en obtener una función que acote (por arriba o por abajo) el tiempo de ejecución del algoritmo para unos valores de entrada dados.
Otro que ofrece un medida real (a posteriori), consiste en medir el tiempo de ejecución del algoritmo para unos valores de entrada dados y en una computadora concreta.
(C) A. Sánchez L. 2017
Pasos en el análisis y diseño, IV Ambas medidas son importantes:
La primera nos ofrece estimaciones del comportamiento de los algoritmos de forma independiente de la computadora donde serán implementados y sin necesidad de ejecutarlos.
La segunda representa las medidas reales del comportamiento del algoritmo.
Estas medidas son funciones temporales de los datos de entrada.
Tamaño de la entrada: es el número de componentes sobre los que se va a ejecutar el algoritmo.
La unidad de tiempo no puede ser expresada en segundos (no existe una computadora estándar a la que puedan hacer referencia todas las medidas).
(C) A. Sánchez L. 2017
Principio de invarianza, I Sea T(n) el tiempo de ejecución de un algoritmo para una entrada de
tamaño n.
Teóricamente T(n) indica el número de instrucciones ejecutadas por una computadora idealizada.
se deben buscar medidas simples y abstractas independientes de la computadora utilizada
acotar la diferencia entre las distintas implementaciones de un mismo algoritmo
A continuación se formula el principio de invarianza.
Dado un algoritmo y dos de sus implementaciones I1 e I2 con tiempos T1(n) y T2(n) seg., respectivamente.
El principio afirma que existe una constante real c > 0 y un número natural n0 tales que para todo n n0 se verifica que T1(n) cT2(n).
Con esto, podemos definir que un algoritmo tarda un tiempo del orden T(n) si existe un constante real c > 0 y una implementación I del algoritmo que tarda menos que cT(n), para todo n tamaño de la entrada.
(C) A. Sánchez L. 2017
Principio de invarianza, II Es importante notar que el comportamiento de un algoritmo puede
cambiar notablemente para diferentes entradas.
En muchos programas, el tiempo de ejecución es en realidad una función de la entrada específica y no sólo del tamaño de esta.
Se suelen estudiar tres casos para un mismo algoritmo:
Peor caso
Mejor caso
Caso promedio
El mejor caso corresponde a la traza (secuencia de instrucciones) del algoritmo que realiza menos instrucciones.
El peor caso corresponde a la traza del algoritmo que realiza más instrucciones.
El caso promedio corresponde a la traza del algoritmo que realiza un número de instrucciones igual a la esperanza matemática de la variable aleatoria definida por todas las posibles trazas del algoritmo para un tamaño de entrada dado, con las probabilidades de que estas ocurran para esa entrada.
(C) A. Sánchez L. 2017
Medición del tiempo Al medir el tiempo, se hace en función del número de operaciones
elementales que realiza el algoritmo.
Operaciones elementales: son aquellas que la computadora realiza en un tiempo acotado por una constante.
Ejemplos de OE:
Operaciones aritméticas básicas
Asignaciones a variables de tipo predefinido por el compilador
Saltos (llamadas a funciones y procedimientos, retornos, etc.)
Comparaciones lógicas y acceso a estructuras indexadas básicas (vectores y matrices).
1 OE
(C) A. Sánchez L. 2017
Ejemplo de operaciones elementales
Procedure Buscar(Var a:vector; c:integer)
Var
j:integer;
Begin
(1) j=1
(2) while (a[j] < c) and (i < n) do
(3) j = j+1
(4) end
(5) if a[j] = c then
(6) return j
(7) else return 0
(8) end
End
Línea 1: 1OE (asignación)
Línea 2: condición del ciclo, 4 OE ( 2
comparaciones, un acceso al vector y un
and)
Línea 3: un incremento y una asignación
(2 OE)
Línea 4:
Línea 5: una condición y un acceso al
vector (2 OE)
Línea 6: un return (1 OE) si la condición
se cumple
Línea 7: un return (1 OE) cuando la
condición del if anterior es falsa
Nota: No se toma en cuenta la copia del vector a la pila de ejecución del programa (se
pasa por referencia y no por valor). Si se pasa por valor, se debe tomar en cuenta el
costo (un incremento de n OE).
(C) A. Sánchez L. 2017
Reglas generales para el cálculo de las OE, I
Se considera siempre el peor caso.
Estas reglas definen el número de OE de cada estructura básica del lenguaje, el número de OE de un algoritmo puede hacerse por inducción sobre ellas.
1. El tiempo de una OE es por definición, de orden 1.
2. El tiempo de ejecución de una secuencia consecutiva de instrucciones se calcula sumando los tiempos de ejecución de cada una de las instrucciones.
3. El tiempo de ejecución de la sentencia
“case C of
V1 : S1 | V2 : S2 | … Vn : Sn End”
es:
T = T(c) + max {T(S1), T(S2), …, T(Sn)}
T(c) incluye el tiempo de comparación con V1 , V2, …, Vn
4. El tiempo de ejecución de un ciclo de sentencias “while C do S End” es:
(C) A. Sánchez L. 2017
Reglas generales para el cálculo de las OE, II
T = T(C) + (no de iteraciones) * (T(S) + T(C)) , T(S) y T(C) pueden variar en cada iteración.
5. Para calcular el tiempo de ejecución del resto de las sentencias iterativas (for, repeat, loop) basta expresarlas como un ciclo while.
6. El tiempo de ejecución de una llamada a un procedimiento o función F(p1, p2,…, pn) es 1 (por la llamada), más el tiempo de evaluación de los parámetros p1, p2,…, pn; más el tiempo que tarda en ejecutarse F. T = 1 + T(p1) + T(p2) + … + T(pn) + T(F)
No se contabiliza la copia de los argumentos a la pila de ejecución, solo en el caso de estructuras complejas que se pasan por valor (se contabilizan las OE como valores simples).
El paso de parámetros por referencia, no se contabiliza.
7. El tiempo de ejecución de las llamadas a procedimientos recursivos da como resultado ecuaciones en recurrencia.
8. Es importante además, las optimizaciones del código y la forma de evaluación de las expresiones.
(C) A. Sánchez L. 2017
Ejercicios
Procedure Algoritmo1(var a:vector)
var
i, j: cardinal;
temp:integer;
Begin
1) for i=1 to n-1 do
2) for j=n to i+1 by -1 do
3) if a[j-1] > a[j] then
4) temp=a[j-1]
5) a[j-1]=a[j]
6) a[j]=temp
7) end
8) end
9) end
End
Procedure Misterio (n:cardinal)
var
i, j, k, s:integer;
Begin
1) s=0
2) for i=1 to n-1 do
3) for j=i+1 to n do
4) for k=1 to j do
5) s=s+2
6) end
7) end
8) end
End
(C) A. Sánchez L. 2017
Notaciones asintóticas, I Cálculo del tiempo de ejecución T de un algoritmo.
Objetivo: Clasificar dichas funciones de forma que se pueden comparar.
Se definen clases de equivalencia correspondientes a las funciones que “crecen de la misma forma”.
Denotaremos por N al conjunto de los números naturales y por + al conjunto de los reales estrictamente positivos.
Definición 1: Dada una función f : N +, se denomina orden de f al conjunto de todas las funciones de N en + acotadas superiormente por un múltiplo real positivo de f para valores de n suficientemente grandes.
Se denota O(f)
Se pueden considerar funciones t que sean indefinidas o que tomen valores negativos para un número finito de valores de n N. Sólo nos interesa lo que pase para valores de n suficientemente grandes.
0 0( ) : / , , : ( ) ( )O f t N c n N n n t n cf n
(C) A. Sánchez L. 2017
Notaciones asintóticas, II Ejemplo: n2-8 O(n2), log(n-10) O(n)
Cuando se estudia un algoritmo, se trata de encontrar la función f más simple posible de manera que t O(f), t representa el tiempo de ejecución del algoritmo (medida de la cantidad de memoria necesaria) en función de la dimensión de la entrada.
La función t es muy difícil de calcular, por lo que se trata de buscar la f que más se le aproxime asintóticamente (n ).
Se establece una relación de orden en el conjunto de los órdenes de funciones:
O(f) O(g) si t O(f), t O(g)
con lo que intentamos encontrar el menor O(f) /t O(f), se escribe ó indistintamente , ya que la ordenación entre órdenes es una inclusión de conjuntos.
Ejemplo: t(n) = n2 + 2n – 5, t(n) O(n2), t(n) O(n3)
lo más cerca es n2, por lo que decidimos que t es del orden de O(n2)
Se puede comprobar que O(n2 + 2n – 5) = O(n2) y en general se cumple que:
(C) A. Sánchez L. 2017
Notaciones asintóticas, III O(c) = O(d), con c y d constantes
O(c) O(n)
O(n+b) = O(dn+e), si c y d son constantes positivas
O(p) = O(q), p y q son polinomios de igual grado
O(p) O(q), si p es un polinomio de grado menor que q
Las constantes y los coeficientes principales de los polinomios tiene valores positivos.
Definición 2: Dada una función f : N +, se denomina omega de f al conjunto de todas las funciones de N en + acotadas inferiormente por un múltiplo real positivo de f para valores de n suficientemente grandes.
Se denota (f)
Para la notación omega sirven las mismas relaciones que para el orden, pero cambiando el sentido de las desigualdades.
0 0( ) : / , , : ( ) ( )f t N c n N n n t n cf n
(C) A. Sánchez L. 2017
Notaciones asintóticas, IV Definición 3: Dada una función f : N +, llamamos orden exacto de f
al conjunto de todas las funciones de N en + que crecen (salvo las constantes y asintóticamente) de la misma forma que f.
Se denota (f)
Se puede comprobar fácilmente que la definición de es equivalente a otra forma de definición similar a las dadas por O y .
Propiedad 1: Dadas f y g de N en +, f (g) c, d +, n0 N/ n n0 : cg(n) f(n) dg(n).
El estudio de un algoritmo nos da t(n) = n2 + 2n – 5 se sabe que su orden exacto es (n2), pero en otros casos no se puede calcular el orden exacto sino el orden (O) y el omega (), con lo que tendremos en un cierto sentido una cota superior e inferior de la forma en que crece el tiempo de ejecución del algoritmo.
Algunas veces nos interesa perder la información de los coeficientes del término de mayor orden. En este caso se utiliza la notación o(f).
( ) ( ) ( )f O f f
(C) A. Sánchez L. 2017
Notaciones asintóticas, V Definición 4: Dada una función f : N +, llamamos o pequeña de f al
conjunto:
En el caso en que t sea un polinomio de grado m, t O(nm) y t o(amnm).
( )( ) : / lim 1
( )n
t no f t N
f n
(C) A. Sánchez L. 2017
Propiedades de las notaciones asintóticas Propiedad 1. Si f O(g) y g O(h) entonces f O(h). (Si f (g) y g
(h) entonces f (h)).
Propiedad 2. Si f O(g) entonces O(f) O(g). (Si ) f (g) entonces (f) (g)).
Propiedad 3. Dadas f y g de N en + se cumple:
O(f) = O(g) f O(g) y g O(f). ((f) = (g) f (g) y g (f))
O(f) O(g) f O(g). ((f) (g) f (g))
Propiedad 4. Dadas f y g de N en +, O(f + g) = O(max(f, g)). ((f + g) = (max(f, g))).
Propiedad 5. Dadas f y g de N en +, O(f) = O(g) (f) = (g) (f ) = (g).
Propiedad 6. Dadas f y g de N en +, se cumple:
( )) lim ( ) ( ), ( ) ( ), ( ) ( )
( )n
f ni O f O g f g f g
g n
( )) lim 0 ( ) ( ), ( ) ( ), ( ) ( )
( )n
f nii O f O g f g f g
g n
(C) A. Sánchez L. 2017
Más de las propiedades En el caso ii), f no tiene porqué pertenecer a (g).
En el caso iii), f no tiene porqué pertenecer a (g).
( )) lim ( ) ( ) y ( ) ( )
( )n
f niii f g O g O f
g n
(C) A. Sánchez L. 2017
Cotas de complejidad más comunes, I El orden de un polinomio anx
n + … + a0, con an positivo es O(xn).
El orden de una sumatoria es O(mn+1).
La medida logarítmica aparece cuando se hace una operación para n/2, otra para n/4, otra para n/8, y así sucesivamente. En este caso la complejidad es O(log2 n).
Las medidas más frecuentes que aparecen en el estudio de los algoritmos son las polinómicas y logarítmicas y el producto de estas.
Algunas relaciones entre órdenes de complejidad son:
En general, con p y q enteros positivos se cumple O((log n)p) O(n1/q).
Con la notación se invierten las inclusiones.
Todas las inclusiones se pueden demostrar utilizando la propiedad 6.
1
m n
ii
(1) (log ) ( ) ( ) ( log ) ( log log )O O n O n O n O n n O n n n 2 3( ) ( ) ... (2 ) ( !) ( )n nO n O n O O n O n
(C) A. Sánchez L. 2017
Cotas de complejidad más comunes, II Por ejemplo, podemos demostrar que O(log n) O( ) calculando el
límite:
ya que O(ln n) = O(log n) al diferenciarse en una constante. Aplicando la regla de l’Hôpital tenemos:
con lo que queda demostrado lo que queríamos.
Del mismo modo se puede demostrar que O((log n)2) O(n1/2).
n
lnlimn
n
n
1ln 2
lim lim lim 01
2n n n
n n
n nn
2 12lnln 4lnlim lim lim 0
12
n n n
n nn
n nn