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


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á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


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


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


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.


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)


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.


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).


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.


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.


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


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).


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:


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.


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


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


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:


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


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


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


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


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


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


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

introducción al análisis de algoritmosasanchez/ada/introduccionada.pdf · procedure...

Documents