%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% EP2 de MAC323 Estruturas de Dados                                  %
% BCC, 1o. semestre de 2001                                          %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Monday 02 Apr 2001 03:06:22pm BRST yoshi@rebutosa>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[reqno]{amsart}

\usepackage[colorlinks,backref]{hyperref}

%% 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, 2o.~EP, Verificador Ortográfico]%
{{\footnotesize MAC323/BCC Segundo exercício-programa}\\
\vspace{6\jot}
\textsl{Verificador Ortográfico}}
\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 30/4/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ê estudará o uso de \textit{árvores binárias de
  busca} (ABBs) na implementação de tabelas de símbolos, dando especial
atenção à eficiência de tais implementações.  


\section{O problema a ser resolvido}
\label{sec:problema}
O programa que você escreverá neste exercício deve resolver o seguinte
problema: (\textit{i})~a entrada de seu programa é um texto e uma coleção de
dicionários (listas de palavras) e (\textit{ii})~a saída de seu programa deve
ser uma lista contendo as palavras do texto que não ocorrem em nenhum dos
dicionários fornecidos.

\subsection{Um programa exemplo}
\label{sec:knuth}
Inicialmente, você deve estudar cuidadosamente o programa \texttt{wordtest}
escrito por Knuth, disponível em
$$
\href{http://www.ime.usp.br/~yoshi/2001i/mac323/EPs/EP2/wordtest}
{\texttt{http://www.ime.usp.br/\~\null yoshi/2001i/mac323/EPs/EP2/wordtest}}
$$
O programa de Knuth está escrito em sua linguagem de programação favorita,
o \href{http://www-cs-staff.Stanford.EDU/~knuth/cweb.html}{CWEB}.  Veja a
página 
$$
\href{http://www.ime.usp.br/~pf/mac328/aulas/cweb.html}
{\texttt{http://www.ime.usp.br/\~\null pf/mac328/aulas/cweb.html}}
$$
do professor \href{http://www.ime.usp.br/~pf}{Paulo Feofiloff} sobre o
CWEB.

O programa de Knuth usa uma estrutura chamada \textit{treap}.  Você não
precisa estudar o funcionamento desta estrutura.  Você deve, entretanto,
entender que um treap é usado no programa de Knuth para implementar uma tabela
de símbolos.  Você também deve estudar os pontos finos da funcionalidade do
programa de Knuth.  Por exemplo, o que são as opções de linha de comando de
\texttt{wordtest}? 

\section{O seu programa}
\label{sec:EP}
A sua tarefa principal neste exercício-programa é escrever \textit{um clone do
  programa de Knuth}.  Do ponto de vista do usuário, seu programa deve se
comportar exatamente da mesma forma que \texttt{wordtest}.  

As diferenças entre seu programa, digamos \texttt{ep2}, e o programa de Knuth
devem ser as seguintes:
\begin{enumerate}
\item O \texttt{wordtest} supõe que as palavras do texto de entrada vêm uma
  por linha.  Você deve implementar uma opção de linha de comando adicional,
  digamos \texttt{-t}, para permitir que o texto de entrada seja um arquivo
  texto ``normal'', com várias palavras por linha.  Assim, quando fazemos
\begin{verbatim}
  ep2 -t [outras opções e argumentos]
\end{verbatim}
  o seu programa deve primeiro isolar as palavras do texto antes de
  processá-las, como fazia seu primeiro EP.

  \textbf{Observação.}\quad Você pode achar interessante estudar o
  programa \texttt{tr} do Unix; em particular, estude o que faz a chamada
\begin{verbatim}
  tr -cs a-zA-Z '\n'
\end{verbatim}
  Os programas \texttt{tr} e \texttt{wordtest} em conjunto podem simular o seu
  programa com a opção \texttt{-t}.

\item A tabela de símbolos em seu programa deve ser implementada em um módulo
  separado, digamos \texttt{ST.c}, e o acesso a ela deve ser estritamente
  através de uma interface, digamos \texttt{ST.h}.
  
\item Você deve escrever duas implementações de \texttt{ST.c}.  Uma delas deve
  usar uma ABB sem balanceamento.  A segunda deve usar \textit{alguma} ABB
  balanceada (fica a seu critério qual---escolha uma boa!).  O seu sistema
  precisa ser tal que ele possa ser compilado com qualquer uma das duas
  implementações de \texttt{ST.c} sem qualquer modificação.  Organize seus
  arquivos em dois conjuntos (diretórios).  A única diferença entre os dois
  conjuntos deve ser o arquivo \texttt{ST.c}.

\item O seu programa deve ser ``portável''.  Observe que no mínimo o seu
  programa deve compilar sem problemas com o \texttt{gcc}.

\end{enumerate}

\subsection*{Observação.} Costumo dar este EP regularmente, pois eu acredito
que ele é bastante instrutivo.  Você pode ver outras edições deste EP nas
páginas abaixo:
\begin{enumerate}
\item MAC122, 2o.~semestre de 1998:
  $$
  \href{http://www.ime.usp.br/~yoshi/mac122/EPs/ep3.html}%
  {\texttt{http://www.ime.usp.br/\~\null yoshi/mac122/EPs/ep3.html}}
  $$
\item MAC324, 1o.~semestre de 1999:
  $$
  \href{http://www.ime.usp.br/~yoshi/mac324/projeto/}%
  {\texttt{http://www.ime.usp.br/\~\null yoshi/mac324/projeto}} 
  $$
\end{enumerate}
Note que o nosso EP é uma \textit{variante} dos EPs acima.  Entretanto, pode
valer a pena dar uma olhada nas páginas acima, pois elas contêm várias dicas. 

\section{Análise de desempenho}
\label{sec:analise}
Faça uma análise empírica de desempenho, comparando seus dois programas e o
programa \texttt{wordtest}.  Faça um pequeno relatório com os resultados e
conclusões. 

\subsection{Dados}
\label{sec:dados}
Procure implementar sua tabela de símbolos de forma que os seus dois programas
possam manipular arquivos de tamanho `razoavelmente grandes' como, por
exemplo, o
\href{ftp://ibiblio.org/pub/docs/books/gutenberg/etext92/bible11.txt}{\textit{King
    James' Bible}}, que contém algo como~$800.000$ palavras.

Como no primeiro exercício programa, uma boa fonte de arquivos para testar o
seu programa é o \href{http://promo.net/pg/}{Projeto Gutenberg}.  

\subsection{Dicionários}
\label{sec:dicios}
Você pode usar os dicionários do Unix para processar textos em inglês.  Para o
português, você pode usar os dicionários 
\begin{enumerate}
\item \texttt{br} (2.7M): uma lista de palavras do português brasileiro,
\item \texttt{pt} (4.2M): uma lista de palavras do português português,  
\item \texttt{uniao} (4.8M): uma união de \texttt{br} e \texttt{pt} (sem
  repetições, naturalmente),
\end{enumerate}
todos disponíveis em
$$
\href{http://www.ime.usp.br/~yoshi/Dicios}%
{\texttt{http://www.ime.usp.br/\~\null yoshi/Dicios}}
$$
Gerei o arquivo acima para o português brasileiro a partir do trabalho de
\href{http://www.ime.usp.br/~ueda}{Ricardo Ueda}.  Veja, em particular, a sua
\href{http://www.ime.usp.br/~ueda/br.ispell}{página sobre \texttt{br.ispell}}.
Note que uma condição que devemos respeitar é que qualquer coisa que
produzirmos com a ajuda deste arquivo deve ficar livremente redistribuível
(veja \href{http://www.ime.usp.br/~ueda/br.ispell/gpl}{a licença GNU GPL}).

Para gerar os arquivos para o português português, usei o trabalho de
\href{http://shiva.di.uminho.pt/~jj/pln/pln.html}{José João Almeida}.  Este
trabalho também é distribuído de acordo com a licença GNU GPL.  Para entender
a motivação e filosofia dos termos da licença GNU GPL, veja a
\href{http://www.gnu.ai.mit.edu/}{página do Projeto GNU}.

Uma página muito interessante sobre recursos computacionacionais para o
português é 
$$
\href{http://www.portugues.mct.pt/recursos.html}%
{\texttt{http://www.portugues.mct.pt/recursos.html}}.
$$
Consulte!

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

\begin{enumerate}
\item \textit{Este EP é individual.}
\item Preste atenção na modularização descrita neste enunciado.
\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 \textit{Não imponha restrições arbitrárias sobre a entrada}.  Quando
  usado forma inesperada, o seu programa deve parar de forma `graciosa'.
\item Organizem-se na turma para fazer bons testes.  Comparem entre vocês o
  desempenho de seus programas.
\item Seja criativo.  Se seu programa fizer algo a mais do que foi pedido você
  poderá ganhar algum bônus na nota.  Por outro lado, você \textit{deve}
  respeitar as especificações dadas neste enunciado.
\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: 
