tecnicas-de-projeto-de-algoritmos.tex

% !TEX encoding = ISO-8859-1
\chapter{Técnicas de Projeto de Algoritmos}
\label{ch:tecnicas-de-projeto-de-algoritmos}

\index{técnicas de projeto de algoritmos}
\index{Levitin}
Consideramos as seguintes técnicas de projeto de algoritmos (seguindo
as ideias de Levitin \cite{Levitin:Introd-Design-Analysis-Alg}):

\begin{description}

\item[Divisão] (em inglês, chamada de {\em divide-and-conquer\/}):
  \index{técnica de projeto de algoritmos!divisão} 
  \index{técnica de projeto de algoritmos!{\em divide-and-conquer\/}} 
  é baseada em dividir a instância do problema em duas ou mais partes
  menores, resolver essas duas ou mais sub-instâncias e combinar os
  resultados obtidos para solução do problema original.

  Algoritmos de caminhamento em árvores binárias (pre-ordem, pos-ordem
  e visita-no-meio (em inglês, {\em in-order\/}) são exemplos de uso
  da técnica de divisão (veja exercício resolvido
  \ref{ex:caminhamento-em-arvores-binarias}). Outros exemplos são {\em
    quickSort\/} (seção \ref{sec:quickSort}) e {\em mergeSort\/} (seção
  \ref{sec:mergeSort}). 

\item[Decremento] (em inglês, chamada de {\em
  decrease-and-conquer\/}): 
  \index{técnica de projeto de algoritmos!decremento} 
  \index{técnica de projeto de algoritmos!{\em decrease-and-conquer\/}} 
  é baseada em passar da instância original para uma instância menor
  ou reduzir o tamanho da entrada do problema para solução da
  instância original. O decréscimo é tipicamente de um valor ou por um
  fator constante no tamanho da entrada, mas pode também ser um
  decréscimo de um valor ou por um fator variável. Note que o
  decremento por um fator constante não é caracterizado como divisão
  (seguindo \cite{Levitin:Introd-Design-Analysis-Alg}): a diferença
  está em que decrementar não origina duas ou mais sub-instâncias
  (apenas decrementa o tamanho da entrada).

  A vasta maioria dos algoritmos apresentados neste livro usam a
  técnica de decremento. Veja por exemplo \inh{maiorElem} (seção
  \ref{sec:maior-elemento}), \inh{elem} (seção
  \ref{sec:pesquisa-em-lista}), \inh{verifUnicidade} (seção
  \ref{sec:unicidade}), ordenação por inserção (seção
  \ref{sec:insertion-sort-func}), funções \inh{sorted}, \inh{perm} e
  \inh{delete} (seção \ref{sec:insertion-sort-func}), multiplicação de
  matrizes (seção \ref{sec:multiplicacao-de-matrizes}), função
  \inh{fib} (seção \ref{sec:numeros-de-fibonacci}).

\item[Uso-da-Definição] (também chamada de {\em força bruta\/}):
  \index{técnica de projeto de algoritmos!uso-da-definição} 
  \index{técnica de projeto de algoritmos!força-bruta} 
  baseada em uso direto da especificação do problema e das definições
  dos conceitos envolvidos na especificação do problema e, além disso,
  quando a técnica não se encaixa em alguma das demais técnicas acima.

  Exemplos: inserção de elemento em início de lista (seções
  \ref{sec:insercao-em-lista}), operações sobre pilhas
  (\ref{sec:pilha}) e filas (\ref{sec:fila}).

\end{description}

\index{TPA} Vamos chamar cada técnica do conjunto de técnicas acima de
TPA. Todo programa apresentado neste livro é classificado segundo uma,
e apenas uma, TPA. O objetivo é o de motivar e ajudar no processo de
desenvolvimento do raciocínio usado na elaboração de algoritmos. É
instrutivo não apenas entender a classificação e procurar classificar
algoritmos segundo uma TPA, mas também considerar a existência ou não
de outros algoritmos, elaborados segundo outra TPA. Isso ajuda a
organizar o raciocínio, e pode contribuir para o entendimento sobre
algoritmos existentes e para o aumento da motivação no estudo de novos
algoritmos.

Para espeficicar a classificação de algoritmo, implementado por função
com nome salientado no texto em cor \textcolor{Mahogany}{mogno},
usamos cores de fundo, como a seguir:

  \begin{description}
    \item[{\colorbox{\divisao}{divisão}}] 
    \item[{\colorbox{\decremento}{decremento}}]
    \item[{\colorbox{\definicao}{definição}}]
  \end{description}

Quando não se trata de um algoritmo, ou quando são incluídas várias
funções e não está se considerando a análise da eficiência de um
algoritmo, é usado fundo branco.

\index{técnicas de solução de problemas}
As técnicas de projeto de algoritmos abaixo, tradicionalmente vistas
como principais, são consideradas não como técnicas de projeto de
algoritmos mas como técnicas de solução de problemas, não constituindo
base para classificação de algoritmos específicos:

  \begin{enumerate}

     \item gananciosa (em inglês, {\em greedy\/}) 
       \index{técnica de solução de problema!gananciosa}
       \index{técnica de solução de problema!{\em greedy\/}}
       --- para problemas de {\em otimização\/}, baseada na escolha de
       {\em ótimo\/} local, i.e.~baseada em fazer melhor escolha na
       fase ou instante corrente.

       Exemplos...

     \item programação dinâmica --- ....
       \index{técnica de solução de problema!programação dinâmica}

     \item busca exaustiva --- 
       \index{técnica de solução de problema!busca exaustiva}
       baseada na tentativa de todos os possíveis valores que possam
       levar a uma solução, até que uma solução seja encontrada. É um
       caso de uso-da-definição.

       A limitação mais importante da busca exaustiva é sua
       ineficiência. Em geral, o número de possíveis valores que podem
       levar a uma solução cresce muito rapidamente
       (e.g.~exponencialmente) com o crescimento do tamanho da
       entrada.

       Exemplos ....

     \item retrocedimento (em inglês, {\em backtracking\/}) ---
       \index{técnica de solução de problema!retrocedimento}
       baseada na tentativa de realizar escolhas, dentre opções
       existentes, para construção da solução passo a passo e
       retroceder na escolha feita em um passo se esta escolha não
       puder ser usada para gerar uma solução.

       No pior caso, retrocedimento pode acabar gerando todas as
       soluções possíveis, como no caso da busca exaustiva, mas não é
       comum isso ocorrer. 

       É instrutivo visualizar a técnica de retrocesso como um
       processo de construir uma árvore que mostra as decisões tomadas
       a cada passo. A raiz da árvore corresponde ao estado inicial
       antes do primeiro passo, e cada nó da árvore contém sub-árvores
       com raízes que correspondem a estados que caracterizam a
       decisão tomada no passo seguinte.

       Por exemplo, a árvore abaixo descreve a técnica de
       retrocedimento aplicada ao problema de colocar 4 rainhas em um
       tabuleiro 4x4 sem que haja uma rainha atacando outra (veja
       exercício \ref{rainhas-nao-se-atacando}).

       ......

  \end{enumerate}

%    \item[transformação]
%       \begin{description}
%         \item[{\colorbox{\simplificacao}{simplificação}}]
%         \item[{\colorbox{\mudancaRep}{mudança de representação}}]
%         \item[{\colorbox{\preProcess}{pré-processamento}}]
%      \end{description}

\index{técnica de solução de problemas!transformação}
\index{técnica de solução de problemas!{\em transform-and-conquer\/}}
\index{transformação}
\index{{\em transform-and-conquer\/}}
Levitin considera também a técnica de transformação (em inglês,
chamada de {\em transform-and-conquer\/}), baseada em transformar a
instância do problema original em outra instância do mesmo ou de outro
problema (com o mesmo tamanho da instância original), e em usar ou
adaptar o resultado para solução do problema original.  A
transformação para uma instância do mesmo problema pode envolver {\em
  simplificação\/} ou {\em mudança de representação\/} ou {\em
  pré-processamento\/} da entrada.

\index{técnica de solução de problemas!simplificação}
\index{simplificação}
\index{técnica de solução de problemas!mudança de representação}
\index{mudança de representação}
A simplificação não envolve mudança de representação da entrada: usa a
mesma representação original, transformando a entrada para que ela
tenha alguma propriedade que torna a solução do problema mais fácil ou
mais eficiente (por exemplo, ordenando os dados de entrada). O
pré-processamento é caracterizado pela existência de um ou mais passos
adicionais sobre os dados de entrada, para obtenção de dados extras,
novamente para tornar a solução do problema mais fácil ou mais
eficiente.

Consideramos que a técnica de transformação está, assim como as
técnicas gananciosa, programação dinâmica, busca exaustiva e
retrocedimento, mencionadas acima, em um outro nível, acima das
TPAs. Elas constituem técnicas usadas para solução de um problema mas
não uma classificação de técnica de projeto usada para um algoritmo
particular, como acontece nos casos das TPAs. 

O projeto de algoritmos é composto por duas fases: a primeira consiste
em decidir qual técnica usar para solução do problema. A segunda fase
consiste no projeto do algoritmo propriamente dito, usando uma das
TPAs. Seja qual for a técnica adotada na solução de um problema, o
algoritmo deve ser projetado e implementado, e poderá então ser
classificado de acordo com alguma TPA.

\section{Exercícios Resolvidos}

Escreva programa para solução de cada problema enunciado a seguir e
indique a TPA usada.

\begin{enumerate}

\item \label{ex:caminhamento-em-arvores-binarias} 
      \index{caminhamento em árvore binária}
      \index{árvore binária!caminhamento}
      \index{árvore binária!busca em profundidade}
      \index{árvore binária!busca em largura}

  Considere o problema de caminhamento em árvores (aplicado em geral a
  grafos) chamados de {\em busca em profundidade\/} e {\em busca em
    largura\/}.

  A busca em profundidade ...

  A busca em largura ...

  Escreva algoritmos para caminhamento em árvores binárias, árvores
  com qualquer número de filhos e árvores que usam a {\em
    representação com primogênito-irmão-e-pai} (e indique a técnica
  usada em cada algoritmo).

\item Problema da Celebridade: \index{celebridade}
      \index{problema da celebridade}
  uma celebridade de um grupo de $n$ pessoas é uma pessoa que não
  conhece ninguém do grupo mas é conhecida por todas as pessoas do
  grupo.  O problema consiste em, dados: i) $n$, ii) uma lista de
  pessoas, e iii) uma tabela que indica, para cada par de pessoas
  $(a,b)$ da lista, se $a$ conhece $b$, identificar uma celebridade do
  grupo de pessoas (supondo, por simplicidade, que uma celebridade de
  fato existe).

  {\bf Solução}: O algoritmo que soluciona o problema usa a técnica de
  decremento. O essential é considerar (``descobrir'') que basta usar
  um mapeamento que, para cada pessoa, guarda duas informações: 1) se
  ela conhece alguém, e 2) o número de pessoas que a conhece.  Ou
  seja, não é preciso uma estrutura de dados ``bi-dimensional'', que
  guarda uma lista de informações para cada pessoa, nem um arranjo
  bidimensional de pessoas.  

  Para cada par de pessoas $a$ e $b$ tais que $a$ conhece $b$, o
  algoritmo simplesmente armazena que $a$ conhece alguém (portanto,
  não pode ser celebridade) e incrementa o número de pessoas que
  conhece $b$. No final, só pode existir uma única pessoa que não
  conhece ninguém (se existirem duas pessoas que não conhecem ninguém,
  não há celebridade); para esta única pessoa que não conhece ninguém,
  basta verificar se o número de pessoas que a conhece é igual ao
  total de pessoas menos 1.
 
