5 estrategiasalgoritmicas parte2 publicar2

1PROCESO DE ADMISIÓN 2019

Centro de Investigación y de Estudios Avanzados del Instituto Politécnico NacionalCinvestav - Tamaulipas

Tema:

Estrategias Algorítmicas - Parte 2

Dr. Mario Garza Fabre


Parte 1:

• Introducción

• Algoritmos voraces

• Búsqueda sistemática (Búsqueda exhaustiva, Búsqueda con retroceso, Ramificación y poda)

Parte 2:

• Divide y vencerás / Decrementa y vencerás

Parte 3:

• Programación dinámica

• Resumen y comentarios finales

Contenido


Divide y Vencerás


Filosofía general para resolver problemas (en diversos ámbitos) y posiblemente la técnica más conocida y aplicable para el diseño de algoritmos eficientes.

Divide y Vencerás (Divide-and-Conquer)

Consiste en descomponer un problema en varios subproblemas más pequeños, resolver recursivamente estos subproblemas, y finalmente combinar las soluciones a los subproblemas para construir la solución al problema original.



El paradigma Divide y Vencerás involucra tres pasos en cada nivel de la recursión:

1. Dividir: el problema se divide en subproblemas, es decir, problemas similares pero más pequeños

2. Vencer: los subproblemas son resueltos recursivamente. Si el subproblema es suficientemente pequeño, se resuelve directamente (caso base/trivial)

3. Combinar: las soluciones a los subproblemas se combinan para resolver el problema original



Ilustrando los pasos del paradigma Divide y Vencerás:

Problema

SoluciónProblema

Dividir

Vencer

Combinar

SubproblemaSubproblema

SoluciónSubproblema




Ilustrando los pasos del paradigma Divide y Vencerás:

Problema

SoluciónProblema

Dividir

Vencer

Combinar




Problema

SoluciónProblema

Dividir

Vencer

Combinar




Problema

SoluciónProblema

Dividir

Vencer

Combinar




Solución recursiva de subproblemas



Más formalmente:

• Sea ! el tamaño del problema, y S(!) el problema

