Construção e Análise de Algoritmos – 2016.1

Regras

• Segunda chamada: consulte as regras para a solicitação de prova de segunda chamada.

• Nota da disciplina: Consistirá na média aritmética das notas obtidas pelo aluno nas três avaliações parciais da disciplina:

  Média das Avaliações	≥ 7	7 > média ≥ 4	< 4
  Situação	Aprovado	AF	Reprovado

Bibliografia

Atenção: há exemplares na biblioteca, e, na falta de um, se você não pode comprar um livro para estudar, pode também conseguir uma cópia na internet (em todo caso, se você usa bastante um certo livro, considere comprar um exemplar assim que puder, por ética e respeito aos autores e editoras).

O livro-texto da disciplina é este:

• Original: Introduction to Algorithms (third edition). Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. MIT Press. 2009. ISBN: 9780262033848 (capa dura) e 9780262533058 (capa fina).

• Tradução: Algoritmos – Teoria e Prática. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Editora Campus. 2012. ISBN: 978-85-352-3699-6.

Este livro também cobre o conteúdo da disciplina:

• Original: Algorithms. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. McGraw-Hill. 2006. ISBN: 978-0-07-352340-8.

• Tradução: Algoritmos. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. McGraw-Hill. 2009. ISBN: 978-85-7726-032-4.

Outros livros sobre projeto e análise de algoritmos:

• Algorithm Design and Applications. Michael T. Goodrich, Roberto Tamassia. Wiley. 2015. ISBN: 978-1-118-33591-8.

  Da versão de 2002 desse livro, há capítulos publicamente acessíveis, sobre algoritmos gulosos, divisão-e-conquista, programação dinâmica, algoritmos em grafos e NP-completude.

• Projeto de Algoritmos – com implementações em Pascal e C - 3ª edição. Nivio Ziviani. Cengage Learning. 2011. ISBN: 9788522110506.

• Original: How to Think About Algorithms. Jeff Edmonds. Cambridge University Press. 2008. ISBN: 978-0-521-84931-9.

  Tradução: Como Pensar sobre Algoritmos. Jeff Edmonds. LTC. 2010. ISBN: 9788521617310.

• An Introduction to the Analysis of Algorithms, 2nd Edition. Robert Sedgewick, Philippe Flajolet. Addison-Wesley. 2013. ISBN: 978-0-321-90575-8.

• Algorithms, 4th Edition . Robert Sedgewick, Kevin Wayne. Addison-Wesley. 2011. ISBN: 978-0-321-57351-3.

• Original: Methods in Algorithmic Analysis. Vladimir Dobrushkin. Chapman & Hall/CRC. 2009. ISBN: 978-1420068290.

  Tradução: Métodos para Análise de Algoritmos. Vladimir Dobrushkin. LTC. 2012. ISBN: 9788521620662.

Estes livros cobrem em detalhes a teoria da complexidade:

• Também cobre autômatos e teoria da computação:

  Original: Introduction to the Theory of Computation, 3rd Edition. Michael Sipser. Cengage Learning. 2013. ISBN: 9781133187790.

  Tradução: Introdução à Teoria da Computação (2ª edição). Michael Sipser. Cengage Learning. 2007. ISBN: 9788522104994.

• Clássico:

  Computers and Intractability: a Guide to the Theory of NP-Completeness. Michael R. Garey, David S. Johnson. W. H. Freeman & Company. 1979. ISBN: 0-7167-1045-5.

• Avançado:

  Computational Complexity: A Modern Approach. Sanjeev Arora, Boaz Barak. Cambridge University Press. 2009. ISBN: 978-0521424264.

  A versão preliminar do livro é publicamente acessível!

Aulas: Conteúdos e Exercícios

• Aula 1 (2016-03-15, terça-feira): introdução à disciplina; corretude de algoritmos: pré- e pós-condições; terminação; estrutura de seleção; laço (uso e demonstração de invariantes).

  EXERCÍCIOS ESSENCIAIS:

  1. Escreva um algoritmo iterativo que compute o elemento máximo de um vetor v[1..n] (suponha que n ≥ 1), e prove que o seu algoritmo está correto. Escreva o algoritmo no formato sugerido em sala (nome do algoritmo, entrada, pré-condição, saída, pós-condição e corpo do algoritmo), fornecendo uma especificação completa para ele, e então demonstre a corretude do algoritmo.

  2. Idem ao exercício anterior, mas com relação a uma versão iterativa do algoritmo de busca binária.

  EXERCÍCIO PARA PÓS-GRADUAÇÃO: Escreva (de acordo com a sua preferência), especifique e prove a corretude do algoritmo de Ordenação por Seleção. Observe que tanto o laço externo como o interno possuirão seus invariantes, e que os invariantes de um laço são utilizados para provar os invariantes do outro.

  MATERIAIS DE ESTUDO:

  • As notas de aula [1] e [2] de 2015.1 cobrem essencialmente o mesmo conteúdo que vimos nesta aula, e apresentam por escrito as demonstrações que apresentei apenas verbalmente (há diferenças, mas mais em forma que em conteúdo).

  • No Cormen, invariantes de laço são discutidos no capítulo 2, seção 1.

• Aula 2 (2016-03-18, sexta-feira): tira-dúvidas de exercício sobre verificação; prova da corretude do algoritmo de máximo de um vetor; uso e prova de variantes (para provar a terminação) de laço; especificação de algoritmo recursivo: tamanho de lista encadeada; correspondência entre lista encadeada e lista como tipo indutivo.

  EXERCÍCIOS ESSENCIAIS:

  1. Com relação ao algoritmo de busca binária citado nos exercícios da aula passada, defina e prove um variante para o laço do algoritmo, e então o utilize para provar que o algoritmo sempre termina.

  2. Com relação ao algoritmo de Ordenação por Seleção citado nos exercícios da aula passada, defina e prove variantes para os dois laços do algoritmo, e então os utilize para provar que o algoritmo sempre termina. Atenção: neste exercício você não precisa provar que o algoritmo é correto, nem apresentar ou provar invariantes para os dois laços do algoritmo; pede-se apenas a demonstração da terminação do algoritmo, via variantes de laço (por outro lado, é possível que, para argumentar sobre um variante, você acabe precisando usar alguns invariantes dos laços do algoritmo; neste caso, basta enunciar (corretamente) esses invariantes, sem prová-los).

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. O variante que você apresentou no exercício anterior sobre a busca binária permite identificar imediatamente que o algoritmo executa um número de iterações no máximo logarítmico sobre o tamanho do vetor? Caso não, forneça um variante que use a função log₂.

  2. Como você já sabe como se especifica a relação entre uma lista encadeada e uma lista matemática (elemento de um conjunto indutivo), escreva um algoritmo iterativo que calcule o tamanho de uma lista encadeada, apresente para ele uma especificação e prove a corretude do algoritmo, incluindo a terminação (ou seja, em particular, você deve definir, usar e provar um variante para o laço do algorimo). As definições de funções sobre "listas matemáticas" apresentadas no material citado abaixo podem ser úteis.

  MATERIAIS DE ESTUDO:

  • Esta nota de aula de 2015.1 [1] cobre o que vimos em sala a respeito de variantes e terminação de laços. Esta nota de aula de Matemática Discreta de 2015.2 [2] descreve em detalhes o tipo "matemático" lista de números como um conjunto indutivo (vá direto à seção 3) (conjuntos indutivos em si são apresentados nesta nota de aula [3]).

  • No Cormen, variantes de laço não são discutidos, nem conjuntos indutivos. Além de nas notas de aula, você pode ler sobre eles também na Wikipédia: variantes, tipos indutivos.

  • O conteúdo que vimos sobre verificação de algoritmos recursivos está explicado neste material [4].

