Construção e Análise de Algoritmos (CAnA)

• Turma: CK0019 – T02 – 2014.2
• Professor: Pablo
• Curso: Matemática Industrial
• Horário: seg/qua/sex 08-10h
• Local: bloco 952 (ao lado do 910), sala 2.
• Menu: informações gerais, avisos, regras, bibliografia, plano de atividades, e dados das aulas.

Informações gerais

Caro aluno, na regulamentação desta disciplina você pode acessar informações básicas sobre ela, incluindo objetivos e ementa. Além disso, como esta é a primeira vez em que eu ministro esta disciplina, e como eu estou tomando como referência a disciplina ministrada pelo professor Rudini, eu sugiro que você, caso deseje, consulte a página da disciplina dele para encontrar materiais adicionais, incluindo listas de exercícios e referências para páginas de outros professores.

A minha sugestão para a obtenção de um bom desempenho na disciplina é participar das aulas, estudar o conteúdo, fazer os exercícios e tirar as dúvidas no tempo certo, isto é, aula-a-aula. Caso você possua uma dúvida no horário da aula, o ideal é tirá-la na própria ocasião, para que os demais alunos também se beneficiem das explicações. Entretanto, caso necessário, você também pode me contactar fora do horário de aula.

Avisos

• Passe no meu gabinete para explicar as suas respostas na AF: isso facilita a correção, pode tirar dúvidas, etc.

• Aqui estão as notas da 1ª metade da AP3; as notas completas serão divulgadas neste fim de semana.

• As respostas da AP3 estão na página.

• Veja as regras para solicitação de segunda chamada.

• Esta página está em contínua construção. Por favor, entre em contato comigo caso você precise de alguma informação adicional, ou caso acredite ter encontrado um erro aqui. Obrigado!

Plano de atividades

Abaixo está o plano para as atividades da disciplina, mas atenção: trata-se apenas de uma estimativa. Como esta é a primeira vez em que eu ministro esta disciplina, o que de fato realizaremos pode ser consideravelmente diferente.

Aulas: conteúdos e exercícios

• Aula 1 (2014-07-28, segunda-feira): apresentação da disciplina; problema de ordenação de vetores; ordenação por seleção (direta).

  Exercícios:

  1. Nós vimos que o algoritmo de ordenação por seleção executa um número de passos proporcional a n² mesmo no melhor caso, e então consideramos como alternativa a estratégia de ordenação por inserção. Nesse caso:

     1. Materialize a estratégia de ordenação por inserção na forma de um algoritmo.

     2. Conte quantas vezes cada instrução do algoritmo é executada no melhor caso e no pior caso.

     3. Como você argumentaria que o algoritmo que você escreveu está correto?

  2. A versão mais simples do algoritmo de ordenação por inserção realiza, em cada iteração, uma busca linear no trecho já ordenado do vetor, para descobrir a posição correta do elemento em consideração. Escreva então uma versão do algoritmo em que essa busca linear é substituída por uma busca binária. Além disso, responda: o novo algoritmo deixa de ser quadrático no pior caso?

• Aula 2 (2014-07-30, quarta-feira): ordenação por inserção: algoritmo e tempo de execução (melhor e pior casos); conceito e estratégia de prova de um invariante de laço; invariante do laço externo do algoritmo de ordenação por inserção; busca linear: algoritmo, prova de um invariante de laço e demonstração verbal da correção parcial do algoritmo (isto é, correção supondo a terminação).

  Exercícios:

  1. Argumente que o algoritmo de busca linear sempre termina, e então demonstre, utilizando o lema provado em sala, que ele sempre retorna uma resposta correta.

  2. Calcule o tempo de execução do algoritmo de busca linear no melhor e no pior casos.

  3. Supondo que um dado vetor de números está sabidamente ordenado, é possível realizar uma busca em menos que O(n) no pior caso? Se sim, escreva um algoritmo que o faz.

