%\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\crseurl{http://www.inf.ufes.br/~raulh/ufes/teaching/courses/lpii}

\def\cwurl{\crseurl/page/cw/0/}

\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 0: \\ \'Arvores e estruturas de prioridade\\
       Draft 1}

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


\def\scref#1{sc. \ref{#1}}
\def\exref#1{ex. \ref{ex:#1}}
\def\tabref#1{tab. \ref{tab:#1}}

\begin{document}

\maketitle

\section{Preliminares}

Neste trabalho voc\^e exercitar\'a seus conhecimentos de algumas estruturas
fundamentais da arte de programa\c{c}\~ao de computadores: seq\"u\^encias, 
\'arvores bin\'arias de pesquisa e de prioridade, ordena\c{c}\~ao. O objetivo
consiste em explorar os recursos de linguagens de programa\c{c}\~ao funcionais 
para obter c\'odigo claro e compacto e, simultaneamente, buscar efici\^encia.

A se\c{c}\~ao \ref{graphs:tsp}
apresenta os fundamentos de teoria de grafos que ser\~ao
usados no trabalho.
A se\c{c}\~ao \ref{exs} apresenta os exerc\'{\i}cios a realizar. A se\c{c}\~ao
\ref{credits} define os crit\'erios que ser\~ao utilizados na corre\c{c}\~ao do
trabalho e atribui\c{c}\~ao de pontos.  A se\c{c}\~ao \ref{submit}
define o que deve ser entregue e a forma de submiss\~ao do trabalho para
corre\c{c}\~ao. A se\c{c}\~ao \ref{errata} descreve alterac\~oes feitas 
neste documento desde a primeira vers\~ao.

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.
	\item Comece a trabalhar de imediato: o trabalho foi concebido
		para ser realizado em quatro semanas. Depois disso, 
		voc\^e ter\'a outro
		trabalho e nova prova.
\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.

\def\tsp{\textbf{TSP}}
\def\tour{\textbf{tour}}
\def\xpair#1#2{\ensuremath{(#1,#2)}}
\def\xdist#1#2{\ensuremath{dist(#1,#2)}}

\section{O Problema do Caixeiro Viajante}\label{graphs:tsp}
Os exerc\'{\i}cios deste trabalho lidam com o \emph{Problema do Caixeiro
Viajante}, \emph{Traveling Salesman Problem}, de agora em diante chamado \tsp.
Este problema demanda encontrar o caminho mais curto para visitar cada cidade
de um conjunto dado exatamente uma vez e retornar ao ponto de partida. Para 
representar cidades, usaremos uma abstra\c{c}\~ao: um grafo n\~ao dirigido.

Um grafo n\~ao dirigido \'e um par \xpair VE, onde $V$ \'e um conjunto de pontos
e $E$ \'e um conjunto de pares de pontos, cada par de pontos sendo chamado de 
arestas. Para nosso trabalho valem as seguintes restri\c{c}\~oes:
\begin{itemize}
	\item uma aresta \xpair uv indica que existe uma conex\~ao direta do
		ponto $u$ ao ponto $v$;
	\item o grafo \'e geom\'etrico: os pontos s\~ao elementos 
		de um espa\c{c}o 
		Euclideano de duas dimens\~oes;
	\item as coordenadas dos pontos s\~ao pares de inteiros positivos;
	\item para qualquer par de pontos $u$ e $v$ do grafo existe uma  aresta 
		\xpair uv, que tem um custo associado
		dado pela dist\^ancia entre $u$ e $v$;
	\item o grafo \'e n\~ao direcionado e a exist\^encia de uma aresta 
		\xpair uv indica a exist\^encia de outra aresta \xpair vu com
		mesmo custo que a primeira.
\end{itemize}

Um caminho em um grafo \'e uma seq\"u\^encia de pontos do mesmo. Um circuito
Hamiltoniano $C$
\'e uma seq\"u\^encia de pontos com as seguintes restri\c{c}\~oes:
\begin{itemize}
	\item cada ponto do grafo inicial figura exatamente uma vez no circuito;
	\item o circuito indica a seq\"u\^encia de pontos a visitar para sair
		de um v\'ertice inicial, o primeiro da seq\"u\^encia dado, ir
		at\'e o \'ultimo v\'ertice da seq\"u\^encia, visitando todos os
		outros na ordem dada por $C$, e voltar ao ponto de partida.
\end{itemize}