• Aula 3 (2016-03-22, terça-feira): notação assintótica: definição da notação O; exercícios em sala (2n = O(n), 2n³+n² = O(n³), 3n+7 = O(n)); notação Ω; exercício em sala (f = O(g) → g = Ω(f)); notações Θ, o e ω.

  EXERCÍCIOS ESSENCIAIS:

  1. Prove que:

     1. n = Ω(1) – ou seja, mostre que f = Ω(g), sendo f(n) = n e g(n) = 1.

     2. n = ω(1)

     3. 3n = o(n²)

     4. n = O(2ⁿ)

  2. Em sala, nós comentamos que, informalmente, é simples mostrar que todo polinômio de grau k é O(n^k), desde que o monômio de maior grau tenha coeficiente positivo. Forneça uma prova precisa para esse resultado, usando indução.

     Além disso: −5n³ + 100n² = O(n³)?

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Prove que:

     1. n = o(2ⁿ)

     2. n² = O(2ⁿ)

     3. lg(n!) = Θ(n*lg(n)), sendo lg(x) = log₂(x).

  MATERIAIS DE ESTUDO:

  • O final desta nota de aula de 2015.1 [1] e o início desta outra [2] cobrem o que vimos em sala a respeito de notação assintótica.

  • No Cormen, a notação assintótica é apresentada no capítulo 3, seção 1.

• 2016-03-25, sexta-feira: sem aula – feriado nacional.

• Aula 4 (2016-03-29, terça-feira): tempo de execução de algoritmos iterativos: cálculo do número de iterações de um laço; uso de variantes para formalizar esse cálculo (opcional); complexidade assintótica de tempo de execução; exemplos: busca linear, ordenação por seleção.

  OBSERVAÇÃO: não deixe de ler o material abaixo sobre contagem de iterações via variantes de laço!

  EXERCÍCIOS ESSENCIAIS:

  1. Apresente limites assintóticos inferior e superior, para os melhor caso, pior caso e caso geral, do algoritmo de ordenação por bolha.

  2. Idem para o algoritmo tradicional de multiplicação de duas matrizes, uma "m x n" e outra "n x o".

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Faça os exercícios 1 e 2 do material abaixo sobre contagem de iterações via variantes de laço.

  MATERIAIS DE ESTUDO:

  • O material [1] da aula passada introduz o assunto do cálculo do tempo de execução de algoritmos iterativos.

  • (IMPORTANTE) Este material [2] explica cuidadosamente a técnica (opcional) de contagem de iterações via variantes de laço ilustrada em sala, além de apresentar um terceiro exemplo de análise de tempo de execução de algoritmo iterativo (busca binária).

  • No Cormen, o cálculo do tempo de execução de algoritmos iterativos é apresentado no capítulo 2, seção 2 – leitura recomendada!

• Aula 5 (2016-04-01, sexta-feira): tempo de execução de algoritmos recursivos: tempo de execução em termos de relações de recorrência; limite assintótico via solução exata de recorrência (exemplo: Torres de Hanói); limite assintótico direto para recorrências (exemplo: Busca Binária).

  EXERCÍCIOS ESSENCIAIS:

  1. Escreva um algoritmo recursivo que calcule o n-ésimo número de Fibonacci e prove um limite superior assintótico para o seu tempo de execução:

     fib(n) = | n,                   se n ∈ {0,1}
              | fib(n-1) + fib(n-2), se n ≥ 2
     

  2. Escreva uma relação de recorrência para o tempo de execução do algoritmo abaixo e prove que essa função é O(n).

     Algoritmo: soma_rec
     Entrada:   vetor v[1..n] de números, naturais "i" e "f"
     Pré-cond.: n ≥ 0 e (i ≤ f → 1 ≤ i e f ≤ n)
     Saída:     número "k"
     Pós-cond.: k = ∑j ∈ [i..f] v[j]
     ----------------------------------------------------------------------
     1. SE f < i
     2. | RETORNE 0.
     3. SE i = f
     4. | RETORNE v[i].
     5. m := (i+f) ÷ 2
     6. RETORNE soma_rec(v[1..n], i, m) + soma_rec(v[1..n], m+1, f).
     

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Prove ou Refure: g(n) = O(lg n), sendo

     g(n) = | a,            se n ≤ 1
            | b + g(⌈n/2⌉), se n ≥ 2.
     

  MATERIAIS DE ESTUDO:

  • O lema 2 deste material [1] de 2015.1 contêm a prova que fizemos em sala do limite superior assintótico da recorrência do tempo de execução do algoritmo de busca binária recursivo.

  • No Cormen, o cálculo do tempo de execução de algoritmos recursivos é introduzido no capítulo 2, seção 3.2 – leitura recomendada!

• Aula 6 (2016-04-05, terça-feira): técnicas para a solução assintótica de recorrências: (1) fortificar resultado a ser provado por indução (exemplo: soma recursiva de vetor); (2) aumentar o intervalo de números incluídos no caso base da indução (exemplo: "g(n) = b + g(⌊lg n/2⌋ + 3)").

  EXERCÍCIOS ESSENCIAIS:

  1. Escreva a prova do caso base da 2ª indução da aula, lembrando que o passo foi provado para t = k+1, com k+1 ≥ 300.

     Recapitulando, a afirmação a ser provada é que, para todo t ≥ 2, vale g(t) ≤ c*lg t, onde

     g(t) = | a,                se 1 ≤ t < 8
            | b + g(⌊t/2⌋ + 3), se 8 ≤ t.
     

  2. Qual é o menor número "k" que torna a função abaixo bem-definida?

     g(t) = | a,                se 1 ≤ t < k
            | b + g(⌈t/2⌉ + 5), se k ≤ t.
     

     Depois de encontrar o valor de "k", prove que g(t) = O(lg n).

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Prove um limite assintótico superior para

     g(n) = | g(⌊n/2⌋) + g(⌈n/2⌉) + 5n, se 2 ≤ n
            | a,                        se 0 ≤ n < 2.
     

  MATERIAIS DE ESTUDO:

  • O primeiro resultado da aula de hoje foi o lema 7 deste material [1], e o segundo resultado foi semelhante ao lema 5 deste outro material [2].

  • No Cormen, a solução de recorrências é discutida no capítulo 4, seção 4.3 (na 3ª edição) ou 4.1 (na 2ª edição) – leitura recomendada!

• Aula 7 (2016-04-08, sexta-feira): o problema de ordenação; ordenação por "monte" ("heapsort") como melhoria da seleção direta; heap como estrutura eficiente para seleção de elemento máximo; descida de elemento após retirada do máximo; ordenação por sucessivas retiradas do máximo (heapsort); construção de heap em tempo O(n*lg n); construção de heap em tempo O(n).

  EXERCÍCIOS ESSENCIAIS:

  1. Em sala, nós acabamos não efetivamente escrevendo os algoritmos que discutimos. Escreva então cada um deles (alguns podem ser iterativos ou recursivos, você escolhe):

     • descer(v[1..n], t, i), sendo 1 ≤ i ≤ t ≤ n: realiza a descida do elemento v[i] caso necessário (isto é, caso ele seja menor que um dos filhos). Para a função, o heap começa no elemento v[1] e termina no elemento v[t] (o caso t < n é útil quando o heap não ocupa todo o vetor).

       A função pressupõe que, de toda a parte da "árvore" composta por v[i] e seus descendentes, v[i] é o único elemento que possivelmente não é maior ou igual aos seus filhos. Ao terminar, a função deve garantir que toda essa parte da árvore satisfaz a propriedade em questão (pai ≥ filhos).

     • heapificar(v[1..n], t), sendo 0 ≤ t ≤ n: transforma o trecho v[1..t] num heap (isto é, permuta os elementos de forma que "pai ≥ filhos" valha para todos os elementos).

       O seu algoritmo deve executar em tempo O(t) (você não precisa demonstrar esse fato, basta escrever o algoritmo adequadamente).

       Como discutido em sala, não é necessário chamar descer para as folhas. Nesse caso, se v[t] é o último elemento do heap, qual é o índice do último elemento que não é uma folha?

     • heapsort(v[1..n]), sendo 0 ≤ n: ordena o vetor segundo a ordem ≤, conforme descrito em sala.

  2. Qual é o tempo de execução do heapsort no melhor caso, assintoticamente falando?

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Apresente e prove um variante para o laço do algoritmo "descer" (se acima você escreveu um algoritmo recursivo, escreva agora uma versão iterativa). Esse variante deve ser logarítmico, isto é, deve permitir concluir que "descer" executa em tempo O(lg t).

  2. Prove que um heap de n ≥ 1 elementos pode ser construído em tempo O(n) (o argumento foi dado em sala; o que você deve fazer é escrevê-lo precisamente).

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje – cuidado para não ver respostas para os exercícios acima antes de tentar fazê-los!

  • No Cormen, o conteúdo da aula de hoje está no capítulo 6, do início até a seção 6.4 – leitura interessante! (Assim como a seção 6.5, se você não conhecia heaps como uma estrutura de utilidade por si mesma.)