• Aula 3 (2014-08-01, sexta-feira) (nota de aula): variante de laço (conceito); prova de um variante para o laço do algoritmo de busca linear; conceitos de correção parcial, terminação e correção total; prova da correção total do algoritmo de busca linear.

  Material para leitura adicional:

  • A Wikipédia em inglês possui artigos muito bons sobre invariantes e variantes de laços.

  • Existe software para a verificação formal de programas reais, como por exemplo aqueles escritos em C.

  • O artigo clássico de Robert W. Floyd é um excelente trabalho pioneiro sobre verificação de programas. Um excelente resumo moderno sobre o assunto é o capítulo 1 deste trabalho.

  ATENÇÃO: neste ponto da disciplina, você deve saber como demonstrar a correção de um algoritmo iterativo qualquer por meio de variantes e invariantes de laços.

  Exercícios:

  1. Escreva uma demonstração cuidadosa do seguinte lema: "1 ≤ i ≤ n+1" é um invariante do laço do algoritmo busca_linear.

     Sugestão: embora a prova tenha sido feita oralmente em sala, tente escrevê-la sem consultar o seu caderno.

  2. Escreva um algoritmo que receba como entrada um vetor de números reais e que retorne a média aritmética dos elementos do vetor. Em seguida, prove a correção total do seu algoritmo.

  3. Escreva o algoritmo de busca binária em duas versões, uma iterativa e outra recursiva. Qual é o tempo de execução do algoritmo no melhor caso? E no pior caso?

     Extra: se você tiver tempo, tente encontrar invariantes e variantes de laço que permitiriam provar a correção da versão iterativa do algoritmo.

• Aula 4 (2014-08-04, segunda-feira) (nota de aula): busca binária: algoritmo, enunciado de invariante, definição de função variante, prova do número no máximo logarítmico de iterações.

  Exercícios:

  1. Prove o invariante e o variante apresentados em sala.

  2. Em sala, nós concluímos que o tempo de execução da busca binária é no máximo t_b(n) = c_1*lg(n) + c, e que o tempo da busca linear é no máximo t_l(n) = c_4*n + c', para certas constantes c_1, c, c_4 e c'. Mostre agora que, quaisquer que sejam os valores dessas constantes, sempre existe n' tal que, para todo n ≥ n', t_l(n) ≥ t_b(n).

• Aula 5 (2014-08-06, quarta-feira) (nota de aula – pdf): notações O e Ômega (Ω) de complexidade assintótica.

  Exercícios (os 4 primeiros são fáceis, os outros são mais elaborados):

  1. Mostre que, para quaisquer constantes reais não-negativas a, b e c, vale a*n² + b*n + c = O(n²).

     (Moral da história: em termos de complexidade assintótica, num polinômio de uma variável, os monômios de menor grau são dominados pelo de maior grau, e por isso são descartados da análise.)

  2. Mostre que se f = O(g) e g = O(h), então f = O(h).

  3. Mostre que se f = O(g) e h = Ômega(g), então f = O(h).

  4. Mostre que, se f = O(g) e f' = O(g'), então f*f' = O(g*g').

  5. Generalizando um dos exercícios anteriores, mostre que, para qualquer polinômio não-negativo f(n) = a_k*n^k + a_k-1*n^k-1 + ... + a₁*n¹ + a₀*n⁰, temos f(n) = O(n^k).

  6. Mostre que, para qualquer natural k, vale n^k = O(2ⁿ) e 2ⁿ != O(n^k).

  7. Mostre que lg(n) = O(n) e n != O(lg(n)).

• Aula 6 (2014-08-08, sexta-feira) (nota de aula – pdf): notações "ϴ", "o" e "ω" de complexidade assintótica; custo da versão recursiva do algoritmo de busca binária.

  Exercícios (nenhum é particularmente difícil; os menos imediatos talvez sejam aqueles envolvendo recorrências, pois são relativos ao próximo conteúdo da disciplina):

  1. Veja os exercícios já enunciados na nota de aula (acima); eles não serão repetidos aqui.

  2. Mostre que log_a(n) = ϴ(log_b(n)) para quaisquer naturais "a" e "b" maiores que 1.

  3. Assim como no caso da busca binária, vários algoritmos são naturalmente escritos de forma recursiva. Nesse sentido, escreva uma versão recursiva do algoritmo de busca linear. Em seguida, analogamente ao que fizemos em sala, apresente, em termo de n e constantes c₁, c₂, etc, relações de recorrência que definam uma função t(n) que represente o tempo de execução do algoritmo para um vetor de "n" elementos. Por fim, resolva a recorrência, encontrando uma expressão de t(n) em termos apenas de "n" e das constantes utilizadas, e então mostre que t = O(n).

  4. Mostre que, para qualquer real positivo "a", f(n) = a, então f = O(1), mas que n != O(1). Mostre também que n = ω(1).

  5. Mostre que n = o(n * lg n).

  6. Mostre que f = o(g) sse g = ω(f).

  ATENÇÃO: neste ponto da disciplina, você deve saber obter expressões para o tempo de execução de algoritmos iterativos, e também a complexidade assintótica de tais expressões.

