Aaaaaaaaa

Solo disponible en BuenasTareas
  • Páginas : 4 (804 palabras )
  • Descarga(s) : 0
  • Publicado : 28 de noviembre de 2011
Leer documento completo
Vista previa del texto
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...
tracking img