• Aula 8 (2016-04-12, terça-feira): projeto de algoritmos por Divisão-e-Conquista; ordenação por entrelaçamento ("mergesort") como algoritmo de divisão-e-conquista para o problema de ordenação; função de entrelaçamento usando memória auxiliar; estimativa de tempo de execução via árvore de recursão; prova do tempo de execução do mergesort.

  OBSERVAÇÃO: pelos experimentos que fiz há alguns anos, comparando vários algoritmos de ordenação, o Mergesort (otimizado) era o algoritmo mais rápido, superando Heapsort e Quicksort. Isso está de acordo com os resultados teóricos e experimentais deste artigo (que, por sinal, é ótima leitura). E nas suas implementações, qual é o algoritmo mais rápido?

  OBSERVAÇÃO: em sala, foi prometida a apresentação posterior de um argumento via variantes de que o algoritmo de entrelaçamento escrito em sala executa em tempo linear. Em retrospecto, a solução é trivial, pois é suficiente mostrar que cada um dos 3 laços sucessivos do algoritmo executa em tempo linear. Em todo caso, é possível mostrar que o número de iterações do laço principal mais as do laço seguinte é limitado por "t", mostrando-se que o seguinte é um variante para o laço principal:

  (s-1 -e +1) + (f -d +1) - k
  

  sendo "k" o número de elementos que não são copiados no laço principal. Observe que "k" pode ser definido assim: se, das duas metades do vetor, aquela que possui o maior elemento é a esquerda, então "k" é o número dos elementos da metade esquerda que são maiores que todos os elementos da metade direita (o outro caso é simétrico). O variante acima resolve o problema pois é fácil mostrar que o segundo laço do algoritmo executa em "k" iterações, o que mostra que o número total de iterações dos dois laços é t = f-i+1.

  EXERCÍCIOS ESSENCIAIS:

  1. Usando as dicas apresentadas no final da aula, prove que f(t) = O(t*lg t), sendo:

     f(t) = | a,                             se t ≤ 1
            | f(⌈t/2⌉) + f(⌊t/2⌋) + c*t + b, se 1 < t.
     

  2. Escreva uma versão não-recursiva do mergesort, seguindo "de baixo para cima":

     1. Primeiro imagine os "n" elementos do vetor como "n" segmentos já individualmente ordenados.

     2. Em seguida, para cada par de segmentos adjacentes (o par (1,2), depois o par (3,4), depois (5,6), etc), faça o entrelaçamento desses segmentos. Observe que, ao final dessa rodada de entrelaçamentos, todos os novos segmentos do vetor (com a possível exceção do último segmento) estão ordenados e têm tamanho 2.

     3. Repita o passo anterior, gerando segmentos de tamanho 4. Depois, de novo, obtendo segmentos de tamanho 8. Repita o processo até que todo o vetor seja um único segmento ordenado.

     Tendo escrito o algoritmo, prove que ele executa em O(n*lg n).

     Observação: além de ser útil por si mesma (mostra como implementar o mergesort sem recursão), essa modificação do algoritmo é útil para implementar as melhoras mencionadas nos exercícios abaixo.

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Uma ineficiência evidente do Mergesort são as várias cópias feitas do vetor auxiliar para o vetor original. Escreva então uma variação do Mergesort na qual:

     1. O algoritmo seja iterativo, como no exercício anterior.

     2. A primeira rodada de entrelaçamentos acontece do vetor original para o vetor auxiliar e os elementos não são copiados de volta.

     3. A segunda rodada de entrelaçamentos acontece do vetor auxiliar para o vetor original.

     4. As demais rodadas de entrelaçamento alternem entre um sentido e outro, até que haja apenas um segmento ordenado. Nesse caso, se o segmento já estiver no vetor original, a ordenação está concluída; em caso contrário, basta copiá-lo para o vetor original. Observe que isso acontecerá então no máximo uma vez durante toda a execução do algoritmo, ao invés de "lg n" vezes.

  2. É interessante observar que mesmo o algoritmo anterior não tem um desempenho tão bom quanto seria desejável no caso em que o vetor de entrada está ordenado. A solução para isso é simples:

     1. No início, ao invés de fazer segmentos de tamanho 1, percorra o vetor e o "divida" em segmentos que já estão ordenados.

     2. Daí para a frente, proceda como antes (exercício anterior).

     Escreva esta versão do algoritmo, observando que ela executa em O(n) no melhor caso, mas que precisa de um segundo vetor auxiliar, para manter o registro do início e do fim dos segmentos ordenados.

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje – cuidado para não ver respostas para os exercícios acima antes de tentar fazê-los! Observe também que o algoritmo de entrelaçamento desse material é diferente (e mais otimizado) que aquele escrito em sala.

  • No Cormen, o conteúdo da aula de hoje está na seção 2.3 – leitura recomendada!

• Aula 9 (2016-04-15, sexta-feira):

  • Outra ideia de Divisão-e-Conquista para Ordenação: Particionamento.
  • Ordenação por Particionamento ("Quicksort").
  • 2 Estratégias de Particionamento: Algoritmos de Nico Lomuto e de "Tony" Hoare.
  • Tempo de Execução do Particionamento.
  • Tempo de Execução da Ordenação (via Árvore de Recursão), no Melhor e no Pior Casos.
  • Substituição da Chamada Recursiva de Cauda do Quicksort por um Laço.

  EXERCÍCIOS ESSENCIAIS:

  1. Escreva os algoritmos de particionamento de Lomuto e de Hoare, lembrando que o algoritmo de particionamento de Lomuto procede assim

       1                    i
     | x |   <=   |   >   | y      ?        |
       |                    |
       └─> pivô             └─> verificar se "y ≤ x" ou se "y > x"
     

     e o de Hoare assim

       1            e            d
     | x |   <=   |       ?        |   >   |
       |            |
       └─> pivô     └─> trocar v[e] e v[d] quando "v[e] > x" e "v[d] ≤ x".
     

     Dica: se você não tiver certeza sobre a corretude do seu algoritmo, pense em que invariantes deveriam valer em cada laço, e verifique se eles de fato estão válidos.

  2. Escreva uma relação de recorrência que defina o custo de pior caso do Quicksort, e prove que essa função é O(n²).

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Escreva a versão do Quicksort (discutida em sala) na qual a chamada recursiva de cauda é substituída por um laço, e na qual a chamada recursiva restante sempre é feita sobre o menor dos intervalos a serem ordenados. Em seguida, prove que nessa versão a pilha de chamadas recursivas simultâneas sempre tem no máximo ⌊lg(t) + 1⌋ chamadas, sendo "t" o tamanho (positivo) do intervalo de a ser ordenado pela chamada mais externa.

  2. Escreva um algoritmo de tri-particionamento que, ao invés de fazer isto

     |     <=     |     >    |
     

     faça isto

     |       <   |   =   |     >    |
     

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje – cuidado para não ver respostas para os exercícios acima antes de tentar fazê-los!

  • No Cormen, o conteúdo da aula de hoje está no capítulo 7 – leitura recomendada!

  • Este artigo fala sobre como otimizar o Quicksort na prática (veja também as referências lá citadas).

