%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% EP3 de MAC323 Estruturas de Dados                                  %
% BCC, 1o. semestre de 2001                                          %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Wednesday 09 May 2001 03:28:41pm BRST yoshi@jaca>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[reqno]{amsart}

\usepackage[colorlinks,backref]{hyperref}
\usepackage{epsfig}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

\let\:=\colon
\def\dist{\mathop{\rm dist}\nolimits}
\def\RR{\mathbb R}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}

\begin{document}
%\title[MAC323 Estruturas de Dados]{{\small Primeiro Exercício-Programa}\\
%\vspace{1\jot}{\tiny BCC, Primeiro Semestre de de 2001}\\
%\vspace{3\jot}} 

\title[]%[MAC323, 3o.~EP, Contagem de Poliminós]%
{{\footnotesize MAC323/BCC Terceiro exercício-programa}\\
\vspace{6\jot}
\textsl{Contagem de Poliminós}}
\author[]{Y.\ Kohayakawa}
\date{Versão de \today}
\maketitle
\thispagestyle{empty}

\subsubsection*{Data de entrega}  Você deve entregar este EP até as 18:00 do
dia 4/6/2001, na secretaria do Departamento de Ciência da Computação,
sala~256, bloco~A.

\section{Introdução}
\label{sec:intro}
Neste exercício-programa você investigará, através de um exemplo, o uso de
estruturas de dados na implementação de algoritmos eficientes.

