Matlab Uch1 Clase11

MATEMÁTICA DISCRETA Clase 11 •COMPLEJIDA ALGORITMICA

Cuando los problemas del mundo real se desean resolver con modelos de sistemas computacionales, trae consigo una cantidad indefinida de requisitos que compiten entre sí y algunas veces se contradicen. 1

DEFINICIONES PREVIAS ALGORITMO.Un algoritmo es una secuencia finita y ordenada de instrucciones elementales que, dados los valores de entrada de un problema, en algún momento finaliza y devuelve la solución. La Teoría de Algoritmos es una ciencia que estudia cómo construir algoritmos para resolver diferentes problemas. La Teoría de Algoritmos también proporciona herramientas formales que nos van a permitir decidir qué algoritmo es mejor en cada caso.

Nota.El tiempo de ejecución de un algoritmo viene dado por las entradas concretas que le introduzcamos. Por esto distinguimos 3 alternativas: Mejor caso, Peor caso y caso promedio. Universidad de Ciencias y Humanidades Algebra Computacional

2

ANÁLISIS DE ALGORITMOS La Teoría de la Complejidad Computacional es la parte de la teoría de la computación que estudia los recursos requeridos durante el cálculo para resolver un problema. Un cálculo resulta complejo si es difícil de realizar. En este contexto podemos definir la complejidad de cálculo como la cantidad de recursos necesarios para efectuar un cálculo. Así, un cálculo difícil requerirá más recursos que uno de menor dificultad. Los recursos comúnmente estudiados son el tiempo (número de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (cantidad de memoria utilizada para resolver un problema). Un algoritmo que resuelve un problema pero que tarda mucho en hacerlo, difícilmente será de utilidad. Igualmente un algoritmo que necesite mas de un gigabyte de memoria no será probablemente utilizado. A estos recursos se les puede añadir otros, tales como el número de procesadores necesarios para resolver el problema en paralelo. Si un cálculo requiere más tiempo o espacio (disco duro) que otro decimos que es más complejo Universidad de Ciencias y Humanidades Algebra Computacional

3

Ejemplo1

a⇐3 b⇐a*5 If b==5 then a⇐2 Else a⇐1 End if

(1) (2) (3) (4) (5) (6) (7)

El algoritmo tiene 5 instrucciones de las cuales se ejecutan solamente 4 . Por tanto el costo en tiempo del programa es 4C, siendo C una constante que indica cuanto tiempo tarda en ejecutarse una instrucción . El espacio que necesita el programa es el espacio ocupado por las variables a y b. Es decir 2Ec, siendo Ec el espacio que ocupa una variable. Universidad de Ciencias y Humanidades Algebra Computacional

4

Ejemplo 2.-

a⇐3

(1)

b⇐a*5

(2)

If b==5 then

(3)

a⇐2 Else

(4) (5)

a⇐1 End if Este programa cuesta ahora :

(6) (7)

3*C1+1*C2+1*C3

Donde: C1: Costo de la asignación C2: Costo de la multiplicación C3: Costo de comparar dos números. Universidad de Ciencias y Humanidades Algebra Computacional

5

Ejemplo 3.Supongamos que no disponemos de una función que eleve un número a un cierto exponente y, pero si disponemos de una función que multiplique un número por otro. Potencia (x,y) // calcula xy donde x>0 If y==0 then return 1 Else

(1) (2) (3)

result⇐x

(4)

for i=1 to y-1 do

(5)

result⇐result*x

(5)

End for

(6)

End if

(7)

Return result

(8)

¿Cuánto cuesta el algorítmo?... Universidad de Ciencias y Humanidades Algebra Computacional

6

La comparación del if se realiza siempre, supongamos que y no es cero (mayormente va a pasar) El costo del algoritmo es:

……………………………………………..……………………..

Donde: C1: Costo de comparar dos números C2: Costo de realizar una asignación C3: Costo de realizar una multiplicación ¿Es eficiente el algoritmo? Nota.Los algoritmos que no son correctos a veces pueden ser útiles si, por ejemplo producen una respuesta aproximada a un problema particularmente difícil en forma eficiente. Universidad de Ciencias y Humanidades Algebra Computacional

7

Ejemplo 4.La ordenación de la burbuja es uno de los algoritmos de busqueda mas simples, pero no uno de los mas eficientes

Universidad de Ciencias y Humanidades Algebra Computacional

8

For i=1 to n-1 do

(1)

for j=1 to n do

(2)

if A(j)>A(i) intercambiar(A(i),A(j)) end if end for End for

(3) (4) (5) (6) (7)

El costo del algoritmo se va a calcular suponiendo que C1 es el costo de efectuar la comparación y que C2 es el costo de efectuar intercambiar.

Universidad de Ciencias y Humanidades Algebra Computacional

9

Luego tenemos en el peor de los casos: n −1 ⎛

⎜ f (n) = ⎜⎜ i =1 ⎝

⎞ ⎟ ( C1 + C 2 ) ⎟ ⎟ j =i +1 ⎠ n

∑ ∑

………………………….………………………………………………………………………………………… ………………………….………………………………………………………………………………………..

Universidad de Ciencias y Humanidades Algebra Computacional

10

NOTACIÓN O La notación O es usada para estimar el número de operaciones que realiza un algoritmo a medida que la entrada crece. Con la ayuda de esta notación podemos determinar si es práctico usar un algoritmo particular para solucionar un problema a medida que la entrada aumenta. Por ejemplo si tenemos dos algoritmos que resuelven un problema usando 100n2 +17n+4 operaciones otro n3 operaciones, la notación O nos ayuda a ver que el primero de ellos realiza menos operaciones cuando n es grande.

Definición.Sean f y g dos funciones del conjunto de los enteros o de los reales en el conjunto de los reales. Decimos que f(x) es O(g(x)) si existen constantes C y k tales que |f(x)|≤C|g(x)| siempre que x>k Universidad de Ciencias y Humanidades Algebra Computacional

11

Ejemplo 1.Demuestre que f(n)=n2+2n +1 es O(n2) Solución: Observamos que podemos estimar el tamaño de f(n) cuando n>1 y 11 por tanto 0≤n2+2n+1≤n2+2n2+n2=4n2 Siempre que n>1, por consiguiente podemos tomar C=4 y k=1 Para mostrara que f(n) es O(n2). Es decir f(n)=n2+2n+1<4n2 siempre que n>1

Universidad de Ciencias y Humanidades Algebra Computacional

12

Ejemplo 2.¿Cómo se puede utilizar la notación O para estimar la suma de los primeros n enteros positivos? Solución: Tenemos que: 1≤n 2≤n.. Y asi hasta obtener 1+2+…+n ≤ n+n+…+n=n2 De esto se obtiene que 1+2+3+…+n es de O(n2)

Universidad de Ciencias y Humanidades Algebra Computacional

13

COMPLEJIDADES MAS USADAS

Universidad de Ciencias y Humanidades Algebra Computacional

14

Universidad de Ciencias y Humanidades Algebra Computacional

15

CONCLUSIONES ● Los algoritmos no son algo tan lejano como se podría pensar (¿Al salir de casa y llegar a la UCH usamos un algoritmo?) ● Se utilizan para prácticamente cualquier tarea, no sólo para los ordenadores ( máquinas expendedoras de gaseosas) ● Existen multitud de algoritmos, adaptados para cada situación específica. (Para los cajeros de bancos) ● Cada día se inventan nuevos algoritmos para cubrir nuevos problemas. ¿Por qué medimos la complejidad? Para determinar que algoritmo es mejor dentro de una familia de algoritmos que resuelven el mismo problema. ¿Qué medimos? Coste Temporal y Coste Espacial

Universidad de Ciencias y Humanidades Algebra Computacional

16

EJERCICIOS COMPLEMENTARIOS 1) Cree un programa iterativo para hallar el factorial de n y halle su complejidad algorítmica. 2) Cree un programa recursivo para hallar el factorial de n y halle su complejidad algorítmica. 3) Cree un algoritmo para hallar el menor entero de una lista de números.

Universidad de Ciencias y Humanidades Algebra Computacional

17