• Aula 7 (2014-08-13, quarta-feira) (nota de aula – pdf): funções recorrentes como expressão do tempo de execução de algoritmos recursivos; estimativa de limites superiores para funções recorrentes por meio de árvores de recorrência (observação: as árvores não estão desenhadas na nota de aula); prova de limites superiores e de valores exatos para funções recorrentes por indução.

  Exercícios:

  1. Veja os exercícios já enunciados na nota de aula (acima); eles não serão repetidos aqui.

  2. (Fácil) Sendo "t" definida por

     t(1) = 1
     t(n) = 1 + t(piso(n/2))

     encontre g(n) tal que t(n) = θ(g), e prove que esse é o caso. A função "g" deve ser expressa apenas em termos de polinômios e/ou logaritmos de "n".

     Sugestão: como o exercício é bastante semelhante àquele feito em sala, sugiro tentar primeiro fazê-lo sem olhar a nota de aula.

  3. (Intermediário?) Sendo "t" definida por

     t(1) = 1
     t(n) = 1 + t(teto(n/2))

     encontre g(n) tal que t(n) = θ(g), e prove que esse é o caso.

     Observação: para provar que t(n) = Ω(g), sugiro não provar do zero, mas sim levar em consideração o resultado do exercício anterior. A parte realmente relevante deste exercício é mostrar que t(n) = O(g), e pode ser mais difícil do que parece.

  4. (Fácil) Se f(n) = piso(n/2) + 17, então para que valores naturais de n vale n > f(n)? Há valores de n para os quais vale n = f(n)? E para os quais vale n < f(n), há?

  5. (Intermediário?) Prove ou refute: sendo "t" definida por

     t(n) = 1, se n = 33 ou 34
     t(n) = 1 + t(piso(n/2) + 17), se n ≥ 35

     vale t = O(lg n).

  6. (Fácil) Sendo "t" definida por

     t(1) = 1
     t(n) = 1 + 2*t(piso(n/2))

     encontre g(n) tal que t(n) = θ(g), e prove que esse é o caso. A função "g" deve ser expressa apenas em termos de polinômios e/ou logaritmos de "n".

  7. (Intermediário?) Sendo "t" definida por

     t(n) = 1, se n = 33 ou 34
     t(n) = n + 2*t(piso(n/2) + 17), se n ≥ 35

     encontre g(n) tal que t(n) = θ(g), e prove que t = O(g). A função "g" deve ser expressa apenas em termos de polinômios e/ou logaritmos de "n".

• Aula 8 (2014-08-18, segunda-feira) (nota de aula – pdf): técnicas de prova de relações de recorrência.

  Exercícios:

  1. Veja os exercícios já enunciados na nota de aula (acima); eles não serão repetidos aqui.

