david y yolanda

David de Frutos EscrigYolanda Ortega Mallén

Ideas y visualizaciones MatemIdeas y visualizaciones Matemááticas ticas

CCáátedra Miguel de Guzmtedra Miguel de Guzmáán (UCM)n (UCM)

Vamos a hablar de algoritmos...... pero no (sólo) de ciertos

algoritmos,

sino de LOS ALGORITMOS en general.¿Cuáles son esos (posibles) algoritmos?

Algoritmo

= Método automático,

preciso

y general para resolver (todas las instancias) de un problema.

Algoritmo

= Método automático,

preciso

y general para resolver (todas las instancias) de un problema.

Ejemplo (no matemático) paradigmático clásico:

Otros ejemplos de la vida real :

•

Trasladarse cada mañana de casa al trabajo.

•

Resolver un crucigrama.

•

Aprendizaje basado en cursos “virtuales”

•

Hacer un sudoku.

Una receta de cocinaUna receta de cocina

Conceptualmente sencilloAlgoritmos basados en pasos básicos (instrucciones atómicas),que se podrán combinar

mediante un

programa.

Los algoritmos indicarán sin ambigüedad y de un modo claro, en qué ordenhan de ejecutarse las instrucciones.

Los problemas a resolver dependen de unos datos (de entrada) que pertenecen a un dominio “grande”.Queremos evitar mecanismos “mágicos”que resuelven ¡correctamente! un problema sin coste aparente.

√30864197524691358025 =5555555555√30864197524691358025 =5555555555

Tablas trigonométricas o de logaritmosTablas trigonométricas o de logaritmos

100% precisaFinitud vs genericidad ¡potencialmente infinita!Datos: cantidad (finita) de naturales Nk

Cada natural se representa por una secuencia (finita, suficientemente larga) de bits (base 2).Simplificar matemáticamente (sin pérdida de generalidad) usando el isomorfismo: Nk ~ N

Problema (potencialmente algorítmico)función f : Nk Nl

que se desea computar

Problema (potencialmente algorítmico)función f : Nk Nl

que se desea computar

Programación (básica) no estructurada

Programa

= Secuencia

de instrucciones atómicas, numeradas (según el orden de aparición).

Programa

= Secuencia

de instrucciones atómicas, numeradas (según el orden de aparición).

1 : I12 : I2

...n : In

Registros de entradaRegistros de salidaRegistros auxiliares (también preestablecidos)

COPIAR(R,S)INCREMENTAR(R)DECREMENTAR_CONDICIONAL(R,j)Si R

> 0 modificamos R

a R-1,

en caso contrario ir a IjSALTO_INCONDICIONAL(k) Ir a IkTERMINAR

Instrucciones básicas◦

Asignación R := E(R)

Constructores estructurados◦

Secuencia [I1

,...,Ik

]...

V F◦

Condicional

si C entonces I1

si-no I2◦

Bucles repetitivos

repetir I hasta-que C

I1

I1 Ik

Ik

CC

I1

I1 I2

I2

II

CCVF

Programa = Definición inductiva

0! = 1(n + 1) ! = (n + 1) x n!0! = 1(n + 1) ! = (n + 1) x n!

Alonzo ChurchAlonzo Churchpadre del padre del λλ--ccáálculolculo

Un (sencillo) problema no resoluble algorítmicamente.El problema de parada.

TODAS

las formalizaciones (conocidas) del concepto de algoritmo son equivalentes

TODAS

las formalizaciones (conocidas) del concepto de algoritmo son equivalentes

Pero los algoritmos no lo resuelven todo...

|{ f :

Nk N }|

= ω1

|UNk

| = ω0

Robustez del concepto de algoritmo

Algunos algoritmos trabajan demasiado despacio.

vs

Cálculo de determinantes◦

Aplicación de la definición◦

Método de Gauss

Función de Fibonacci: F(0) = F(1) = 1F(n+2) = F(n+1) + F(n)

Pero a veces no se puede hacer más rápido (que se sepa...).Problemas muy difíciles: coste exponencial

Problemas combinatorios

7

34

5

8 21

7

10

¿P = NP?¿P = NP?

Esquemas algorítmicosEsquemas algorítmicos

¿¿IngenierIngenieríía?a?

¿¿Arte?Arte?

Niklaus Wirth, Niklaus Wirth, 19761976

Memoria vs TiempoMemoria vs Tiempo

Encontrar la ficha de un alumnoEncontrar la ficha de un alumno

•Montón de fichas•Secuencia de fichas•Secuencia ordenada de fichas•Árbol binario de búsqueda

Estáticas•

Homogéneas: arrays (vectores, matrices)

•

Heterogéneas: registrosDinámicas•

Secuencias

•

Pilas•

Colas

•

Árboles•

Tablas hash

Descomponer el problema a resolver en una colección de subproblemas más pequeños, resolver estos subproblemas y combinar

los

resultados para obtener la solución del problema original.Los subproblemas son del mismo tipo que el problema original, y se resuelven usando la misma técnica. Algoritmo recursivo.

