Introducción: ALGORITMOS

• Estudia:

Diseño de algoritmos: esquemas para resolver problemas. Divide y vencerás, avance rápido, programación dinámica, Backtracking, Branch & Bound, y otros.

Análisis de algoritmos: recursos necesarios para resolver el problema con el algoritmo elegido. Ocupación de memoria, tiempo de ejecución. De manera que se pueda decidir qué algoritmo es mejor para nuestro problema y entrada.

Introducción: ALGORITMO

• Conjunto de reglas para resolver un problema. Debe ser:

Definible. En seudocódigo, pero pueda dar lugar a un programa.De un conjunto de datos de entrada producir unos datos de salida, en un número finito de pasos (tiempo de ejecución finito). Además debemos diseñar algoritmos eficientes: que el tiempo para acabar sea “razonable”.Determinista si para la misma entrada produce siempre la misma salida. No determinista en caso contrario (redondeos, probabilistas, paralelos, …)

Introducción: PROGRAMACIÓN

Problema real

Modelo matemático

Algoritmo en lenguaje natural

Tipo abstracto de datos

Programa en seudolenguaje

Estructura de datos

Programa ejecutable

modelizaciónEstructura de datos

algorítmica

programación

Estudio de algoritmos

• Se trata de diseñar algoritmos eficientes: que usan pocos recursos:

-memoria-tiempo

-otros (memoria secundaria, tiempo de programación, …)

• Para decidir:

-qué algoritmo programar-qué algoritmo utilizar en resolver un problema para

una cierta entrada -detectar fallo en programa que no funciona bien

Tiempo de ejecución• Se intenta obtener el tiempo de ejecución para un cierto tamaño de entrada, t(n)

• Influyen factores externos al algoritmo: compilador, máquina, programador, …; por lo que normalmente se estudia la forma en que crece t(n), y se utilizan notaciones asintóticas: , O, , o

• Se cuenta el número de operaciones, o las de un cierto tipo, o cada operación afectada de un coste diferente

• Se estudian:Caso más favorable tm(n)Caso más desfavorable tM(n)Tiempo promedio tp(n)

Ej: Cálculo del factorial fact(n):

si n=1devolver 1

en otro casodevolver (fact(n-1)*n)

• tiempo:t(n)=t(n-1)+a=t(n-2)+2*a= ... =t(1)+(n-1)*c

• memoria:m(n)=m(n-1)+c=m(n-2)+2*c= ... =m(1)+(n-1)*c

Ej: Torres de Hanoi

Hanoi(origen,destino,pivote,discos):si discos=1

moveruno(origen,destino)en otro caso

Hanoi(origen,pivote,destino,discos-1)moveruno(origen,destino)Hanoi(pivote,destino,origen,discos-1)

Ej: Torres de Hanoi

Número de movimientos:

t(1)=1t(n)=2t(n-1)+1, si n>1

Expandiendo la recurrencia:

t(n) = 2 t(n-1) +1 = 2 (2t(n-2)+1) +1 = 22 t(n-2) +1+2 = 22 (2t(n-3)+1) +1+2 = 23 t(n-3)+1+2+22

….

2n-1 t(1)+1+2+…+ 2n-2 = 2n-1

Tiempo promedio • tp(n) =

S(n) t() * p()

• Conteo de instrucciones afectadas por probabilidad:

Ej: búsqueda secuencial con centinela

i=0a[n+1]=xrepetir

i=i+1hasta a[i]=x

tp(n)=2+2*p/n+4*p/n+...+2*n*p/n+(2*n+2)*(1-p)=2n+4-p(n+1)

Ej: Algoritmo de Euclides Calcular m.c.d(m,n), con m>n

repetirr = resto(m/n)m = nn = r

hasta r =0mcd = m

t(m,n) = a , si m múltiplo de nt(m,n) = b+t(n,resto(m/n)) , si m no es múltiplo de n

Algoritmos - Estructuras

Grafo Matriz de adyacencia Listas de adyacencia