• Aula 10 (2016-04-19, terça-feira):

  • O Problema de Seleção
  • Consideração de Soluções para o Problema
  • Solução Baseada em Sucessivas Remoções em um Heap
  • O Algoritmo de Seleção de Hoare
  • Tempo de Execução do Algoritmo

  OBSERVAÇÃO: a versão inicial do algoritmo de Hoare que foi escrita em sala não possuía retorno (pois de fato tal retorno não é útil quando o algoritmo é utilizado dentro do Quicksort). Entretanto, a definição escrita em sala do problema de seleção solicitava o valor do elemento a ser encontrado, e por isso aqui está uma versão alternativa do algoritmo, que está de acordo com essa definição do problema:

  ================================================================================
  Algoritmo: sel_hoare
  Entrada:   vetor v[1..n], índices "i", "p", "f".
  Pré-cond.: 1 ≤ i ≤ p ≤ f ≤ n.
  Saída:     um elemento do tipo dos elementos de "v".
  Pós-cond.: (1) v[i..f] é uma permutação dos elementos inicialmente em v[i..f].
             (2) Os elementos em v[1..i-1] e em v[f+1..n] não são alterados.
             (3) ∀j ∈ {i..p-1}, v[j] ≤ v[p].
             (4) ∀j ∈ {p+1..f}, v[p] ≤ v[j].
  --------------------------------------------------------------------------------
  1. q := particionar (v[1..n], i, p, f)
  2. SE p = q
  3. | RETORNE v[p].
  4. SE p < q
  5. | RETORNE sel_hoare (v[1..n], i, p, q-1).
  6. RETORNE sel_hoare (v[1..n], q+1, p, f).
  ================================================================================
  

  EXERCÍCIOS ESSENCIAIS:

  1. Prove que o algoritmo acima satisfaz à especificação (pós-condições). Além disso: seria correto substituir ≤ por < na pós-condição 4? Por quê?

  2. O algoritmo de seleção acima é orientado a posições no vetor, isto é, a entrada "p" é a posição onde o elemento retornado estará após o particionamento. Escreva uma variação do algoritmo onde "p" é substituído por um índice "k" de 1 a "f-i+1" (ou de 0 a "f-i"), significando que o algoritmo deve retornar um k-ésimo menor elemento. Atenção aos índices repassados nas chamadas recursivas. No final das contas, qual versão você prefere?

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Escreva um algoritmo de seleção baseado em sucessivas remoções de um heap.

  2. Tente provar, conforme discutido em sala, que o algoritmo do item anterior executa em O(n + lg²(k)) para "k" suficientemente pequeno. Além disso, até que valor de "k" o algoritmo executa nessa complexidade de tempo?

  MATERIAIS DE ESTUDO:

  • As duas primeiras páginas deste material [1] cobrem o assunto da aula de hoje (a seção sobre o algoritmo linear de seleção é o assunto da próxima aula).

  • No Cormen, o conteúdo da aula de hoje está na seção 9.2 – leitura recomendada! (Assim como a seção 9.1.)

• Aula 11 (2016-04-22, sexta-feira):

  • Revisão do Algoritmo de Seleção O(n²) de Hoare.
  • Versão do Quicksort utilizando a Seleção de Hoare.
  • Intuição do Algoritmo de Seleção de Blum et al.: Escolha Cuidadosa do Pivô.
  • Escrita Detalhada do Algoritmo de Seleção de Blum et al..
  • Tempo de Execução do Algoritmo.

  EXERCÍCIOS ESSENCIAIS:

  1. Recapitule a árvore de recursão apresentada em sala para o algoritmo linear de seleção:

            Custo por Entrada  -------------  Custo por nível
               ____t____        -----------------  ϴ(t)
              /         \
           t/5        7t/10     -----------------  ϴ(9t/10)
          /   \       /    \
       t/25  7t/50  7t/50  49t/100   ------------  ϴ(t*(9/10)²)
       ...
     

     O algoritmo ainda executaria em tempo linear se os segmentos tivessem 7 elementos, ao invés de 5? E se tivessem 9 elementos? E 3? Argumente em cada um dos 3 casos.

  2. Escreva uma variação do algoritmo que executa em tempo linear mesmo se o vetor possuir elementos repetidos. Para tanto, você deve utilizar um algoritmo de tri-partição (veja os exercícios da aula sobre o Quicksort).

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Estendendo o primeiro exercício acima, prove que o algoritmo sempre executa em tempo linear quando os segmentos têm tamanho 2k+1, para todo k ≥ 2.

  2. Complementando o 2º exercício essencial acima, prove que o algoritmo de seleção equipado com tri-partição sempre executa em tempo linear.

  MATERIAIS DE ESTUDO:

  • Este material [1] apresenta uma discussão informal do algoritmo linear de seleção, e este material [2] apresenta uma prova detalhada do tempo de execução do algoritmo.

  • No Cormen, o conteúdo da aula de hoje está na seção 9.3 – leitura recomendada!

• Aula 12 (2016-04-26, terça-feira):

  • Árvores de Decisão para o Problema de Ordenação
  • O Limite Ω(n*lg n) para a Ordenação Baseada em Comparações
  • Ordenação por Contagem ("counting sort")

  EXERCÍCIOS ESSENCIAIS:

  1. Escreva o algoritmo de Ordenação por Contagem discutido em sala, que tem como entrada um inteiro "k", um vetor v[1..n] de números de "1" a "k", e vetores auxiliares c[1..k] e w[1..n]. O seu algoritmo deve executar em tempo O(n+k), ser estável (isto é, preservar a ordem relativa de elementos de mesma chave) e funcionar mesmo na presença de dados-satélite nos elementos do vetor.

  2. Escreva uma variação do algoritmo anterior, na qual, ao invés de "k", são recebidos inteiros (possivelmente negativos) "a" e "b" tais que a ≤ v[i] ≤ b para todo i ∈ [1..n]. Qual é o tempo de execução do algoritmo?

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Escreva uma variação da ordenação por contagem na qual, ao invés de um vetor w[1..n], é recebido um vetor d[1..k] de inteiros.

  2. E se o segundo vetor auxiliar for um vetor de bits, ainda é possível fazer o algoritmo funcionar?

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje – cuidado para não ver respostas para os exercícios acima antes de tentar fazê-los!

  • No Cormen, o conteúdo da aula de hoje está na seção 8.2 – leitura recomendada!

• Aula 13 (2016-04-29, sexta-feira):

  • Definição de um Problema de Seleção de Atividades
  • Proposição e Análise de Algoritmos para o Problema
  • Apresentação de uma Solução Gulosa

  EXERCÍCIOS ESSENCIAIS:

  1. Escreva um algoritmo O(n*lg n) que materialize a última estratégia de solução apresentada para o problema:

     1. Escolha a atividade que termina primeiro (ou uma delas, se houver mais de uma).

     2. Descarte as atividades que têm choque de horário com a atividade selecionada.

     3. Se ainda houver atividades selecionáveis, repita o processo.

     A entrada do algoritmo devem ser dois vetores c[1..n] e f[1..n], com os tempos de começo e fim das "n" atividades (c[i] < f[i] para todo "i"), e também um vetor s[1..n] de booleanos, onde deve ser armazenada a saída do algoritmo ("s[i] = V" significando se a tarefa "i" foi selecionada).

     Observação: seguindo o "Cormen", nós estipulamos que, se f[i] ≤ c[j], então as atividades "i" e "j" não têm choque de horário. Diferentemente do Cormen, porém, nós não supomos que as atividades já estão ordenadas pelo tempo de finalização.

     Observação: você não precisa escrever explicitamente a parte da ordenação, basta escrever uma linha como "ordene o vetor ...".

     Atenção: se você ordenar as tarefas, as posições delas nos vetores "c" e "f" podem não corresponder mais aos índices que elas têm inicialmente, e com relação aos quais deve ser escrita a saída no vetor "s"; como se resolve isso?

  2. Prove ou Refute: a estratégia que, ao invés de selecionar a atividade que termina primeiro, seleciona a atividade que começa por último, também sempre leva a soluções ótimas.

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Prove ou Refute: a seguinte estratégia também sempre leva a soluções ótimas:

     1. Seja "a" a atividade que começa primeiro (dentre aquelas ainda passíveis de serem escolhidas).

     2. Seja "C" o conjunto que possui "a" e as atividades (ainda passíveis de escolha) que têm choque de horário com "a".

     3. Para cada atividade i ∈ C, compute o número de atividades de C que têm choque de horário com "i".

     4. Dentre as atividades de "C", considere aquelas que com o menor número de choques de horário, e, dentre estas últimas, selecione uma com a menor duração possível.

     5. Descarte as atividades que têm choque de horário com a atividade selecionada e repita o processo até não restarem mais atividades selecionáveis.

  2. Que invariantes você usaria para provar que o algoritmo do primeiro exercício essencial está correto?

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje – cuidado para não ver respostas para os exercícios acima antes de tentar fazê-los!

  • No Cormen, o conteúdo da aula de hoje está na seção 16.1 – leitura recomendada!