• Aula 9 (2014-08-20, quarta-feira) (nota de aula – pdf): técnicas de prova de relações de recorrência; teorema mestre.

  Observação: veja, na página da Wikipédia sobre o Teorema Mestre, exemplos de aplicação e de não aplicação do teorema.

  Exercícios:

  1. Veja os exercícios já enunciados na nota de aula (acima); eles não serão repetidos aqui.

  2. Com relação à equação de recorrência t(n) = 2*t(teto(n/3) - 13) + 7:

     1. Complete a relação de recorrência, apresentando para que valores de n a equação acima pode ser aplicada, e fornecendo casos base para a relação (você pode escolher os valores assumidos pela função nesses casos).

     2. Prove, por indução (como feito em sala), que a função definida pelas equações de recorrência fornecidas por você no item anterior está definida para todo n a partir de um certo valor.

     3. Encontre uma função "g" envolvendo apenas logaritmos e/ou polinômios sobre n tal que t = ϴ(g), e então prove que t = Ω(g) e que t = O(g) (o "caso" Ω é o mais interessante).

  3. (Este exercício visa fornecer intuição sobre o teorema mestre.) Primeiramente, utilizando o teorema mestre, mostre que:

     1. t(n) = 2t(n/2) + 1 ⇒ t = ϴ(n).

     2. t(n) = t(n/2) + 1 ⇒ t = ϴ(lg n).

     3. t(n) = t(n/2) + n ⇒ t = ϴ(n).

     Em seguida, prove cada um dos itens acima por indução, substituindo ϴ por O para diminuir o trabalho (utilize piso(n/2) no lugar de n/2, e defina t(1) = 1 como base da recorrência).

     Em seguida, observe o resultado de cada item, e compare a complexidade assintótica de t(n) com f(n) – que é o custo do primeiro nível da árvore de recursão –, com lg(n) – que é a altura da árvore de recursão – e com n – que é a quantidade total de "chamadas recursivas".

     Por fim, observe o que muda se, nos 3 casos acima, a função f(n) (que vale "1" nos 2 primeiros casos e "n" no 3o) for substituída por:

     1. lg n

     2. n^2

  4. Veja a lista de exercícios 1 do professor Rudini, onde há exercícios sobre notação assintótica e recorrências.

  ATENÇÃO: neste ponto da disciplina, você deve saber obter expressões para o tempo de execução de algoritmos recursivos, e também a complexidade assintótica de tais expressões.

• Aula 10 (2014-08-22, sexta-feira) (nota de aula – pdf): técnicas de projeto de algoritmos: estratégia incremental (insertion sort) e divisão em conquista (merge sort); ordenação por entrelaçamento (merge sort): algoritmo, correção e complexidade do tempo de execução.

  Exercícios:

  1. Veja os exercícios já enunciados na nota de aula (acima); eles não serão repetidos aqui.

  2. Outras versões e melhorias da ordenação por entrelaçamento:

     1. Escreva uma versão não-recursiva do algoritmo.

     2. Como comentado em sala, o algoritmo sempre executa em tempo ϴ(n * lg n), inclusive se o vetor de entrada já estiver ordenado, e, nesse caso, executa em tempo pior que o de ordenação por inserção. Escreva, então, a modificação sugerida em sala, na qual o algoritmo começa particionando o vetor em intervalos maximais que já estão ordenados, e então, em cada iteração, faz o entrelaçamento dos diversos pares de intervalos sucessivos.

        Observação: nesta versão, você provavelmente precisará de outro vetor auxiliar, que armazenará o início e o fim de cada intervalo ordenado.

     3. Escreva a modificação sugerida em sala para evitar cópias desnecessárias entre os vetores A e B. Mais especificamente, escreva uma versão na qual os primeiros entrelaçamentos ocorrem de A para B, e na qual os entrelaçamentos seguintes ocorrem de B para A, e depois novamente de A para B, etc. No final, deve haver um teste, para se descobrir se os elementos ordenados acabaram no vetor A ou no vetor B: no primeiro caso, não há mais nada a ser feito; no segundo, é necessário copiar os elementos de volta para o vetor A.

  3. Em sala, nós justificamos os invariantes do algoritmo "entrelaçar" oralmente; agora, tente produzir uma argumentação escrita de que os invariantes são corretos, e igualmente de que o variante é correto.

  4. Em sala, foi proposta uma variação do algoritmo "entrelaçar" na qual o laço principal do algoritmo passa a ter a condição "k ≤ f", tornando desnecessários os 2 comandos "RETORNE". Adapte então a argumentação de terminação e correção do algoritmo para a versão em questão.

• Aula 11 (2014-08-25, segunda-feira) (nota de aula – pdf): ordenação por monte ("heapsort"): algoritmo e complexidade do tempo de execução.

  Exercícios:

  1. Veja os vários exercícios presentes na nota de aula (acima).