fun

divide-y-vencerás (x:problema) dev

y:soluciónsi

pequeño(x) entonces

y := método-directo(x)

si no {descomponer x en k≥1problemas más pequeños} <x1

, x2

,…, xk

> := descomponer(x) {resolver recursivamente los subproblemas}

para

j = 1 hasta

k haceryj

:= divide-y-vencerás(xi

) fpara{combinar los yj

para obtener una solución y para x} y := combinar(y1

,…, yk

) fsi

ffun

fun

divide-y-vencerás (x:problema) dev

y:soluciónsi

pequeño(x) entonces

y := método-directo(x)

si no {descomponer x en k≥1problemas más pequeños} <x1

, x2

,…, xk

> := descomponer(x){resolver recursivamente los subproblemas} para

j = 1 hasta

k hacer

yj

:= divide-y-vencerás(xi

) fpara{combinar los yj

para obtener una solución y para x} y := combinar(y1

,…, yk

) fsi

ffun

{ord(V,c,f) ∧ 1 ≤

c ≤

f+1 ≤

n+1}fun

búsqueda-binaria (V[1..n] de ent, x : ent, c, f : nat)

dev

<b:bool, p: nat>si

c > f entonces <b,p> := <falso,c>

si no m := (c+f) div 2 casos

x < V[m] <b,p> := búsqueda-binaria (V,x,c,m-1)☐ x = V[m] <b,p> := <cierto,m>☐ x > V[m] <b,p> := búsqueda-binaria (V,x,m+1,f)fcasos

fsiffun{(b c≤p≤f ∧ V[p]=x) ∨ (¬b c≤p≤f+1 ∧ V[c..p)<x<V[p..f])}

{ord(V,c,f) ∧ 1 ≤

c ≤

f+1 ≤

n+1}fun

búsqueda-binaria (V[1..n] de ent, x : ent, c, f : nat)

dev

<b:bool, p: nat>si

c > f entonces <b,p> := <falso,c>

si no m := (c+f) div 2 casos

x < V[m] <b,p> := búsqueda-binaria (V,x,c,m-1)☐ x = V[m] <b,p> := <cierto,m>☐ x > V[m] <b,p> := búsqueda-binaria (V,x,m+1,f)fcasos

fsiffun{(b c≤p≤f ∧ V[p]=x) ∨ (¬b c≤p≤f+1 ∧ V[c..p)<x<V[p..f])}

fproc

ord-mezclas(V[1..n] de elem, c, f : nat)si

c < f entoncesm := (c+f) div 2ord-mezclas(V,c,m)ord-mezclas(V,m+1,f)mezclar(V,c,m,f)

fsifproc

fproc

ord-mezclas(V[1..n] de elem, c, f : nat)si

c < f entoncesm := (c+f) div 2ord-mezclas(V,c,m)ord-mezclas(V,m+1,f)mezclar(V,c,m,f)

fsifprocfproc

ord-rápida(V[1..n] de elem, c, f : nat)

si

c < f entoncespartir(V,c,f,p) ord-rápida(V,c,p-1)ord-rápida(V,p+1,f)

fsifproc

fproc

ord-rápida(V[1..n] de elem, c, f : nat)si

c < f entoncespartir(V,c,f,p) ord-rápida(V,c,p-1)ord-rápida(V,p+1,f)

fsifproc

≤

V[p] ≥

V[p]V[p]

http://www.youtube.com/watch?v=vxENKlcs2Tw

Conjunto de candidatos para construir la solución.Optimización local: seleccionar en cada etapa el mejor según cierto criterio, sin tener en cuenta elecciones futuras.Cada candidato se trata una sola vez. Las decisiones tomadas nunca se reconsideran.Los algoritmos son sencillos y eficientes.

fun

voraz (datos : conjunto) dev

S : conjuntovar candidatos: conjunto

S := ø

{en S se va construyendo la solución}candidatos := datosmientras candidatos ≠

ø

∧¬es-solución?(S)

hacer

x := seleccionar(candidatos) candidatos := candidatos -

{x}

si

es-factible?(S U {x}) entonces

S := S U {x} fsi

fmientrasffun

fun

voraz (datos : conjunto) dev

S : conjuntovar candidatos: conjunto

S := ø

{en S se va construyendo la solución}candidatos := datosmientras candidatos ≠

ø

∧¬es-solución?(S)

hacer

x := seleccionar(candidatos)candidatos := candidatos -

{x}

si

es-factible?(S U {x}) entonces

S := S U {x} fsi

fmientrasffun

Cuando Alí-Babá consigue por fin entrar en la Cueva de los Cuarenta Ladrones encuentra allígran cantidad de objetos muy valiosos. A pesar de su pobreza, Alí-Babá conoce muy bien el peso y valor de cada uno de los objetos en la cueva. Debido a los peligros que tiene que afrontar en su camino de vuelta, solo puede llevar consigo aquellas riquezas que quepan en su pequeña mochila, que soporta un peso máximo conocido.Suponiendo que los objetos son fraccionables, determinar qué objetos debe elegir Alí-Babá para maximizar el valor total de lo que pueda llevarse en su mochila.

