%\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}

\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\btreeplusprog{\textbf{BtreeX}}

\def\tour{\emph{tour}}
\begin{document}

\maketitle

\section{Preliminares}

Neste trabalho voc\^e estudar\'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 cache.
\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 detec\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{Veja \cite{dek:taocp:iii,cormen:lrs:algo}.
	}
	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:basics}.

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

\begin{ex}\label{ex:btreeplus}
	Implemente um programa que use um \'{\i}ndice baseado em
	\btree\footnote{Sobre \btree\ em geral veja \cite{dek:taocp:iii}
	e veja o \hcomer{\it survey} sobre varia\c{c}\~oes.
	}
	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:plus}.

	O programa compilado resultante ser\'a denominado \btreeplusprog.
\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 acessos a disco;
		\item uso de cache;
		\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. 

	O uso do programa \href{http://valgrind.org/}{valgrind} na
	obten\c{c}\~ao de dados de uso de \emph{cache} e mem\'oria para 
	seu artigo.
\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:basics}; \btreeplusprog,
parte do exerc\'{\i}cio \ref{ex:btreeplus}, cujo \'{\i}ndice \'e descrito 
em \ref{btree:plus}.}
admitir\~ao o mesmo tipo de \textbf{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 sa\'{\i}da de cada programa}\label{sec:input}
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
				\'e um par composto da palavra e o nome do 
				documento em que ela ocorre, separados 
				por um espa\c{c}o em branco.
		\end{itemize}

		Por exemplo, um arquivo com o formato da figura \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{zlist}, cont er\'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 ou
		mais
		arquivos com o \'{\i}ndice gerado pelo seu programa. Note
		que o \'{\i}ndice gerado deve poder ser reutilizado para
		opera\c{c}\~oes posteriores: deve ser poss\'{\i}vel executar seu
		programa v\'arias vezes sobre o mesmo \'{\i}ndice.
\end{itemize}

\subsection{Dados de sa\'{\i}da de seus programas}
Todo \emph{output} gerado pelo seu programa ser\'a gravado em arquivos 
como descrito na se\c{c}\~ao \ref{sec:input}.

\section{Os algoritmos de indexa\c{c}\~ao}
Os dois programas construir\~ao \'{\i}ndices obrigatoriamente baseados em 
\btree. O primeiro programa, \btreeprog, do exerc\'{\i}cio \ref{ex:btree},
usar\'a em sua implementa\c{c}\~ao uma das varia\c{c}\~oes  de \btree,
descrita na se\c{c}\~ao \textbf{6.2.4} de \cite{dek:taocp:iii} ou em
\cite{cormen:lrs:algo}. 

Em seu segundo programa, \btreeplusprog, do exerc\'{\i}cio \ref{ex:btreeplus},
voc\^e tentar\'a obter uma \btree\ que seja eficiente em termos uso
de espa\c{c}o em disco, redu\c{c}\~ao de acessos a disco e tempo
de pesquisa dentro de um n\'o.

\subsection{\'Indice baseado em \btree}\label{btree:basics}
O programa \btreeprog\ usar\'a obrigatoriamente um \'{\i}ndice baseado em 
alguma variante de \btree, descrita 
descrita na se\c{c}\~ao \textbf{6.2.4} de \cite{dek:taocp:iii} ou em
\cite{cormen:lrs:algo}. \'E importante levar em conta que:

\begin{itemize}
	\item Suas chaves s\~ao strings de tamanhos vari\'aveis: pode haver 
		palavras a indexar com um caracter e palavras com cem
		caracteres. Para superar esta dificuldade voc\^e pode, como
		descrito em \cite{dek:taocp:iii}:
		\begin{itemize}
			\item armazenar nos n\'os refer\^encias para
				ocorr\^encias de palavras, em vez das pr\'oprias
				palavras;
			\item fixar o espa\c{c}o dispon\'{\i}vel por n\'o para
				as chaves, mas permitir que cada uma delas ocupe
				espa\c{c}o vari\'avel.
		\end{itemize}
	\item Seu \'{\i}ndice e seus documentos residir\~ao necessariamente
		em disco.
\end{itemize}

\subsection{\'Indice baseado em \btree\ para strings}\label{btree:plus}
O programa \btreeplusprog\ usar\'a obrigatoriamente um \'{\i}ndice baseado em 
alguma variante de \btree, 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:iii};
	\item \hprefixbtree{Prefix \btree};
	\item \hlometbtree{Evolu\c{c}\~ao de estudo de caches}.
\end{itemize}

Uma restri\c{c}\~ao fundamental \'e de que ele deve ser necessariamente mais 
eficiente do que o programa \btreeprog. Voc\^e deve tentar encontar uma forma 
de tratar eficientemente os seguintes fatos:
\begin{itemize}
	\item Suas chaves s\~ao strings de tamanhos vari\'aveis: pode haver 
		palavras a indexar com um caracter e palavras com cem
		caracteres.
	\item Seu \'{\i}ndice e seus documentos residir\~ao necessariamente
		em disco.
	\item Suas pesquisas em mem\'oria devem tentar usar o melhor
		poss\'{\i}vel o cache de sua m\'aquina.
\end{itemize}

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

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}

\def\exref#1{Exerc\'{\i}cio \ref{ex:#1}}

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
		\exref{btree} & $30$ \\
		\exref{btreeplus} & $30$ \\
		\exref{article} & $20$ \\
		Se\c{c}\~ao \ref{perform:btree} & $10$ \\
		Se\c{c}\~ao \ref{perform:btreeplus} & $10$ \\\hline
	\end{tabular}
	\caption{Tabela de atribui\c{c}\~ao de cr\'editos}
	\label{tab:credits}
\end{table}

\subsection{Desempenho do programa \btreeprog}\label{perform:btree}
Este item atribuir\'a pontos de acordo com o desempenho do programa 
\btreeprog, de acordo com o crit\'erio de desempenho:
o programa mais r\'apido ganha $10$ cr\'editos.

\subsection{Desempenho do programa \btreeplusprog}\label{perform:btreeplus}
Este item atribuir\'a pontos de acordo com o desempenho do programa 
\btreeplusprog, de acordo com o crit\'erio de desempenho:
o programa mais r\'apido ganha $10$ cr\'editos.

\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 ou 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 data final de entrega deste trabalho \'e 04/04/05.

A mensagem de submiss\~ao do seu trabalho dever\'a conter:
\begin{itemize}
	\item \textbf{Subject:} \textbf{tbo.tp2}
	\item \textsl{Attachment}: \textbf{tp2.tar.bz2}
\end{itemize}

O corpo da mensagem ser\'a desprezado. O arquivo anexdo dever\'a ser
obrigatoriamente denominado 

\centerline{\textbf{tp2.tar.bz2}}

Ele conter\'a todo os fontes necess\'arios para compilar  seu trabalho pr\'atico,
incluindo fontes em \LaTeX, C/C++, Makefile e arquivo de
identifica\c{c}\~ao. 

As seguintes regras devem ser rigorosamente seguidas, n\~ao cabendo recurso no
caso de alguma delas n\~ao ser respeitada:
\begin{itemize}
	\item Nenhum compilado deve ser enviado.
	\item N\~ao use os pacotes \textbf{listings} e \textbf{noweb} no artigo 
		deste trabalho. 
	\item O \tarball\ do seu trabalho conter\'a a seguinte estrutura:
		\begin{itemize}
			\item arquivo de \textbf{id}

				Conter\'a uma linha inicial com \emph{e-mail}
				de contato do grupo e, depois, uma linha de
				identifica\c{c}\~ao para elemento do grupo,
				contendo n\'umero de matr\'{\i}cula e nome
				completo separados por '\textbf{:}' (dois
				pontos.) Por exemplo:

				\begin{verbatim}
				jolero@gmail.com
				99900089:Ze' do lero 
				\end{verbatim}
			\item arquivo \textbf{Makefile}
			
			\item diret\'orio \textbf{Btree}

				Conter\'a a implementa\c{c}\~ao do
				exerc\'{\i}cio \exref{btree}.

			\item diret\'orio \textbf{BtreeX}

				Conter\'a a implementa\c{c}\~ao do
				exerc\'{\i}cio \exref{btreeplus}
				
		
			\item diret\'orio \textbf{doc}

				Conter\'a os fontes de toda a documenta\c{c}\~ao 
				do trabalho.
		\end{itemize}

		Adicionalmente seu \tarball\ poder\'a conter outros diret\'orios
		relevantes para a sua implementa\c{c}\~ao.

	\item seu \tarball\ ser\'a aberto e compilado com as seguintes linhas:

		\begin{verbatim}
		tar -jxf tp2.tar.gz
		make all
		\end{verbatim}

		Essas linhas gerar\~ao os seguintes arquivos:

		\begin{itemize}
			\item \textbf{Btree}

				Execut\'avel que implementa a solu\c{c}\~ao do
				exerc\'{\i}cio
				\exref{btree}.
			\item \textbf{BtreeX}

				Execut\'avel que implementa a solu\c{c}\~ao do 
				\exref{btreeplus}.
			\item \textbf{artigo.pdf}

				Artigo em formato \textbf{PDF}, que avalia 
				qualidade de \tour\ e desempenho dos algoritmos.

		\end{itemize}
\end{itemize}


\section{Trabalho extra}
Este trabalho n\~ao \'e obrigat\'orio. Ele poder\'a contribuir
para a sua nota nas
seguintes condi\c{c}\~oes:
\begin{itemize}
 	\item Se voc\^e concluir o semestre com nota igual ou superior a seis, 
		estar\'a aprovado e a nota 
		deste trabalho poder\'a ser
		usada para elevar sua nota final, como
		descrito no documento de regras de avalia\c{c}\~ao da
		disciplina.
	\item Alunos que conclu\'{\i}rem o semestre com nota entre cinco e seis,
		ser\~ao aprovados com nota seis desde que: concluam 
		$60\%$ das listas de exer\c{c}\'{\i}cio
		e alcancem nota sete neste trabalho.
	\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,
		\`as 13 horas,
		na sala de aulas usada durante o semestre.
\end{itemize}

\bibliographystyle{amsplain}
\bibliography{abbrev,general,program,simulation,co,algorithms,compgeo,formal,maths}

\end{document}