\section{O problema a ser resolvido}
\label{sec:problema}
O programa que você escreverá neste exercício deve determinar o número de
poliminós com~$n$ células.  \textit{Poliminós} generalizam dominós (que são
poliminós com $n=2$~\textit{células}).  Você já conhece os
\textsl{pentaminós}, do \href{http://www.ime.usp.br/~cef/mac122-2000/eps/}%
{Exercício-Programa~2} de MAC$\,$122 (2o.~semestre de 2000).  Poliminós também
são conhecidos como \textit{animais}.\footnote{Você pode, portanto, dizer que
  este EP é \textit{o EP animal}.}

Formalmente, nossos poliminós são formados por quadrados de lado unitário (as
\textit{células}).  As células em um poliminó devem formar uma configuração
\textit{conexa}, isto é, entre quaisquer duas células~$c$ e~$c'$ de nosso
poliminó, deve haver uma seqüência de células~$c_0,\dots,c_\ell$ com~$c_0=c$
e~$c_\ell=c'$ e tal que~$c_{i-1}$ e~$c_i$ têm uma aresta comum para
todo~$1\leq i\leq\ell$.  Você encontra na Figura~\ref{fig:1} um belo poliminó
(ou um belo animal se você preferir).

\begin{figure}[htbp]
    $$\convertMPtoPDF{polyomino2}{1}{1}$$
    \caption{Um belo animal}
    \label{fig:1}
\end{figure}

Faremos a contagem de nossos poliminós ``a menos de translação''.  Isto é,
identificamos dois poliminós~$X$ e~$Y$ se~$X$ pode ser obtido de~$X$ por uma
translação.  Note que não permitimos rotação ou reflexão.  De acordo com esta
convenção, há dois dominós e há~$2+4=6$ triminós.

Seja~$a_n$ o número de poliminós com~$n$ células.  Os valores conhecidos
de~$a_n$ são dados na Tabela~\ref{tab:series} [veja I.~Jensen,
\textit{Enumerations of lattice animals and trees}, a aparecer no Journal of
Statistical Physics, disponível
\href{http://xxx.lanl.gov/abs/cond-mat/0007239}%
{\texttt{arXiv:cond-mat/0007239}}].

\begin{table}
\caption{\label{tab:series} Número de poliminós~$a_n$}
\begin{center}
\small
\renewcommand{\arraystretch}{0.85}
\begin{tabular}{rl}  \hline  \hline
$n$  & $a_n$ \\
\hline
1 & 1 \\ 
2 & 2 \\ 
3 & 6 \\ 
4 & 19 \\ 
5 & 63 \\ 
6 & 216 \\ 
7 & 760 \\ 
8 & 2725 \\ 
9 & 9910 \\ 
10 & 36446 \\ 
11 & 135268 \\ 
12 & 505861 \\ 
13 & 1903890 \\ 
14 & 7204874 \\ 
15 & 27394666 \\ 
16 & 104592937 \\ 
17 & 400795844 \\ 
18 & 1540820542 \\ 
19 & 5940738676 \\ 
20 & 22964779660 \\ 
21 & 88983512783 \\ 
22 & 345532572678 \\ 
23 & 1344372335524 \\ 
24 & 5239988770268 \\ 
25 & 20457802016011 \\ 
26 & 79992676367108 \\ 
27 & 313224032098244 \\ 
28 & 1228088671826973 \\ 
29 & 4820975409710116 \\ 
30 & 18946775782611174 \\ 
31 & 74541651404935148 \\ 
32 & 293560133910477776 \\ 
33 & 1157186142148293638 \\ 
34 & 4565553929115769162 \\ 
35 & 18027932215016128134 \\ 
36 & 71242712815411950635 \\ 
37 & 281746550485032531911 \\ 
38 & 1115021869572604692100 \\ 
39 & 4415695134978868448596 \\ 
40 & 17498111172838312982542 \\ 
41 & 69381900728932743048483 \\ 
42 & 275265412856343074274146 \\ 
43 & 1092687308874612006972082 \\ 
44 & 4339784013643393384603906 \\ 
45 & 17244800728846724289191074 \\ 
46 & 68557762666345165410168738 \\ 
\hline \hline
\end{tabular}
\end{center}
\end{table}

\subsection{Programas de exemplo}
\label{sec:knuth}

É instrutivo estudar o programa escrito por Knuth, chamado
\href{http://www.ime.usp.br/~yoshi/2001i/mac323/EPs/EP3/Knuth/polynum.pdf}%
{\texttt{polynum}}, baseado no algoritmo de Jensen descrito em seu
\href{http://xxx.lanl.gov/abs/cond-mat/0007239}%
{artigo acima}.  A codificação de Knuth é bastante sofisticada, e assim um
entendimento completo de seu programa pode estar além do escopo desta
disciplina.  Por outro lado, você pode aprender várias coisas interessantes
estudando este programa e, portanto, recomento fortemente que você dedique um
certo tempo a ele.  O programa \texttt{polynum} deve ser usado em conjunto com
\href{http://www.ime.usp.br/~yoshi/2001i/mac323/EPs/EP3/Knuth/polyslave.pdf}%
{\texttt{polyslave}}.

Estudando cuidadosamente a estratégia de \texttt{polynum} e
\texttt{polyslave}, você deverá ser capaz de escrever um programa que
determina o número de animais~$a_n$ para valores de~$n$ moderadamente
grandes.  

\subsubsection{Recomendações}
Sugiro que você comece escrevendo um programa simples, para ver até qual valor
de~$n$ você consegue chegar com técnicas elementares.  Procure entender as
partes mais simples de \texttt{polynum} e \texttt{polyslave} para ver se você
consegue incorporar idéias do método de Jensen e Knuth.  Você ainda pode achar
interessante ver 
\href{http://www.ime.usp.br/~yoshi/2001i/mac323/EPs/EP3/Knuth/polyenum.pdf}%
{um programa que Knuth escreveu} antes de conhecer o trabalho de Jensen.

Você pode entregar até duas versões deste EP: uma versão elementar e a melhor
versão que você conseguir escrever.  

\section{Observações}
\label{sec:obs}

\begin{enumerate}
\item \textit{Este EP pode ser feito em duplas.}
\item Seja cuidadoso com sua programação (correção, documentação,
  apresentação, clareza do código, etc), dando especial atenção a suas
  estruturas de dados.  A correção será feita levando isso em conta.
\item Comparem entre vocês o desempenho de seus programas.
\item Entregue o seu EP seguindo os moldes usuais: listagem impressa,
  cabeçalho claro, disquete com os arquivos (coloque um \texttt{Makefile}) e
  eventuais arquivos de teste.
\end{enumerate}

\subsubsection*{Observação final}  Enviem dúvidas para a lista de discussão da
disciplina.  Eventualmente, ajustes no enunciado ocorrerão ao discutirmos este
EP na lista.

\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 
