%% LyX 1.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[a4paper,portuges]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{babel}
\usepackage{algorithm}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}
\newcommand{\noun}[1]{\textsc{#1}}
%% Special footnote code from the package 'stblftnt.sty'
%% Author: Robin Fairbairns -- Last revised Dec 13 1996
\let\SF@@footnote\footnote
\def\footnote{\ifx\protect\@typeset@protect
    \expandafter\SF@@footnote
  \else
    \expandafter\SF@gobble@opt
  \fi
}
\expandafter\def\csname SF@gobble@opt \endcsname{\@ifnextchar[%]
  \SF@gobble@twobracket
  \@gobble
}
\edef\SF@gobble@opt{\noexpand\protect
  \expandafter\noexpand\csname SF@gobble@opt \endcsname}
\def\SF@gobble@twobracket[#1]#2{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{algorithmic}

\makeatother
\begin{document}

\title{Projeto e Análise de Algoritmos\\
1\ensuremath{º} Trabalho Prático}


\author{Tiago Alves Macambira}


\date{2003.1}

\maketitle

\section{Avaliar as Somas}


\subsection{\protect\( \sum _{i=1}^{n}a^{i}\protect \)}

Isso é simplesmente o somatório dos n primeiros elementos elementos
de uma progressão geométrica, com \( a_{1}=q=a \). A dedução é trivial
e encontra-se em qualquer livro de 2\ensuremath{º} grau. De qualquer
forma, vamos a ela:

\( S_{n}=a^{1}+a^{2}\ldots +a^{n} \)

\( S_{n}=a+aa\ldots +aa^{n-1} \)

Introduzindo \( a^{n+1} \) em ambos os lados

\( S_{n}+a^{n+1}=a+aa^{1}+\ldots +aa^{n-1}+a^{n+1}=a+aa^{1}\ldots +aa^{n-1}+aa^{n} \)

\( S_{n}+aa^{n}=a+aa\ldots +aa^{n-1}+aa^{n} \)

\( S_{n}+aa^{n}=a+a\left( a+aa\ldots +aa^{n-1}\right)  \)

\( S_{n}+aa^{n}=a+aS_{n} \)

\( S_{n}=\frac{a\left( a^{n}-1\right) }{a-1} \)

Assim \( \sum _{i=1}^{n}a^{i}=\frac{a\left( a^{n}-1\right) }{a-1} \)para
\( a\neq 1 \). 

Para \( a=1 \), \( \sum _{i=1}^{n}a^{i}=1+\ldots +1=n \)


\subsection{\protect\( \sum _{i=1}^{n}\frac{1}{i}\protect \)}

Usando aproximação por integrais\cite[p50]{bibcormen}

A margem inferior:

\[
\sum ^{n}_{k=m}\frac{1}{k}\geq \int _{m}^{n+1}\frac{dx}{x}=\ln \left( n+1\right) \]


Para margem superior, derivamos a inequação:

\[
\sum ^{n}_{k=2}\frac{1}{k}\leq \int _{1}^{n+1}\frac{dx}{x}=\ln n\]


O que dá a margem:

\[
\sum ^{n}_{k=1}\frac{1}{k}\leq \ln n+1\]



\subsection{\protect\( \sum _{i=1}^{n}\log i\protect \)}

\begin{eqnarray*}
\sum _{i=1}^{n}\log i & = & \log 1+\log 2+\ldots +\log n\\
 & = & \log \left( 1\cdot 2\cdot \ldots \cdot n\right) \\
 & = & \log n!
\end{eqnarray*}


Usando a {}``Aproximação de Stirling''\cite{bibcormen,matconcr},
chegamos em

\begin{eqnarray*}
\sum _{i=1}^{n}\log i & = & \log n!\\
 & = & \Theta \left( n\log \right) 
\end{eqnarray*}



\section{Apresente a compliexidade de tempo para os procedimentos abaixo:}


\subsection{Pesquisa(n)}

Caso Base:

\begin{eqnarray*}
T\left( 1\right)  & = & 1\\
T\left( n\right)  & = & 1+\left( n-1\right) +T\left( \frac{3}{5}n\right) \\
 & = & n+T\left( \frac{3}{5}n\right) 
\end{eqnarray*}


Aplicando o \emph{Master Theorem}\cite[p62]{bibcormen}, tendo que
\( a=1 \), \( b=\frac{5}{3} \) e \( f\left( n\right) =n \), chegamos
ao resultado que 

\[
T\left( n\right) =\Theta \left( f\left( n\right) \right) =\Theta \left( n\right) \]


de qualquer forma, pelo método da substituição:

\begin{eqnarray}
T\left( n\right)  & = & n+T\left( \frac{3}{5}n\right) \\
T\left( \frac{3}{5}n\right)  & = & \frac{3}{5}n+T\left( \frac{3^{2}}{5^{2}}n\right) \\
T\left( \frac{3^{2}}{5^{2}}n\right)  & = & \frac{3}{5}n+T\left( \frac{3^{3}}{5^{3}}n\right) \\
 & \vdots  & \\
T\left( \left( \frac{3}{5}\right) ^{i}n\right)  & = & \left( \frac{3}{5}\right) ^{i}n+T\left( \left( \frac{3}{5}\right) ^{i+1}n\right) \label{2.1.1} \\
 & \vdots  & \\
T\left( \left( \frac{3}{5}\right) ^{k}n\right)  & = & 1
\end{eqnarray}


Ora, chegaremos ao fim da recursão quando

\begin{eqnarray}
\left( \frac{3}{5}\right) ^{k}n & = & 1\\
k\log _{\frac{3}{5}}n & = & 1\\
k & = & \log _{\frac{5}{3}}n
\end{eqnarray}


Logo, 

\begin{eqnarray}
T\left( n\right)  & = & \left( \frac{3}{5}\right) ^{0}n+\left( \frac{3}{5}\right) ^{1}n+\ldots +\left( \frac{3}{5}\right) ^{k}n\\
 & = & \sum ^{k}_{i=0}\left( \frac{3}{5}\right) ^{i}n\\
 & = & \sum _{i=0}^{\log _{\frac{3}{5}}n}\left( \frac{3}{5}\right) ^{i}n\\
 & = & n\frac{1-\frac{3}{5}^{1+\log _{\frac{5}{3}}n}}{1-\frac{3}{5}}
\end{eqnarray}



\subsection{Fib}

Vamos inicialmente ver a condição inicial dessa recursão

\begin{eqnarray*}
T\left( 0\right)  & = & 1\\
T\left( 1\right)  & = & 1
\end{eqnarray*}


Para \( n \) qualquer, a expressão de tempo desse algoritmo fica

\[
T\left( n\right) =T\left( n-1\right) +T\left( n-2\right) \]


Ora, a expressão acima é a função de recorrência que devolve o \( n \)-ésimo
numero de Fibonacci. Logo, a complexidade de tempo desse algoritmo
será, para uma entrada \( k \), o valor do \( k \)-ésimo número
de Fibonacci, cujo valor é dado pela fórmula:

\[
F_{n}=\frac{1}{\sqrt{5}}\left( \phi ^{n}-\hat{\phi }^{n}\right) \]


Ou, arredondando para o inteiro mais próximo:

\begin{eqnarray*}
F_{n} & = & \left\lfloor \frac{\phi ^{n}}{\sqrt{5}}+\frac{1}{2}\right\rfloor \\
 & = & \frac{\phi ^{n}}{\sqrt{5}}
\end{eqnarray*}


Onde \( \phi =\frac{\left( 1+\sqrt{5}\right) }{2} \)

A demonstração completa da obtenção de \( F_{n} \) pode ser obtida
em\cite[p.212-219]{matconcr}

Finalmente, para fechar esse item, seria bom resaltar que \( T\left( n\right) =O\left( 2^{n}\right)  \)


\subsection{Sort1}

O algoritmo é o merge-sort, que é \( O\left( n\log n\right) . \)
De qualquer forma, vamos à análise desse algoritmo.


\subsubsection{Merge}

Antes de prosseguirmos, precisamos saber a complexidade de tempo do
procedimento \noun{merge.} É sabido que dá para se construir sem
muito esforço um algoritmo que fazer intercalação de dois vetores
de tamanho iguais, cada um deles ordenados, em \( O(n) \). Para provar,
propomos um algoritmo que faça isso e calcularemos a sua complexidade:


\begin{algorithm}

\caption{\label{Algoritmo}Merge de dois vetores}

\begin{algorithmic}

\REQUIRE $vetor AUX$

\STATE $pos_i \leftarrow i$

\STATE $pos_j \leftarrow m+1$

\STATE $k \leftarrow i$

\WHILE{$k \leq j$}

\WHILE{$(A[pos_i] \leq A[pos_j]) and (pos_i \leq m)$}

\STATE $Aux[k] \leftarrow A[pos_i]$

\STATE $k \leftarrow k + 1$

\STATE $pos_i \leftarrow pos_i + 1$

\ENDWHILE

\WHILE{$k \leq j$}

\STATE $Aux[k] \leftarrow A[pos_j]$

\STATE $k \leftarrow k + 1$

\STATE $pos_j \leftarrow pos_j + 1$

\ENDWHILE

\ENDWHILE

\FOR{$x \leftarrow i..j$}

\STATE $A[x] \leftarrow AUX[x]$

\ENDFOR

\end{algorithmic}
\end{algorithm}
No algoritmo \ref{Algoritmo}, acima o laco \emph{while} mais externo
garante que não haja sobreposição dos dois vetores que estão sendo.
A cada iteração desse laço, os dois laços internos vão linearmente
percorrendo e inserindo, ordenadamente, os elementos contidos nas
respectivas partições de A que cada laço trata: 

\[
3(m-i+1)+3[j-(m+1)+1]+(j-i+1)=4(j-i+1)=O(n)\]



\subsubsection{Sort1}

Uma vez sabendo a complexidade de tempo do procedimento \noun{merge},
sigamos para o cálculo da complexidade de tempo do algoritmo Sort1
como um todo.

\[
T\left( n\right) =2T(n/2)+O(n)\]


Aplicando o \emph{Master Theorem}\cite[p62]{bibcormen}, tendo que
\( a=2 \), \( b=2 \) e \( f\left( n\right) =O\left( n\right)  \),
chegamos ao resultado que 

\[
f\left( n\right) =\Theta \left( n^{\log _{b}a}\right) \Rightarrow T\left( n\right) =\Theta \left( n^{\log _{b}a}\log n\right) =\Theta \left( n^{\log _{2}2}\log n\right) =\Theta \left( n\log n\right) \]


Já temos uma idéia do que procurar. Desenvolvamos a equação recursiva
por substituições:

\begin{eqnarray*}
T\left( n\right)  & = & 2T(\frac{n}{2})+O(n)\\
 & = & 4T\left( \frac{n}{4}\right) +20\left( n\right) \\
 & \vdots  & \\
T\left( n\right)  & = & 2^{i}T\left( \frac{n}{2^{i}}\right) +iO\left( n\right) 
\end{eqnarray*}


Fazendo \( i=\lg n \)

\begin{eqnarray*}
T\left( n\right)  & = & n+O(n)\lg n\\
 & = & o(n\lg n)
\end{eqnarray*}



\subsection{Sort2}

Esse algoritmo é muito parecido com o anterior. 

A sua fórmula de recorrência é:

\[
T\left( n\right) =\left\{ \begin{array}{c}
1,\\
3T\left( \frac{n}{3}\right) +\frac{5n}{3}-2
\end{array}para\right. n=1\]


Aplicando o \emph{Master Theorem}\cite[p62]{bibcormen}, tendo que
\( a=3 \), \( b=3 \) e \( f\left( n\right) =\frac{5n}{3}-2 \),
chegamos ao resultado que 

\[
f\left( n\right) =\Theta \left( n^{\log _{b}a}\right) \Rightarrow T\left( n\right) =\Theta \left( n^{\log _{b}a}\log n\right) =\Theta \left( n^{\log _{3}3}\log n\right) =\Theta \left( n\log n\right) \]



\section{Limite Inferior}

Ordenações através de comparações podem ser vistas abstratamente em
termos de \emph{árvores de decisão}.Uma arvore de decisão representa
as comparações realizadas pelo algoritmo de ordenação quando ele trabalha
em uma entrada de um dado tamanho.

O tamanho do caminho mais longo partindo da raíz de uma árvore de
decisão para qualquer um de suas folhas representa o pior-caso no
número de comparações que um algoritmo de ordenação realiza. Conseqüentemente,
o pior-caso no número de comprarações para uma ordenação por comparação
corresponde à altura da sua árvore de decisão.

Assim, achar o limite inferior para a altura de uma árvore de decisão
equivale a achar o limite inferior para o tempo de execução de qualquer
algoritmo de ordenação por comparação.

Considere a arvore de decisão de altua \( h \) que ordena \( n \)
elementos. Como existem \( n! \) permutações dos \( n \) elementos,
cada permutação representa uma ordem de ordenação distinta, a árvore
tem que ter pelo menos \( n! \) folhas. Já que uma árvore binária
de altura \( h \) tem não maus do que \( 2^{h} \) folhas, temos:

\[
n!\leq 2^{h}\]


que, através do uso de logaritmos, fica

\[
h\geq \lg \left( n!\right) \]
, já que a função é monotonicamente crescente. Usand as aproximação
de Stirling, temos:

\[
n!\geq \left( \frac{n}{e}\right) ^{n}\]


onde \( e \) é a base dos logaritmos naturais; assim:

\begin{eqnarray*}
h & \geq  & \lg \left( \frac{n}{e}\right) ^{n}\\
 & = & n\lg n-n\lg e\\
 & = & \Omega \left( n\lg \right) 
\end{eqnarray*}
 - 

\cite{bibweiss,bibcormen}


\section{Algoritmos de ordenação parcial: estudos comparativos}

Em anexo, no documento \emph{estatisticas/tempo.txt}, há um lista
com os médios tempos de execução de vários algoritmos, para vários
valores de n e k.

Também em anexo, gráficos relativos a essas estatisticas em \emph{graficos/time\_graph\_{*}.ps}.


\subsection{Experimentalmente, o número de comparações e movimentos-de-registro}

Os algoritmos originados de algoritmos \( O\left( n^{2}\right)  \)
perdem muito tempo fazendo comparações. O partital\_Selection é destes
aquele que mais realiza comparaçõe, seguido do insertion ( também
originado de um algoritmo \( O\left( n2\right) . \) Heap e quick
sort realizam um número bem parecido de movimentações de regi:stros. 

Em relação a comparação de registros, partial\_insertion sort é o
que mais se destaca quando do crescimento do n. Todos os outros ficam
relativamente estáveis.


\subsection{Tempo de Execução}


\subsubsection{Interpretação}

É interessante notar que os algoritmos descendentes de algoritmos
\( O\left( n^{2}\right)  \), a exceção de \( n \) muito pequenos,
a medida que \( k \) aumenta, sua performance diminui drasticamente.
A perforamance desses algoritmos, contudo, ainda dá margens para interessantes
surpresas: o partial\_selection é disparadoo melhor algoritmo para
\( k=1 \). Mas também esse é o unico caso onde ele se dá bem. O partial\_insertion\_sort
também apresenta uma acelerada taxa de crescimento com um aumento
de \( k \). Ainda assim é, para valores de \( k \) proximos de \( \sqrt{n} \)
uma boa opção, rivalizando nas faixas iniciais de \( k \) até com
o quicksort.

Enrtre os algoritmos cujos originais eram \( O(n\log n) \) o quicksort
é sempre a melhor opção. O partial\_heapsort apresente, em alguns
momentos, um custo inicial de montar a heap alto demais, em comparação
com os algoritmos cujos originais são \( O(n^{2}) \). Não pouca vezes
perdeu para o insetion\_sort com valores pequenos de k.


\subsection{Resultados Analíticos}


\subsubsection{Partial insertion sort}

o que difere este algoritmo do original é que ele

\begin{enumerate}
\item Realiza um insertion sort normal para os k primeiros elementos (\( O(k^{2} \)))
\item Para cada elemento fora desse intervalo, ele compara o valor destes
com o do ultimo ( e maior ) elemento contudo no intervalo e, se for
o caso, troca esses elementos de lugar, chamando novamente insertion
sort nos k primeiros elementos para ordená-los (\( O(n-k)k^{2} \))
\end{enumerate}
A complexidade desse algoritmo fica então:

\begin{eqnarray*}
T(n) & = & O(nk^{2}+k^{2}-k^{3})\\
 &  & 
\end{eqnarray*}


Logo, esse algoritmo, com L pequenos é bom, pois o fator \( nk^{2} \)
fica minimizado. Mas, aumentos em \( k \) acarreta um crescimento
muito grande na parcela \( nk^{2} \)


\subsubsection{Partial Selection Sort}

O que difere esse do original é que o laço externo é limitado a rodar
k vezes. Complexidade:

\begin{eqnarray*}
T\left( n\right)  & = & \sum _{i=0}^{k-1}n-i\\
 & = & k\frac{n+n-k-1}{2}\\
 & = & \frac{2nk-k^{2}-k}{2}\\
 & = & O\left( nk+k^{2}\right) 
\end{eqnarray*}


Pela fórmula analítica fica fácil de ver pq o selection decresce tanto
em relação ao insertion: apeser de ser inicialmente menor do que o
insertions, k tem um grande peso nesse algoritmo.


\subsubsection{Partial Heapsort}

Aqui nada de estranho: inicialmente cria-se um heap\_invertido. Faz-se
k vezes o o passo de remoção do raiz da heap para o final da fila.
Ao final da ordenação dos k elementos , estes, que estavam em ordem
reversa ao no final do vertor, são copiado de volta.

\begin{itemize}
\item O custo para montar o heap é o mesmo: \( O\left( n\right)  \)
\item O custo apra retirar os k primeiros: \( k\cdot (\log  \)m)
\item O custo para re-ordenar os k elementos no incio do vertor: \( O(k) \)
\end{itemize}
Total: \( k\log n+k \)=\( O\left( k\log n\right)  \)

Um \( k \) pequeno ajuda mas o \( \log n \) estará sempre presente.


\subsubsection{Partial Quick}

Melhor algoritmo para \( k \) e \( n \) grandes - ele simplesmente
se dá bem de qualquer forma.

A complexidade dele, no pior caso é iqual á do quicksort normal: \( O\left( n^{2}\right)  \).
Esse pior caso poderia ser facilmente evitado se fosse utilizado antes
um algoritmo \( O\left( n\right)  \) pra selecionar o \( k \)-esimo
elemento do vetor e, com ele em mãos, fazer o particiomento de forma
{}``perfeita''. Contudo, a nossa implementação no caso médio é boa
o suficiente para atender as nossas espectativas.

\begin{thebibliography}{1}
\bibitem{bibcormen}{}``Introduction to Altorithms'', Cormen et al, 1st Edition
\bibitem{bibweiss}{}``Algorithms, Data Structures, and Problem Solving With C++''
, Mark Allen Weiss.
\bibitem{matconcr}{}``Matemática Concreta - Fundantos para a Ciência da Computação'',
Graham, Knuth, Patashnik; 2\ensuremath{ª} edição; LTC Editora\end{thebibliography}

\end{document}
