%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% EP1 de MAC323 Estruturas de Dados                                  %
% BCC, 1o. semestre de 2001                                          %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Monday 02 Apr 2001 11:26:18am 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, 1o.~EP, Palavras Mais Freqüentes]%
{{\footnotesize MAC323/BCC Primeiro exercício-programa}\\
\vspace{6\jot}
\textsl{Palavras Mais Freqüentes}}
\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/3/2001, na secretaria do Departamento de Ciência da Computação,
sala~256, bloco~A.

\section{Introdução}
\label{sec:intro}
Neste primeiro exercício-programa, você se familiarizará com a noção de
\textit{tabela de símbolos}.  Nesta etapa, você não precisará usar
implementações sofisticadas de tais tabelas; a idéia principal é você entender
como podemos usar tais estruturas.  A referência básica para este EP é a parte
inicial do Capítulo~12 de Sedgewick (inclusive \S12.1). 

\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 é formada por um inteiro~$n$
e um texto e (\textit{ii})~a saída de seu programa deve ser a lista das
$n$~palavras mais freqüentes no texto, com suas respectivas freqüências
(número de ocorrências na entrada).

\subsubsection*{Observações} Uma \textit{palavra} é uma seqüência maximal de
letras.  Você deve distinguir letras maiúsculas de minúsculas, de forma que
\texttt{Vitória} e \texttt{vitória} devem ser consideradas palavras
diferentes.  As palavras que ocorrem um mesmo número de vezes devem ser
listadas em ordem `alfabética'.  Use a ordem alfabética induzida pela tabela
ASCII, por exemplo, \texttt{Zoroastro} deve vir antes de \texttt{alabastro}.
O seu programa deve parar após~$n$ palavras terem sido devolvidas, caso a
entrada tenha pelo menos~$n$ palavras.

\subsubsection*{Execução} A entrada de seu programa 
deve vir do \texttt{stdin} e o seu programa deve receber o inteiro~$n$ na
linha de comando.  A saída deve ser enviada para o \texttt{stdout}.  Por
exemplo, executando o seu programa no texto do
\href{ftp://ibiblio.org/pub/docs/books/gutenberg/etext92/bible11.txt}{\textit{King
    James' Bible}} do \href{http://promo.net/pg/}{Projeto Gutenberg}
(removendo o cabeçalho contendo informações sobre o Projeto Gutenberg, termos
de distribuição, etc), obtemos algo como
{\small
\begin{verbatim}
meu_prompt > ep1 -n5 < entrada.txt
     62064 the
     38847 and
     34428 of
     13378 to
     12846 And
\end{verbatim}
  } Esta saída diz que, por exemplo, a palavra mais freqüente é \textit{the},
com~$62064$ ocorrências.

\section{Estrutura geral do programa}
\label{sec:estrutura}
Você deve estruturar o seu programa da seguinte forma.

\subsection{Objetos das tabelas de símbolos}
\label{sec:Item}
Os objetos a serem armazenados em sua tabela de símbolos devem ser do tipo
\texttt{Item}, implementados em \texttt{Item.c} e manipulados através da
interface \texttt{Item.h}.

\subsection{Tabela de símbolos}
\label{sec:TS}
A sua tabela de símbolos deve ser implementada em \texttt{ST.c} e o acesso a
ela deve ser \textit{estritamente através da interface} \texttt{ST.h}.
Projete a interface \texttt{ST.h} de forma que ao alterar a implementação da
tabela de símbolos, você não precisará alterar outras partes do programa.
Possivelmente, você disponibilizará uma função de protótipo
\begin{verbatim}
  void ST_first_n(void (*visit)(Item), int n);
\end{verbatim}
em \texttt{ST.h}, para enviar as~$n$ palavras mais freqüentes à saída, por
exemplo, com a chamada
\begin{verbatim}
  ST_first_n(ITEMshow, n);
\end{verbatim}
em seu programa principal.

Procure implementar sua tabela de símbolos de forma que o seu programa possa
manipular arquivos de tamanho `razoavelmente grandes'.  Com o que vimos em
sala até o momento, provavelmente não sabemos como escrever um programa que
possa realmente processar um arquivo como o
\href{ftp://ibiblio.org/pub/docs/books/gutenberg/etext92/bible11.txt}{\textit{King
    James' Bible}}, que contém algo como~$800.000$ palavras.


\subsection{Arquivos de teste}
\label{sec:testes}
Uma boa fonte de arquivos para testar o seu programa é o
\href{http://promo.net/pg/}{Projeto Gutenberg}.  

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

\begin{enumerate}
\item \textit{Este EP é individual.}
\item Preste atenção na modularização descrita neste enunciado.  Se você
  seguir estas instruções, será mais fácil você fazer o EP2.
\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: 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: 