{\bf Versão funcional}: Em Haskell, usamos abaixo um mapeamento, em
vez de um arranjo, para armazenar, para cada pessoa ($p$), as duas
informações necessárias (se $p$ conhece alguém e o número de pessoas
que conhecem $p$).

\HRule
{\em Nota\/}: 

Um valor de tipo \inh{Map k a}, para tipos \inh{k} e \inh{a} quaisquer
com a única condição que \inh{k} seja da classe \inh{Ord} (sobre
classes de tipos em Haskell, veja seção \ref{sec:Classes-de-tipos}),
associa valores de tipo \inh{k}, chamados de {\em chaves}, a valores
de tipo \inh{a} (de modo semelhante a arranjos e funções). O conjunto
de chaves (de um valor \inh{m} de tipo \inh{Map k a}) é chamado de
{\em domínio\/} de \inh{m}. Internamente, um valor de tipo \inh{Map k
  a} é implementado como uma árvore binária balanceada.

No programa abaixo, usamos valores \inh{m} de tipo \inh{Map (Pessoa,Pessoa) Bool} 
para indicar se duas pessoas \inh{(a,b)} se conhecem ou não: em caso
positivo \inh{m ! (a,b)} é igual a \inh{True}. Em caso negativo, o par
\inh{(a,b)} não faz parte do domínio de \inh{m} (ou seja, o par
\inh{(a,b)} não foi inserido como uma chave de \inh{m}) e nesse caso a
avaliação de \inh{m ! (a,b)} resulta em um erro. Usamos por isso
\inh{findWithDefault False (a,b) m}, que retorna \inh{False} se
\inh{(a,b)} não pertence ao domínio de \inh{m} (\inh{findWithDefault v
  k m} retorna \inh{m!k} --- o valor associado à chave \inh{k} em
\inh{m} --- se \inh{k} pertence ao domínio de \inh{m}, caso contrário
retorna o valor \inh{v}). 

