%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% D2 de MAC323 Estruturas de Dados                                   %
% BCC, 1o. semestre de 2001                                          %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 03 Apr 2001 09:13:58am 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, 2o.~Desafio, Análise de Desempenho]%
{{\footnotesize MAC323/BCC Segundo Desafio}\\
\vspace{6\jot}
\textsl{Análise de Desempenho de Tabelas de Símbolos}}
\author{Y.\ Kohayakawa}
\date{Versão de \today}
\maketitle
\thispagestyle{empty}

Este desafio é mais um ``exercício'', isto é, embora haja espaço para várias
idéias criativas, o básico não envolve nenhuma dificuldade maior (apenas um
pouco de trabalho).  Entretanto, acredito que este desafio será muito
instrutivo para aqueles que o atacarem.  Neste desafio, você deve elaborar um
\textit{esquema de teste comparativo de desempenho para as várias
  implementações de tabelas de símbolos que estudaremos ao longo do semestre}.

Por exemplo, uma base para tal teste seria o seu \texttt{ep1}.  Naquele EP,
você implementou a tabela de símbolos de forma modular.  Portanto, cada vez
que estudarmos uma nova implementação de tabelas de símbolos, você pode
substituir o seu \texttt{ST.c} de seu \texttt{ep1} para obter uma nova versão
do seu EP.

Um outro exemplo instrutivo é o programa de indexação de textos, disponível em 
$
\href{http://www.ime.usp.br/~yoshi/2001i/mac323/exx/Text_index}%
{\texttt{http://www.ime.usp.br/\~\null yoshi/2001i/mac323/exx/Text\_index}}
$.

\subsection*{A sua tarefa}
Elabore um documento que descreva (\textit{i})~seu procedimento para analisar
o desempenho de seus programas e (\textit{ii})~seus resultados com várias
implementações de tabelas de símbolos.


\subsubsection*{Metodologia e literatura de suporte}
Você certamente achará útil estudar com cuidado as análises de desempenho
apresentadas no livro do \href{http://www.cs.princeton.edu/~rs/}{Sedgewick}
[\href{http://www.awl-he.com/titles/0201314525.html}{\textit{Algorithms
    in~C}}, 3a.~edição, vol.~1, Addison Wesley Longman, 1998].

Outros livros e mateiral de suporte muito importantes são os seguintes:
\begin{enumerate}
\item Um esquema refinado de teste de desempenho proposto por
  \href{http://www-cs-staff.Stanford.EDU/~knuth/}{D.$\,$E.~Knuth} envolve a
  contagem do número de acessos à memória.  Para este tópico, você pode
  consultar algum colega que já tenha feito a disciplina MAC328,
  \textsl{Algoritmos em Grafos}.  Esta disciplina, nos últimos 5~anos, tem
  sido baseada em parte no \href{http://www-cs-staff.Stanford.EDU/~knuth/sgb.html}%
  {\textit{Stanford GraphBase}}.  (Veja também a
  \href{http://www.ime.usp.br/~pf/SGB/index.html}{página} do professor
  \href{http://www.ime.usp.br/~pf}{Paulo Feofiloff} sobre o SGB.)  Seria
  excelente você estudar algumas implementações de tabelas de símbolos usando
  a metodologia de Knuth.
  
\item Um livro muito instrutivo sobre programação em geral e eficiência em
  particular é o \href{http://www.programmingpearls.com/}{\textit{Programming
      Pearls}}, de \href{http://www.cs.bell-labs.com/who/jlb/index.html}{Jon
    Bentley}, da \href{http://www.bell-labs.com/}{Bell Labs}.  Em particular,
  na Coluna~9 há uma discussão sobre \textit{code tuning} (ajustes finos de
  programas) e a técnica de \textit{profiling}.
  
\item Finalmente, você também pode consultar outro excelente livro,
  \href{http://cm.bell-labs.com/cm/cs/tpop/}{\textit{The Practice of
      Programming}}, de \href{http://www.cs.bell-labs.com/who/bwk/}{Brian
    W.~Kernighan} e \href{http://www.cs.bell-labs.com/who/rob/}{Rob Pike}.  Os
  Capítulos~2 e~7 deste livro são de particular interesse para nós.

\end{enumerate}

\subsubsection*{Observação}
Você pode entregar seu relatório em partes, pois estudaremos implementações
novas até o fim do semestre.  Entretanto, você deve de qualquer forma produzir
um relatório final, contendo uma análise comparativa geral.

\subsection*{Avaliação}
Na avaliação de seu relatório, estarei particularmente interessado na
metodologia que você adotou para medir e comparar o desempenho de seus
programas.  Ademais, também estarei muito interessado em seus resultados e
conclusões. 

\end{document}

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