• Aula 14 (2016-05-03, terça-feira):

  • Escrita do Algoritmo de Seleção de Atividades da Aula Anterior
  • Tempo de Execução desse Algoritmo
  • Definição e Exemplos para um Problema de Agendamento de Tarefas
  • Consideração de Estratégias para Resolver o Problema
  • Escrita de um Algoritmo O(n²) para o Problema
  • Enunciado de um Invariante de Laço para a Demonstração de Corretude do Algoritmo

  EXERCÍCIOS ESSENCIAIS:

  1. Prove o invariante enunciado em sala para o laço principal do algoritmo de agendamento de tarefas:

     "A solução parcial construída até então pode ser completada de forma a se tornar uma solução ótima."

  2. O algoritmo de agendamento de tarefas escrito em sala possui um trecho não muito eficiente: a descoberta de uma posição disponível para a tarefa "j" em questão é feita por meio de uma busca linear no vetor s[1..n], o que acaba levando tempo Θ(j) no pior caso. Como se pode acelerar essa parte do algoritmo?

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Prove que a sua solução para o exercício 2 acima leva o algoritmo a executar em o(n²) mesmo no pior caso.

  2. Escreva e prove invariantes significativos para o algoritmo de seleção de atividades escrito no início da aula.

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje, incluindo a parte que ficou faltando e que veremos na próxima aula (prova do invariante), mas ele introduz de forma precisa uma quantidade significativa de notação que nós não utilizaremos (por estarmos argumentando em nível menos formal).

  • No Cormen, o problema de Agendamento de Tarefas é estudado na seção 16.5, mas usando "matróides", que é um conceito que não vemos na nossa disciplina. O algoritmo apresentado em sala é a solução alternativa discutida no Problema 16-4.

• Aula 15 (2016-05-06, sexta-feira):

  • Demonstração de Corretude do Algoritmo O(n²) de Agendamento de Tarefas
  • Ideia de uma Versão mais Rápida do Algoritmo, pela Manutenção de uma certa Estrutura do Vetor

  EXERCÍCIOS ESSENCIAIS:

  1. Certifique-se de que você consegue reproduzir a demonstração apresentada em sala. A demonstração permanece válida se o algoritmo não garantir a escolha da posição livre mais à direita até o deadline d[j]? E com relação à escolha da posição livre mais à direita até o fim o fim do vetor: ela é essencial?

  2. Em sala, nós adiantamos que a versão mais rápida do algoritmo seria implementada por meio de uma estrutura de dados que mantenha o registro de conjuntos disjuntos. Tente então criar uma estrutura de dados com as seguintes operações:

     • criar_conj(x): cria um conjunto unitário com o elemento "x".

     • enc_repr(x): encontra e retorna o representante do conjunto ao qual "x" pertence. Todo conjunto possui um representante, que é um dos seus elementos. O representante de um certo conjunto não deve mudar enquanto ele possuir os mesmos elementos.

     • unir_conj(x,y): une os 2 conjuntos aos quais "x" e "y" pertencem.

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Com relação à estrutura da sua solução para o segundo exercício acima, se ao todo forem feitas "m" chamadas às 3 funções em questão, das quais "n" sejam a "criar_conj", qual é o tempo de execução total dessas chamadas?

  2. Escreva uma variação do algoritmo escrito em sala que use uma estrutura de dados como a descrita acima. Como explicado em sala, a ideia é usar essa estrutura para manter o vetor particionado em segmentos da forma

       i               j
      ------------------- 
     | 0 |  ... != 0 ... |
      ------------------- 
     

  MATERIAIS DE ESTUDO: os mesmos da aula anterior.

• Aula 16 (2016-05-07, sábado – aula extra):

  • Teorema Mestre para Solução Assintótica de Recorrências.
  • Algoritmo de Karatsuba para a Multiplicação de Inteiros Grandes.
  • Algoritmo de Strassen para a Multiplicação de Matrizes Grandes.

  OBSERVAÇÃO: em sala, eu disse que, pelo nome, Karatsuba deveria ser japonês, mas na verdade ele era russo!

  EXERCÍCIOS ESSENCIAIS:

  1. Exercício 4 da Lista 1 do Rudini.

  2. Exercício 13 da Lista 1 do Rudini.

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Exercício 7 da Lista 1 do Rudini.

  2. Exercício 9 da Lista 1 do Rudini.

  MATERIAIS DE ESTUDO:

  • As páginas 268–273 deste capítulo [1] contêm todo o conteúdo da aula de hoje (este livro está na bibliografia).

  • No Cormen, o Teorema Mestre é apresentado na seção 4.5 (3ª edição) ou 4.3 (2ª edição), mas veja também a versão mais geral do material acima. O algoritmo de Strassen é apresentado na seção 4.2 (3ª edição) ou 28.2 (2ª edição).

• Aula 17 (2016-05-10, terça-feira):

  • Definição das Operações sobre uma Estrutura de Conjuntos Disjuntos
  • Consideração de Ideias para Implementação da Estrutura
  • Estrutura de Floresta para a Manutenção de Conjuntos Disjuntos
  • Heurísticas: União Ponderada e Compressão de Caminho

  COMPLEMENTO: eis uma versão O(n*lg n) do Algoritmo de Agendamento de Tarefas que usa Conjuntos Disjuntos:

  ================================================================================
  agendam_tarefas (d[1..n], w[1..n], s[1..n])
  --------------------------------------------------------------------------------
  01. constr_conj(0) , mín[0] := 0
  02. PARA j DE 1 A n
  03. | i[j] := j , constr_conj(j) , mín[j] := j
  04. Ordene w[1..n] segundo ≥ e faça em d[1..n] e i[1..n] as permut. corresp.
  05. PARA j DE 1 A n
  06. | k := mín[ enc_repr( d[j] ) ]
  07. | SE k = 0
  08. | | k := mín [ enc_repr(n) ]
  09. | s[k] := i[j] , m := mín[ enc_repr(k-1) ]
  10. | unir_conj (k-1, k) , mín[ enc_repr(k) ] := m
  ================================================================================
  

  Explicação:

  • O algoritmo utiliza conjuntos disjuntos para particionar o vetor em segmentos da forma

      i-1  i               j  j+1
    -----------------------------------
     ... | 0 |  ... != 0 ... | 0 | ...
    -----------------------------------
    

    Em cada momento, cada conjunto contém os índices "i, i+1, …, j" que formam um segmento como o ilustrado acima.

  • Como comentado em sala, no início do algoritmo cada segmento contém apenas um índice, o que corresponde à criação de conjuntos unitários nas linhas 1 e 3 do algoritmo.

  • Quando, na linha 9, uma tarefa i[j] é inserida em s[k], é necessário realizar a união do conjunto que começava na posição "k" com aquele que terminava na posição k-1, e isso é feito na linha 10.

  • Como não existe a garantia de que o representante de cada conjunto será sempre o seu elemento de menor valor, o algoritmo possui um vetor adicional "mín", que armazena a informação do menor elemento para cada representante de conjunto (e não para cada elemento do conjunto, assim economizamos tempo na atualização dessas informações).

  • No início do algoritmo, quando cada conjunto possui apenas um elemento, esse mesmo elemento é também o menor elemento do conjunto (linha 3). Além disso, no momento da inserção de uma tarefa i[j], a posição da inserção é o menor elemento do conjunto ao qual d[j] pertence (linha 6), exceto se esse conjunto contiver também o índice 0 (linha 7), o que então indica que todas as posições até d[j] já estão ocupadas; nesse caso, insere-se a tarefa no início do segmento da posição "n" (linha 8).

  EXERCÍCIOS ESSENCIAIS:

  1. Certifique-se de que você entende o algoritmo acima. Em particular, execute o algoritmo para a mesma instância utilizada na explicação do algoritmo O(n²) em sala de aula. Na simulação dessa execução, registre também as árvores de conjuntos disjuntos, e os vetores pai[1..n] e h[1..n].

  2. Prove que o algoritmo acima executa em tempo O(n*lg n), tomando como base o fato de que, para a estrutura de floresta de conjuntos disjuntos, qualquer sequência válida de "m" chamadas às funções "constr_conj", "enc_repr" e "unir_conj", das quais "n" sejam a "criar_conj", executa em tempo O(m*lg n).

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO: (as respostas estão no material [1] desta aula)

  1. Prove que, numa floresta de conjuntos disjuntos, toda árvore cuja raiz é um nó "r" tem pelo menos 2^h[r] nós.

  2. Utilizando o resultado do item anterior, argumente que, numa sequência de chamadas às funções de conjuntos disjuntos, enquanto "criar_conj" tiver sido chamada no máximo "n" vezes, então, ∀x, h[x] ≤ ⌊lg n⌋.

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre a parte da aula de hoje relativa à Floresta de Conjuntos Disjuntos, apresentando os códigos dos algoritmos e a prova do tempo de execução O(m*lg n). Este material [2] explica melhor o sentido das funções para conjuntos disjuntos, além de mostrar como elas podem ser implementadas por listas encadeadas e provar o tempo de execução O(m + n*lg n).

  • No Cormen, a Floresta de Conjuntos Disjuntos é apresentada no capítulo 23 (sugiro ler do início até a seção 3; veja também os exercícios 21.4-(2 e 4)). A ideia de aplicar essa estrutura ao algoritmo de Agendamento de Tarefas é apresentada no Problema 16-4, item b.