\inh{filterWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> Map k a}
é tal que \inh{filterWithKey p m} seleciona (filtra) todos os valores
para os quais \inh{p k v} retorna \inh{True}, para \inh{k} no domínio
e \inh{v} na imagem de \inh{k} em \inh{m}. No caso, queremos
selecionar os pares \inh{(a,b)}, para algum \inh{b}, que estão no
domínio de \inh{m}.

O mapeamento que indica se pares de pessoas se conhecem pode ser
criado com a função \inh{conheceM0}, que cria um mapeamento a partir
de uma lista de pares \inh{((a,b),True)}, que indica que a pessoa
\inh{a} conhece a pessoa \inh{b}. 

\HRule

\begin{center}
\begin{tabular}{l}
\begin{hask}{celebridade}{\decremento}
module Celebridade where

import Data.Map       (Map, findWithDefault, fromList, filterWithKey, null)
import Prelude hiding (null)

type Pessoa     = Integer

type ConheceM   = Map (Pessoa,Pessoa) Bool
-- For m::ConheceM, findWithDefault False (a,b) m = True sse (a conhece b).

conheceM0 :: [(Pessoa,Pessoa)] -> ConheceM
conheceM0 x = fromList [(p,True) | p <- x]

celebridade :: [Pessoa] -> ConheceM -> Pessoa
-- Pre: celebridade n x m implica n = length x
celebridade (a:b:r) m
  | findWithDefault False (a,b) m = celebridade (b:r) m -- 'a' não é celeb. (celeb. não conhece ninguém)
  | otherwise                     = celebridade (a:r) m -- 'b' não é celeb. (todos conhecem celeb.)
celebridade [a] m = null (filterWithKey (\ (k,_) _ -> a==k) m)  -- se existe (a,_) no domínio de m, 'a' não é celeb.
\end{hask}
\end{tabular}
\end{center}

{\bf Versão imperativa}: \ldots

....

\item \label{rainhas-nao-se-atacando} ....

\end{enumerate}

\section{Exercícios}