• Aula 12 (2014-08-27, quarta-feira) (nota de aula – pdf): ordenação por particionamento ("quicksort"): algoritmo, correção e complexidade do tempo de execução.

  Exercícios:

  1. Veja os exercícios presentes na nota de aula (acima).

  2. Escreva a versão alternativa comentada em sala do algoritmo de particionamento, que mantém, no início do vetor, a seção dos números ≤ ao pivô e, logo em seguida, a seção dos elementos > que o pivô, seguida pelo restante dos elementos (no início do algoritmo, o pivô é movido para o final do vetor). Em seguida, argumente que ela também executa em tempo ϴ(n), onde n = f-i+1.

  3. Escreva uma variação do algoritmo de particionamento que sempre retorna um pivô exatamente na metade do vetor. A ideia é utilizar o algoritmo original repetidas vezes: caso o primeiro pivô não fique exatamente no meio do vetor após o particionamento, deve-se escolher (adequadamente) outro elemento como pivô e fazer novo particionamento, até que o pivô escolhido fique no meio do vetor.

     Em seguida, analise a complexidade assintótica desse algoritmo no pior e no melhor casos.

• Aula 13 (2014-08-29, sexta-feira) (nota de aula – pdf): problema da seleção do k-ésimo menor elemento: algoritmo de Hoare – ϴ(n²) no pior caso, mas O(n) no caso médio – e algoritmo de Blum, Floyd, Pratt, Rivest e Tarjan – O(n) no pior caso.

  Exercícios: veja aqueles presentes na nota de aula (acima).

• Aula 14 (2014-09-01, segunda-feira) (nota de aula – pdf): limite Ω(n*lg n) para o tempo de execução de algoritmos de ordenação baseados em comparação; algoritmo de ordenação por contagem ("counting sort").

  Exercícios:

  1. Veja os exercícios presentes na nota de aula (acima).

• Aula 15 (2014-09-03, quarta-feira) (nota de aula – pdf): algoritmo de ordenação por dígitos ("radix sort"), com aplicação à ordenação de inteiros; Torres de Hanói.

  Exercícios:

  1. Veja os exercícios presentes na nota de aula (acima).

  2. Escreva um algoritmo não-recursivo para o problema das torres de Hanói.

• Aula 16 (2014-09-05, sexta-feira) (nota de aula – pdf): algoritmos para a multiplicação de números naturais: algoritmo direto, algoritmo por deslocamento de bits, algoritmo básico de divisão-e-conquista e algoritmo de Karatsuba (exercício: algoritmo de Strassen).

• Aula 17 (2014-09-08, segunda-feira): revisão para a prova.

  ATENÇÃO: neste ponto da disciplina, você deve saber resolver problemas utilizando a estratégia de divisão-e-conquista, conforme exemplificado em sala para o problema de ordenação e outros.

• Atividade em 2014-09-10, quarta-feira: AP1, parte 1.

• Atividade em 2014-09-12, sexta-feira: AP1, parte 2.

• Aula 18 (2014-09-15, segunda-feira) (nota de aula – pdf): algoritmos para o n-ésimo número de Fibonacci: divisão-e-conquista, programação dinâmica e memoização; agendamento para linha-de-montagem.

• Aula 19 (2014-09-17, quarta-feira) (nota de aula – pdf): o problema da ordem de multiplicação de uma cadeia de matrizes.

• Aula 20 (2014-09-19, sexta-feira) (nota de aula – pdf): o problema da mochila 0-1.

• Aula 21 (2014-09-22, segunda-feira) (nota de aula – pdf): o problema da subsequência comum máxima ("LCS").

• Aula 22 (2014-09-24, quarta-feira) (nota de aula – pdf): árvores de busca ótimas.

  ATENÇÃO: neste ponto da disciplina, você deve saber resolver problemas utilizando a estratégia da programação dinâmica.

• Aula 23 (2014-09-26, sexta-feira) (nota de aula – pdf): caminhos mínimos entre todos os pares de vértices de um grafo direcionado ponderado em O(n³).

• Aula 24 (2014-09-29, segunda-feira) (nota de aula – pdf): seleção de atividades: algoritmo de programação dinâmica; algoritmo guloso.

• Aula 25 (2014-10-01, quarta-feira) (nota de aula – pdf): escalonamento de tarefas: consideração de estratégias para o problema.

• Aula 26 (2014-10-03, sexta-feira) (nota de aula – pdf): escalonamento de tarefas: correção da estratégia gulosa; solução O(n²).

