Análise e Técnicas de Algoritmos
Período 2003.2

Divisão-e-Conquista

Divisão e Conquista

Introdução

Esta abordagem de concepção de algoritmos é baseada na estratégia de guerra dos antigos romanos: dividir os inimigos e então conquistar cada pedaço dividido.
Na concepção de algoritmos, a idéia é pegar um problema com um tamanho de entrada grande, dividir a entrada em pedaços menores, resolver cada pedaço e depois combinar os resultados para obter a solução global.
Uma questão que pode surgir: como resolver os pedaços (subproblemas) depois da divisão? A resposta é usar divisão e conquista. O processo termina quando temos pedaços tão pequenos que o problema se torna trivial de resolver.
Em resumo, algoritmos que utilizam uma abordagem baseada na técnica de divisão e conquista consistem de 3 passos básicos:
1. Divisão: Dividir o problema original, em subproblemas menores.
2. Conquista: Resolver cada subproblema recursivamente.
3. Combinação: Combinar as soluções encontradas, compondo uma solução para o problema original.
Um exemplo clássico é o mergesort, algoritmo de ordenação que já foi bastante trabalhado em nosso curso.
- Divisão: Dividir os números a serem ordenados em duas metades.
- Conquista: Ordenar cada metade separadamente.
- Combinação: Fazer o merge das duas metades ordenadas.
Algoritmos baseados em divisão e conquista são, em geral, recursivos. Isso é facilmente explicado uma vez que a parte da conquista utiliza a mesma técnica para resolver os subproblemas.

A maioria dos algoritmos de divisão e conquista divide o problema em subproblemas da mesma natureza, de tamanho . Se for o tempo requerido para decompor o problema em partes iguais e depois combinar o resultado, a complexidade de tempo pode ser determinada pela resolução da seguinte relação de recorrência: .

É possível utilizarmos o Teorema Master para resolver a recorrência.

Além da forma tradicional que vimos quando estudamos resolução de relação de recorrência, o Teorema Master pode ser reescrito da seguinte forma:

Se existir um onde $g(n) \in \Theta(n^k)$ então,

