Aaaaaaaaa
Páginas: 4 (804 palabras)
Publicado: 28 de noviembre de 2011
Divide y vencerás
Introducción La búsqueda dicotómica La ordenación por fusión El algoritmo de ordenación de Hoare Algoritmos de selección y de búsqueda de la medianaMultiplicación de enteros grandes Potenciación de enteros Introducción a la criptografía Multiplicación de matrices Calendario de un campeonato
2 8 13 15 18 22 29 36 47 52
J. Campos - C.P.S. Esquemasalgorítmicos - Divide y vencerás Pág. 1
El esquema divide y vencerás: Introducción
Técnica de diseño de algoritmos “divide y vencerás”:
– descomponer el ejemplar a resolver en un ciertonúmero de subejemplares más pequeños del mismo problema; – resolver independientemente cada subejemplar; – combinar los resultados obtenidos para construir la solución del ejemplar original. aplicar estatécnica recursivamente
J. Campos - C.P.S. Esquemas algorítmicos - Divide y vencerás Pág. 2
El esquema divide y vencerás: Introducción
Esquema genérico:
función divide_y_vencerás(x:tx)devuelve ty función divide_y_vencerás(x:tx) devuelve ty variables x1,…,xk:tx; y1,…,yk:ty variables x1,…,xk:tx; y1,…,yk:ty principio principio si x es suficientemente simple si x es suficientemente simpleentonces devuelve solución_simple(x) entonces devuelve solución_simple(x) sino sino descomponer x en x1,… ,xk; descomponer x en x1,… ,xk; para i:=1 hasta k hacer para i:=1 hasta k haceryi:=divide_y_vencerás(xi) yi:=divide_y_vencerás(xi) fpara; fpara; devuelve combinar(y1,…,yk) devuelve combinar(y1,…,yk) fsi fsi fin fin
Si k=1, el esquema anterior se llama técnica de reducción.
J.Campos - C.P.S. Esquemas algorítmicos - Divide y vencerás Pág. 3
El esquema divide y vencerás: Introducción
Sobre el coste computacional:
– Sea un algoritmo A que emplea un tiempo cuadrático. –Sea c una constante tal que una implementación particular de A emplea un tiempo tA(n)≤cn2 para un ejemplar de tamaño n. – Supongamos que A se puede descomponer en tres subejemplares de tamaño...
Introducción La búsqueda dicotómica La ordenación por fusión El algoritmo de ordenación de Hoare Algoritmos de selección y de búsqueda de la medianaMultiplicación de enteros grandes Potenciación de enteros Introducción a la criptografía Multiplicación de matrices Calendario de un campeonato
2 8 13 15 18 22 29 36 47 52
J. Campos - C.P.S. Esquemasalgorítmicos - Divide y vencerás Pág. 1
El esquema divide y vencerás: Introducción
Técnica de diseño de algoritmos “divide y vencerás”:
– descomponer el ejemplar a resolver en un ciertonúmero de subejemplares más pequeños del mismo problema; – resolver independientemente cada subejemplar; – combinar los resultados obtenidos para construir la solución del ejemplar original. aplicar estatécnica recursivamente
J. Campos - C.P.S. Esquemas algorítmicos - Divide y vencerás Pág. 2
El esquema divide y vencerás: Introducción
Esquema genérico:
función divide_y_vencerás(x:tx)devuelve ty función divide_y_vencerás(x:tx) devuelve ty variables x1,…,xk:tx; y1,…,yk:ty variables x1,…,xk:tx; y1,…,yk:ty principio principio si x es suficientemente simple si x es suficientemente simpleentonces devuelve solución_simple(x) entonces devuelve solución_simple(x) sino sino descomponer x en x1,… ,xk; descomponer x en x1,… ,xk; para i:=1 hasta k hacer para i:=1 hasta k haceryi:=divide_y_vencerás(xi) yi:=divide_y_vencerás(xi) fpara; fpara; devuelve combinar(y1,…,yk) devuelve combinar(y1,…,yk) fsi fsi fin fin
Si k=1, el esquema anterior se llama técnica de reducción.
J.Campos - C.P.S. Esquemas algorítmicos - Divide y vencerás Pág. 3
El esquema divide y vencerás: Introducción
Sobre el coste computacional:
– Sea un algoritmo A que emplea un tiempo cuadrático. –Sea c una constante tal que una implementación particular de A emplea un tiempo tA(n)≤cn2 para un ejemplar de tamaño n. – Supongamos que A se puede descomponer en tres subejemplares de tamaño...
Leer documento completo
Regístrate para leer el documento completo.