• Aula 18 (2016-05-13, sexta-feira):

  • O Problema da Árvore Geradora Mínima
  • Ideias de Solução do Problema
  • Corretude da Estratégia de Kruskal
  • Implementação do Algoritmo de Kruskal usando Conjuntos Disjuntos:

    =================================================================
    Kruskal ( G = (V,E) , w )
    -----------------------------------------------------------------
    01. Ordene as arestas de G pelo peso, segundo ≤.
    02. PARA cada v ∈ V
    03. | criar_conj(v)
    04. A := ∅
    05. ENQUANTO |A| != |V| - 1
    06. | Seja {u,v} a "próxima aresta" (segundo a ordem da linha 1).
    07. | SE enc_repr(u) != enc_repr(v)
    08. | | A := A U { {u,v} }
    09. | | unir_conj(u,v)
    10. RETORNE A.
    =================================================================
    

  EXERCÍCIOS ESSENCIAIS:

  1. Argumente que o algoritmo de Kruskal executa em tempo O(|E|*lg |V|).

  2. Se os pesos das arestas forem números naturais de 1 a "k", pode-se escrever uma variação do algoritmo de Kruskal que executa em que complexidade de tempo? Para que valores de "k" essa variação é vantajosa?

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Prove que sempre existe uma árvore geradora mínima que possui a segunda aresta mais leve do grafo. (Observe que essa questão é puramente matemática, e que o algoritmo de Kruskal não é sequer mencionado!)

  2. Considere a variação do algoritmo de Kruskal na qual, depois de se selecionar a aresta mais leve, ao invés de sempre se (tentar) escolher a próxima aresta mais leve dentre todas as restantes, se seleciona a aresta mais leve apenas dentre aquelas que têm exatamente uma extremidade em comum com arestas já escolhidas. Essa estratégia sempre leva a soluções ótimas? Prove ou refute.

  MATERIAIS DE ESTUDO:

  • Este material [1] apresenta definições básicas sobre grafos.

  • Este material [2] apresenta uma versão de alto nível do algoritmo de Kruskal e prova a corretude do algoritmo.

  • No Cormen, o algoritmo de Kruskal é apresentado na seção 23.2.

• 2016-05-17, terça-feira): AP1.

• Aula 19 (2016-05-20, sexta-feira):

  • Tira-dúvidas e Correção das Questões 1 e 2 da AP1 (as demais serão corrigidas na monitoria).

• Aula 20 (2016-05-24, terça-feira):

  • O Problema de Caminhos Mínimos com Fonte Única em Grafos Direcionados Ponderados.
  • Consideração de Soluções para o Problema.
  • Solução 1: Variação da Busca em Profundidade, Revisitando Vértices quando Necessário.
  • Solução 2: Estratégia do Algoritmo de Dijkstra (atualiza estimativas de distância mas não revisita vértices)
  • Corretude desta Última Estratégia.

  EXERCÍCIOS ESSENCIAIS:

  1. A última estratégia discutida em sala é gulosa? Por quê?

  2. Escreva uma versão do algoritmo de Dijkstra (isto é, da última estratégia discutida em sala) que use apenas vetores para resolver o problema. Argumente que o algoritmo executa em tempo O(|V|²). (O material [1] abaixo apresenta uma solução, mas escreva a sua primeiro.)

  3. Escreva agora uma versão do algoritmo que utilize um monte ("heap"). Argumente que o algoritmo executa em tempo O( (|V| + |E|)*lg |V| ). (Resposta no Cormen, §24.3.)

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. O algoritmo de Dijkstra funciona corretamente mesmo caso o grafo possua circuitos (ciclos orientados). Entretanto, caso já se saiba que o grafo de entrada não tem circuitos, você consegue escrever um algoritmo mais rápido? Qual é o tempo de execução do novo algoritmo?

  2. O algoritmo de Dijkstra funciona corretamente mesmo quando os pesos das arestas são números reais. Entretanto, caso já se saiba que os pesos do grafo são números naturais, você consegue escrever um algoritmo que faça uso útil desse fato? Qual é o tempo de execução do novo algoritmo?

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje.

  • No Cormen, o Algoritmo de Dijkstra é apresentado na seção 24.3.

• Aula 21 (2016-05-27, sexta-feira):

  • Codificações de Tamanho Fixo e de Tamanho Variável para Arquivos de Texto.
  • Códigos Livres de Prefixo e Árvores Binárias.
  • O Problema da Obtenção de Códigos Livres-de-Prefixo Ótimos.
  • Ideias de Solução para o Problema.
  • O Algoritmo de Huffman e uma Implementação O(n*lg n) via Heap.
  • Corretude do Algoritmo de Huffman.

  EXERCÍCIOS ESSENCIAIS:

  1. Seja (C,o) uma entrada para o problema – "C" sendo um conjunto de pelo menos 2 caracteres e "o" o vetor de ocorrências – e sejam "a" e "b" os caracteres de menores ocorrências dessa entrada. Prove então que existe uma solução (árvore) ótima T na qual "a" e "b" são irmãos e ocorrem no nível mais profundo da árvore.

  2. Mostre como o Algoritmo de Huffman pode ser implementado de forma a executar em tempo O(n) caso o vetor que dá as ocorrências dos "n" caracteres de entrada já esteja em ordem crescente. Dica: use duas filas!

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Sejam "(C,o)", "a" e "b" como definidos no primeiro exercício acima. Além disso, seja (C',o') a variação da entrada (C,o) na qual os caracteres "a" e "b" são substituídos por um novo caractere "ab" tal que o'[ab] = o[a] + o[b]. Prove então que:

     1. Se "T" é uma solução (árvore) para (C,o), então existe uma solução T' para (C',o') tal que custo(T') ≤ custo(T) - o[a] - o[b].

     2. Para toda solução T' para (C',o'), existe uma solução T para (C,o) tal que custo(T') = custo(T) - o[a] - o[b].

  2. Utilize o resultado do exercício anterior para provar que, se T' é uma solução ótima para (C',o'), então é fácil obter uma solução T ótima para (C,o) e tal que custo(T') = custo(T) - o[a] - o[b].

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje.

  • No Cormen, o Algoritmo de Huffman é apresentado na seção 16.3.

