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

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

\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 1: \\ \'Arvores e estruturas de prioridade em C\\
       Final}

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

\def\tsp{\textbf{TSP}}
\def\tour{\textbf{tour}}
\def\xnn{\emph{Nearest Neighboor}}
\def\nn{\textbf{NN}}
\def\greedy{\emph{Greedy}}
\def\kopt{\emph{k-opt}}
\def\hprevcw{\hbref\cwurl{0/0.pdf}{Trabalho Pr\'atico 0}}
\def\clang{linguagem \emph{C/C++}}

Este trabalho consiste em exerc\'{\i}cio de programa\c{c}\~ao em uma
linguagem imperativa sobre algumas das estruturas do trabalho anterior. Para
tal voc\^e implementar\'a em \clang\ duas solu\c{c}\~oes heur\'{\i}sticas 
para o problema de encontrar o melhor \tour\ para o problema do 
\tsp. Voc\^e implementar\'a as heur\'{\i}stica \nn\ e \greedy\ com fila
de prioridade descritas no
trabalho anterior\footnote{
Para mais detalhes sobre o problema e as heur\'{\i}sticas veja documento
do \hprevcw\ e refer\^encias nele contidas.
}
e uma heur\'{\i}stica para melhora de \tour\ obtido.


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.
\def\xpair#1#2{\ensuremath{(#1,#2)}}
\def\xdist#1#2{\ensuremath{dist(#1,#2)}}

\section{As heur\'{\i}sticas}

\subsection{Vizinho mais pr\'oximo e guloso}
As heur\'{\i}stica \nn\ e \greedy\ est\~ao descritas no documento do \hprevcw.


\subsection{Busca local}
\def\fredmantspds{\textbf{Fredman:tspds}}
\def\htspdsref#1{\href{http://portal.acm.org/citation.cfm?id=313668}#1}
\def\htspds{\htspdsref{\fredmantspds}}

Uma das mais importantes heur\'{\i}sticas para obter o melhor \tour
poss\'{\i}vel para o \tsp\ consiste em usar os seguintes passos:
\begin{itemize}
	\item construir um \tour\ inicial $t_0$ usando heur\'{\i}sticas como
		\nn\ ou \greedy;
	\item melhorar o \tour\ $t_0$ usando heur\'{\i}sitca de busca local
		realizam exclus\~ao de algumas arestas, seguida de
		religa\c{c}\~ao dos n\'os de grau um para obter um \tour.
\end{itemize}

A heur\'{\i}stica de busca local acima referida \'e implementada a partir de
alguma variante do processo de permuta\c{c}\~ao limitada de n\'os, conhecido
na literatura como opera\c{c}\~ao \kopt\footnote{
Veja \htspdsref{artigo}, referenciado neste documento como \fredmantspds,
sobre alternativas para representa\c{c}\~ao de \tour,
que facilitam a implementa\c{c}\~ao da opera\c{c}\~ao \kopt.}.

Um \tour\ $t_1$ \'e obtido de um \tour\ $t_0$ por \kopt\ quando $t_1$ \'e obtido pelos
seguintes passos:
\begin{itemize}
	\item gera\c{c}\~ao de um grafo desconexo $t'$ pela exclus\~ao de
		$k$ arestas n\~ao consecutivas de $t_0$;
	\item religa\c{c}\~ao de n\'os de grau um presentes em $t'$ para
		obter o \tour\ $t_1$
\end{itemize}


\section{Representa\c{c}\~ao de \tour}
\def\array{\emph{array}}
\def\splay{\emph{splay}}

Escolha para representar seu \tour\ uma das seguintes estruturas\footnote{
Descritas em \htspds.}:
\begin{itemize}
	\item \array\  com a seq\"u\^encia de n\'os;
	\item lista duplamente encadeada;
	\item \'arvore bin\'aria com opera\c{c}\~oes de \splay;
	\item \'arvore em dois n\'{\i}veis.
\end{itemize}

As seguintes observa\c{c}\~oes s\~ao importantes na escolha da
representa\c{c}\~ao do \tour:
\begin{enumerate}
	\item Voc\^e deve escolher obrigatoriamente dentre uma das alternativas
		acima.
	\item Sua escolha afetar\'a significativamente o desempenho do programa,
		que \'e\ o item mais importante da avalia\c{c}\~ao deste
		trabalho.
	\item Implementar as opera\c{c}\~oes descritas na p\'agina quatro de 
		\htspds\ dever\'a faciltar em muito sua tarefa de
		implementa\c{c}\~ao. As opera\c{c}\~oes  ali descritas s\~ao:
		\begin{itemize}
			\item $Next(a)$: Dado n\'o $a$, determina o n\'o que o 
				segue no \tour.
			\item $Prev(a)$: Dado n\'o $a$, determina o n\'o que o 
				precede no \tour.
			\item $Between(a,b,c)$: predicado que determina 
				se $b$ est\'a entre $a$ e $c$ no \tour.
			\item $Flip(a,b,c,d)$: atualiza \tour, excluindo 
				as arestas $(a,b)$ e $(c,d)$ e inserindo as
				arestas $(b,c)$ e $(a,d)$.
		\end{itemize}

		Note que est\'a impl\'{\i}cito em todas essas opera\c{c}\~oes o
		par\^ametro que representa o \tour. 
\end{enumerate}

\section{Fila de prioridade}
\def\hbinomqueue{\href{http://portal.acm.org/citation.cfm?id=359478&coll=portal&dl=ACM&ret=1}{vuillemin}}
\def\hselfadjustbintree{\href{http://portal.acm.org/citation.cfm?id=808752}{\textbf{sleator83}}}
\def\hsplaytree{\href{http://portal.acm.org/citation.cfm?id=3835}{\textbf{sleator85}}}


A heur\'{\i}stica \greedy\ demanda uma estrutura de prioridade. Escolha sua
estrutura de prioridade dentre as seguintes:
\begin{enumerate}
	\item \emph{Binomial queue}\footnote{Descrita no artigo \hbinomqueue.}
	\item \'Arvore auto-ajust\'avel\footnote{
		Descritas em \hselfadjustbintree\ e no \hprevcw.}
	\item \'Arvores \splay\footnote{Descritas em \hsplaytree.}
	\item \'Arvore 2-3.
\end{enumerate}

Novamente sua escolha est\'a restrita a uma dessas estruturas e ela afetar\'a 
significativamente o desempenho do seu programa.
\section{Os exerc\'{\i}cios}

Os exerc\'{\i}cios desta se\c{c}\~ao demandam a implementa\c{c}\~ao de quatro
programas diferentes para a avalia\c{c}\~ao de \tour. Todos usam o mesmo
padr\~ao de entrada e sa\'{\i}da dos programas do \hprevcw.

\begin{ex}\label{ex:nn}
	Implemente um programa c\'alculo de \tour, usando a heur\'{\i}stica 
	\nn\ e uma estrutura de \'arvore bin\'aria espacial, como descrita no
	\hprevcw.
\end{ex}

\begin{ex}\label{ex:greedy}
	Implemente um programa para c\'alculo de \tour, usando a heur\'{\i}stica
	\greedy, combinada com \'arvore bin\'aria espacial e \'arvore de 
	prioridade.
\end{ex}

\begin{ex}\label{ex:nnopt}
	Implemente um programa que gere um \tour\ inicial usando a
	heur\'{\i}stica \nn, como no exerc\'{\i}cio \exref{nn}, melhore
	o \tour\ usando \kopt.
\end{ex}

\begin{ex}\label{ex:greedyopt}
	Implemente um programa que gere um \tour\ inicial usando a
	heur\'{\i}stica \greedy, como no exerc\'{\i}cio \exref{greedy}, melhore
	o \tour\ usando \kopt.
\end{ex}


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

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 \exref{nn} & $10$ \\
		Se\c{c}\~ao \exref{greedy} & $10$ \\
		Se\c{c}\~ao \exref{nnopt} & $10$ \\
		Se\c{c}\~ao \exref{greedyopt} & $10$ \\
		Se\c{c}\~ao \ref{profile} & $10$ \\
		Se\c{c}\~ao \exref{bestnn} & $10$ \\
		Se\c{c}\~ao \exref{bestgreedy} & $10$ \\
		Se\c{c}\~ao \exref{bestopt} & $10$ \\
		Sec\~ao \exref{besttour} & $10$ \\
		Se\c{c}\~ao \exref{bestmem} & $10$ \\\hline
	\end{tabular}
	\caption{Tabela de atribui\c{c}\~ao de cr\'editos}
	\label{tab:credits}
\end{table}

\subsection{Crit\'erio fundamental da atribui\c{c}\~ao de cr\'editos}
Os crit\'erios que definem atribui\c{c}\~ao de cr\'editos colocam uma \^enfase
especial na efici\^encia ($50\%$ dos cr\'editos v\~ao para desempenho) e 
corre\c{c}\~ao: programas que apresentam qualquer erro n\~ao podem participar
de nenhuma competi\c{c}\~ao de desempenho. 


\subsection{A avalia\c{c}\~ao n\~ao comparativa}
Os itens das se\c{c}\~oes \exref{nn},\exref{greedy},\exref{nnopt} e 
\exref{greedyopt} ser\~ao avaliados em rela\c{c}\~ao:
\begin{itemize}
	\item Corre\c{c}\~ao do \tour;
	\item Corre\c{c}\~ao do uso de mem\'oria;
	\item Melhoria no \tour\ no caso das se\c{c}oes \exref{nnopt} e
		\exref{greedyopt}.
\end{itemize}

\subsection{Estudo de qualidade}\label{profile}
Escreva um artigo curto (duas ou tr\^es p\'aginas em \LaTeX) comparando
os programas implementados com respeito a:
\begin{itemize}
	\item qualidade do \tour;
	\item tempo de execu\c{c}\~ao;
	\item demanda de mem\'oria.
\end{itemize}
Importante: N\~ao use os pacotes \textbf{listings} e \textbf{noweb} no artigo 
deste trabalho. 

\subsection{O melhor \tour}\label{ex:besttour}
Neste item os \tour s de todos programas ser\~ao comparados para definir
o melhor. Em cada teste realizado, o grupo com o melhor programa receber\'a 
dez cr\'editos e os outros grupos receber\~ao cr\'editos raz\~ao inversa da piora
da qualidade do \tour, quando comparado com o melhor grupo. 

A nota de cada grupo neste item ser\'a a m\'edia das notas dos diversos testes.

\subsection{O mais r\'apido \nn}\label{ex:bestnn}
Usando a mesma metodologia de atribui\c{c}\~ao de cr\'editos da se\c{c}\~ao
\exref{besttour}, buscar-se-\'a aqui a implementa\c{c}\~ao mais r\'apida para 
o exerc\'{\i}cio \exref{nn}.


\subsection{O mais r\'apido \greedy}\label{ex:bestgreedy}
Usando a mesma metodologia de atribui\c{c}\~ao de cr\'editos da se\c{c}\~ao
\exref{besttour}, buscar-se-\'a aqui a implementa\c{c}\~ao mais r\'apida para 
o exerc\'{\i}cio \exref{greedy}.

\subsection{O mais r\'apido \kopt}\label{ex:bestopt}
Usando a mesma metodologia de atribui\c{c}\~ao de cr\'editos da se\c{c}\~ao
\exref{besttour}, buscar-se-\'a aqui a implementa\c{c}\~ao mais r\'apida para 
os exerc\'{\i}cio \exref{nnopt} e \exref{greedyopt}, obedecendo \`a seguinte
restri\c{c}\~ao: 
\begin{itemize}
	\item S\'o podem participar programas que tenham produzido \tour\
		que seja no m\'aximo $10\%$ pior que o vencedor do 
		teste da se\c{c}\~ao \exref{besttour}. Eliminam-se aqui
		programas que s\~ao r\'apidos porque n\~ao produzem um \tour\
		minimamente respeit\'avel.
\end{itemize}

\subsection{O mais econ\^omico \kopt}\label{ex:bestmem}
Usando a mesma metodologia de atribui\c{c}\~ao de cr\'editos da se\c{c}\~ao
\exref{besttour}, buscar-se-\'a aqui a implementa\c{c}\~ao com 
menor uso de mem\'oria para 
os exerc\'{\i}cio \exref{nnopt} e \exref{greedyopt}, obedecendo \`a seguinte
restri\c{c}\~ao: 
\begin{itemize}
	\item S\'o podem participar programas que tenham produzido \tour\
		que seja no m\'aximo $10\%$ pior que o vencedor do 
		teste da se\c{c}\~ao \exref{besttour}. Eliminam-se aqui
		programas que s\~ao r\'apidos porque n\~ao produzem um \tour\
		minimamente respeit\'avel.
\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\SC{\textbf{Senhor do Castelo}}
\def\haskell{\textbf{Haskell}}
\def\makefile{\textbf{Makefile}}
\def\kdtree{\emph{kd-tree}}

Submeta sua trabalho por \href{mailto:raulh@inf.ufes.br}{e-mail}
at\'e 07/03/05. Trabalhos entregues
at\'e 18/03/2005 poder\~ao, a crit\'erio do \SC, ser corrigidos.


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

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

\centerline{\textbf{tp1.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 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{kdtree}

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

			\item diret\'orio \textbf{pq}

				Conter\'a a implementa\c{c}\~ao da fila de
				prioridade.
				
		
			\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{opt} com implementa\c{c}\~ao 
				da heur\'{\i}stica \kopt.
			\item diret\'orio \textbf{nnopt} com implementa\c{c}\~ao
				do programa usando \textbf{nn} e \kopt, referido
				no exerc\'{\i}cio \exref{nnopt}.
			\item diret\'orio \textbf{greedyopt} com implementa\c{c}\~ao
				do programa usando \textbf{greedy} e \kopt,
				referido no exerc\'{\i}cio \exref{greedyopt}.
			\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 tp1.tar.gz
		make all
		\end{verbatim}

		Essas linhas gerar\~ao os seguintes arquivos:

		\begin{itemize}
			\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.nnopt}

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

				Execut\'avel que implementa heur\'{\i}stica do
				\exref{greedyopt}.
			\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. 

Importante: voc\^e n\~ao \'e obrigado a usar essas rotinas de entrada e
sa\'{\i}da. Seu programa deve apresentar o mesmo padr\~ao de entrada e
sa\'{\i}da do \hprevcw, mas a implementa\c{c}\~ao \'e decis\~ao sua.





\end{document}