• S(!) se descompone en una colección de %subproblemas S !& , S !( , … , S(!*), donde !+ < !, para - ∈ 1, 2, … , 1

• S !& , S !( , … , S(!*) se resuelven recursivamente

• Se resuelve S(!) al combinar las soluciones obtenidas para S !& , S !( , … , S(!*)


• S " : ordenar secuencia

de tamaño "

• Dividir: divide en

S "# y S "% , donde

"# = ⁄" % y "% = ⁄" %

• Vencer: resuelve

S "# y S "%recursivamente

• Combinar: mezclar

ordenadamente las soluciones de S "# y S "%

Ejemplo:

Ordenamiento por mezcla (merge sort)


Análisis del Ordenamiento por Mezcla y comentarios:

• Ordenamiento por mezcla es un ejemplo claro del enfoque Divide y Vencerás

• Complejidad O(n log n): en cada paso se divide el problema a la mitad, pero combinar las soluciones a los subproblemas es una tarea de complejidad O(n)

• Asintóticamente más eficiente que otros algoritmos como el Ordenamiento Burbuja y por Inserción (O(n!))

Ejemplo:

Ordenamiento por mezcla (merge sort)


Ejercicio:

• Implementar algoritmo de Ordenamiento por Mezcla

• Utilizar cualquier lenguaje de programación


Tenemos ! discos apilados, en orden decreciente de tamaño, en uno de los tres postes. El objetivo es trasladar

los discos a otro poste respetando las siguientes reglas:

• Sólo se puede mover un disco a la vez

• Un disco no puede colocarse sobre otro más pequeño

• Sólo se puede mover el disco superior de cada poste

Ejemplo:

Torres de Hanoi


Ejemplo:

Torres de Hanoi¿Cómo resolver siguiendo el enfoque Divide y Vencerás?

Consideremos un ejemplo pequeño, en el que tenemos

! = # discos y queremos moverlos del poste A al B:

Subproblema 1Estado inicial

Subproblema 2 Subproblema 3

Subproblemas:

1. Mover disco pequeño a poste auxiliar

2. Mover disco grande a poste destino

3. Mover disco pequeño a poste destino


Ejemplo:

Torres de Hanoi

¡Podemos generalizar para el caso de ! discos!

Descomponemos en subproblemas:

1. Mover los !− # discos más pequeños desde el poste origen al poste auxiliar (resolver recursivamente)

2. Mover !-ésimo disco desde el poste origen al poste destino

3. Mover los !− # discos más pequeños desde el poste auxiliar al poste destino (resolver recursivamente)


Ejemplo:

Torres de Hanoi

Análisis del algoritmo Divide y Vencerás, comentarios:

• Resuelve con mínimo número de movimientos

• Movimientos para un total de ! discos: "! − $

• Por lo tanto, la complejidad del algoritmo es

exponencial: % "!


Ejercicio:

• Implementar algoritmo de Divide y Vencerás para resolver el problema de las Torres de Hanoi



Decrementa y Vencerás (Decrease-and-Conquer)

Algunos autores consideran que “Divide y Vencerás” es un término que debe reservarse únicamente para casos en los que el problema se descompone en ! ≥ # subproblemas.

Se ha propuesto el término “Decrementa y Vencerás” para referirse a escenarios donde el problema se resuelve mediante la solución de un único subproblema, ! = %.

El enfoque Decrementa y Vencerás reduce el problema a una versión más pequeña del mismo, la resuelve (recursivamente), y extiende esta solución para resolver el problema original.

También: enfoque incremental, inductivo o de simplificación.


Decrementa y Vencerás (Decrease-and-Conquer)

Decrementa y Vencerás involucra tres pasos en cada nivel de la recursión:

1. Reducir: identificar una instancia más pequeña del problema

2. Vencer: resolver recursivamente instancia pequeña del problema

3. Extender: aprovechar solución de la instancia pequeña para obtener solución al problema original

Problema

Subproblema


SoluciónProblema

Reducir

Vencer

Extender


Factorial de un número !:

!! = 1 × 2 × … × ( − 1 × ( = *+,-

!+

Relación de recurrencia:

!! = .-, ! = 0! × !− - !, ! > 0Recursivamente, el problema se

resuelve a través de la solución de una instancia más pequeña.

Ejemplo:

Factorial de un Número

Reducir

Vencer

Extender

5!

4!

3!

2!

1!

0!

1

1 x 1 = 1

2 x 1 = 2

3 x 2 = 6

4 x 6 = 24

5 x 24 = 120


Por ejemplo:

Ejercicio:• Determinar relación de recurrencia (definición recursiva)

• Implementar en cualquier lenguaje de programación

Dada una base ! y un

exponente ":

!" =$%&'

(!

Ejemplo:

Potenciación


Ejercicio:

• Investigue cómo resolver utilizando el algoritmo de Potenciación Binaria (o por Cuadrados)

• Implemente el algoritmo de Potenciación Binaria (o por Cuadrados) en el lenguaje de programación de su elección

• Observar el número total de multiplicaciones que el algoritmo realiza en comparación con las ! − #multiplicaciones del enfoque “tradicional”


Análisis de algoritmos Decrementa y Vencerás para !":

• El planteamiento recursivo “tradicional” realiza en total " − $ multiplicaciones. Por lo tanto, resulta en un algoritmo de complejidad lineal, % "

• Algoritmo de Potenciación Binaria (o por Cuadrados), de complejidad% &'( " , representa una estrategia mucho más eficiente

Ejemplo:

Potenciación


Problema: Buscar un elemento dado en un arreglo ordenado de valores.

Búsqueda binaria: Comparar elemento central con el valor buscado. Si son iguales, la búsqueda termina (devolver posición). Si son distintos, la búsqueda continua (recursivamente) en la primera o segunda mitad del arreglo, quedando descartada la otra mitad.

Ejemplo:

Búsqueda Binaria

En cada nivel de recursión, el tamaño del problema queda reducido a la "mitad”:

Complejidad ! "#$ %


Ejercicio:

• Implementar el algoritmo de Búsqueda Binaria



Ejemplo:

Búsqueda de Raíces

Un problema frecuente en ingeniería es el de encontrar las raíces de ecuaciones de la forma ! " = $, donde ! " es una función real de una variable ".

Por ejemplo, para la ecuación ! " = %"% − " − ' = $

las raíces son:

• 1.850781059

• -1.350781059


El Método de Bisección es uno de los métodos numéricos más sencillos para resolver, de forma aproximada, ecuaciones en una variable.

Dado un intervalo inicial que contenga alguna raíz de la ecuación, este intervalo se divide sucesivamente a la mitad y se busca en el subintervalo que contiene la raíz.

Ejemplo:

Búsqueda de Raíces: Método de Bisección

Teorema de Bolzano: sea ! una función continua en ", $ , con ! " y ! $ de signos contrarios. Entonces existe % dentro de ", $ tal que ! % = '.


Ejemplo:

Búsqueda de Raíces: Método de Bisección

! "

"#$

%$

1. Elegir intervalo inicial #$, %$ tal que ! #$ ! %$ < $

2. Calcular ($ =#$*%$

+y ! ($ . Si

! ($ = $ detener (($ es la raíz)

3. Si ! ($ ≠ $ determinar nuevo subintervalo #-, %- :a. Si . /0 . 10 < 0: #- = #$, %- = ($

b. Si . 30 . 10 < 0: #- = ($, %- = %$

4. Repetir (2) y (3) hasta alcanzar la precisión deseada o anchura predeterminada de #4, %4

5. Producir resultado: (4 =#4*%4

+

Algoritmo

Método de

Bisección


Ejercicio:

• Implemente el Método de Bisección en el lenguaje de programación de su elección (usando recursividad)

• Utilice su programa para encontrar una aproximación a la raíz de las siguientes ecuaciones:

• En todos los casos, detener la búsqueda cuando se encuentre un valor ! tal que " ! ≤ $. $$$&

Ecuación Intervalo inicial Raíz

" ! = (!( − ! − * = $ [-2, 1] x = -1.35078

" ! = !( − ! − & = $ [1, 2]

" ! = !+ + (!( + &$! − ($ = $ [-1, 2]

" ! = !+ − !( + ( = $ [-200, 300]

" ! = !( − - [-1, 1]


Sucesión de Fibonacci: (0, ) 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …

Relación de recurrencia: f! = f!#$+ f!#%, con f& = & y f$ = $

• Programar función recursiva f(n) para calcular el n-ésimo

número de Fibonacci (cualquier lenguaje de programación)

• Calcular f(10)

• ¿Cuántas veces se ejecuta f(i), para 1 ≤ i ≤ 10?

• ¿Cuántas veces en total se invocó a la función f?

• ¿Cuántas operaciones de suma se realizaron en total?

• Repetir para f(20). ¿Observaciones?

Ejercicio:


• Para resolver un problema: dividir en subproblemas, resolver (vencer) recursivamente, combinar soluciones

o Decrementa y Vencerás: reducir a instancia pequeña, resolver (vencer) recursivamente, extender solución

• Técnica que permite el diseño de algoritmos eficientes (merge sort, búsqueda binaria, potenciación, …)

o Para lograrlo, es importante que los subproblemas sean independientes (no solapamiento/traslape entre ellos)

o De lo contrario, el tiempo de ejecución puede ser exponencial debido a la repetición de cálculos

Divide y Vencerás (Comentarios)


Ejercicios Adicionales:

• Investigar cómo se aplica el diseño Divide y Vencerás (o Decrementa y Vencerás) para resolver problemas adicionales, por ejemplo:

o Problema de encontrar par de puntos más cercanos

o Algoritmo de ordenamiento Quicksort

o Algoritmo de Karatsuba para multiplicar números grandes

o Algoritmo de Euclides para calcular máximo común divisor

o Algoritmo de Strassen para multiplicación de matrices

• ¿Qué ventajas ofrece este diseño algorítmico?

• Implementar algunos de estos algoritmos en el lenguaje de programación de su preferencia


Estrategias Algorítmicas

- Fin de la Parte 2 -

5 estrategiasalgoritmicas parte2 publicar2

Documents