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