%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% EP2 de MAC122 Princípios de Desenvolvimento de Algoritmos          %
% BMAC, 2o. semestre de 2003                                         %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 14 Oct 2003 06:44:42pm BRT yoshi@erdos.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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[MAC122, 2o.~EP, Ocorrências próximas]%
{{\footnotesize MAC122/BMAC Segundo exercício-programa}\\
\vspace{6\jot}
\textsl{Ocorrências próximas}}
\author{Y.\ Kohayakawa}
\date{Versão de \today}
\maketitle
\thispagestyle{empty}

\subsubsection*{Data de entrega}  Você deve entregar este EP até o dia
5/11/2003, pelo Panda.

\section{Introdução}
\label{sec:intro}
Neste segundo exercício-programa, você verá como usar \textit{tabelas de
  símbolos} em seus programas.  Neste EP, você também precisará resolver um
pequeno problema de otimização.

\section{O problema a ser resolvido}
\label{sec:problema}
O programa que você escreverá neste exercício deve resolver o 
problema que descrevemos a seguir.

O usuário dará inicialmente um texto~$T$, possivelmente longo.  O usuário irá
então fornecer uma seqüência~$C_1,C_2,\dots$ de conjuntos de palavras.  Para
cada conjunto~$C_i$, o seu programa deve imprimir um trecho do texto~$T$ que
contém todas as palavras em~$C_i$.  Caso o texto não contenha todas as
palavras em~$C_i$, seu programa deve imprimir uma mensagem dizendo isso.  (O
programa pode devolver o resultado para~$C_i$ logo após ler~$C_i$.)  O
problema de otimização vem aqui: adicionalmente, vamos impor a condição de que
\begin{itemize}
\item[(*)]\textit{o trecho devolvido como resposta para a entrada~$C_i$ deve
    ter o menor número de caracteres possível.}
\end{itemize}

\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.  

\subsubsection*{Execução} O texto~$T$ de entrada deve vir em um arquivo, cujo
nome será especificado pelo usuário.  O seu programa deve receber os
conjuntos~$C_i$ no \texttt{stdin}, com os~$C_i$ separados por linhas em
branco.  Assim, seu programa poderia ser executado, por exemplo, como segue:
\begin{verbatim}
meu_prompt $ ep2 bible.txt < conjuntos
\end{verbatim}%$
onde \texttt{conjuntos} é o arquivo de conteúdo
\begin{verbatim}
In created earth

divided sea Moses
\end{verbatim}
As respostas poderiam ser\footnote{Eu não verifiquei!} 
\begin{verbatim}
In the beginning God created the heaven and the earth
\end{verbatim}
e
\begin{verbatim}
Moses stretched out his hand over the sea; and the LORD
caused the sea to go back by a strong east wind all that
night, and made the sea dry land, and the waters were divided
\end{verbatim}

\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 se alterar a implementação
da tabela de símbolos, não será necessário se alterar outras partes do
programa.

Nesta etapa, procure implementar sua tabela de símbolos de forma que o seu
programa possa manipular arquivos de tamanho razoável, mas não necessariamente
tão grandes como um livro.  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 EP3.
\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 seu EP seguindo os moldes usuais: cabeçalho claro, instruções
  claras para o monitor poder compilar e executar seu programa, e eventuais
  arquivos de teste (não muito grandes).
\end{enumerate}

\subsubsection*{Observação final}  Tragam dúvidas para as nossas aulas.
Eventualmente, ajustes no enunciado poderão ocorrer ao discutirmos este EP em
sala.

\end{document}

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