ALGORÍTMICAIngeniería Técnica en Informática de Gestión y de Sistemas

curso 2002-2003

Teoría: Domingo GiménezSeminario C: José María RodríguezPrácticas Gestión: Joaquín Cervera

Prácticas Sistemas: Domingo Giménez

TEMARIO

Valor en la puntuación final

Análisis de algoritmos 3Diseño de algoritmos:

Divide y vencerás 2Algoritmos voraces 1Programación Dinámica 1Backtracking 2Branch & Bound 1

BIBLIOGRAFÍA

• Brassard, Bratley: Fundamentos de algoritmos. (estudio por paradigmas)

• Cormen, Leiserson, Rivest: Introduction to Algorithms. The MIT Press. 1990. (estudio por problemas)

• Apuntes de la asignatura (estudio por paradigmas) en: servinf.dif.um.es/˜domingoTambién: enlaces a otros cursos,

exámenes resueltos

PRÁCTICAS

• Seminario de C: octubre-noviembrelaboratorio 1.2lunes, jueves 11:30-13:30

• Prácticas: laboratorio 1.2,martes 8:30-10:30jueves 9:30-11:30

laboratorio 1.3,martes 16:30-18:30martes 18:30-20:30viernes 18:30-20:30

EVALUACIÓN• Examen de teoría 7.5 (mínimo de 2.5 / 7.5) Prácticas 2.5 (mínimo de 1.25 / 2.5)• En convocatoria de febrero se puede optar por:

examen de teoría 5 (mínimo 1.75 / 5)prácticas 5 (mínimo 2.5 / 5)

entregando las prácticas en los plazos establecidos,revisándolas y obteniendo evaluación positiva,no habría que examinarse de las partes correspondientes:

divide y vencerásprogramación dinámicabacktracking

• Se puede aprobar la teoría y la práctica por separado o quedar pendiente de prácticas (hasta septiembre de 2003).

Introducción: ALGORÍTMICA

• Estudia:

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

› 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áticoAlgoritmo en lenguaje natural

Tipo abstracto de datosPrograma en seudolenguaje

Estructura de datosPrograma 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?