\documentclass[a4paper,10pt]{article}
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage[backref=page,plainpages=false,pdfpagelabels]{hyperref}

\author{D\'ebora Zupeli Bossois \\ Jo\~ao Olavo Bai\~ao de Vasconcelos}

\title{Testes}

\begin{document}

\maketitle

\section{Testes comparativos utilizando a KDTree}

Rodamos o algoritmo KDTree para alguns conjuntos de pontos a fim de obter uma tabela com os tempos de execu\c c\~ao de cada conjunto e a quantidade de mem\'oria usada por cada conjunto. \\


\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|} \hline
\multicolumn{3}{|c|}{\textbf{KDTree}} \\
\hline N.ptos & \textbf{Tempo} & \textbf{Mem\'oria} ($10^{5}$) \\
\hline \hline \textbf{att48} & 0m0.018s   & 8,363 bytes\\
\hline \textbf{kroA100}      & 0m0.027s   & 17,000 bytes \\
\hline \textbf{lin318}       & 0m0.060s   &  54,347 bytes\\
\hline \textbf{pr1002}       & 0m0.154s   & 177,806 bytes\\
\hline \textbf{nrw1379}      & 0m0.212s   & 241,071 bytes\\
\hline \textbf{pla7397}      & 0m1.255s   & 1.415,285 bytes\\
\hline \textbf{pla33810}     & 0m6.165s   & 6.682,207 bytes\\
\hline \textbf{pla85900}     &  0m16.313s & 17,505.565 bytes\\
\hline
\end{tabular}
\caption{Tempo e uso de mem\'oria do m\'odulo KDTree}
\label{tab1}
\end{center}
\end{table}

AQUI FICAM OS COMENT\'ARIOS!!

\section{Testes de corre\c c\~ao do M\'odulo Binpq}

Ser\~ao aqui mostrados testes de corre\c c\~ao dos operadores utilizados no m\'odulo \textit{Binpq}.

Operadores:
\begin{itemize}
\item{findmin}
\item{delmin}
\item{merge}
\item{insertBinpq}
\end{itemize}

As varia\c c\~oes de par\^ametros que aqui fazemos s\~ao pensadas analizando cada algoritmo.

\subsection{Operador \textit{findmin}}

Para o teste do operador \textit{findmin}, utilizamos um conjunto de 5 \'arvores de prioridade. Foram elas: \\
\begin{itemize}
\item{(NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ))}
\item{(NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) LeafPQ)}
\item{(NodePQ 2 LeafPQ (NodePQ 4 LeafPQ LeafPQ))}
\item{(NodePQ 2 LeafPQ LeafPQ)}
\item{LeafPQ}
\end{itemize}

Eis aqui os resultados para cada dado:

\begin{verbatim}
Binpq> findmin (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ))
Just 2
Binpq> findmin (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) LeafPQ)
Just 2
Binpq> findmin (NodePQ 2 LeafPQ (NodePQ 4 LeafPQ LeafPQ))
Just 2
Binpq> findmin (NodePQ 2 LeafPQ LeafPQ)
Just 2
Binpq> findmin LeafPQ
Nothing
\end{verbatim}


Essas \'arvores cobrem todas as possibilidades de par\^ametros que a fun\c c\~ao pode receber, e todas as respostas obtidas foram as esperadas.

\subsection{Operador \textit{delmin}}

As mesmas op\c c\~oes de par\^ametros utilizadas no operador acima tamb\'em cobrem todas as possibilidades de par\^ametros do operador \textit{delmin}. Vamos aos testes: \\

\begin{verbatim}
*Binpq> delmin (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ))
NodePQ 3 (NodePQ 4 LeafPQ LeafPQ) LeafPQ
*Binpq> delmin (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) LeafPQ)
NodePQ 3 LeafPQ LeafPQ
*Binpq> delmin (NodePQ 2 LeafPQ (NodePQ 4 LeafPQ LeafPQ))
NodePQ 4 LeafPQ LeafPQ
*Binpq> delmin (NodePQ 2 LeafPQ LeafPQ)
LeafPQ
*Binpq> delmin LeafPQ
LeafPQ
\end{verbatim}

Obtemos os resultados corretos.

\subsection{Operador \textit{merge}}

Aplicamos as diversas varia\c c\~oes poss\'iveis para \textit{merge} e, como visto no resultado abaixo, as opera\c c\~oes foram conclu\'idas com \^exito.

\begin{verbatim}
*Binpq> merge LeafPQ LeafPQ
LeafPQ
*Binpq> merge LeafPQ (NodePQ 2 LeafPQ LeafPQ)
NodePQ 2 LeafPQ LeafPQ
*Binpq> merge (NodePQ 2 LeafPQ LeafPQ) LeafPQ
NodePQ 2 LeafPQ LeafPQ
*Binpq> merge (NodePQ 2 LeafPQ LeafPQ) (NodePQ 10 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 LeafPQ LeafPQ) LeafPQ
*Binpq> merge (NodePQ 10 LeafPQ LeafPQ) (NodePQ 2 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 LeafPQ LeafPQ) LeafPQ
*Binpq> merge (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) LeafPQ) (NodePQ 10 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 LeafPQ LeafPQ) (NodePQ 3 LeafPQ LeafPQ)
*Binpq> merge (NodePQ 2 LeafPQ (NodePQ 3 LeafPQ LeafPQ)) (NodePQ 10 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 3 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) LeafPQ
*Binpq> merge (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ))
        (NodePQ 10 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 4 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) (NodePQ 3 LeafPQ LeafPQ)
