Dividir y conquistar

Introducci´n
o
Esquema de la t´cnica
e
Eficiencia de los algoritmos
Ejemplo 1
Ejemplo 2
B´squeda Binaria
u
Mergesort
Quicksort
Ejercicio

Cap´
ıtulo 2: Paradigmas:
Divide and Conquer
Carlos G´mez-Pantoja
o
Universidad Andr´s Bello
e

Oto˜o, 2013
n

Carlos G´mez-Pantoja Universidad Andr´s Bello
o
e

Cap´
ıtulo 2: Paradigmas: Divide and Conquer

Introducci´n
oEsquema de la t´cnica
e
Eficiencia de los algoritmos
Ejemplo 1
Ejemplo 2
B´squeda Binaria
u
Mergesort
Quicksort
Ejercicio

Tabla de Contenidos
1

Introducci´n
o

2

Esquema de la t´cnica
e

3

Eficiencia de los algoritmos

4

Ejemplo 1

5

Ejemplo 2

6

B´squeda Binaria
u

7

Mergesort

8

Quicksort

9

Ejercicio
Carlos G´mez-Pantoja Universidad Andr´sBello
o
e

Cap´
ıtulo 2: Paradigmas: Divide and Conquer

Introducci´n
o
Esquema de la t´cnica
e
Eficiencia de los algoritmos
Ejemplo 1
Ejemplo 2
B´squeda Binaria
u
Mergesort
Quicksort
Ejercicio

Introducci´n
o

Popularmente, divide y vencer´s (conquista o reinar´s), hace
a
a
referencia a un refr´n que implica resolver un problema dif´
a
ıcil,
dividi´ndolo en partes m´ssimples tantas veces como sea
e
a
necesario, hasta que la resoluci´n de las partes se torna obvia.
o
La soluci´n del problema principal se construye con las
o
soluciones encontradas.

Carlos G´mez-Pantoja Universidad Andr´s Bello
o
e

Cap´
ıtulo 2: Paradigmas: Divide and Conquer

Introducci´n
o
Esquema de la t´cnica
e
Eficiencia de los algoritmos
Ejemplo 1
Ejemplo 2
B´squedaBinaria
u
Mergesort
Quicksort
Ejercicio

Introducci´n
o
En las ciencias de la computaci´n, el t´rmino divide y
o
e
conquista (DyC) hace referencia a uno de los m´s importantes
a
paradigmas de dise˜o algor´
n
ıtmico.
El m´todo [2] est´ basado en la resoluci´n recursiva de un
e
a
o
problema dividi´ndolo en dos o m´s subproblemas de igual tipo
e
a
o similar.
El procesocontin´a hasta que ´stos llegan a ser lo
u
e
suficientemente sencillos como para que se resuelvan
directamente.
Al final, las soluciones a cada uno de los subproblemas se
combinan para dar una soluci´n al problema original.
o

Carlos G´mez-Pantoja Universidad Andr´s Bello
o
e

Cap´
ıtulo 2: Paradigmas: Divide and Conquer

Introducci´n
o
Esquema de la t´cnica
e
Eficiencia de losalgoritmos
Ejemplo 1
Ejemplo 2
B´squeda Binaria
u
Mergesort
Quicksort
Ejercicio

Introducci´n
o
El uso de DyC data de la antigua Babilonia en el 200 A.C. [4].
Es la b´squeda binaria, donde el problema original es partido
u
sucesivamente en subproblemas simples de m´s o menos la mitad del
a
tama˜o [4].
n
Una descripci´n del algoritmo en computador apareci´ en 1946 en un
o
o
art´
ıculode John Mauchly [4].
Otro ejemplo antiguo de algoritmo de DyC con m´ltiples subproblemas es
u
la descripci´n realizada por Gauss en 1805 de lo que se le llama ahora
o
algoritmo de la r´pida transformaci´n de Fourier-Cooley-Tukey (FFT) [3].
a
o
Otro problema antiguo de 2 subdivisiones de DyC fue espec´
ıficamente
desarrollado para computadores y analizado adecuadamente es el
algoritmo deMerge-Sort, inventado por John von Neumann en 1945 [4].
Carlos G´mez-Pantoja Universidad Andr´s Bello
o
e

Cap´
ıtulo 2: Paradigmas: Divide and Conquer

Introducci´n
o
Esquema de la t´cnica
e
Eficiencia de los algoritmos
Ejemplo 1
Ejemplo 2
B´squeda Binaria
u
Mergesort
Quicksort
Ejercicio

Esquema de la t´cnica
e

Descomponer el caso a resolver en subcasos m´s peque˜os dela
n
mismo problema.
Resolver independientemente cada subcaso.
Combinar los resultados para construir la soluci´n del caso
o
original.
Este proceso se suele aplicar recursivamente.
La eficiencia de esta t´cnica depende de c´mo se resuelvan los
e
o
subcasos.

Carlos G´mez-Pantoja Universidad Andr´s Bello
o
e

Cap´
ıtulo 2: Paradigmas: Divide and Conquer

Introducci´n
o...