$\begin{displaymath}t(n) \in \left\{ \begin{array}{ll} \Theta(n^k) & \mbox{se $a... ...heta(n^{\log _b^a}) & \mbox{se $a > b^k$} \end{array} \right. \end{displaymath}$

Existe um grande número de problemas computacionais que podem ser resolvidos eficientemente por divisão e conquista. Na verdade, esta é uma das primeiras técnicas (excetuando a solução ingênua ou força bruta) que é tentado para a solução eficiente de um problema.

Entretanto, nem todos os problemas admitem uma solução eficiente por divisão e conquista. Em alguns casos, a solução por divisão-e-conquista apresenta a mesma complexidade assintótica de tempo que a solução ingênua. Em muitos destes casos, porém, ainda é uma estratégia interessante:

Requer um número menor de acessos à memória.
São altamente paralelizáveis. Se existem vários processadores disponíveis, a estratégia propicia eficiência.

Existem três condições que indicam que a estratégia de divisão-e-conquista pode ser utilizada com sucesso:

Deve ser possível decompor uma instância em sub-instâncias.
A combinação dos resultados deve ser eficiente.
As sub-instâncias devem ser mais ou menos do mesmo tamanho.

É possível identificar pelo menos duas situações genéricas em que a abordagem por divisão-e-conquista é adequada:

Problemas onde um grupo de operações são correlacionadas ou repetidas. A multiplicação de matrizes, que veremos a seguir, é um exemplo clássico.
Problemas em que uma decisão deve ser tomada e, uma vez tomada, quebra o problema em peças disjuntas. Em especial, a abordagem por divisão-e-conquiasta é interessante quando algumas peças passam a ser irrelevantes.

Exemplos

Exemplo: Achar Maxim

O problema consiste em encontrar o maior elemento de um array .

Solução Ingênua

$\begin{algorithmic} \STATE \STATE \STATE $max = A[1];$\FOR{i = 2 to n} \IF{A[i] $\rangle$\ max} \STATE max = A[i] \ENDIF \ENDFOR \end{algorithmic}$

A solução ingênua é claramente .

Solução por Divisão e Conquista

Divisão: Dividir o array em duas partes (de mesmo tamanho).
Conquista: Achar o maior valor em cada um dos sub-arrays.
Combinação: Determinar o maior valor entre os dois valores encontrados.

$\begin{algorithmic} \STATE \STATE \STATE {\bf function} Maxim(x, y) \STATE \IF{ ... ...y)/2 + 1, y) \STATE {\bf return} max(max1, max2) \ENDIF \STATE \end{algorithmic}$

A análise do algoritmo que utiliza divisão e conquista requer a solução da seguinte relação de recorrência:

, se $n \leq 2$ .
, caso contrário.

Neste caso, , $g(n) \in \Theta(1)$ . Logo, .

$\begin{algorithmic} \STATE \STATE Como $2 > 2^0$. \STATE $T(n) \in \Theta (n^{\log _2^2})$\STATE $T(n) \in \Theta (n)$\STATE \STATE \end{algorithmic}$

O método de divisão e conquista também produz um algoritmo com .

Exemplo: Busca Binária

O problema consiste em encontrar o índice do elemento em um array ordenado. Vamos assumir que o elemento sempre existe.

A solução ingênua para este problema é fazer uma busca sequencial do elemento no array. Parar quando o elemento for encontrado. É trivial observar que este algoritmo é .

A solução por divisão e conquista:

Divisão: Comparar com o elemento médio.
Conquista: Buscar na metade esquerda ou metade direita.
Combinação: Trivial.

$\begin{algorithmic} \STATE \STATE \STATE {\bf function} Busca(A, x, l, r) \STATE... ... \ELSE \STATE Busca$(A, x, m + 1, r)$\par\ENDIF \ENDIF \STATE \end{algorithmic}$

A análise do algoritmo que utiliza divisão e conquista requer a solução da seguinte relação de recorrência:

$T(n) = 2.T(n/2) + \Theta(1)$ .

Neste caso, e .

$\begin{algorithmic} \STATE \STATE Como $1 = 2^0$. \STATE $T(n) \in \Theta (n^k.\log n)$\STATE $T(n) \in \Theta (\log n)$\STATE \STATE \end{algorithmic}$

A busca binária é mais eficiente do que uma busca sequencial, quando é grande.

Exemplo: A Função Power

O problema consiste em computar , em que $n \in I\!\!N$ .
A solução ingênua é $\Theta (n)$

Solução Alternativa por Divisão e Conquista

$\begin{displaymath}a^n = \left\{ \begin{array}{ll} a^{n/2}.a^{n/2} & \mbox{se $... ....a^{n-1/2}.a & \mbox{se $n$\ é ímpar} \\ \end{array} \right. \end{displaymath}$

A relação de recorrência é, portanto,

$T(n) = T(n/2) + \Theta (1) \Rightarrow T(n) = \Theta (\log n)$ .

Exemplo: Multiplicação de Inteiros Grandes

O problema consiste em multiplicar dois números inteiros grandes.
A multiplicação clássica (a que aprendemos fazer na escola) requer tempo $\Theta (n^2)$ . Isso porque fazemos multiplicação dígito a dígito.
A multiplicação de números grandes é bastante utilizada em criptografia.

Solução Alternativa por Divisão e Conquista

Para evitar maiores complicações, vamos assumir que o número de dígitos em cada número é potência de 2.
A multiplicação de um número por um número pode ser efetuada dividindo-se o número original em dois super-dígitos e procedendo a multiplicação, como mostrado abaixo.

$\epsffile{mpy.eps}$

$mult(A, B) = mult(w, y).10^{2m} + (mult(w, z) + mult(x, y)).10^m + mult(x, z)$
A multiplicação por pode ser vista como o deslocamento de posições para a direita.
As adições envolvidas tomam tempo $\Theta (n)$ cada.
A multiplicação de dois inteiros longos é o resultado de 4 produtos de inteiros de tamanho metade do valor original, e um constante número de adições e deslocamentos, com tempo $\Theta (n)$ .

A solução por divisão e conquista:

Divisão: Dividir cada número em dois números com metade da quantidade de dígitos.
Conquista: Proceder a multiplicação das quatro partes.
Combinação: Combinar os resultados com deslocamento e adições.

A análise do algoritmo que utiliza divisão e conquista requer a solução da seguinte relação de recorrência:

$T(n) = 4.T(n/2) + \Theta(n)$ .

Neste caso, e .

$\begin{algorithmic} \STATE \STATE Como $4 > 2^1$. \STATE $T(n) \in \Theta (n^{\log _2^4})$\ (caso 3) \STATE $T(n) \in \Theta (n^2)$\STATE \STATE \end{algorithmic}$

Essa solução por divisão e conquista não apresenta vantagem em relação à solução original de multiplicação de inteiros.

Uma Solução por Divisão e Conquista Mais Eficiente

Apesar da primeira solução por divisão e conquista não ser mais eficiente do que a solução original, ela nos dá algumas dicas.
Por que não temos a eficiência desejada? Ora, temos 4 multiplicaçõs de números de tamanho . Realmente não deve mudar nada.
A solução seria reduzir o número de multiplicações? Isso é verdade pois sabemos que a adição e deslocamentos contribui com $\Theta (n)$ , apenas.
Se observarmos mais detalhadamente, podemos reduzir para três o número de multiplicações: , e . Da seguinte forma:

$\begin{algorithmic} \STATE \STATE $C = mult(w, y)$. \STATE $D = mult(x, z)$. \ST... ...E Logo, teremos: $mult(A, B) = C.10^{2m} + E.10^m + D$. \STATE \end{algorithmic}$

No total, fazemos 3 multiplicações, 4 adições e 2 subtrações de números com dígitos. É necessário ainda fazer deslocamentos mas, vimos que tudo isso representa $\Theta (n)$ .

Logo, a análise do algoritmo que utiliza divisão e conquista requer a solução da seguinte relação de recorrência:

$T(n) = 3.T(n/2) + \Theta(n)$ .

Neste caso, e .

$\begin{algorithmic} \STATE \STATE Como $3 > 2^1$. \STATE $T(n) \in \Theta (n^{\l... ...)$\ (caso 3) \STATE $T(n) \in \Theta (n^{1.585})$\STATE \STATE \end{algorithmic}$

Essa solução é realmente mais eficiente? Já estudamos isso. Para muito grande, essa solução é muito mais eficiente.

Exemplo: Multiplicação de Matrizes

O algoritmo ingênuo:

$\begin{algorithmic} \STATE \STATE \STATE {\bf function} MultMatriz(X, Y, Z, n) \... ...] = X[i, j] + Y[i, k].Z[k, j]$ \ENDFOR \ENDFOR \ENDFOR \STATE \end{algorithmic}$

Considerando que cada operação de inteiros é $\Theta (1)$ , o algoritmo ingênuo é $\Theta (n³)$ .

Solução Alternativa por Divisão e Conquista

Para evitar maiores complicações, vamos assumir que é potência de 2.
A multiplicação de matrizes pode ser feita dividindo-se cada matriz em quatro matrizes $(n/2) \times (n/2)$ , da seguinte forma:

$\begin{displaymath}X = \left[ \begin{array}{ll} I & J \\ K & L \end{array} \right] \end{displaymath}$

$\begin{displaymath}Y = \left[ \begin{array}{ll} A & B \\ C & D \end{array} \right] \end{displaymath}$

$\begin{displaymath}Z = \left[ \begin{array}{ll} E & F \\ G & H \end{array} \right] \end{displaymath}$

Então,

$\begin{algorithmic} \STATE \STATE $I = AE + BG$\STATE $J = AF + BH$\STATE $K = CE + DG$\STATE $L = CF + DH$\STATE \end{algorithmic}$

A análise do algoritmo que utiliza divisão e conquista requer a solução da seguinte relação de recorrência:

$T(n) = 8.T(n/2) + \Theta(n²)$ .

Neste caso, e .

$\begin{algorithmic} \STATE \STATE Como $8 > 2^2$. \STATE $T(n) \in \Theta (n^{\log _2^8})$\ (caso 3) \STATE $T(n) \in \Theta (n^3)$\STATE \STATE \end{algorithmic}$

Essa solução por divisão e conquista não apresenta vantagem em relação à solução original de multiplicação de inteiros.

Uma Solução por Divisão e Conquista Mais Eficiente

Da mesma forma que no algoritmo da multiplicação de inteiros grandes, seria mais eficiente se diminuíssemos o número de chamadas recursivas.
O Algoritmo de Strassen resolve a multiplicação mais eficientemente da seguinte forma:

$\begin{algorithmic} \STATE \STATE $M_1 = (A + C)(E + F)$\STATE $M_2 = (B + D)(G ... ... + D).E$\STATE $M_6 = (A + B).H$\STATE $M_7 = D.(G - E)$\STATE \end{algorithmic}$

Então,

$\begin{algorithmic} \STATE \STATE $I = M_2 + M_3 - M_6 - M_7$\STATE $J = M_4 + M_6$\STATE $K = M_5 + M_7$\STATE $L = M_1 - M_3 - M_4 - M_5$\STATE \end{algorithmic}$

Logo, a análise do algoritmo que utiliza divisão e conquista requer a solução da seguinte relação de recorrência:

$T(n) = 7.T(n/2) + \Theta(n²)$ .

Neste caso, e .

$\begin{algorithmic} \STATE \STATE Como $7 > 2^2$. \STATE $T(n) \in \Theta (n^{\l... ...7})$\ (caso 3) \STATE $T(n) \in \Theta (n^{2.8})$\STATE \STATE \end{algorithmic}$

Para muito grande, essa solução é muito mais eficiente.

Jorge C. A. de Figueiredo 2003-12-09

Análise e Técnicas de Algoritmos Período 2003.2

Divisão e Conquista

Introdução

Exemplos

Exemplo: Achar Maxim

Exemplo: Busca Binária

Exemplo: A Função Power

Exemplo: Multiplicação de Inteiros Grandes

Exemplo: Multiplicação de Matrizes

Análise e Técnicas de Algoritmos
Período 2003.2