%\documentclass[dvips,12pt]{amsart}
\documentclass[pdftex,12pt]{amsart}
\usepackage{amsmath}
\usepackage[portuges]{babel}
\usepackage{enumerate}

\usepackage{hyperref}
\def\hbref#1#2#3{\href{#1#2}{#3}}


\def\cwurl{http://www.inf.ufes.br/~raulh/ufes/teaching/courses/s.and.s/page/cw/}

\input{defport}
\input{deflogic}
\input{defseqs}
\input{deftrees}
\def\stb#1#2{\ensuremath{st.#1.b.#2}}
\def\xstb#1#2#3{\ensuremath{\stb#1#2=\langle#3\rangle}}
\def\xoldstb#1#2#3{\ensuremath{#1\in\stb#2#3}}

\def\stdin{\emph{stdin}}
\def\stdout{\emph{stdout}}
\def\tarball{\emph{tarball}}
\def\mailto#1{\href{mailto:#1}{#1}}
\title{Trabalho 2: \\ Indexa\c{c}\~ao em Disco \\
       Draft 0}

\author{Raul H.C. Lopes}
\def\radixsort{\emph{radix sort}}
\def\splitter{\emph{splitter}}
\def\quicksort{\emph{quick sort}}
\def\mergesort{\emph{merge sort}}
\def\prefsum{prefix sum}
\def\real{Real}

%\setcounter{page}{0}
%\setcounter{section}{0}
%\setcounter{subsection}{0}

\def\clang{linguagem \emph{C/C++}}
\def\hbuffertree#1{\href{http://www.brics.dk/RS/96/28/BRICS-RS-96-28.pdf}{#1}}
\def\hcomer#1{\href{http://portal.acm.org/citation.cfm?id=356776}{#1}
\def\hprefixbtree#1{\href{http://portal.acm.org/citation.cfm?id=320530}{#1}}
\def\hlometbtree#1{\href{http://www.cs.duke.edu/~junyang/cps216/papers/lomet-2001.pdf}{#1}}
\def\hbtreecaches#1{\href{http://doi.ieeecomputersociety.org/10.1109/ICDE.2001.914847}{#1}}

\def\btreeprog{\textbf{Btree}}
\def\sortprog{\textbf{Sort}}

\begin{document}

\maketitle

\section{Preliminares}

Neste trabalho voc\^e estudara\'a uma das mais importantes estruturas de
indexa\c{c}\~ao de arquivos: a \btree\footnote{Veja \cite{dek:taocp:iii},
\cite{cormen:lrs:algo}, como refer\^encias gerais sobre \btree e o 
\hcomer{\emph{survey}}
que aborda \btree\ e varia\c{c}\~oes.}.

Neste trabalho em particular voc\^e dever\'a concentrar sua aten\c{c}\~ao na
implementa\c{c}\~ao de indexa\c{c}\~ao em disco via \btree\ e em detalhes
de desempenho envolvidos, como:
\begin{itemize}
	\item redu\c{c}\~ao de acesso a disco;
	\item efici\^encia de pesquisa dentro do n\'o;
	\item import\^ancia de uso inteligente de \c{c}ache.
\end{itemize}

Algumas dicas importantes sobre a execu\c{c}\~ao do trabalho seguem.
\begin{enumerate}
	\item N\~ao deixe de ler este documento por completo antes de iniciar o
		trabalho.
	\item Siga estritamente as especifica\c{c}\~oes deste documento: qualquer
		desvio delas pode significar a anula\c{c}\~ao de um
		exerc\'{\i}cio ou de todo o trabalho.
\end{enumerate}

O trabalho pode ser executado em grupos, mas, como estabelecido na se\c{c}\~ao 
\ref{credits}, grupos maiores recebem menos cr\'editos. Um elemento importante
da avalia\c{c}\~ao do trabalho trata da dete\c{c}\~ao de mutualismo
parasit\'ario: situa\c{c}\~ao em que um aluno atua de vampiro parasita 
sugando o resultado do trabalho do grupo. Fato: pl\'agio em qualquer item de
um trabalho implica
na anula\c{c}\~ao completa do trabalho  do(s) grupo(s) envolvidos.
Qualquer elemento de um grupo pode ser,
durante a execu\c{c}\~ao do trabalho ou ap\'os a entrega do
mesmo, avaliado em rela\c{c}\~ao ao conhecimento do que foi
feito. Essa avalia\c{c}\~ao poder\'a ser feita de forma oral ou por escrito.


\section{Os exerc\'{\i}cios}
O objetivo dos exerc\'{\i}cios consiste em estudar o desempenho de
duas estruturas para indexar  uma s\'erie de documentos.

\begin{ex}\label{ex:btree}
	Implemente um programa que use um \'{\i}ndice baseado em
	\btree\footnote{
	}
	para realizar opera\c{c}\~oes sobre as ocorr\^encias de palavras de
	uma s\'erie de textos como descrito na se\c{c}\~ao \ref{sec:ops}.
	Seu \'{\i}ndice ter\'a obrigatoriamente a estrutura descrita na 
	\ref{btree:idx}.

	O programa compilado resultante ser\'a denominado \btreeprog.
\end{ex}

\begin{ex}\label{ex:sort}
	Implemente um programa que um \'{\i}ndice constru\'{\i}do via 
	ordena\c{c}\~ao externa\footnote{
	}
	para realizar opera\c{c}\~oes sobre as ocorr\^encias de palavras de
	uma s\'erie de textos como descrito na se\c{c}\~ao \ref{sec:ops}.
	Seu \'{\i}ndice ter\'a obrigatoriamente a estrutura descrita na 
	\ref{sort:idx}.

	O programa compilado resultante ser\'a denominado \sortprog.
\end{ex}

\begin{ex}\label{ex:article}
	Escreva artigo em \LaTeX, contendo estudo de desempenho de seus 
	indexadores com diversos conjuntos de documentos. Seu artigo abordar\'a
	ao menos:
	\begin{itemize}
		\item n\'umero de acesos a disco;
		\item uso de \c{c}ache;
		\item tempo de execu\c{c}\~ao.
	\end{itemize}

	Procure caracterizar esses tr\^es itens em rela\c{c}\~ao a
	diferentes tipos de seq\"u\^encias de opera\c{c}\~oes. 
\end{ex}

\section{As opera\c{c}\~oes a implementar}\label{sec:ops}

Seus dois programas\footnote{
Esses programas s\~ao: \btreeprog, parte do exerc\'{\i}cio \ref{ex:btree}
e que usa \'{\i}ndice descrito na se\c{c}\~ao \ref{btree:idx}; \sortprog,
parte do exerc\'{\i}cio \ref{ex:sort}, cujo \'{\i}ndice \'e descrito 
em \ref{sort:idx}.}
admitir\~ao o mesmo tipo de \input\ e implementar\~ao as mesmas opera\c{c}\~oes,
que consistem em inserir palavras de tamanho vari\'avel em um \'{\i}ndice,
excluir palavras e listar ocorr\^encias de palavras desse mesmo
\'{\i}ndice.

\subsection{Dados de entrada de cada programa}
Cada programa receber\'a como \'unico argumento da linha de comando o
nome de um arquivo com o conjunto das opera\c{c}\~oes a realizar. Esse
arquivo ter\'a a seguinte estrutura:
\begin{itemize}
	\item A primeira linha: nome do diret\'orio contendo os documentos de
		entrada.
	\item A segunda linha: nome do diret\'orio contendo os arquivos de 
		\'{\i}ndice gerados.
	\item A terceira linha: o nome do diret\'orio que conter\'a os
		resultados das opera\c{c}\~oes do tipo \textbf{l}, definido a
		seguir.

		Este diret\'orio conter\'a um arquivo para cada opera\c{c}\~ao 
		\textbf{l}, veja abaixo, especificada.
	\item As linhas seguintes, em n\'umero vari\'avel e em qualquer ordem
		ter\~ao sempre o formato:  uma letra, definindo uma
		opera\c{c}\~ao, seguida de um espa\c{c}o, seguida de um
		nome de arquivo, que estar\'a contido no dirtet\'orio de 
		entrada. As opera\c{c}\~oes (e letras) associadas s\~ao:
		\begin{itemize}
			\item \textbf{i}: insira no \'{\i}ndice todas as 
				palavras do documento;
			\item \textbf{d}: exclua do \'{\i}ndice todas as 
				ocorr\^encias de palavras do documento;
			\item \textbf{l}: liste em ordem crescente todas
				as ocorr\^encias de palavras
				que tenham como prefixo as palavras contidas
				no documento. Uma ocorr\^encia de uma palavra
				em par composto da palavra e o nome do 
				documento em que ela ocorre, separados 
				por branco.
		\end{itemize}

		Pro exemplo, um arquivo com o formato da \ref{fig:format}
		define:
		\begin{figure}
			\begin{center}
				\begin{verbatim}
				indir
				outdir
				listdir
				i text
				i ztext
				l list
				d ztext
				l alist
				\end{verbatim}
			
			\end{center}
			\caption{Exemplo de entrada}
			\label{fig:format}
		\end{figure}
		\begin{enumerate}
			\item O diret\'orio de nome \textbf{indir} cont\'em os
				arquivos de entrada do seu programa.
			\item O diret\'orio de nome \textbf{outdir{ conter\'a os
				arquivos gerados pelo seu programa.
			\item A primeira opera\c{c}\~ao consiste em inserir,
				no \'{\i}ndice situado no diret\'orio
				\textbf{outdir},
				todos as palavras do arquivo \textbf{text},
				localizado no diret\'orio \textbf{indir}.
			\item A segunda opera\c{c}\~ao consiste em inserir,
				todos as palavras do arquivo \textbf{ztext},
				localizado no diret\'orio \textbf{indir}.
			\item A terceira opera\c{c}\~ao consiste em listar em
				ordem crescente todas
				as ocorr\^encias  de palavras que tenham como
				prefixo palavras do arquivo de nome
				\textbf{list}, contido no diret\'orio de nome
				\textbf{indir}.
			\item A quarta opera\c{c}\~ao consiste em excluir, 
				do \'{\i}ndice situado no diret\'orio
				\textbf{outdir},
				todas as palavras do arquivo \textbf{ztext},
				localizado no diret\'orio \textbf{indir}.
			\item A quinta opera\c{c}\~ao consiste em listar em
				ordem crescente todas
				as ocorr\^encias  de palavras que tenham como
				prefixo palavras do arquivo de nome
				\textbf{alist}, contido no diret\'orio de nome
				\textbf{indir}.
			\item Ao final, o diret\'orio de nome \textbf{listdir}
				conter\'a dois arquivos:
				\begin{itemize}
					\item \textbf{list}, conter\'a o
						resultado da primeira
						opera\c{c}\~ao \textbf{l},
						realizada com palavras do
						arquivo \textbf{list}.
					\item \textbf{list}, conter\'a o
						resultado da segunda
						opera\c{c}\~ao \textbf{l},
						realizada com palavras do
						arquivo \textbf{alist}.
				\end{itemize}

				Por exemplo, o arquivo \textbf{list}, em
				\textbf{listdir}, poderia conter a linha

				\centerline{\it brrrp ztext}

				que \emph{diz} que a palavra \textbf{brrrp}
				ocorre no arquivo \textbf{ztext}.
		\end{enumerate}
		O diret\'orio de nome \textbf{outdir} conter\'a ao final um
		arquivo 
\end{itemize}

\subsection{\'Indice baseado em \btree}\label{btree:idx}
O programa \btree\ usar\'a obrigatoriamente um \'{\i}ndice baseado em 
alguma variante de \'arvore. Use obrigatoriamente uma variante definida em
um dos artigos:
\begin{itemize}
	\item \hcomer{Refer\^encia b\'asica} sobre \btree\ e varia\c{c}\~oes;
	\item A b\'{\i}blia \cite{dek:taocp:ii};
	\item \hprefixbtree{Prefix \btree};
	\item \hlometbtree{Evolu\c{c}\~ao de estudo de caches}.
\end{itemize}

\subsection{\'Indice baseado em seq\"u\^encia ordenada}
O programa construir\'a um \'{\i}ndice de palavras distintas ordenado via
\extsort. A refer\^encia fundamental sobre o assunto \'e a b\'{\i}blia 
\cite{dek:taocp:iii}.

\section{Cr\'editos}\label{credits}

  implementacao  (5)
  artigo curto discutindo  para varios tipos de textos: (3) 
              numero de disk acceses
	      numeros char cmps
	      cache misses
  desempenho de speed (2)

A defini\c{c}\~ao dos  crit\'erios de avalia\c{c}\~ao 
A atribui\c{c}\~ao de nota para o trabalho ocorrer\'a em duas fases:
\begin{enumerate}
	\item Atribui\c{c}\~ao de cr\'editos pelo trabalho submetido, de 
		acordo com a tabela \ref{tab:credits}.
	\item Defini\c{c}\~ao do multiplicador de acordo com a tabela
		\ref{tab:mult}.
\end{enumerate}

\subsection{Defini\c{c}\~ao do n\'umero de cr\'editos}

Cada trabalho submetido ser\'a avaliado para receber de zero a cem cr\'editos
de acordo com a tabela \ref{tab:credits}.

\begin{table}
	\centering
	\begin{tabular}{|l|r|}\hline
		Crit\'erio & Cr\'editos \\ \hline
		Se\c{c}\~ao \ref{ex:btree} & $30$ \\
		Se\c{c}\~ao \ref{ex:sort} & $30$ \\
		Se\c{c}\~ao \ref{ex:article} & $20$ \\
		Se\c{c}\~ao \ref{performance} & $20$ \\
	\end{tabular}
	\caption{Tabela de atribui\c{c}\~ao de cr\'editos}
	\label{tab:credits}
\end{table}

\subsection{Desempenho}\label{performance}
Este item atribuir\'a pontos de acordo com o desempenho de cada um dos
programas:
\begin{itemize}
	\item \btreeprog: o melhor ganha $10$ cr\'editos, e os outros 
		receber\~ao 
		proporcionalmente;
	\item \sortprog: o melhor ganha $10$ cr\'editos, e os outros 
		receber\~ao 
		proporcionalmente.

\end{itemize}


\subsection{Defini\c{c}\~ao de multiplicador}

O nota  de cada trabalho \'e dada pelo n\'umero de cr\'editos obtidos pelo
trabalho multiplicado pelo fator da tabela \ref{tab:mult}.

\begin{table}
	\centering
	\begin{tabular}{|l|r|}\hline
		Fator & Multiplicador \\
		Grupos de 1 aluno & $11/100$ \\
		Grupos de 2 alunos & $ 10/100$ \\
		Grupos de 3 alunos & $ 75/100$ \\
		Grupos de 4 alunos & $ 60/100$ \\
	 	Grupos de mais 4 alunos & $0$ \\
		Pl\'agio & $0$ \\ \hline
	\end{tabular}
	\caption{Tabela de multiplicadores}
	\label{tab:mult}
\end{table}

Em caso de pl\'agio todos os trabalhos de grupos envolvidos s\~ao anulados.
Poder\'a ser enquadrado como pl\'agio qualquer trabalho em que um mais 
alunos do grupo n\~ao tenham conhecimento de qualquer item do trabalho. Esse
conhecimento dever\'a ser demonstrado em prova e/ou enttrevista.

\section{A submiss\~ao para corre\c{c}\~ao}\label{submit}

A defini\c{c}\~ao do formato de submiss\~ao do trabalho estar\'a na vers\~ao 
deste documento do dia 07/03/05.

A data provis\'oria de entrega deste trabalho \'e 17/03/05.

\section{Trabalho extra}
Este trabalho n\~ao \'e obrigat\'orio. Ele contribuir\'a para a sua nota nas
seguintes condi\c{c}\~oes:
\begin{itemize}
	\item Se vo\c^e aprovado com nota igual ou superior a seis, a nota 
		deste trabalho ser\'a usada para elevar sua nota final, como
		descrito no documento de regras de avalia\c{c}\~ao da
		disciplina.
	\item Se voc\^e fizer prova final, ela ser\'a composta de duas
		partes: este trabalho, valendo quarenta por cento da nota da
		prova, e uma prova escrita a ser realizada no dia 16/03/05,
		na sala de aulas usada durante o semestre.
\end{itemize}

\end{document}