1 2 3 41 2 1 0 1 1 0 1 2 3 N

2 0 0 1 0 2 3 N4 3 3 0 0 0 0 3 N

4 1 0 1 0 4 1 3 N

Memoria n2 n+a

Inicialización n2 n+a

Grado salida n gs(nodo)

Grado entrada n n+a

Comparación de algoritmos

1.1 fin=false1.2 mientras no fin1.3 fin=true1.4 para i=1,2,…n-11.5 si xi>xi+1

1.6 cambiar1.7 fin=false

2.1 para i=1,2,…,n-12.2 para j=i+1,…,n2.3 si xi>xj

2.4 cambiar

1.1 fin=false1.2 mientras no fin1.3 fin=true1.4 para i=1,2,…n-11.5 si xi>xi+1

1.6 cambiar1.7 fin=false

Caso más favorable:

• Entrada 1,2,3,4:

1.1 , 1.2, 1.3 , 1.4 (i=1) , 1.5 1.4 (i=2) , 1.5 1.4 (i=3) , 1.5 1.4 (sale) 1.2 (sale)Total 11 instrucciones

• Entrada 1,2,…,n:1.1 , 1.2, 1.3 , 1.4 (i=1) , 1.5 1.4 (i=2) , 1.5 … 1.4 (i=n-1) , 1.5 1.4 (sale) 1.2 (sale)Total 2n+3 instrucciones

2.1 para i=1,2,…,n-12.2 para j=i+1,…,n2.3 si xi>xj

2.4 cambiar

Caso más favorable:• Entrada 1,2,3,4:

2.1 (i=1), 2.2 (j=2), 2.3 2.2 (j=3), 2.3 2.2 (j=4), 2.3 2.2 (sale)2.1 (i=2), 2.2 (j=3), 2.3 2.2 (j=4), 2.3 2.2 (sale)2.1 (i=3), 2.2 (j=4), 2.3 2.2 (sale)2.1 (sale)Total 19 instrucciones

• Entrada 1,2,…,n:2.1 (i=1), 2.2 (j=2), 2.3 … 2.2 (j=n), 2.3 2.2 (sale)2.1 (i=2), 2.2 (j=3), 2.3 … 2.2 (j=n), 2.3 2.2 (sale) …2.1 (i=n-1), 2.2 (j=n), 2.3 2.2 (sale)2.1 (sale)Total n2+n-1 instrucciones

1.1 fin=false1.2 mientras no fin1.3 fin=true1.4 para i=1,2,…n-11.5 si xi>xi+1

1.6 cambiar1.7 fin=false

Caso más desfavorable:• Entrada 4,3,2,1:1.1 , 1.2 , 1.3 , 1.4 (i=1) , 1.5 , 1.6 (3421) , 1.7 1.4 (i=2) , 1.5 , 1.6 (3241) , 1.7 1.4 (i=3) , 1.5 , 1.6 (3214) , 1.7 1.4 (sale) 1.2 , 1.3 , 1.4 (i=1) , 1.5 , 1.6 (2314) , 1.7 1.4 (i=2) , 1.5 , 1.6 (2134) , 1.7 1.4 (i=3) , 1.5 1.4 (sale) …¿instrucciones?

2.1 para i=1,2,…,n-12.2 para j=i+1,…,n2.3 si xi>xj

2.4 cambiar Caso más desfavorable:

• Entrada 4,3,2,1:2.1 (i=1), 2.2 (j=2), 2.3 , 2.4 (3421) 2.2 (j=3), 2.3 , 2.4 (2431) 2.2 (j=4), 2.3 , 2.4 (1432) 2.2 (sale)2.1 (i=2), 2.2 (j=3), 2.3 , 2.4 (1342) 2.2 (j=4), 2.3 , 2.4 (1243) 2.2 (sale)2.1 (i=3), 2.2 (j=4), 2.3 , 2.4 (1234) 2.2 (sale)2.1 (sale)¿instrucciones?