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

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

\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 trabalho consiste de
exerc\'{\i}cios de implementa\c{c}\~ao 
sobre as essas estruturas e algoritmos a elas associados.

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. 

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
		assumindo que voc\^e usaria, em per\'{\i}odo de aulas,
		cerca de tr\^es dias em cada se\c{c}\~ao de
		exerc\'{\i}cios e um dia na se\c{c}\~ao final. 
\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{kdtree:build}
	Defina em Haskell um algoritmo com o seguintes tipo:
	
	$$build::[\xpoint a]\rightarrow \xkdtree{a}$$
	
	que, dada uma seq\"u\^encia de pontos $S$,
	constr\'oi uma \kdtree\ dos pontos de $S$.
\end{ex}

\begin{ex}
	Apresente em Haskell um algoritmo com o seguinte tipo:
	
	$$isK\!Dtree::\xkdtree{a}\rightarrow Bool$$
	
	que testa a corre\c{c}\~ao do
	algoritmo apresentado no exerc\'{\i}cio \ref{kdtree:build}. 
\end{ex}

\begin{ex}
	Apresente testes comparativos de corre\c{c}\~ao, desempenho e uso de
	mem\'oria, usando dados dos arquivos da se\c{c}\~ao \ref{testing}.
\end{ex}



\subsection{\'Arvores bin\'arias de priodidade}\label{pqtree}

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

\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{binheap:def}
	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.

	Considre a seguinte defini\c{c}\~ao de operador para realizar o
	\emph{merge} de duas \'arvore de prioridade.
	\begin{align}
		\label{nilnon}&\xmerge \xnullnd y = y\\
		\label{nonnil}&\xmerge x\xnullnd = x\\
		\label{mergelt}&a<b\limp\lr.\xmerge{\xbinnd xay}{\xbinnd ubv} =
		\xbinnd{\xmerge y{\xbinnd ubv}}ax\\
		\label{mergege}&a\ge b\limp\lr.\xmerge{\xbinnd xay}{\xbinnd ubv} =
		\xbinnd{\xmerge{\xbinnd xay}v}bu
	\end{align}

	Defina em Haskell os seguintes operadores e tipos:

	\begin{itemize}
		\item $\hbinpq a$

			Para \binheaps.
		\item $merge :: \hmap{\hbinpq a}{\hmap{\hbinpq a}{\hbinpq}}$

			que constr\'oi o \emph{merge} de duas \binheaps.
		\item $insert :: \hmap{\hbinpq a}{\hmap a{\hbinpq a}}$

			que, dados \binheap\ $h$ e item $x$, constr\'oi uma
			\binheap\ resultante da inser\c{c}\~ao de $x$ em $h$.

		\item $min :\hmap{\hbinpq a}a$

			que retorna o valor m\'{\i}nimo de uma \binheap.
		\item $delmin:\hmap{\hbinpq a}{\hbinpq a}$

			que, dada uma \binheap\ $h$, exclui dela o valor
			m\'{\i}nimo.
	\end{itemize}
\end{ex}

\begin{ex}\label{ex:isbinpq}
	Defina em Haskell um operador com tipo
	$$ isbinpq :: \hmap {\hbinpq a}{Bool}$$

	que testa se $h$ \'e uma \binheap.
\end{ex}

\begin{ex}
	Apresente testes de corre\c{c}\~ao, desempenho e uso de mem\'oria 
	para cada um dos operadores definidos no exerc\'{\i}cio 
	\ref{binheap:def}.
\end{ex} 
\subsection{TSP e heur\'{\i}stica NN}\label{tsp.nn}
\def\dsjstsp{\href{http://www.research.att.com/~dsj/papers/stspchap.pdf}{Experimental
Analysis of Heuristics for the STSP}}
\def\NN{\textbf{NN}}

Nos exerc\'{\i}cios a seguir, voc\^e trabalhar\'a com a heur\'{\i}stica
\textbf{Nearest Neighbor (NN)}, descrita na p\'agina 23 de \dsjstsp. 
 
\begin{ex}\label{ex:nn}
	Implemente um algoritmo para encontrar um \tour\ para o \tsp, usando a
	heur\'{\i}stica \NN. Esta heur\'{\i}stica come\c{c}a
	com um \tour\ parcial contendo um ponto escolhido aleat\'oriamente do conjunto
	dado. A cada passo, um novo ponto \'e escolhido para ser agregado ao \tour: o
	ponto escolhido \'e aquele que se encontra mais pr\'oximo do \'ultimo ponto
	adicionado ao \tour.

	Seu algoritmo ter\'a o seguinte tipo:

	$$nn :: \hmap{[\xpoint a]}{[\xpoint a]}$$

\end{ex}

\begin{ex}
	Defina um algoritmo 

	$$istour ::\hmap{[\xpoint a]}{Bool}$$

	que testa se seq\"u\^encia de cidades \'e um \tour\ e use-o para testar 
	a corre\c{c}\~ao da solu\c{c}\~ao do exerc\'{\i}cio \ref{ex:nn}.
\end{ex}


  
\subsection{TSP e heur\'{\i}stica FRP}\label{tsp.frp}

\begin{ex}\label{ex:frp}
	Use uma \kdtree\ para particionar o conjunto de cidades dado. Em
	seguida, percorra a \'arvore das folhas para a raiz, construindo
	\tour s:
	\begin{itemize}
		\item em uma folha construa um \tour\ dos pontos presentes,
			usando \NN;
		\item em um n\'o interno, use um procedimento de
			\emph{merge} unir os \tour s
			obtidos nas suas duas sub\'arvores. Por exemplo,
			una os dois pontos extremos mais pr\'oximos dos 
			dois \tour s, desconecte duas arestas incidentes a
			esses pontos e una os outros dois pontos a que as
			arestas removidas eram incidentes.
	\end{itemize}
	Seu algoritmo ter\'a o seguinte tipo:

	$$frp :: \hmap{[\xpoint a]}{[\xpoint a]}$$
\end{ex}


      

   

\begin{ex}
	Teste corre\c{c}\~ao, desempenho, uso de mem\'oria e qualidade do \tour\ 
	da sua solu\c{c}\~ao.
\end{ex}
\subsection{TSP e heur\'{\i}stica Greedy}\label{tsp.greedy}
 

\def\greedy{\textbf{Greedy}}
Na heur\'{\i}stica \greedy, descrita na p\'agina 24 de \dsjstsp, 
o \tour\ \'e mantido como uma seq\"u\^encia
de arestas (pares de pontos.) Come\c{c}ando com a aresta de menor peso, 
a cada passo adiciona-se a aresta \xpair uv 
que atende \`as restri\c{c}\~oes:
\begin{itemize}
	\item \'e a aresta de menor peso dentre as candidatas
		eleg\'{\i}veis;
	\item \xpair uv \'e eleg\'{\i}vel se $u$ e $v$ t\^em cada um
		grau zero ou um;
	\item a adi\c{c}\~ao de \xpair uv n\~ao completa um ciclo.
\end{itemize}

\begin{ex}\label{ex:greedy}
	Implemente em Haskell uma vers\~ao simples da heur\'{\i}stica \greedy,
	usando apenas ordena\c{c}\~ao de arestas por peso como estrutura
	b\'asica.
	Seu algoritmo ter\'a o seguinte tipo:

	$$greedy :: \hmap{[\xpoint a]}{[\xpoint a]}$$
\end{ex}

\begin{ex}
	Teste a corre\c{c}\~ao, desempenho, uso de mem\'oria e qualidade de
	\tour\ da sua implementa\c{c}\~ao da heur\'{\i}stica \greedy.
\end{ex}

\subsection{\'Arvore bin\'aria espacial semi-din\^amica}\label{dynkdtree}

\begin{ex}\label{delkdtree}
	Implemente na sua  \'arvore bin\'aria 
	espacial, conforme descri\c{c}\~ao de \jbkdtree:
	\begin{itemize}
		\item operador de exclus\~ao de ponto com tipo
			$$delete :: \hmap{\xpoint a}{\hmap{(\xkdtree a)}
			            {(\xkdtree a)}}$$
		\item operador  com tipo
			$$nn :: \hmap{(\xpoint a)}{\hmap{(\xkdtree)}{(\xpoint
			a)}}$$
			
			para encontrar, dentre os pontos n\~ao exclu\'{\i}dos
			de uma \'arvore, o vizinho mais pr\'oximo de um ponto
			dado.
	\end{itemize}
\end{ex}

\begin{ex}\label{ex:pqgreedy}
	Use uma \'arvore bin\'aria espacial e uma fila de prioridade, como 
	descrito na p\'agina 24 de \dsjstsp, para produzir uma nova vers\~ao 
	da heur\'{\i}stica \greedy, com tipo:

	$$pqgredy::\hmap{[\xpoint a]}{[\xpoint a]}$$
\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}\label{credits}

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{kdtree} & $12$ \\
		Se\c{c}\~ao \ref{pqtree} & $12$ \\
		Se\c{c}\~ao \ref{tsp.nn} & $12$ \\
		Se\c{c}\~ao \ref{tsp.frp} & $12$ \\
		Se\c{c}\~ao \ref{tsp.greedy} & $12$ \\
		Se\c{c}\~ao \ref{dynkdtree} & $12$ \\
		Desempenho (ver \ref{testing} & $16$ \\
		An\'alise de qualidade de \tour & $6$ \\
		Estudo de \emph{profile} & $6$ \\ \hline
	\end{tabular}
	\caption{Tabela de atribui\c{c}\~ao de cr\'editos}
	\label{tab:credits}
\end{table}

O item \emph{desempenho} da tabel \ref{tab:credits} refere-se \`a
avalia\c{c}\~ao de desempenho das quatro heur\'{\i}sticas para solu\c{c}\~ao 
de \tour, sendo atribu\'{\i}dos at\'e quatro cr\'editos por heur\'{\i}stica.
A atribui\c{c}\~ao leva em conta tempo de execu\c{c}\~ao e segue as seguintes
restri\c{c}\~oes:
\begin{itemize}
	\item S\'o podem se canditar aos creditos programas que n\~ao apresentem
		erros;
	\item O programa mais r\'apido leva o total de cr\'editos.
	\item Outros programas recebem cr\'editos na proporc\~ao do respectivo
		desempenho em rel\c{c}\~ao ao total. 
\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}
\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} nos dias
01/03/05 e/ou 02/03/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{tbo.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{point.io}

				Conter\'a a defini\c{c}\~ao do tipo |emph{Point
				a} e entrada e sa\'{\i}da de pontos.
				
			\item diret\'orio \textbf{kdtree}

				Conter\'a a implementa\c{c}\~ao da \kdtree.

				Note que o teste de corre\c{c}\~ao de 
				\kdtree\ ser\'a realizado atrav\'es de um
				m\'odulo que importar\'a a estrutura de
				pontos e a \kdtree, usando as seguintes linhas:

				\begin{verbatim}
				
				import Point
				import KDTree

				\end{verbatim}

			\item diret\'orio \textbf{pq}

				Conter\'a a implementa\c{c}\~ao da fila de
				prioridade.
				
				Note que o teste de corre\c{c}\~ao de 
				fila de prioridade 
				ser\'a realizado atrav\'es de um
				m\'odulo que importar\'a a estrutura de
				pontos e a fila, usando as seguintes linhas:

				\begin{verbatim}
				
				import Point
				import Binpq

				\end{verbatim}

			\item diret\'orio \textbf{frp}

				Conter\'a a implementa\c{c}\~ao da
				heur\'{\i}stica \frp, do \exref{frp}.
			\item diret\'orio \textbf{nn}

				Conter\'a a implementa\c{c}\~ao da
				heur\'{\i}stica nearest-neighbor, do \exref{nn}.
			\item diret\'orio \textbf{greedy}

				Conter\'a a implementa\c{c}\~ao da
				heur\'{\i}stica \greedy, do \exref{greedy}.
			\item diret\'orio \textbf{pqgreedy}

				Conter\'a a implementa\c{c}\~ao da
				heur\'{\i}stica greedy com fila de prioridade,
				do \exref{pqgreedy}
			\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.frp}

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

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

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

				Execut\'avel que implementa heur\'{\i}stica do
				\exref{pqgreedy}.
			\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{As notas}
\def\scref#1{\ref{#1}}
\def\tspds#1#2{& #1 & #2}
\def\tsph#1#2#3#4{& #1 & #2 & #3 & #4 }
\def\prfrm#1#2#3{& #1 & #2 & #3}

As notas seguem na tabela \ref{tab:marks}. 
Elas foram atribu\'{\i}das, usando os crit\'erios da
se\c{c}\~ao \ref{credits}.


\begin{table}
	\centering
	\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|r|}\hline
		Grp& \scref{kdtree} & \scref{pqtree} &\scref{tsp.frp}
		& \scref{tsp.nn} &\scref{tsp.greedy} 
		&\scref{dynkdtree} & desempenho
		& an\'alise & prof \\ \hline
		1\tspds{12}{0}\tsph{10}{10}{12}{0}\prfrm{10}{6}{6}\\ 
		3\tspds{12}{12}\tsph{10}{10}{12}{9}\prfrm{14}{0}{0}\\ 
		4\tspds{12}{0}\tsph{8}{8}{2}{4}\prfrm{6}{0}{0}\\ 
		5\tspds{12}{0}\tsph{9}{10}{12}{0}\prfrm{12}{0}{0}\\ 
		6\tspds{12}{12}\tsph{10}{10}{12}{0}\prfrm{9}{6}{6}\\ 
		7\tspds{12}{12}\tsph{10}{10}{12}{9}\prfrm{12}{6}{6}\\ 
		8\tspds{12}{12}\tsph{9}{10}{12}{0}\prfrm{9}{6}{6}\\ 
		9\tspds{12}{12}\tsph{9}{10}{12}{9}\prfrm{12}{6}{6}\\ 
		10\tspds{12}{10}\tsph{8}{8}{0}{0}\prfrm{9}{6}{6}\\ 
		11\tspds{12}{0}\tsph{10}{10}{12}{0}\prfrm{10}{6}{6}\\ 
		12\tspds{12}{12}\tsph{12}{12}{12}{11}\prfrm{16}{6}{6}\\ 
		13\tspds{12}{12}\tsph{9}{10}{12}{8}\prfrm{14}{6}{6}\\ \hline
	\end{tabular}
	\caption{Tabela de notas}
	\label{tab:marks}
\end{table}

Algumas observa\c{c}\~oes sobre as notas dos exerc\'{\i}cios:
\begin{itemize}
	\item O grupo $4$ recebeu quatro pontos no exerc\'{\i}cio
		\exref{pqgreedy}, embora na tenha submetido nada
		referente a esse exerc\'{\i}cio. Raz\~ao: ponto para
		\emph{fair play}. Ao contr\'ario de outros alunos que n\~ao
		conseguiram terminar o exerc\'{\i}cio e enviaram uma
		``solu\c{c}\~ao'' enganosa, Anderson foi honesto e n\~ao enviou
		o que nao tinha.
	\item Nenhum grupo implementou uma \kdtree\ din\^amica como apresentada
		no artigo. Das que foram submetidas, a melhor foi a do grupo
		$12$, o que se reflete nos testes.
	\item No item de desempenho do \tour\ e desempenho foram levadas em 
		conta as inst\^ancias: \textbf{pla7397, pla33810, rl1889,
		rl5934, tl5915.} Foram atribu\'{\i}dos atr\^es prontos por
		heur\'{\i}stica, desde que o a heur\'{\i}stica do grupo tivesse
		uma implementa\c{c}\~ao honesta.
\end{itemize}

As notas finais seguem na tabela \ref{tab:final}. Nos casos de trabalhos
individuais elas j\'a est\~ao multiplicadas pelo fator respectivo.

\def\nota#1#2{#1 & #2}

\begin{table}
	\centering
	\begin{tabular}{|l|r|} \hline
		Grp& nota \\ \hline
		\nota{1}{6,6}\\
		\nota{3}{9,5}\\
		\nota{4}{4,8}\\
		\nota{5}{5,5}\\
		\nota{6}{7,7}\\
		\nota{7}{8,9}\\
		\nota{8}{7,6}\\
		\nota{9}{8,8}\\
		\nota{10}{7,1}\\
		\nota{11}{6,6}\\
		\nota{12}{9,9}\\
		\nota{13}{8,9}\\\hline
	\end{tabular}
	\caption{Tabela de notas}
	\label{tab:final}
\end{table}


\end{document}

