SLIDES - Tecnología Digital V Diseño de Algoritmos (4)

Vista previa del material en texto

DIVIDE AND CONQUER
Tecnología Digital V: Diseño de Algoritmos
Universidad Torcuato Di Tella
Divide and conquer
# La técnica divide and conquer (divide y vencerás) es una idea para
diseñar algoritmos recursivos.
# Un algoritmo divide and conquer divide recursivamente el problema en
dos o más subproblemas del mismo tipo (o similar), hasta que los
subproblemas son tan pequeños que se pueden resolver directamente.
# Una vez hecho esto, las soluciones de los subproblemas se combinan
para obtener una solución del problema original.
# Esta técnica es la base de algoritmos eficientes para muchos problemas,
como ordenamiento de arreglos, multiplicación de números grandes, y
el cálculo de la transformada discreta de Fourier, entre otros.
TD5: Diseño de Algoritmos - UTDT 2
Divide and conquer
# Si la instancia � de entrada es pequeña, entonces utilizar un algoritmo ad
hoc para el problema.
# En caso contrario:
1. Dividir � en sub-instancias �1 , �2 , . . . , �: más pequeñas.
2. Resolver recursivamente las : sub-instancias.
3. Combinar las soluciones para las : sub-instancias para obtener una solución
para la instancia original �.
Dos de los algoritmos de ordenamiento más eficientes están basados en divide and
conquer: quicksort (Hoare, 1960) y mergesort (von Neumann, 1945).
Tony Hoare (1934–) John von Neumann (1903–1957)
TD5: Diseño de Algoritmos - UTDT 3
Ejemplo: Quicksort
# El algoritmo quicksort para ordenar un arreglo es un ejemplo de un
algoritmo basado en divide and conquer.
# Si el arreglo es grande:
1. Seleccionar un elemento G del arreglo (llamado el pivote).
2. Permutar el arreglo para que queden primero los elementos menores o
iguales a G, luego el mismo G y finalmente los elementos mayores que G.
3. Recursivamente aplicar el mismo procedimiento sobre las dos “mitades” del
arreglo.
# Si el arreglo es pequeño, ordenar por cualquier método sencillo (o
incluso no hacer nada si tiene menos de dos elementos).
TD5: Diseño de Algoritmos - UTDT 4
Ejemplo: Mergesort
# El algoritmo mergesort es similar a quicksort, con la diferencia de que no
hay trabajo previo a la recursión, y en cambio se debe trabajar para
combinar las soluciones de los dos subproblemas.
# Si el arreglo es grande:
1. Dividir el arreglo en dos mitades.
2. Ordenar recursivamente cada mitad.
3. Combinar las dos mitades ordenadas para obtener los elementos del arreglo
completo ordenados (apareo de arreglos).
# Si el arreglo es pequeño, ordenar por cualquier método sencillo.
TD5: Diseño de Algoritmos - UTDT 5
Motivación
Problema
Tenemos datos históricos de una acción ($MELI en este caso).
# Para un rango de fechas, conocemos su valor de cierre en el mercado.
# Asumimos que podemos comprar una acción en un día al valor de cierre
del anterior y venderla en una fecha posterior.
# Buscamos hacer un análisis de cuál hubiese sido la ganancia máxima
(independientemente del tiempo invertido).
TD5: Diseño de Algoritmos - UTDT 6
Análisis preliminar
No podemos asumir que el
máximo ocurre después del
mínimo.
No podemos asumir que la
mayor ganancia ocurre en el
máximo o en el mínimo.
Pregunta
# Cómo sería un algoritmo de fuerza bruta para el problema?
# Qué complejidad tiene?
TD5: Diseño de Algoritmos - UTDT 7
Maximum subarray problem
Consideramos los siguientes datos para la acción de MELI para los días
hábiles entre el 10.12.2022 y 26.12.2022
precio 880.25 870.65 867.29 835.09 843.97 884.27 875.90 900.09 873.26 878.32
diff -9.59 -3.35 -32.20 8.88 40.29 -8.36 24.19 -26.83 5.05
El subarray con máxima suma se da entre las posiciones 3 y 6 inclusive, con
un valor aprox. de 65.
TD5: Diseño de Algoritmos - UTDT 8
Maximum subarray problem: divide and conquer
Consideramos el vector de números transformados y tomamos el elemento
medio tomando mid = (low + high)/2
[-9.59 -3.35 -32.20 8.88 40.29 -8.36 24.19 -26.83 5.05]
low mid mid+1 high
Preguntas
# Cómo sería el llamado recursivo?
# Cuál es el caso base?
# Qué puede pasar con el máximo subarray en función de la recursión
planteada?
# Cuál es la respuesta final?
TD5: Diseño de Algoritmos - UTDT 9
Maximum subarray problem: divide and conquer
# El máximo subarray puede estar contenido en el llamado recursivo
A[low,...,mid].
[low . . . mid mid+1 . . . high]
# El máximo subarray puede estar contenido en el llamado recursivo
A[mid+1,...,high].
[low . . . mid mid+1 . . . high]
# El máximo subarray puede cruzar el punto medio mid.
[low i . . . mid mid+1 . . . j high]
En este caso, es necesario encontrar el máximo subarray que cruza por el
punto medio mid.
Pregunta
Cómo encontramos el subarray de máxima suma que cruza el punto medio
mid?
TD5: Diseño de Algoritmos - UTDT 10
Maximum subarray problem: divide and conquer
FindMaxCrossingSubarray(A, low, mid, high)
suma_izq = −∞, suma = 0, izq = null ⊲ Inicializamos variables
for (i = mid; i >= low; i–) do
suma = suma + A[i]
if suma > suma_izq then ⊲ Actualizamos si mejora la suma.
suma_izq = sum
izq = i
end if
end for
suma_der = −∞, suma = 0, der = null ⊲ Inicializamos variables
for (i = mid; i <= high; i++) do
suma = suma + A[i]
if suma > suma_der then ⊲ Actualizamos si mejora la suma.
suma_der = sum
der = i
end if
end for
return (izq, der, suma_izq + suma_der) ⊲ Devolvemos los índices y el valor
TD5: Diseño de Algoritmos - UTDT 11
Maximum subarray problem: divide and conquer
FindMaximumSubarray(A, low, high)
if high == low then ⊲ Caso base.
return (low, high, A[low])
else
mid = (low + high)//2 ⊲ Recursión y caso particular.
l_low, l_high, l_sum = FindMaximumSubarray(A, low, mid)
r_low, r_high, r_sum = FindMaximumSubarray(A, mid+1, high)
c_low, c_high, c_sum = FindMaxCrossingSubarray(A,low, mid, high)
if l_sum >= r_sum and l_sum >= c_sum then
return (l_low, l_high, l_sum) ⊲ Rta. en lado izquierdo
else if r_sum >= l_sum and r_sum >= c_sum then
return (r_low, r_high, r_sum) ⊲ Rta. en lado derecho
else
return (c_low, c_high, c_sum) ⊲ Rta. cruza mid
end if
end if
TD5: Diseño de Algoritmos - UTDT 12
Análisis de complejidad
Pregunta
# Qué complejidad computacional tiene FindMaximumSubarray?
# Qué complejidad computacional tiene FindMaxCrossingSubarray?
0. Caso base: Si � tiene longitud 0 o 1, no hacer nada. $(1)
1. Dividir: Partir � en 2 sublistas de longitud ∼ =
2
. $(1)
2. Conquistar: Calcular el máximo subarray recursivamente en cada
sublista. 2)( =
2
)
3. Combinar:
◦ Calcular FindMaxCrossingSubarray.
◦ Retornar el máximo entre los subarrays.
TD5: Diseño de Algoritmos - UTDT 13
Análisis de complejidad
FINDMAXIMUMSUBARRAY
)(=) =
{
$(1) si = = 1
2)( =
2
) + $(=) si = > 1.
Queremos ver que )(=) ∈ $(= log(=)).
)(=) = 2)(=
2
) + $(=)
= 2)(=
2
) + 2 · =
= 2(2)(=
4
) + 2 · =
2
) + 2 · =
= 4)(=
4
) + 2 · 2 · =
= 4(2)(=
8
) + 2 · =
4
) + 2 · 2 · =
= 8)(=
8
) + 3 · 2 · =
. . .
= 2: · )( =
2
:
) + : · 2 · =
TD5: Diseño de Algoritmos - UTDT 14
Análisis de complejidad
# Sabemos que
)(1) = $(1)
# Cuántas veces puedo dividir a = por 2 hasta llegar a 1?
Respuesta: ≈ log
2
=
≈ 2log2(=) × )
(
=
2
log
2
(=)
)
+ log
2
= × 2 × = cuando : ≈ log
2
=
≈ = × )(1) + log
2
= × 2 × = cuando : ≈ log
2
=
= $(=) + $(= log =)
= $(= log =)
# Por lo tanto, FindMaximumSubarray tiene complejidad $(= log =).
TD5: Diseño de Algoritmos - UTDT 15