• Aula 22 (2016-05-31, terça-feira):

  • O Problema do Corte de Haste.
  • Ideias de Solução para o Problema.
  • Observação de que a Estratégia Gulosa (maior razão preço/tamanho) nem Sempre Funciona.
  • Alternativa: Reaproveitar Cálculos Resolvendo Instâncias da Menor à Maior (Programação Dinâmica).

  EXERCÍCIOS ESSENCIAIS:

  1. Utilizando a técnica da Programação Dinâmica, escreva um programa eficiente para calcular o n-ésimo número de Fibonacci:

     fib(n) = | n,                   se n ∈ {0,1}
              | fib(n-1) + fib(n-2), se n ≥ 2
     

  2. Como comentado em sala, a estratégia de resolver instâncias das pequenas para as grandes, reaproveitando os cálculos sempre que possível, tem como objetivo evitar a repetição de cálculos e o consequente impacto no tempo de execução do algoritmo.

     Para avaliar esse impacto no caso do problema acima, escreva uma variação recursiva do algoritmo produzido em sala, sem se preocupar com repetição de cálculos. Em seguida, prove que o seu algoritmo executa em Ω(2^n).

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Escreva um algoritmo O(n) para o problema da linha de montagem com duas linhas de montagem de "n" estações cada uma. (Esse problema é descrito na seção 15.1 da 2ª edição do Cormen, acessível pela hiper-ligação anterior.)

  2. Resolva a questão 2 da lista 2 do Rudini.

  MATERIAIS DE ESTUDO:

  • Este material [1] não trata do Problema do Corte de Haste, mas soluciona os exercícios sobre Fibonacci e Linhas de Montagem acima.

  • No Cormen, o Problema do Corte de Haste é apresentado na seção 15.1 da 3ª edição.

• Aula 23 (2016-06-03, sexta-feira):

  • O Problema da Multiplicação de Cadeia de Matrizes
  • Ideias de Solução para o Problema
  • Observação do Não Funcionamento da Estratégia Gulosa
  • Algoritmo de Programação Dinâmica

  EXERCÍCIOS ESSENCIAIS:

  1. Simule a execução do algoritmo para as entradas abaixo, e avalie também se a estratégia gulosa (de sucessivamente colocar parênteses em torno da maior dimensão da entrada) leva ou não à solução ótima:

     1. 30x35, 35x15, 15x5, 5x10, 10x20, 20x25.

     2. 50x40, 40x30, 30x20, 20x10.

  2. O algoritmo escrito em sala retorna tanto o custo de uma solução ótima como a solução propriamente dita, na forma de uma matriz "P" tal que P[i,j] é o índice "k" tal que a parentetização ótima da entrada M_i,..., M_j é (M_i,..., M_k)(M_k+1,..., M_j).

     Assim sendo, escreva um algoritmo que receba (a) matrizes M₁,..., M_n e (b) a matriz P[1..n-1,2..n] descrita acima, e que retorne o produto das "n" matrizes, computado segundo a parentetização descrita em "P".

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Prove que o algoritmo descrito em sala executa em tempo Ω(n³).

  2. Escreva um algoritmo recursivo para o problema, mas que também utilize uma matriz auxiliar para evitar computar uma solução mais de uma vez.

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje.

  • No Cormen, o Problema da Multiplicação de Cadeia de Matrizes é apresentado na seção 15.2.

• Aula 24 (2016-06-04, sábado – aula extra):

  • O Problema da Subsequência Comum Máxima.
  • Ideias de Solução para o Problema.
  • Desenvolvimento de uma Solução via Programação Dinâmica.

  EXERCÍCIOS ESSENCIAIS:

  1. O algoritmo desenvolvido em sala retorna como resposta para uma instância ( X[1..m] , Y[1..n] ) o valor M[m,n] da matriz "M" tal que

     M[i,j] = | 0,                          se i = 0 ou j = 0
              | 1 + M[i-1, j-1],            se i,j > 0 e X[i] = Y[j]
              | máx{ M[i,j-1] , M[i-1,j] }, se i,j > 0 e X[i] != Y[j].
     

     Escreva um algoritmo que receba as sequências "X" e "Y" e a matriz M[1..m][1..n] e que retorne uma subsequência comum máxima "Z" entre "X" e "Y".

  2. Escreva um algoritmo recursivo O(m*n) para resolver o problema da aula, utilizando uma matriz para não repetir cálculos.

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Utilizando a definição de subsequência apresentada em sala, demonstre matematicamente que:

     1. Se X[m] = Y[n], então o tamanho de uma subsequência comum máxima (SCM) de X e Y é 1 mais o tamanho de uma SCM de X[1..m-1] e Y[1..n-1].

     2. Se X[m] != Y[n], então o tamanho de uma SCM de X e Y ou é o tamanho de uma SCM de X[1..m] e Y[1..n-1] ou é o tamanho de uma SCM de X[1..m-1] e Y[1..n].

  2. Conforme comentado em sala, se apenas o tamanho da subsequência comum máxima é desejado, então é possível escrever uma versão do algoritmo que utiliza quantidade linear de memória, pois, ao invés de utilizar uma matriz inteira, basta armazenar a linha anterior da matriz.

     Assim sendo, escreva uma variação do algoritmo que utilize O(mín{m,n}) de memória e que continue executando em tempo O(m*n).

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje.

  • No Cormen, o Problema da Subsequência Comum Máxima é apresentado na seção 15.4.

• Aula 25 (2016-06-07, terça-feira):

  • O Problema da Árvore de Busca Ótima.
  • Ideias de Solução para o Problema.
  • Verificação do não Funcionamento da Estratégia Gulosa (nós de maior probabilidade em cima na árvore).
  • Algoritmo O(n³) de Programação Dinâmica.

  EXERCÍCIOS ESSENCIAIS:

  1. Prove que o algoritmo escrito em sala executa em tempo Ω(n³).

  2. Generalize o algoritmo escrito em sala para lidar com o caso em que se recebe não apenas a probabilidade p[i] de uma consulta pela i-ésima chave, mas também a probabilidade q[i] de uma consulta por uma chave maior que a i-ésima e menor que a (i+1)-ésima. Por exemplo, na árvore

       b
      /
     a
     

     uma consulta pode buscar ou a chave "a", ou a chave "b", ou uma chave menor que "a", ou uma chave entre "a" e "b", ou uma chave maior que "b"; as duas primeiras destas consultas têm probabilidade p[1] e p[2] e custo 2 e 1, enquanto as 3 últimas têm probabilidade q[0], q[1] e q[2] e custo 3, 3 e 2, respectivamente.

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Faça o exercício 4 da lista 2 do Rudini, que é também o problema 15-2 do Cormen 3ª edição.

  2. As páginas 4–6 do artigo original do Knuth (de 1971!) explicam como diminuir o tempo do algoritmo dado em sala para O(n²). Esse é também o exercício 15.5-4 do Cormen.

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje.

  • No Cormen, o Problema da Árvore de Busca Ótima é apresentado na seção 15.5.

• Aula 26 (2016-06-10, sexta-feira):

  • Veja aqui e aqui os materiais desta aula dada pelo Thiago Marcilon.

• Aula 27 (2016-06-14, terça-feira):

  • O Problema da Mochila 0-1.
  • Ideias de Solução para o Problema.
  • Verificação do não Funcionamento da Estratégia Gulosa (incluir logo itens de maior valor ou de maior razão valor/peso).
  • Algoritmo O(W*n) de Programação Dinâmica ("n" itens, mochila de capacidade "W").

  EXERCÍCIOS ESSENCIAIS:

  1. Escreva um algoritmo que receba como entrada a matriz de escolhas ME[1..n, 0..c] retornada pelo algoritmo escrito em sala, e que então retorne um vetor s[1..n] que informe, para cada objeto "i", se ele foi incluído ou não na solução (s[i] = 1 ou s[i] = 0, respectivamente).

  2. Resolva a variação do problema da mochila 0-1 na qual cada objeto pode ser selecionado qualquer número de vezes.

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Exercício 1.c do material [1] abaixo.

  2. Exercício 1.d do material [1] abaixo.

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o assunto da aula de hoje.

  • No Cormen, o Problema da Mochila 0-1 é apresentado na seção 16.2.

• Aula 28 (2016-06-17, sexta-feira):

  • Introdução Informal à Complexidade de Problemas:

    1. Problemas Polinomiais e Problemas de Complexidade Desconhecida

    2. Verificação em Tempo Polinomial e em Tempo Não-Polinomial

    3. Redução Polinomial entre Problemas