• Aula 27 (2014-10-06, segunda-feira) (nota de aula – pdf): códigos de Huffman.

• Aula 28 (2014-10-08, quarta-feira) (defs_grafos – AGM-Kruskal): árvores geradoras mínimas: algoritmo de Kruskal.

• Aula 29 (2014-10-10, sexta-feira) (nota de aula – pdf): caminhos mínimos a partir de um único vértice: algoritmo de Dijkstra.

  ATENÇÃO: neste ponto da disciplina, você deve saber resolver problemas utilizando a estratégia gulosa, nos casos em que ela se aplica.

• Aula 30 (2014-10-13, segunda-feira) (nota de aula – pdf): revisão para a AP2; o problema do corte de haste.

• 2014-10-15, quarta-feira: recesso escolar – Dia do Professor.

• 2014-10-17, sexta-feira: AP2, parte 1.

• 2014-10-20, segunda-feira: AP2, parte 2.

• 2014-10-22, quarta-feira: sem aula – Encontros Universitários 2014.

• 2014-10-24, sexta-feira: sem aula – Encontros Universitários 2014.

• 2014-10-27, segunda-feira: recesso escolar – Dia do Servidor Público (antecipado).

• Aula 31 (2014-10-29, quarta-feira) (defs_grafos – classe P): a classe de complexidade de problemas "P".

• 2014-10-31, sexta-feira: sem aula – alunos da Matemática Industrial participando da SEMI.

• Aula 32 (2014-11-03, segunda-feira) (classe_P – classe NP): aceitação em tempo polinomial e a classe P; algoritmo de verificação versus algoritmo de decisão.

• Aula 33 (2014-11-05, quarta-feira) (classe NP): verificação em tempo polinomial: a classe NP.

  ATENÇÃO: neste ponto da disciplina, você deve entender os conceitos de decisão, aceitação e verificação, e saber mostrar a pertinência de problemas às classes P e NP.

• Aula 34 (2014-11-07, sexta-feira) (classe NPC): redução em tempo polinomial e a classe NP-completa.

• Aula 35 (2014-11-10, segunda-feira) (SAT-CIRCUITOS, SAT): problemas NP-completos: Satisfatibilidade de Circuitos (SAT-CIRCUITOS) e Satisfatibilidade de Fórmulas (SAT).

• Aula 36 (2014-11-12, quarta-feira): definição e NP-completude de 3-CNF-SAT (3-SAT).

  SEM NOTA DE AULA: consulte o livro-texto da disciplina e/ou outras fontes, como esta, que descreve bem a redução explicada em sala (que é a mesma do livro).

• Aula 37 (2014-11-14, sexta-feira): definição e NP-completude dos problemas: Clique, Conjunto Independente, Cobertura por vértices, Caminho hamiltoniano (para este último problema, apenas um sentido da equivalência entre as instâncias foi argumentado).

  SEM NOTA DE AULA: consulte o livro-texto da disciplina e/ou outras fontes, como esta, que descreve as mesmas reduções explicadas em sala (que são essencialmente as mesmas do livro), exceto a redução para Ciclo Hamiltoniano, que pode ser encontrada, por exemplo, aqui, aqui e aqui.

  Exercícios:

  1. O problema de decisão Caixeiro Viajante é o de, dado um grafo COMPLETO G = (V,E) com arestas de pesos naturais w : E → N, e dado um natural "k", responder se "G" possui um ciclo hamiltoniano de peso ≤ k.

     MOSTRE QUE Caixeiro Viajante é um problema NP-completo.

  ATENÇÃO: neste ponto da disciplina, você deve entender os conceitos de redução polinomial e classe NP-completa, bem como saber mostrar a pertinência de problemas a essa classe.

• Aula 38 (2014-11-17, segunda-feira) (nota de aula): definição e NP-completude dos problemas Caixeiro Viajante e Soma de Subconjunto.

• Aula 39 (2014-11-19, quarta-feira) (exercícios): revisão para a AP3; problemas mecanicamente insolúveis (problema da parada).

• 2014-11-21, sexta-feira: sem atividade (AP3 adiada).

• 2014-11-24 e -26 (segunda e quarta-feira): AP3.