Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Programación – Método Divide y vencerás




Enviado por Pablo Turmero




    Monografias.com

    1

    Método general
    La técnica divide y vencerás consiste en descomponer el problema en un conjunto de subproblemas más pequeños. Después se resuelven estos subproblemas y se combinan las soluciones para obtener la solución para el problema original.

    Esquema general:
    divide_venceras (p: problema)
    dividir (p, p1, p2, …, pk)
    para i = 1, 2, …, k
    si = resolver (pi)
    solucion = combinar (s1, s2, …, sk)

    Puede ser recursivo siendo “resolver” una nueva llamada a “divide_venceras”
    Si el problema es “pequeño”, entonces se puede resolver de forma directa.

    Ejemplo: Torres de Hanoi

    Monografias.com

    2

    Método general

    Para que pueda aplicarse la técnica divide y vencerás necesitamos:
    El problema original debe poder dividirse fácilmente en un conjunto de subproblemas, del mismo tipo que el problema original pero con una resolución más sencilla (menos costosa).
    La solución de un subproblema debe obtenerse independientemente de los otros.
    Normalmente los subproblemas deben ser de tamaños parecidos. Como mínimo necesitamos que haya dos subproblemas. Si sólo tenemos un subproblema hablamos de técnicas de reducción (o simplificación).
    Necesitamos un método (más o menos directo) de resolver los problemas de tamaño pequeño.
    Es necesario tener un método de combinar los resultados de los subproblemas.

    Monografias.com

    3

    Método general, esquema recursivo
    Normalmente para resolver los subproblemas se utilizan llamadas recursivas al mismo algoritmo (aunque no necesariamente).

    Esquema recursivo (con división en 2 subproblemas):
    divide_venceras (p, q: indice)
    var m: indice
    si pequeño (p, q)
    solucion = solucion_directa (p, q)
    en otro caso
    m = dividir (p, q);
    solucion = combinar (divide_venceras (p, m),
    divide_venceras (m+1, q));

    Monografias.com

    4

    Análisis de tiempos de ejecución
    Para el esquema recursivo, con división en dos subproblemas:
    g(n) Si n?n0 es suficientemente pequeño
    t(n) =
    2*t(n/2) + f(n) En otro caso
    t(n): tiempo de ejecución del algoritmo.
    g(n): tiempo de comprobar si es pequeño y calcular la solución para el caso base
    f(n): tiempo de comprobar si es pequeño y de dividir el problema y combinar los resultados.

    Monografias.com

    5

    Análisis de tiempos de ejecución

    Desarrollando tenemos:
    Suponiendo que n es potencia de 2, n = 2k, y n0 = n/2m.

    Si n0=1, entonces m=k:

    Monografias.com

    6

    Análisis de tiempos de ejecución

    Ejemplo 1. La resolución directa se puede hacer en un tiempo constante y la combinación de resultados también.
    g(n) = c; f(n) = d

    Ejemplo 2. La solución directa se calcula en O(n2) y la combinación en O(n).
    g(n) = c·n2; f(n) = d·n

    Monografias.com

    7

    Análisis de tiempos de ejecución
    Si el problema se divide en a llamadas recursivas de tamaño n/b, y la combinación requiere f(n) = d·n ? O(n), entonces:
    t(n) = a·t(n/b) + d·n
    Suponiendo n = bk ? k = logb n
    t(bk) = a·t(bk-1) + d·bk
    Podemos deducir que:
    O(nlogba) Si a > b
    t(n) ? O(n·log n) Si a = b
    O(n) Si a < b
    Ejemplo 3. Dividimos en 2 trozos de tamaño n/2 (ordenación por mezcla):
    a = b = 2
    t(n) ? O(n·log n)
    Ejemplo 4. Realizamos 4 llamadas recursivas con trozos de tamaño n/2.
    a = 4; b = 2
    t(n) ? O(nlog24) = O(n2)

    Monografias.com

    8

    Búsqueda del máximo y del mínimo
    Método directo:
    MaxMin (A: array [1..N] of tipo; var Max, Min: tipo)
    Max = A[1]
    Min = A[1]
    para i=2, 3, …, N
    si A[i]>Max
    Max = A[i]
    en otro caso si A[i]

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter