Las matemticas como Las matemticas como medio para medir la medio para medir la

eficiencia de los Algoritmos eficiencia de los Algoritmos ComputacionalesComputacionales

Qu es un algoritmo?Qu es un algoritmo?

(del rabe al-Khowrizm, sobrenombre (del rabe al-Khowrizm, sobrenombre del clebre matemtico rabe Mohmed del clebre matemtico rabe Mohmed ben Musa). Conjunto ordenado y finito de ben Musa). Conjunto ordenado y finito de operaciones que permite encontrar la operaciones que permite encontrar la solucin a un problemasolucin a un problema

Un algoritmo, puede expresarse en Un algoritmo, puede expresarse en trminos de un lenguaje de programacin, trminos de un lenguaje de programacin, para obtener un programa que resuelve el para obtener un programa que resuelve el problema por medio de la computadora.problema por medio de la computadora.

Cita...Cita... No hay un incremento concebible en el poder de las No hay un incremento concebible en el poder de las

computadoras que pueda saturar la demanda cientfica: an computadoras que pueda saturar la demanda cientfica: an pensando que una computadora posea un ciclo de tiempo pensando que una computadora posea un ciclo de tiempo subnuclear (10subnuclear (10-23-23 seg.) y densidades de almacenamiento seg.) y densidades de almacenamiento subnucleares (10subnucleares (103939 bits/cm bits/cm33), sta no podra manejar la mayora ), sta no podra manejar la mayora de los problemas que son importantes en la investigacin de los problemas que son importantes en la investigacin cientfica bsica y aplicada. Por lo tanto, existir siempre una cientfica bsica y aplicada. Por lo tanto, existir siempre una fuerte presin para incrementar la fuerte presin para incrementar la eficienciaeficiencia de los programas, de los programas, para poder incrementar tambin la cantidad de informacin para poder incrementar tambin la cantidad de informacin ltil generada por un programa.ltil generada por un programa.

Ken Wilson, Nbel de Fsica 1982Ken Wilson, Nbel de Fsica 1982

reas de estudioreas de estudio

Cmo construir algoritmos?Cmo construir algoritmos? Tcnicas de diseoTcnicas de diseo

Cmo expresar algoritmos?Cmo expresar algoritmos? Enfoques de los lenguajes de programacinEnfoques de los lenguajes de programacin

Cmo validar algoritmos?Cmo validar algoritmos? Verificacin formalVerificacin formal

Cmo analizar algoritmos?Cmo analizar algoritmos? Complejidad computacional, eficiencia, legibilidad, Complejidad computacional, eficiencia, legibilidad,

usabilidad, etc...usabilidad, etc...

Anlisis de algoritmosAnlisis de algoritmos

Si se tuvieran 2 programas que hacen lo Si se tuvieran 2 programas que hacen lo mismo, cmo se podran comparar?mismo, cmo se podran comparar?

1. Eficiencia:1. Eficiencia:Tiempo de ejecucinTiempo de ejecucinUso de espacios de memoriaUso de espacios de memoria

2. Facilidad de lectura, mantenimiento, 2. Facilidad de lectura, mantenimiento, rapidez para codificarlo.rapidez para codificarlo.

Medicin del tiempo de Medicin del tiempo de ejecucinejecucin

El tiempo de ejecucin depende de:El tiempo de ejecucin depende de:1. La entrada al programa:1. La entrada al programa:

Su tamaoSu tamaoSus caractersticasSus caractersticas

2. La calidad del cdigo generado para el 2. La calidad del cdigo generado para el programa por el compilador .programa por el compilador .

3. La rapidez de las instrucciones de 3. La rapidez de las instrucciones de mquina.mquina.

4. La 4. La complejidad de tiempo del complejidad de tiempo del algoritmoalgoritmo..

Cmo medir?Cmo medir?

Cantidad de instrucciones bsicas (o Cantidad de instrucciones bsicas (o elementales) que se ejecutan.elementales) que se ejecutan.

