Apostila-algoritmos-unicamp

Notas de Aula de Complexidade de Algoritmos Flávio Keidi Miyazawa INSTITUTO DE COMPUTAÇÃO UNIVERSIDADE ESTADUAL DE CAMPINAS A principal referência usada neste texto é o livro Introduction to Algorithms, Cormen, Leiserson e Rivest. A maior parte do texto é uma tradução grosseira de parte deste e de outros livros. Este texto está mal escrito (a maior parte foi escrita pouco tempo antes das aulas) e serve apenas como notas de aula para os cursos de Análise e Complexidade de Algoritmos. Uso estas notas de aula de maneira a organizar melhor a apresentação das aulas e a organização do assunto. Por isso, recomendo que você use este texto no máximo como um guia para os itens que estaremos considerando no curso, mesmo porque diversos assuntos não estão cobertos aqui. Na bibliografia listo alguns dos livros que serão usados. Recomendo que você leia estes livros, principalmente o livro indicado acima, pois é um livro bem escrito que tem tanto amplitude como profundidade nos diversos assuntos do curso. Por motivos de tempo, estas notas não foram revisadas. Se você tem alguma sugestão ou correção, por favor, escreva para mim. FLÁVIO KEIDI MIYAZAWA Instituto de Computação UNICAMP Caixa Postal 6176 13083-970 Campinas-SP fkm@ic.unicamp.br www.ic.unicamp.br/~fkm 2 Sumário 1 Introdução à Análise de Algoritmos 1 1.1 Conceitos Básicos .......................................... 1 1.2 Tipos de Provas ............................................ 5 1.2.1 Prova por Construção ................................ 5 1.2.2 Prova por Contradição .............................. 6 1.2.3 Prova por Indução .................................... 7 1.3 Notação Assintótica ....................................... 8 1.3.1 Exponenciais .......................................... 11 1.4 Algumas Relações Matemáticas ...................... 13 1.4.1 Fatoriais .................................................. 13 1.4.2 Exponenciais ............................................. 13 1.4.3 Polinômios .............................................. 14 1.4.4 Logaritmos .............................................. 14 1.4.5 Somatórias .............................................. 15 2 Recorrências 19 2.1 Merge Sort .................................................. 19 2.2 Recorrência do Merge Sort .................................. 19 2.2.1 Um erro comum ........................................ 22 2.2.2 Mudanças de variáveis ............................... 22 2.3 Método Iterativo .......................................... 23 2.3.1 Árvores de Recursão ................................. 24 2.4 Relação de Fibonacci e Recorrências Homogêneas .... 25 2.5 Recorrências Não Homogêneas ........................... 27 2.6 Recorrência Geral para Divisão e Conquista ........ 28 2.7 QuickSort ................................................... 30 2.8 Recorrência do QuickSort, Recorrências com História Completa ....................................................... 31 2.9 Comentários ................................................ 33 3 Ordenação em Tempo Linear 34 3.1 Limite Inferior para a Ordenação com Comparações . 34 3 3.2 Algoritmos Lineares para Ordenação .......................................... 36 3.3 CountingSort ................................................................. 36 3.4 BucketSort ................................................................ 37 3.5 RadixSort ................................................................ 37 4 Algoritmos para Seleção .......................................................... 39 4.1 Introdução ................................................................ 39 4.2 Máximos e Mínimos ............................................................. 39 4.3 Heap / HeapSort ............................................................. 40 4.3.1 InsereHeap ............................................................... 42 4.3.2 Rebaixa ................................................................ 43 4.3.3 ConstroiHeap ............................................................... 45 4.3.4 ExtraiMax ................................................................. 46 4.3.5 HeapSort ................................................................. 47 4.4 Seleção do k-ésimo em tempo esperado linear .......................... 48 4.5 Seleção do k-ésimo em tempo linear ...................................... 50 4.5.1 QuickSort em tempo O(n log n) .............................................. 53 4.6 Exercício .................................................................. 53 5 Programação Dinâmica ............................................................. 54 5.1 Elementos da Programação Dinâmica ......................................... 54 5.2 Multiplicação de Matrizes ..................................................... 55 5.3 Problema da Mochila - Knapsack ............................................ 59 5.3.1 Primeira tentativa usando hipótese de indução simples (que não dá certo) ........ 59 5.3.2 Segunda tentativa usando hipótese de indução fortalecida (que dá certo) ........ 59 5.4 Exercício .................................................................. 62 6 Algoritmos Gulosos ................................................................. 63 6.1 Elementos da Estratégia Gulosa ............................................ 63 6.2 Algoritmos Gulosos versus Programação Dinâmica .......................... 63 6.3 Código de Huffman ........................................................... 64 6.4 Fundamentos Teóricos para Métodos Gulosos ............................... 71 6.4.1 Algoritmos Gulosos e Matróides .............................................. 72 6.5 Um Problema de Escalonamento de Tarefas ................................. 74 7 Algoritmos em Grafos .............................................................. 76 7.1 Notação e Definições .......................................................... 76 7.2 Algumas Aplicações ......................................................... 78 7.3 Alguns Resultados ............................................................ 79 7.4 Representação de Grafos .................................................... 80 7.5 Algoritmos para Busca em Grafos ............................................ 82 7.5.1 Busca em Largura ......................................................... 82 7.5.2 Busca em Profundidade ................................................... 83 7.5.3 Achar circuito em um grafo orientado ....................................... 85 7.5.4 Ordenação Topológica ..................................................... 87 7.5.5 Caminho de Peso Mínimo em Grafo Acíclico .......................... 89 7.5.6 Componentes Fortemente Conexas .................................... 90 7.6 Árvore Geradora de Peso Mínimo ............................................ 92 7.6.1 Algoritmo de Kruskal ................................................... 94 7.6.2 Algoritmo de Prim ...................................................... 97 7.7 Algoritmos para Caminhos Mínimos ........................................ 100 7.7.1 Círculos Negativos ..................................................... 100 7.7.2 Representando Caminhos Mínimos .................................. 103 7.7.3 Relaxamento ............................................................ 103 7.7.4 Árvores de Caminhos Mínimo ............................................. 105 7.7.5 Algoritmo de Dijkstra .................................................... 107 7.7.6 Algoritmo de Bellman-Ford ............................................... 110 7.8 Caminho Mínimo Entre Todos os Pares de Vértices ..................... 112 7.8.1 Algoritmo de Floyd-Warshall .......................................... 113 7.8.2 Fecho Transitivo ....................................................... 115 7.8.3 Algoritmo de Johnson .................................................. 117 7.9 Coloração em Grafos Planares ............................................. 120 7.10 Rede de Fluxo ............................................................... 123 7.10.1 Caminhos Aumentadores ............................................. 123 7.10.2 Algoritmo Ford-Fulkerson ............................................ 125 7.10.3 Estratégia Edmonds-Karp ............................................. 126 7.11 Emparelhamento Máximo em Grafos Bipartidos .......................... 128 8 Algoritmos Algébricos .......................................................... 130 8.1 Tamanho das entradas e custo das operações aritméticas ............ 130 8.2 Noções elementares em Teoria dos Números ................................ 130 8.3 Máximo Divisor Comum ..................................................... 133 8.4 Aritmética Modular .......................................................... 136 8.4.1 Grupos Finitos ............................................................. 136 8.4.2 Subgrupos ............................................................... 138 8.4.3 Subgrupos gerados por um elemento .................................. 138 8.5 Resolvendo equações lineares modulares .................................. 140 8.6 Teorema Chinês do resto ................................................... 142 8.7 Potências de um elemento ................................................. 145 8.7.1 Práticas em repetição de quadrados ................................... 147 8.8 Sistema de chaves públicas RSA .......................................... 149 8.8.1 Obtenção das chaves pública e privada ................................ 150 8.9 Teste de números primos .................................................. 151 8.9.1 Densidade dos números primos ........................................ 152 8.9.2 Teste randomizado de Miller-Rabin .................................... 153 9 Polinômios e FFT ............................................................... 157 9.1 Polinômios ................................................................. 157 9.2 Representação através de coeficientes .................................... 158 9.3 Representação através de pontos ......................................... 158 9.4 Multiplicação rápida de polinômios na forma de coeficientes ........... 160 9.5 Transformada Discreta de Fourier (DFT) e Transformada Rápida de Fourier (FFT) .. 161 9.5.1 Raízes complexas da unidade .......................................... 161 9.6 Transformada Discreta de Fourier ........................................ 163 9.7 Transformada Rápida de Fourier ........................................... 164 9.8 Interpolação nas raízes complexas da unidade .............................. 166 10 NP-Completude ............................................................... 169 10.1 Codificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 10.2 Problemas de Decisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 10.3 Classes P e NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 10.4 Exemplos de Relações Polinomiais . . . . . . . . . . . . . . . . . . . 174 11 Tópicos dados em aula e que não estão neste texto 186 11.1 Algoritmos Algébricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 11.2 Complexidade Computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 11.3 Algoritmos Exatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 11.4 Algoritmos de Aproximação . . . . . . . . . . . . . . . . . . . . . . 187 7 1 Introdução à Análise de Algoritmos 1.1 Conceitos Básicos Vamos nos interessar por algoritmos computacionais, ou seja, um algoritmo é um procedimento que recebe alguns valores— a entrada— e produz alguns valores — a saída— usando uma seqüência de passos computacionais bem definidos. Um algoritmo também pode ser visto como uma ferramenta para resolver problemas com- putacionais. Um problema é descrito através de 1. uma descrição geral de todos os seus parâmetros. 2. um enunciado sobre que propriedades a resposta ou solução deve satisfazer. Uma instância de um problema é obtida ao se fixar valores particulares de todos os parâmetros do problema. Para cada instância, associaremos um número natural (ou vários) para representar seu tamanho. Ex. Em um problema de ordenação, o tamanho pode ser dado pelo número de elementos na seqüência de entrada. Em um problema em grafos, o tamanho pode ser dado pelo número de arestas do grafo ou ainda o número de vértices. Exemplo 1.1 Problema de Ordenação Entrada: Seqüência I := (a1,..., an) Saída: Seqüência U := (a1,..., an) que é uma permutação da entrada tal que a1 ≤ a2 ≤ · Dizemos que um algoritmo está correto se para cada instância de entrada ele termina com a resposta correta. Neste caso dizemos que o algoritmo resolve o problema computacional. InsertionSort(vetor V, inteiro n) j <- 2; % Linha (1) enquanto j ≤ n faça % Linha (2) \ AUX = V[j]; % Linha (3); i <- j - 1; % Linha (4) enquanto i > 0 e V[i] > AUX faca % Linha (5) \ V[i +1] <- V[i]; % Linha (6) i <- i - 1; % Linha (7) fim enquanto V[i +1] <- AUX; % Linha (8) j <- j + 1 % Linha (9) fim enquanto 1 Primeiramente, vamos verificar se este algoritmo está correto. Vamos usar duas técnicas, Uso de invariantes e prova por indução. No caso do invariante, analisamos condições que se mantém verdadeiras em todas as ite- rações do algoritmo. No exemplo acima, um invariante na linha (2) é que a seqüência V[1],...,V[j - 1] está ordenada em cada passo. Vamos mostrar isto por indução em j. BASE: Para j = 2 é claramente verdade. HI: Vamos supor que até a iteração j = k, o invariante é verdadeiro. Vamos provar que para j = k+1 o invariante também é válido. Note que quando a condição da linha (5) não é satisfeita então i = 0 e a seqüência ordenada na iteração anterior está deslocada de uma posição) ou V[i] > AUX e a seqüência V[i + 1],...,V[j - 1] está deslocada. Com isso, colocamos AUX na posição i + 1 e a seqüência resultante fica ordenada. Portanto, na última iteração, temos o vetor totalmente ordenado. I.e., O algoritmo está correto. Analisar um Algoritmo é predizer os recursos que o algoritmo requer. Os recursos podem ser temmpo, comunicação, portas lógicas, na maioria das vezes, estaremos interessados em medir seu tempo computacional. Um algoritmo deverá ser analizado no modelo da tecnologia de computador que utilizaremos. Para este curso, vamos supor modelo RAM (Random Access Machine) com um processador. Neste modelo, as instruções são executadas seqüencialmente uma após a outra, sem ope- rações concorrentes. Instruções diferentes podem requerer tempos diferentes de processamento. O tempo de execução de um algoritmo sobre uma entrada particular é o número de operações primitivas ou "passos” executados. Vamos analisar o tempo de execução do algoritmo de ordenação InsertionSort. Suponha que o custo de executar as instruções (1)-(9) sejam dados por c1,...,c9. Assim, o tempo de execução do algoritmo para um vetor com n elementos é dado por: T(n) = c1 +c2 .n +c3(n-1) +c4(n-1) + +c5 ∑_{j=2}^n tj +c6 ∑_{j=2}^n (tj-1) +c7 ∑_{j=2}^n(tj-1) +c8(n-1) +(n-1) ∑_{j=2}^n tj = ∑_{j=2}^n ((c5 + c6 + c7)(n - 1)+ c8 ∑_{i}^n (n-1) = c1 +c2 .n +c3(n-1) +c4(n-1) +c5 ∑_{j=2}^n (tj-1) onde tj é o número de vezes que a condição na linha (5) é verificada. Note que 1≤ tj ≤ j. 2 Melhor Caso: A sequência já está ordenada, e t_j = 1 Vj. Assim, \[T(n) = c_1 + c_2 \cdot n + (c_3 + c_4 + c_5 + c_6)(n-1) + c_5(n-1) = a \cdot n + b.\] Pior Caso: A sequência já está ordenada na ordem contrária, i.e., t_j = j. Assim, \[T(n) = c_1 + c_2 \cdot n + (c_3 + c_4 + c_5 + c_6)(n-1) + c_5(n+2)(n-1)/2 + (c_6 + c_7)n(n-1)/2 = an^2 + bn + c.\] Em geral estaremos analisando o comportamento de pior caso. O ideal seria analisar o caso médio, mas isto depende muito da aplicação e de sua distribuição de probabilidade. Vamos considerar um outro algoritmo de ordenação, por seleção: SelectionSort. SelectionSort(vetor V, inteiro n) se n > 1 então i_max ← Máximo(V, n); Troca(V_i_max, V[n]); SelectionSort(A, n – 1); fim se onde, Máximo(vetor V, inteiro n) i_max ← 1; para i ← 2 até n faça se V[i] > V[i_max] então i_max ← i; fim se fim para Exercício 1.1 Prove o correta e analise o tempo de execução no melhor e pior tempo do algoritmo de ordenação por seleção (sup. indução). Esta técnica de usar um problema particular (ou mais simples) para resolver um mais geral é chamada de técnica de indução. Outro exemplo desta técnica é a busca binária. Vimos que o tempo de execução do InsertionSort é no pior caso, algo em torno de \(T(n) = an^2 + bn + c.\). Este tempo é ditado principalmente pelo termo \(n^2\) que cresce muito mais rápido que os outros termos. A função de complexidade de tempo de um algoritmo expressa o tempo requerido, dando para cada entrada, a maior quantia de tempo necessária para o algoritmo resolver uma instância daquele tamanho.