Um circuito Hamiltoniano, que chamaremos simplemente de \tour,
consiste em uma
permuta\c{c}\~ao do conjunto de pontos de grafo dado. Assumindo que $C!i$ denote
o i-\'esimo elemento do tour $C$, o custo do tour \'e dado por:
$$ cost.C = \bnd{+}{i}{\lelt 0i{n-1}}{\xdist{C!i}{C!(i+1)}}+\xdist{C!(n-1)}{C!0}$$

onde $\xdist uv$ \'e a dist\^ancia geom\'etrica de $u$ a $v$.

O problema do \tsp, como colocado neste trabalho, consiste, ent\~ao, em
determinar o \tour\ de menor custo.




\section{Os exerc\'{\i}cios}\label{exs}
Esta se\c{c}\~ao cont\'em exerc\'{\i}cios sobre estruturas de dados e algoritmos 
usados freq\"u\^entemente em bancos de dados espaciais e problemas sobre grafos
como o \tsp.

Em todos os exerc\'{\i}cios represente o \tour\ resultante 
como uma lista de pontos
sem repeti\c{c}\~ao. Por exemplo, o \tour que parte do ponto $p_0$, vai para
$p_2$, $p_1$ e volta a $p_0$ seria representado pela lista:
$$ [p_0,p_2,p_1]$$

e n\~ao pela lista

$$ [p_0,p_2,p_1,p_0]$$

Note que essa restri\c{c}\~ao refere-se apenas ao \tour\ resultante. Sua
representa\c{c}\~ao interna dos diversos algoritmos fica
a cargo de sua criatividade.

\subsection{\'Arvores bin\'arias espaciais}\label{kdtree}

\def\jbkdtree{\href{http://portal.acm.org/citation.cfm?doid=98524.98564}{K-d
trees for semidynamic point sets}}

\def\kdtree{\emph{kd-tree}}
\def\xkdtree#1{\ensuremath{K\!Dtree\ #1}}
\def\xpoint#1{\ensuremath{Point\ #1}}

Neste trabalho, ser\~ao apenas considerados problemas em duas dimens\~oes.
As \'arvore bin\'arias espaciais usadas armazenar\~ao pontos de duas
coordenadas. Uma \'arvore bin\'aria espacial, ver \jbkdtree, 
apresenta as seguintes
caracter\'{\i}sticas:
\begin{itemize}
	\item cada folha armazena uma seq\"u\^encia de ao menos um ponto e at\'e
		oito pontos.
	\item um n\'o interno particiona o conjunto de pontos de sub\'arvore de
		que ele \'e raiz e
		define ao menos:
		\begin{itemize}
			\item a coordenada usada no particionamento;
			\item o valor da linha de particionamento;
			\item a sub\'arvore da esquerda contendo os pontos que
				t\^em na coordenada de particionamento valor
				menor do que (ou igual a) o valor da linha de
				particionamento;
			\item a sub\'arvore da direita contendo os pontos que
				t\^em na coordenada de particionamento valor
				maior do que o valor da linha de
				particionamento
		\end{itemize}
	\item no  caminho da raiz para as folhas os n\'os internos alternam o
		particionamento dos pontos pelas coordenadas dadas.
\end{itemize}

Defina os seguintes tipos em Haskell:
\begin{itemize}
	\item $\xpoint a$ para representar pontos de um grafo, cujas
		coordenadas s\~ao do tipo $a$.
	\item $\xkdtree a$ para representar tipo das \kdtree\ de pontos do
		tipo $\xpoint a$.
\end{itemize}


\begin{ex}\label{ex:kdtree}
	Defina em Haskell uma estrutura \xkdtree{a} que implemente
	uma \kdtree\ sobre pontos de $a$. Sua estrutura deve apresentar ao
	menos as seguintes opera\c{c}\~oes:
	
	\begin{itemize}
		\item \emph{kdBuild xs}: constr\'oi uma \kdtree\ a partir da
			lista de pontos \emph{xs}.
		\item \emph{kdSearch p t}: determina se o ponto $p$ est\'a na
			\kdtree\ $t$.
		\item \emph{kdInsert p t}: insere $p$ na \kdtree\ $t$.
		\item \emph{kdDelete p t}: exclui $p$ de $t$.
		\item \emph{kdUndelete p t}: reinsere item $p$ previamente
			exclu\'{\i}do de $t$.
		\item \emph{kdNN p t}: encontra o vizinho mais pr\'oximo de $p$
			em $t$.
	\end{itemize}

	
\end{ex}

\begin{ex}\label{ex:kdtree:test}
	Apresente testes comparativos de corre\c{c}\~ao, desempenho e uso de
	mem\'oria da estrutura do exerc\'{\i}cio \exref{kdtree}, 
	usando dados dos arquivos da se\c{c}\~ao \ref{testing}.
\end{ex}



\subsection{\'Arvores bin\'arias de priodidades}\label{pqtree}
\def\hrefsplay{\href{http://portal.acm.org/citation.cfm?id=3835}%
{Self-ajusting Binary Search Trees}}
\def\hrefbinq{\href{http://portal.acm.org/citation.cfm?id=359478}%
{A data structure for manipulating priority queues}}

\def\binheap{\'Arvore bin\'aria de prioridades}
\def\binheaps{\'Arvores bin\'arias de prioridades}

\def\hbinpq#1{\ensuremath{Binpq\ #1}}
\def\hmap#1#2{\ensuremath{#1\rightarrow#2}}
\def\xmerge#1#2{\ensuremath{merge\ #1\ #2}}
\begin{ex}\label{ex:binq}
	Uma \binheap\ \'e uma \'arvore bin\'aria ordenada da raiz para as
	folhas: a raiz \'e menor (ou igual) a qualquer elemento da \'arvore
	e cada uma das suas sub\'arvore \'e uma \binheap.

	Escolha uma estrutura para representar sua \'arvore de prioridades 
	dentre as seguintes:
	\begin{itemize}
		\item \emph{Splay tree}, veja em \hrefsplay.
		\item \emph{Binomial queue}, veja em \hrefbinq.
	\end{itemize}

	Implemente em Haskell uma estrutura \emph{Priority a} para representar
	\'arvores de prioridades, de acordo com a estrutura que voc\^e escolheu.
	Sua estrutura deve ter, ao menos as seguintes opera\c{c}\~oes:
	\begin{itemize}
		\item \emph{join(q0,q1)}: realiza a uni\~ao de duas estrutras
			de prioridade{q0,q1}.
		\item \emph{findMin(q0)}: retorna o m\'{\i}nimo da estrutura.
		\item \emph{delMin(q0)}: exclui o m\'{\i}nimo da estrutura
	\end{itemize}
\end{ex}

\begin{ex}\label{ex:binq:test}
	Apresente testes comparativos de corre\c{c}\~ao, desempenho e uso de
	mem\'oria para a estrutura do exerc\'{\i}cio exref{binq}.
\end{ex}


\subsection{Heur\'{\i}sticas para STSP}\label{stsp}
\def\dsjstsp{\href{http://www.research.att.com/~dsj/papers/stspchap.pdf}{Experimental
Analysis of Heuristics for the STSP}}
\def\FI{\textbf{FI}}
\def\DMST{\textbf{DMST}}

Nos exerc\'{\i}cios a seguir, voc\^e trabalhar\'a com as heur\'{\i}stica
\textbf{Farthest Insertion (FI)}, descrita na p\'agina 23 de \dsjstsp,
e \textbf{Double Minimum Spanning Tree (DMST)}, descrita na p\'agina 22,
do mesmo artigo. Implemente todos os algoritmos em Haskell.
 
\begin{ex}\label{ex:fi}
	Implemente um algoritmo para encontrar um \tour\ para o \tsp, usando a
	heur\'{\i}stica \FI.
	
\end{ex}

\begin{ex}\label{ex:fi:test}
	Apresente testes de corre\c{c}\~ao e desempenho para o algoritmo do
	\exref{fi}.
\end{ex}

\begin{ex}\label{ex:mst}
	Implemente um algoritmo para encontrar a \'arvore geradora m\'{\i}nima
	de um conjunto de prontos.
\end{ex}

\begin{ex}\label{ex:mst:test}
	Apresente testes de corre\c{c}\~ao e desempenho para a estrutura do
	\exref{mst}.  
\end{ex}

\begin{ex}\label{ex:dmst}
	Implemente um algoritmo para encontrar um \tour\ para o \tsp, usando
	a heur\'{\i}stica \DMST.
\end{ex}

\begin{ex}\label{ex:dmst:test}
	Apresente testes de corre\c{c}\~ao e desempenho para o algoritmo do
	\exref{dmst}.
\end{ex}

\begin{ex}\label{ex:fidmst:test}
	Apresente estudo comparativo de desempho, levando em conta tempo e
	qualidade do \tour, para os algoritmos dos exerc\'{\i}cios \ref{ex:fi} e
	\ref{ex:dmst}.
\end{ex}
  
\subsection{Linguagem funcional impura}

\begin{ex}\label{ex:scheme}
	Escolha uma das heur\'{\i}sticas implementadas na \scref{stsp} e 
	implementa em Scheme, buscando obter um c\'odigo o mais r\'apido
	poss\'{\i}vel, com o obhetivo de bater o equivalente em Haskell.
\end{ex}

\begin{ex}\label{ex:scheme:test}
	Apresente testes de corre\c{c}\~ao e desempenho para os algoritmos do
	\exref{scheme}.
\end{ex}

\begin{ex}\label{ex:pureimpure:test}
	Apresente estudo comparativo de desempho, levando em conta tempo e
	qualidade do \tour, para a solu\c{c}\~ao em Scheme do \exref{scheme} e
	equivalente em Haskell.
\end{ex}
 
\subsection{Testes}\label{testing}
\def\testdata{test.data.tar.bz2}
\def\tarball#1{\it tarball #1}

O \hbref\cwurl\testdata{\tarball\testdata}
cont\'em arquivos de dados que voc\^e poder\'a
utilizar para testar seus programas. Interessa avaliar neste trabalho para
cada arquivo:
\begin{itemize}
	\item corre\c{c}\~ao do \tour\ calculado;
	\item tempo de execu\c{c}\~ao;
	\item qualidade do \tour\ quando comparado com o melhor \tour\
		poss\'{\i}vel.
\end{itemize}

Note que os arquivos de dados est\~ao no formato TSPLIB\footnote{
N\~ao deixe de
visitar o \emph{site}
\href{http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95}{TSPLIB}.
}.
Use o programa \textbf{fromtsplib.pl} para convert\^e-los para o formato
do programa \textbf{tourlen}, apresentado na se\c{c}ao \ref{ioexample}.

Abre essa diret\'orio com o comando:

\begin{verbatim}
     tar -jxf test.data.tar.bz2
\end{verbatim}

Leia o arquivo \textbf{README}, no diret\'orio \textbf{test.data} criado, para
mais informa\c{c}\~oes.

\section{Cr\'editos}

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 crit\'erios apresentados na \scref{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}\label{credits}

O n\'umero de cr\'editos atribu\'{\i}dos a cada exerc\'{\i}cio est\'a definido 
na \tabref{credits}. Note que os cr\'editos atribu\'{\i}dos aos exerc\'{\i}cios
de teste de desempenho e corre\c{c}\~ao das diferentes estruturas depender\~ao
da apresenta\c{c}\~ao de artigo em \LaTeX, apresentando tabelas comparativas 
e conclus\~oes dos experimentos realizados por cada grupo. N\~ao hesite em
discutir com outros colegas (de outros grupos) o tipo de teste a realizar. N\~ao
ser\'a considerado pl\'agio mais de um grupo apresentar extamente os mesmos
testes e at\'e estrutura de artigo. Ser\'a certamente pl\'agio coincid\^encia
em excesso nos resultados de testes! Em resumo, d\^e desde o in\'{\i}cio do
trabalho \^enfase especial \`a escrita do artigo.

\def\exval#1#2{\exref{#1} & $#2$}
\begin{table}
	\centering
	\begin{tabular}{|l|r|}\hline
		Tarefa & Valor \\ \hline
		\exval{kdtree}{8} \\
		\exval{kdtree:test}{2}\\
		\exval{binq}{8}\\
		\exval{binq:test}{2}\\
		\exval{fi}{10} \\
		\exval{fi:test}{2}\\
		\exval{mst}{8} \\
		\exval{mst:test}{2}\\
		\exval{dmst}{10} \\
		\exval{dmst:test}{2}\\
		\exval{fidmst:test}{4}\\
		\exval{scheme}{20} \\
		\exval{scheme:test}{2}\\
		\exval{pureimpure:test}{4}\\
		desempenho em \exref{fi} & 4 \\
		desempenho em \exref{dmst} & 4 \\
		desempenho em \exref{scheme} & 4 \\
		cool hacker & 4 \\ \hline
	\end{tabular}\\[\baselineskip]
	\caption{Tabela de Cr\'editos por Tarefa}
	\label{tab:credits}
\end{table}

Oito dos exerc\'{\i}cios referem-se a testes dos algoritmos a implementar.
D\^e \^enfase especial a esses testes e \`a sua apresenta\c{c}\~ao. Os testes
de corre\c{c}\~ao dos algoritmos devem ser realizados atrav\'es de programas
que testem automaticamente propriedades de corre\c{c}\~ao das suas estruturas.
Por exemplo, implemente um algoritmo que teste se a estrutura constru\'{\i}da 
pelos algoritmos do \exref{kdtree} \'e uma \kdtree\ v\'alida. Apresente
testes com esse algoritmo.

Os quatro itens finais da \tabref{credits} referem-se a testes de desempenho.
O testes de desempenho ser\~ao realizados sobre um conjunto de dados, usando
inst\^ancias consideradas desafiadoras do \tsp. Em cada teste, s\'o poder\~ao
participar grupos que tiverem apresentado  solu\c{c}\~oes sem erros
para o respectivo exerc\'{\i}cio :
por exemplo, s\'o participar\~ao do teste de desempenho do
\exref{fi} grupos cuja implementa\c{c}\~ao da heur\'{\i}stica \FI n\~ao tiver 
erros detectados em nenhum teste. 
Os grupos ser\~ao classificados por tempos de execu\c{c}\~ao.
O primeiro colocado receber\'a quatro cr\'editos. Os outros
receber\~ao pontos na raz\~ao inversa do aumento de tempo em rela\c{c}\~ao ao
tempo do vencedor.

O pr\^emio \emph{cool hacker}, \'ultimos quatro pontos da competi\c{c}\~ao,
ser\'a atribu\'{\i}do pela soma dos tempo dos tr\^es testes de desempenho.
Novamente o primeiro leva total de cr\'editos e os outros levam cr\'editos na
raz\~ao inversa da diferen\c{c}a em rela\c{c}\~ao ao vencedor.



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

A 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 \\\hline
		Grupos de 1 aluno & $110/100$ \\
		Grupos de 2 alunos & $ 100/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}\\[\baselineskip]
	\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}
\def\exref#1{exerc\'{\i}cio \ref{ex:#1}}
\def\haskell{\textbf{Haskell}}
\def\makefile{\textbf{Makefile}}
\def\frp{\textbf{frp}}

Submeta sua trabalho por \href{mailto:raulh@inf.ufes.br}{e-mail} entre os dias
30/06/05 e/ou 06/07/05. Trabalhos submetidos fora dessa data ser\~ao
considerados nulos.

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

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

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

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

As seguintes regras devem ser rigorosamente seguidas:
\begin{itemize}
	\item Nenhum compilado deve ser enviado.
	\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{doc}

				Conter\'a os fontes de toda a documenta\c{c}\~ao 
				do trabalho.
		\end{itemize}
	\item seu \tarball\ ser\'a aberto e compilado com as seguintes linhas:

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

		Essas linhas gerar\~ao os seguintes arquivos:

		\begin{itemize}
			\item \textbf{tsp.fi}

				Execut\'avel que implementa heur\'{\i}stica do
				\exref{fi}.
			\item \textbf{tsp.dmst}

				Execut\'avel que implementa heur\'{\i}stica do
				\exref{dmst}.
			\item \textbf{tsp.scheme}

				Execut\'avel que implementa heur\'{\i}stica do
				\exref{scheme}.
			\item \textbf{artigo.pdf}

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

		\end{itemize}
\end{itemize}

\section{Exemplo}\label{ioexample}
\def\pointtarball{point.io.tar.bz2}

O \hbref\cwurl\pointtarball{\tarball\pointtarball}
cont\'em um exemplo de programa para 
leitura e escrita de pontos. Abra o arquivo usando

\begin{verbatim}
     tar -jxf point.io.tar.bz2
\end{verbatim}

Isso criar\'a um diret\'orio de nome \textbf{point.io}. Leia o arquivo 
\textbf{README} desse diret\'orio para instru\c{c}\~oes adicionais. 




\section{Altera\c{c}\~oes neste documento}\label{errata}
As seguintes altera\c{c}\~oes foram realizadas neste documento quando comparado
com sua primeira vers\~ao:
\begin{itemize}
	\item A \tabref{credits} foi corrigida para incluir valor
		atribu\'{\i}do aos exerc\'{\i}cios \ref{ex:binq} e
		\ref{ex:binq:test}.
	\item A scref{credits} inclui agora uma explana\c{c}\~ao sobre os
		testes de corre\c{c}\~ao a realizar.
		
\end{itemize}
\end{document}