Ejemplos de instrucciones bsicas:Ejemplos de instrucciones bsicas: asignacin de escalaresasignacin de escalares lectura o escritura de escalareslectura o escritura de escalares saltos (gotos) implcitos o explcitos.saltos (gotos) implcitos o explcitos. evaluacin de condicionesevaluacin de condiciones llamada a funcionesllamada a funciones etc.etc.

EjemploEjemplo

cont = 1;cont = 1;while (cont

EjemploEjemploz = 0;z = 0;for for (int (int x=1x=1; x

ConsecuenciaConsecuencia

Se requiere contar con una notacin que permita Se requiere contar con una notacin que permita comparar la eficiencia entre los algoritmoscomparar la eficiencia entre los algoritmos

La La NOTACIN ASINTTICANOTACIN ASINTTICA es la propuesta de notacin es la propuesta de notacin aceptada por la comunidad cientfica para describir el aceptada por la comunidad cientfica para describir el comportamiento en eficiencia (o complejidad) de un comportamiento en eficiencia (o complejidad) de un algoritmo.algoritmo.

Describe en forma sinttica el comportamiento de la Describe en forma sinttica el comportamiento de la funcin que con la variable de entrada, determina el funcin que con la variable de entrada, determina el nmero de operaciones que realiza el algoritmo.nmero de operaciones que realiza el algoritmo.

NOTACIN ASINTTICANOTACIN ASINTTICA COMPLEJIDAD TEMPORAL COMPLEJIDAD TEMPORAL (y ESPACIAL)(y ESPACIAL). .

Tiempo Tiempo (o espacio)(o espacio) requerido por un algoritmo, requerido por un algoritmo, expresado en base a una funcin que depende expresado en base a una funcin que depende del tamao del problema.del tamao del problema.

COMPLEJIDAD TEMPORAL ASINTTICA COMPLEJIDAD TEMPORAL ASINTTICA (y (y ESPACIAL)ESPACIAL). Comportamiento lmite conforme el . Comportamiento lmite conforme el tamao del problema se incrementa. Determina tamao del problema se incrementa. Determina el tamao del problema que puede ser resuelto el tamao del problema que puede ser resuelto por un algoritmo.por un algoritmo.

DefinicinDefinicin Se dice que la funcin Se dice que la funcin f(n)f(n) es de orden es de orden g(n)g(n)

[[O(g(n))O(g(n))], si existen constantes positivas ], si existen constantes positivas cc y y nn00 tales que tales que f(n)f(n) = nn00

Ejemplos:Ejemplos: n+5n+5 es es O(n)O(n) pues pues n+5n+5 = 5 (n+1)(n+1)22 es es O(nO(n22)) pues pues (n+1)(n+1)22 = 1 (n+1)(n+1)22 NONO es es O(n)O(n) pues para cualquier pues para cualquier c > 1c > 1

no se cumple que no se cumple que (n+1)(n+1)22

Ordenes ms comunes de los Ordenes ms comunes de los algoritmosalgoritmos

O(1) ConstanteO(1) Constante O(n) LinealO(n) Lineal O(nO(n2 2 ) Cuadrtico) Cuadrtico O(nO(n3 3 ) Cbico) Cbico O (nO (nm m ) Polinomial) Polinomial O(log(n)) LogartmicoO(log(n)) Logartmico O(nlog(n)) nlog (n)O(nlog(n)) nlog (n) O(mO(mn n ) exponencial) exponencial O(n!) factorialO(n!) factorial

Comportamiento Comportamiento de las funcionesde las funciones

log n n

n log n

n sqrt(n)

n2

Otro mtodo para calcular el orden Otro mtodo para calcular el orden de un problemade un problema

Consiste en aplicar reglas a los estatutos Consiste en aplicar reglas a los estatutos estructurados:estructurados:

1.1.Secuencia de instruccionesSecuencia de instrucciones2.2.Decisiones (ejemplo: if)Decisiones (ejemplo: if)3.3.Ciclos (ejemplo: while)Ciclos (ejemplo: while)4.4.RecursividadRecursividad

Regla 1: Secuencia de Regla 1: Secuencia de instruccionesinstrucciones

Ejemplo:Ejemplo: Una secuencia de 3 ciclos:Una secuencia de 3 ciclos:

Ciclo 1 = Ciclo 1 = O(n)O(n) Ciclo 2 = Ciclo 2 = O(log n)O(log n) Ciclo 3 = Ciclo 3 = O(nO(n22))

Tendr como orden totalTendr como orden total O(nO(n22))..

O(g1(n))O(g1(n))

O(g2(n))O(g2(n))

O(g3(n))O(g3(n))

O(gm(n))O(gm(n))

O( mayor(g1(n), g2(n), , gm(n) )

Regla 2: Regla 2: DecisionesDecisiones

Ejemplo:Ejemplo: Una decisin con:Una decisin con:

Rama then = Rama then = O(n log n)O(n log n) Rama else = Rama else = O(log n)O(log n)

Tendr como orden total Tendr como orden total O(n log n)O(n log n)..

O(g1(n))O(g1(n))

O(g2(n))O(g2(n))

O( mayor(g1(n), g2(n)) )

Regla 3: Regla 3: CiclosCiclos

Ejemplo:Ejemplo: Un ciclo cuya instruccin:Un ciclo cuya instruccin:

Tiene un Tiene un O(log n)O(log n) Se repite Se repite n/2n/2 veces veces

Tendr como orden total Tendr como orden total O(O( n log n n log n) = O(n log n)) = O(n log n)..

O(g(n))O(g(n)) O( m * g(n) )

Se repite m veces

Consideraciones especialesConsideraciones especiales

En decisiones y ciclos anidados:En decisiones y ciclos anidados: Analizar el cdigo desde la instruccin ms Analizar el cdigo desde la instruccin ms

interna hacia el ms externa.interna hacia el ms externa. Tip para los ciclos:Tip para los ciclos: Normalmente cul es el orden de la Normalmente cul es el orden de la

instruccin interna?instruccin interna? Si la variable de control se incrementa o Si la variable de control se incrementa o

decrementa con un valor constante: decrementa con un valor constante: Orden Orden LINEALLINEAL..

Si la variable de control se multiplica o divide por Si la variable de control se multiplica o divide por un valor constante: un valor constante: Orden LOGARTIMICOOrden LOGARTIMICO..

Ejemplo: Sort por intercambioEjemplo: Sort por intercambio

for for (int (int i=1i=1; i

Ejemplo: Sort por intercambioEjemplo: Sort por intercambio

for for (int (int i=1i=1; i

Ejemplo: Sort por intercambioEjemplo: Sort por intercambio

for for (int (int i=1i=1; i

Ejemplo: Multiplicacin de Ejemplo: Multiplicacin de matricesmatrices

a11 a12 a1na21 a22 a2n

am1 am2 amn

b11 b12 b1mb21 b22 b2m

bn1 bn2 bnm

X

c11 = a11*b11+a12 *b21 ++ a1n *bn1c12 = a11*b12+a12 *b22 ++ a1n *bn2

c21 = a21*b11+a22 *b21 ++ a2n *bn1

cmm = am1*b1m+am2 *b2m ++ amn *bnm

c11 c12 c1mc21 c22 c2m

cm1 cm2 cmm

=

ccijij = = a aikikbbkjkjnn

k=1k=1

Ejemplo: Multiplicacin de Ejemplo: Multiplicacin de matricesmatrices

for i = 1 to n dofor i = 1 to n dofor j = 1 to n dofor j = 1 to n do

C[i,j] = 0;C[i,j] = 0;for k = 1 to n dofor k = 1 to n do

C[i,j] = C[i,j] + C[i,j] = C[i,j] + A[i,k]*B[k,j];A[i,k]*B[k,j];

O( 1 ) O( n )

O( n2 ) O( n3 )

O( 1 )

Regla 4: RecursividadRegla 4: Recursividad

La complejidad de tiempo se obtiene contando la cantidad La complejidad de tiempo se obtiene contando la cantidad de veces que se hace de veces que se hace la llamada recursivala llamada recursiva..

Casos que normalmente se dan:Casos que normalmente se dan: Orden LINEAL si slo se tiene una llamada recursiva, Orden LINEAL si slo se tiene una llamada recursiva,

con incrementos o decrementos en el parmetro de con incrementos o decrementos en el parmetro de control.control.

Orden LOGARITMICO si slo se tiene una llamada Orden LOGARITMICO si slo se tiene una llamada recursiva, con multiplicaciones o divisiones en el recursiva, con multiplicaciones o divisiones en el parmetro de control.parmetro de control.

Si hay ms de una llamada recursiva, el orden puede Si hay ms de una llamada recursiva, el orden puede tender a ser EXPONENCIAL.tender a ser EXPONENCIAL.

Ejemplo: Fibonacci (Iterativo)Ejemplo: Fibonacci (Iterativo)ant = 1;ant = 1; --> 1--> 1act = 1;act = 1; --> 1--> 1while (n>2)while (n>2){{ --> n-2 + 1--> n-2 + 1 aux = ant + act;aux = ant + act; --> n-2--> n-2 ant = act;ant = act; --> n-2--> n-2 act = aux;act = aux; --> n-2--> n-2 n = n - 1;n = n - 1; --> n-2--> n-2}} --> n-2--> n-2+1+1write (act);write (act); --> 1--> 1

T(n) = 6n-7

Por lo tanto el orden del algoritmo es O(n)O(n)

Ejemplo: Fibonacci (recursivo)Ejemplo: Fibonacci (recursivo)

Function fibonacci (n:int): int;Function fibonacci (n:int): int; if (n < 3) return 1;if (n < 3) return 1; else return fibonacci(n-1) + fibonacci(n-2);else return fibonacci(n-1) + fibonacci(n-2);

Cmo obtener la complejidad de tiempo Cmo obtener la complejidad de tiempo del algoritmo?del algoritmo?

Cantidad de llamadas recursivas: Cantidad de llamadas recursivas: 2 en 2 en cada llamada.cada llamada.

Algoritmo de orden: Algoritmo de orden: O(2O(2n/2n/2))

Anlisis de Fibonacci Anlisis de Fibonacci (recursivo)(recursivo)

Cuntos trminos Cuntos trminos se requieren para se requieren para calcular:calcular:

f(5)?f(5)?f(4)?f(4)?f(3)?f(3)?f(2)?f(2)?f(6)?f(6)?

f(5)

f(3)

f(1) f(2)

f(4)

f(2) f(3)

f(1) f(2)--> 9--> 5--> 3--> 1--> 15

Relacin:El trmino T(n) requiereT(n-1)+T(n-2)+1 trminos para calcularse.

Anlisis de FibonacciAnlisis de Fibonacci

Si el trmino Si el trmino T(n)T(n) requiere requiere T(n-1)+T(n-T(n-1)+T(n-2)+12)+1 trminos para calcularse trminos para calcularse

se puede decir que se puede decir que T(n) > 2 * T(n-2)T(n) > 2 * T(n-2) y por lo tanto: y por lo tanto: T(n) > 2 * 2 * T(n-4)T(n) > 2 * 2 * T(n-4) y y T(n) > 2 * 2 * 2 * T(n-6)T(n) > 2 * 2 * 2 * T(n-6) y as sucesivamente hasta: y as sucesivamente hasta:

T(n) > 2 * 2 * 2 * . * 2 * T(1)T(n) > 2 * 2 * 2 * . * 2 * T(1)

n/2 veces

Por lo tanto:T(n) > 2n/2

y podemos decir que el orden del

algoritmo es

O(2O(2n/2n/2))

Pgina 1Pgina 2Pgina 3Pgina 4Pgina 5Pgina 6Pgina 7Pgina 8Pgina 9Pgina 10Pgina 11Pgina 12Pgina 13Pgina 14Pgina 15Pgina 16Pgina 17Pgina 18Pgina 19Pgina 20Pgina 21Pgina 22Pgina 23Pgina 24Pgina 25Pgina 26Pgina 27Pgina 28Pgina 29