mochila(i,j) = máximo valor que podemos poner en la mochila de peso máximo j considerando los objetos del 1

al i.

mochila(i,j) = máximo valor que podemos poner en la mochila de peso máximo j considerando los objetos del 1

al i.

mochila(i,j) = mochila(i-1,j) si pi

>j

máx{mochila(i-1,j),mochila(i-1,j-pi

)+vi

} si pi

≤j

no coger objeto i coger objeto i

con 1 ≤

i ≤

n, 1 ≤

j ≤

M

casos básicos: mochila(0,j) = 0, 0 ≤

j ≤

Mmochila(i,0) = 0, 0 ≤

i ≤

n

Identificación◦

Especificar la función que representa el problema a resolver.◦

Determinar las ecuaciones recurrentes para calcular dicha función.◦

Comprobar el alto coste de cálculo debido a la repetición de subproblemas a resolver.

Construcción◦

Sustituir la función por una tabla.◦

Inicializar la tabla según los casos base de la función.◦

Sustituir las llamadas recursivas por consultas a la tabla.◦

Planificar un orden adecuado para rellenar la tabla.

Toda solución óptima para una instancia de un problema contiene soluciones óptimas para todas las subinstancias.En una secuencia óptima de decisiones, toda subsecuencia es óptima.

Construir las soluciones por etapas.Búsqueda exhaustiva por el espacio de posibles soluciones hasta encontrar una que satisfaga los criterios exigidos.Impracticable si el espacio de soluciones es muy grande.Estructurar el espacio a explorar para descartar en bloque posibles soluciones no satisfactorias.

En cada nivel se toma la decisión de la etapacorrespondiente.Recorrer el árbol de exploración en cierto orden.

Vuelta atrás: recorrido en profundidad Vuelta atrás: recorrido en profundidad

Ramificación y poda: expande el nodo más prometedor.

Podar

las ramas que no son suficientemente prometedoras.

Ramificación y poda: expande el nodo más prometedor.

Podar

las ramas que no son suficientemente prometedoras.

Para cada nodo se irán generando sus sucesores.◦

Nodo vivo: todavía no se han generado todos sus hijos;◦

Nodo muerto: no puede ser expandido.

Vuelta atrás: recorrido en profundidad; los nodos vivos se gestionan mediante una pila.

Vuelta atrás: recorrido en profundidad; los nodos vivos se gestionan mediante una pila.

Ramificación y poda: expande el nodo vivo más prometedor

los nodos vivos se gestionan mediante una cola con prioridad.

Ramificación y poda: expande el nodo vivo más prometedor

los nodos vivos se gestionan mediante una cola con prioridad.

proc

vuelta-atrás (sol : tupla, k : nat)preparar-recorrido-nivel(k)mientras

¬último-hijo-nivel(k) hacer

sol[k] := siguiente-hijo-nivel(k)si

es-solución?(sol,k) entonces tratar-

solución(sol) sino

si

es-completable?(sol,k) entonces

vuelta-atrás(sol,k+1)fsi

fsifmientras

fproc

proc

vuelta-atrás (sol : tupla, k : nat)preparar-recorrido-nivel(k)mientras

¬último-hijo-nivel(k) hacer

sol[k] := siguiente-hijo-nivel(k)si

es-solución?(sol,k) entonces tratar-

solución(sol)sino

si

es-completable?(sol,k) entonces

vuelta-atrás(sol,k+1)fsi

fsifmientras

fproc

Max Bezzel, Max Bezzel, 18481848

http://www.hbmeyer.de/backtrack/achtdamen/eight.htm#up

Algorithmics: the spirit of computing (3rd Edition), David Harel, Yishai A.Feldman, Addison Wesley 2004The New Turing Omnibus: Sixty-Six Excursions in Computer Science, A.K.Dewdney, Holt Paperbacks 1993Computers Ltd.: What They Really Can't Do, David Harel, Oxford University Press 2000. Revised paperback edition, 2003Introducción a la computación, Narciso Martí Oliet, Miguel Palomino Tarjuelo y José Alberto Verdejo López, Anaya 2006

Fundamentals of data structures with Pascal (4th Edition), Horowitz, E. y Sahni, S., Computer Science Press 1994 Fundamentals of algorithmics, Brassard, G. y Bratley, P., Prentice Hall International 1996. Versión en castellano: Fundamentos de Algoritmia, Prentice Hall, 1997Computer Algorithms (3rd Edition), Horowitz, E., Sahni, S. y Rajasekaran, S., Computer Science Press 1998Introduction to Algorithms (2nd Edition), Cormen, T.H., Leiserson, C.E., Rivest, R.L. y Stein, C. ,The MIT Press 2001

https://campusvirtual.ucm.es:443/SCRIPT/portal-uatducma-5/scripts/serve_homeVedya (Visualización de algoritmos y estructuras de datos)

http://www.fdi.ucm.es/profesor/csegura/