• Aula 29 (2016-06-21, terça-feira):

  • Problemas Abstratos, Concretos e de Decisão.
  • A Classe P de Complexidade de Problemas.
  • Linguagens x Problemas de Decisão.
  • Algoritmos de "Solução" (Decisão) e de Verificação.
  • A Classe NP de Complexidade de Problemas.

  EXERCÍCIOS ESSENCIAIS:

  1. Tomando como base as definições e exemplos das notas de aula, argumente que a versão de decisão do problema de Cobertura por Vértices está na classe NP. Definição do problema:

     1. Dado um grafo simples G = (V,E), uma cobertura é subconjunto C de V tal que toda aresta de G possui pelo menos uma extremidade em C.

     2. A versão de decisão do problema de Cobertura por Vértices consiste em, dado um grafo G e um número k, descobrir se existe uma cobertura de G com "k" vértices.

  2. A versão de otimização do problema de Cobertura por Vértices consiste em, dado um grafo G, descobrir uma cobertura de tamanho mínimo de G. Suponha agora que você possui um algoritmo A(G,k) para resolver a versão de decisão descrita anteriormente; escreva então um algoritmo que receba um grafo G e que responda o tamanho de uma cobertura mínima de G. (Dica: "não é necessário olhar de um em um…")

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Se o algoritmo "A" do exercício 2 acima executar em tempo O(n) para um grafo de "n" vértices, então o seu algoritmo para a versão de otimização do problema executa em quanto tempo? E se "A" executar em O(n^k)?

  2. Faça o Exercício 7 da nota de aula [2] abaixo.

  MATERIAIS DE ESTUDO:

  • Este material [1] cobre o que estudamos sobre a classe P, e este [2] o que estudamos sobre a classe NP.

  • No Cormen, as classes P e NP são apresentadas nas seções 34.1 e 34.2.

• Aula 30 (2016-06-24, sexta-feira):

  • Prova de que P ⊆ NP.
  • Definição de Redução Polinomial e da Classe NP-Completa (NPC).
  • Definição do Problema SAT-Circuitos e Prova de que SAT-Circuitos ∈ NP.
  • Definição do Problema SAT e Prova de que SAT ∈ NPC.

  EXERCÍCIOS ESSENCIAIS:

  1. Prove em detalhes que, dados problemas P1, P2 e P3, se P1 ≤_P P2 e P2 ≤_P P3, então P1 ≤_P P3. (Resposta no item 3 do material [1] abaixo.)

  2. Como vimos em sala, a ideia básica da redução de SAT-Circuitos a SAT é, para cada porta lógica do circuito, escrever um trecho de fórmula correspondente, e então compor esses trechos analogamente ao circuito. Nós argumentamos, porém, que uma aplicação direta dessa estratégia poderia levar a fórmulas muito maiores que os circuitos originais, devido à possibilidade de a saída de uma porta lógica ser utilizada como entrada de várias outras portas lógicas.

     Defina então um tipo de circuito de "n" portas lógicas que levaria uma aplicação direta da estratégia acima a produzir uma fórmula de tamanho não polinomial em "n". (Resposta no item 4 do material [2] abaixo.)

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Prove ou Refute: se P1 ∈ NP e P1 ∉ P, então todo problema P2 NP-difícil não está em P.

  2. O Problema da Mochila 0-1 está em P? E em NP? As respostas podem ser "sim", "não" e "não é possível saber apenas com o que vimos na disciplina"; para as duas primeiras respostas, apresente uma prova; no caso da última resposta, argumente a razão.

  MATERIAIS DE ESTUDO:

  • Estes materiais [1] [2] [3] cobrem o assunto da aula de hoje.

  • No Cormen, a prova de que P ⊆ NP está na seção 34.2, a classe NPC e o problema SAT-Circuitos na seção 34.3, e a redução de SAT-Circuitos a SAT na seção 34.4.

• Aula 31 (2016-06-25, sábado):

  • Fórmulas 3-CNF e o Problema 3-SAT.
  • Prova de que 3-SAT ∈ NP.
  • Prova de que 3-SAT é NP-difícil (redução a partir de SAT-Circuitos).

  EXERCÍCIOS ESSENCIAIS:

  1. Utilizando o algoritmo da redução de SAT a 3-SAT, escreva uma fórmula 3-CNF equivalente à fórmula (A ∧ (B → ¬ C)) ↔ ¬ A.

  2. Uma fórmula está na Forma Normal Disjuntiva (DNF) se ela é uma disjunção de conjunções (ao invés de uma conjunção de disjunções, como na CNF). Assim sendo, prove ou refute: o problema de determinar se uma fórmula DNF é ou não satisfatível está em P.

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Mostre que, se SAT ∈ P, então também é polinomial o problema de encontrar (quando existir) uma atribuição de valores-verdade que satisfaça uma certa fórmula F dada como entrada.

  2. Prove que 2-SAT ∈ P.

  MATERIAIS DE ESTUDO:

  • Exemplo de material online contendo a redução de SAT a 3-SAT.

  • No Cormen, a redução de SAT a 3-SAT está na seção 34.4.

• Aula 32 (2016-06-28, terça-feira):

  • Recapitulação sobre 3-SAT.
  • Versão de Decisão do Problema CLIQUE.
  • Prova de que CLIQUE ∈ NP.
  • Prova de que CLIQUE é NP-difícil.

  EXERCÍCIOS ESSENCIAIS:

  1. Certifique-se de que você entendeu a redução apresentada em sala, escrevendo você mesmo e em detalhes a redução, o que inclui a construção de (G,k) a partir da entrada φ de 3-SAT, e a prova de que G possui possui uma clique de k vértices sse φ é satisfatível.

  2. Prove que CONJUNTO INDEPENDENTE é NP-completo. Definições:

     1. Dado um grafo G = (V,E), um Conjunto Independente é um conjunto C ⊆ V tal que, para quaisquer x,y ∈ C, x != y → {x,y} ∉ E.

     2. O problema de decisão CONJUNTO INDEPENDENTE consiste em, dados um grafo G = (V,E) e um número natural k, responder se G possui um conjunto independente de k vértices.

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Prove que COBERTURA POR VÉRTICES é NP-completo.

  2. Uma coloração própria de um grafo simples é uma atribuição de cores aos vértices do grafo, de forma que vértices adjacentes nunca possuam a mesma cor. (Observe que, se um grafo possui "n" vértices, então sempre existe uma coloração própria desse grafo com "n" cores; a questão interessante normalmente é descobrir a menor quantidade de cores possível para se colorir propriamente um dado grafo.)

     Seja então 2-CORES o problema de, dado um grafo G, descobrir se G possui uma coloração própria que utilize apenas 2 cores. Assim sendo, escolha e realize uma destas tarefas (atente para o fato de que, se uma delas é possível, então a outra é provavelmente muito difícil ou mesmo impossível):

     1. Prove que 2-CORES ∈ P.

     2. Prove que 2-CORES é NP-difícil.

  MATERIAIS DE ESTUDO:

  • Este material online contém a redução de 3-SAT a CLIQUE e também as dos exercícios acima.

  • No Cormen, a redução de 3-SAT a CLIQUE e aquela para COBERTURA POR VÉRTICES estão na seção 34.5.

• 2016-07-01, sexta-feira: AP2, parte 1.

• 2016-07-05, terça-feira: AP2, parte 2.

• Aula 33 (2016-07-08, sexta-feira):

  • Definição do Problema de Soma de Subconjunto (SS).
  • Prova de que SS ∈ NP.
  • Prova de que SS é NP-difícil.

  EXERCÍCIOS ESSENCIAIS:

  1. Qual é a entrada de Soma de Subconjunto correspondente à entrada "(A ou B ou ~C) e (B ou ~A ou C) e (~C ou D ou ~A)" para 3-SAT?

  2. Faça o exercício 7 da lista 3 do Rudini (exceto item "c").

  EXERCÍCIOS PARA PÓS-GRADUAÇÃO:

  1. Seja CONT-SAT o problema

     "Dadas uma fórmula booleana F qualquer e um natural "k", é verdade que há exatamente "k" valorações (das variáveis de F) que tornam a fórmula verdadeira?" .

     Com base na sua compreensão do conteúdo, você acredita que CONT-SAT ∈ NP ou que CONT-SAT ∉ NP?

  2. O problema do item anterior é NP-difícil?

  MATERIAIS DE ESTUDO:

  • No Cormen, a redução de 3-SAT a Soma de Subconjunto está na seção 34.5.