*Binpq> merge (NodePQ 10 (NodePQ 13 LeafPQ LeafPQ) LeafPQ) (NodePQ 2 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 (NodePQ 13 LeafPQ LeafPQ) LeafPQ) LeafPQ
*Binpq> merge (NodePQ 10 LeafPQ (NodePQ 13 LeafPQ LeafPQ)) (NodePQ 2 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 LeafPQ (NodePQ 13 LeafPQ LeafPQ)) LeafPQ
*Binpq> merge (NodePQ 10 (NodePQ 13 LeafPQ LeafPQ) (NodePQ 14 LeafPQ LeafPQ))
        (NodePQ 2 LeafPQ LeafPQ)
NodePQ 2 (NodePQ 10 (NodePQ 13 LeafPQ LeafPQ) (NodePQ 14 LeafPQ LeafPQ)) LeafPQ
*Binpq> merge (NodePQ 2 LeafPQ LeafPQ) (NodePQ 10 (NodePQ 3 LeafPQ LeafPQ) LeafPQ)
NodePQ 2 (NodePQ 10 (NodePQ 3 LeafPQ LeafPQ) LeafPQ) LeafPQ
*Binpq> merge (NodePQ 2 LeafPQ LeafPQ) (NodePQ 10 LeafPQ (NodePQ 3 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 10 LeafPQ (NodePQ 3 LeafPQ LeafPQ)) LeafPQ
*Binpq> merge (NodePQ 2 LeafPQ LeafPQ) (NodePQ 10 (NodePQ 3 LeafPQ LeafPQ)
        (NodePQ 4 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 10 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ)) LeafPQ
*Binpq> merge (NodePQ 10 LeafPQ LeafPQ) (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) LeafPQ)
NodePQ 2 (NodePQ 10 LeafPQ LeafPQ) (NodePQ 3 LeafPQ LeafPQ)
*Binpq> merge (NodePQ 10 LeafPQ LeafPQ) (NodePQ 2 LeafPQ (NodePQ 3 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 3 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) LeafPQ
*Binpq> merge (NodePQ 10 LeafPQ LeafPQ) (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ)
        (NodePQ 4 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 4 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) (NodePQ 3 LeafPQ LeafPQ)
*Binpq> merge (NodePQ 2 (NodePQ 3 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ))
         (NodePQ 10 (NodePQ 11 LeafPQ LeafPQ) (NodePQ 12 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 4 (NodePQ 10 (NodePQ 11 LeafPQ LeafPQ) (NodePQ 12 LeafPQ LeafPQ))
         LeafPQ) (NodePQ 3 LeafPQ LeafPQ)
*Binpq> merge (NodePQ 10 (NodePQ 13 LeafPQ LeafPQ) (NodePQ 14 LeafPQ LeafPQ))
         (NodePQ 2 (NodePQ 11 LeafPQ LeafPQ) (NodePQ 12 LeafPQ LeafPQ))
NodePQ 2 (NodePQ 10 (NodePQ 12 (NodePQ 14 LeafPQ LeafPQ) LeafPQ)
         (NodePQ 13 LeafPQ LeafPQ)) (NodePQ 11 LeafPQ LeafPQ)
\end{verbatim}

\subsection{Operador \textit{insertBinpq}}
Este operador insere um elemento em uma \'arvore de prioridade. Seguindo o algoritmo, um exemplo as possibilidades de par\^ametros s\~ao: \\

LeafPQ  3
(NodePQ 3 LeafPQ LeafPQ) 10
(NodePQ 3 (NodePQ 4 LeafPQ LeafPQ) LeafPQ) 10
(NodePQ 3 LeafPQ (NodePQ 4 LeafPQ LeafPQ) 10
(NodePQ 3 (NodePQ 4 LeafPQ LeafPQ) (NodePQ 5 LeafPQ LeafPQ)) 10

Veja os resultados obtidos a partir dessas entradas:

\begin{verbatim}
*Binpq> insertBinpq LeafPQ  3
NodePQ 3 LeafPQ LeafPQ
*Binpq> insertBinpq (NodePQ 3 LeafPQ LeafPQ) 10
NodePQ 3 (NodePQ 10 LeafPQ LeafPQ) LeafPQ
*Binpq> insertBinpq (NodePQ 3 (NodePQ 4 LeafPQ LeafPQ) LeafPQ) 10
NodePQ 3 (NodePQ 10 LeafPQ LeafPQ) (NodePQ 4 LeafPQ LeafPQ)
*Binpq> insertBinpq (NodePQ 3 LeafPQ (NodePQ 4 LeafPQ LeafPQ)) 10
NodePQ 3 (NodePQ 4 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) LeafPQ
*Binpq> insertBinpq (NodePQ 3 (NodePQ 4 LeafPQ LeafPQ) (NodePQ 5 LeafPQ LeafPQ)) 10
NodePQ 3 (NodePQ 5 (NodePQ 10 LeafPQ LeafPQ) LeafPQ) (NodePQ 4 LeafPQ LeafPQ)
\end{verbatim}

Como j\'a foi testado anteriormente a corre\c c\~ao do \textit{merge}, a utiliza\c c\~ao desses par\^ametros cerca todas as possibilidades de varia\c c\~ao das entradas. E como os resultados obtidos foram os esperados, podemos presumir que o algoritmo est\'a correto.

\end{document}
