Caro aluno, na regulamentação desta disciplina você pode acessar informações básicas sobre ela, incluindo objetivos e ementa. Você também pode consultar a página da disciplina do professor Rudini 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 é, aula-a-aula, participar das aulas, estudar o conteúdo, fazer os exercícios e tirar as dúvidas. 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.
Veja os exercícios da aula sobre Cobertura por Vértices e Soma de Subconjuntos!
A AP3.1 será segunda dia 22/junho, e irá até a nota de aula sobre a classe NP-Completa. Em particular, nela não serão cobradas as provas de NP-dificuldade vistas em sala; entretanto, o conceito de redução polinomial, assim como o da classe NPC, pode ser cobrado.
Veja as regras para solicitação de segunda chamada.
Vejas as regras para o cálculo da nota na disciplina.
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!
Segunda chamada: consulte as regras para a solicitação de prova de segunda chamada.
Consistirá na média aritmética das notas obtidas pelo aluno nas três avaliações parciais (MAP):
| Média das APs | ≥ 7 | ≥ 6 | ≥ 3 | < 3 |
|---|---|---|---|---|
| Situação | Aprovado sem AF | Aprovado com AF (*) | AF | Reprovado |
Cada prova valerá nota de 0 a 10, e será dividida em duas partes, cada uma valendo nota de 0 a 5. A intenção é evitar falta de tempo para fazer as provas, evitar excesso de conteúdo por prova e incitar a regularidade de estudo por parte dos alunos.
À nota de cada AP pode ser adicionada uma nota de trabalho, de no máximo 2 pontos, atribuída pelo professor a trabalho realizado por iniciativa do aluno e combinado entre os dois. O objeto/tema do trabalho é único para cada aluno, de forma que não haverá dois ou mais alunos fazendo o mesmo trabalho.
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).
OBSERVAÇÃO: o meu exemplar é da 2ª edição, e por isso o conteúdo dado em sala pode ser ligeiramente diferente daquele apresentado na 3ª edição do livro.
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.
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!
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.
| Aula | Data | Descrição |
|---|---|---|
| 1 | 20/02 | Apresentação da Disciplina; Correção de Algoritmos com Seleção e Repetição. |
| 2 | 23/02 | Correção Parcial; Uso e Prova de Invariantes de Laço. |
| 3 | 25/02 | Correção Total; Variantes de laço. |
| 4 | 27/02 | Laboratório: Verificação de Programas em C. |
| 5 | 02/03 | Tempo de Execução de Algoritmos; Notação Assintótica. |
| 6 | 04/03 | Notação Assintótica; Complexidade de Algoritmos Recursivos. |
| 06/03 | Sem aula (Reunião do Colegiado do Departamento de Computação). | |
| 7 | 09/03 | Resolução de Recorrências: Árvores de Recursão; Método da Substituição. |
| 8 | 11/03 | Resolução de Recorrências: casos não-triviais. |
| 9 | 13/03 | Resolução de Recorrências: casos não-triviais; Teorema Mestre. |
| 10 | 16/03 | Exercícios |
| 18/03 | AP1 – 1ª parte: correção e tempo de execução de algoritmos. | |
| 20/03 | Sem aula (imprevisto com o professor). | |
| 11 | 23/03 | Ordenação; Algoritmo HeapSort. |
| 25/03 | Feriado Estadual – Data Magna do Ceará. | |
| 12 | 27/03 | Divisão e Conquista; Algoritmo MergeSort. |
| 13 | 30/03 | Algoritmo Quick Sort. |
| 14 | 01/04 | Algoritmos de Seleção do k-ésimo Mínimo: Hoare, O(n²), e Blum et al., O(n). |
| 03/04 | Feriado Nacional – Sexta Feira da Paixão. | |
| 15 | 06/04 | Algoritmo de Seleção O(n) de Blum et al.. |
| 16 | 08/04 | Multiplicação de Inteiros Grandes (Karatsuba) e Matrizes (Strassen). |
| 10/04 | Sem aula (Reunião DC) / Tarefa de implementação (Seleção em tempo linear). | |
| 17 | 13/04 | Limite Ω(n*lg n) para Ordenação por Comparações; "Counting Sort". |
| 18 | 15/04 | Radix Sort |
| 19 | 17/04 | Exercícios |
| 20 | 20/04 | Programação Dinâmica: Fibonacci; Linha de Montagem. |
| 22/04 | AP1 – 2ª parte: Ordenação; Divisão e Conquista. | |
| 21 | 24/04 | Programação Dinâmica: Corte de Haste. |
| 22 | 27/04 | Programação Dinâmica: Multiplicação de Sequências de Matrizes. |
| 23 | 29/04 | Programação Dinâmica: Problema da Mochila 0-1. |
| 01/05 | Feriado Nacional – Dia do Trabalho. | |
| 24 | 04/05 | Programação Dinâmica: Subsequência Comum Máxima. |
| 25 | 06/05 | Programação Dinâmica: Árvores de Busca Ótimas; Aplicabilidade da Programação Dinâmica. |
| 08/05 | Sem aula (Reunião DC) / Tarefa de Implementação (Estrutura de Dados para Conjuntos Disjuntos). | |
| 26 | 11/05 | Programação Dinâmica: Subestrutura Ótima; Algoritmo de Floyd-Warshall; Exercícios |
| 27 | 13/05 | Algoritmos Gulosos: Seleção de Atividades. |
| 28 | 15/05 | Algoritmos Gulosos: Escalonamento de Tarefas. |
| 29 | 16/05 | AULA EXTRA (SÁBADO): Exercícios. |
| 30 | 18/05 | Algoritmos Gulosos: Algoritmo de Kruskal. |
| 20/05 | AP2 – 1ª parte: Programação Dinâmica. | |
| 31 | 22/05 | Algoritmos Gulosos: Algoritmo de Dijkstra. |
| 32 | 25/05 | Algoritmos Gulosos: Códigos de Huffman. |
| 33 | 27/05 | Exercícios |
| 34 | 29/05 | Classes de Complexidade de Problemas: Introdução; Classe P. |
| 01/06 | AP2 – 2ª parte: Algoritmos Gulosos. | |
| 03/06 | Sem aula (professor adoentado). | |
| 35 | 05/06 | Classe P e Aceitação Polinomial. |
| 36 | 08/06 | Classe NP. |
| 37 | 10/06 | Classe NP-Completa; Satisfatibilidade de Circuitos (SAT-CIRCUITOS). |
| 38 | 12/06 | Satisfatibilidade de Fórmulas (SAT). |
| 39 | 15/06 | Satisfatibilidade de Fórmulas em 3-CNF (3-SAT). |
| 40 | 17/06 | Clique e Conjunto Independente. |
| 19/06 | Sem aula (Reunião DC) | |
| 41 | 20/06 | AULA EXTRA (SÁBADO): Cobertura por Vértices; Soma de Subconjunto; Exercícios. |
| 22/06 | AP3 – 1ª parte: Classes de Complexidade de Problemas; Reduções Polinomiais. | |
| 42 | 24/06 | Problemas Mecanicamente Insolúveis; Exercícios. |
| 26/06 | AP3 – 2ª parte: Classes de Complexidade de Problemas; Reduções Polinomiais. | |
| 29/06 | Notas AP3; Situação AF. | |
| 01/07 | AF – 1ª parte. | |
| 03/07 | AF – 2ª parte. | |
| 06/07 | Resultado final da disciplina. |
Aula 1 (2015-02-20, sexta-feira) (nota de aula): introdução à disciplina; correção de algoritmos com seleção; correção de algoritmos com repetição (parte 1).
EXERCÍCIO ESSENCIAL: ENCONTRAR INVARIANTES FORTES O SUFICIENTE para provarmos que o algoritmo de busca linear é correto.
Aula 2 (2015-02-23, segunda-feira) (nota de aula): correção de algoritmos com repetição, parte 2 (usar e provar invariantes de laço).
EXERCÍCIO ESSENCIAL: PROVAR, VIA INVARIANTES DE LAÇO, A CORREÇÃO PARCIAL de um algoritmo que calcula o maior elemento de um vetor de números reais.
Aula 3 (2015-02-25, quarta-feira) (nota de aula): correção de algoritmos com repetição, parte 3 (variantes de laço).
EXERCÍCIO ESSENCIAL: PROVAR A CORREÇÃO TOTAL DO ALGORITMO DE BUSCA BINÁRIA ITERATIVO.
Aula 4 (2015-02-27, sexta-feira) (nota de aula): verificação de programas reais pela plataforma Frama-C.
Aula 5 (2015-03-02, segunda-feira) (nota de aula): tempo de execução de algoritmos; notações assintóticas "O" e "Ω".
EXERCÍCIO ESSENCIAL: PROVAR OU REFUTAR: n = Ω(n²).
Aula 6 (2015-03-04, quarta-feira) (nota de aula): notações assintóticas Θ, "o" e "ω"; tempo de execução de algoritmos recursivos; solução de equações de recorrência.
EXERCÍCIO ESSENCIAL: PROVAR que a busca binária recursiva executa em O(lg n), solucionando para isso a respectiva equação de recorrência (veja a nota de aula).
2015-03-06, quarta-feira: sem aula (presença obrigatória do professor na Reunião do Colegiado do Departamento de Computação).
Reposição da aula: nas QUARTA E SEXTA-FEIRAS DA SEMANA SEGUINTE.
Aula 7 (2015-03-09, segunda-feira) (nota de aula): solução de equações de recorrência: proposição de solução não-recorrente e prova da solução por indução matemática.
EXERCÍCIO ESSENCIAL: sejam a,b,c naturais positivos e "f" a função natural tal que f(n) = a + f(n-1), se n > 1; f(1) = b; f(0) = c. Encontre uma expressão não-recorrente para f(n), e então prove a igualdade entre essa expressão e f(n) por indução matemática.
Aula 8 (2015-03-11, quarta-feira) (nota de aula): solução de equações de recorrência: provando resultado mais forte para fazer a indução funcionar.
EXERCÍCIO ESSENCIAL: veja no final da nota de aula.
Aula 9 (2015-03-13, sexta-feira) (nota de aula): solução de equações de recorrência: mudar a base do logaritmo para fazer a indução funcionar; teorema mestre.
EXERCÍCIO ESSENCIAL: pratique com os exercícios da nota de aula e os exercícios do semestre passado, e traga as possíveis dúvidas na próxima aula.
Aula 10 (2015-03-16, segunda-feira) (nota de aula): revisão para a AP1.
2015-03-18, quarta-feira: AP1, parte 1.
2015-03-20, sexta-feira: sem aula (imprevisto com o professor); aula por recuperar.
Aula 11 (2015-03-23, segunda-feira) (nota de aula): ordenação por monte ("heapsort").
2015-03-25, quarta-feira: sem aula (Feriado Estadual – Data Magna do Ceará).
Aula 12 (2015-03-27, sexta-feira) (nota de aula): técnicas de projeto de algoritmos: incremental, divisão-e-conquista; ordenação por entrelaçamento ("mergesort").
EXERCÍCIO ESSENCIAL: Exercício 7 da lista 1 do Rudini.
Aula 13 (2015-03-30, segunda-feira) (nota de aula): ordenação por particionamento ("quicksort").
EXERCÍCIO ESSENCIAL: escreva o algoritmo de tri-partição descrito no exercício "c" da nota de aula.
Aula 14 (2015-04-01, quarta-feira) (nota de aula): Problema de seleção; Algoritmo de seleção de Hoare; Algoritmo de seleção de Blum et al. (início da explicação).
2015-04-03, sexta-feira: sem aula (Feriado Nacional – Sexta Feira da Paixão).
Aula 15 (2015-04-06, segunda-feira) (nota de aula): Algoritmo de seleção de Blum et al. (continuação e término da explicação).
EXERCÍCIO ESSENCIAL: o algoritmo de seleção em questão ainda executa em tempo linear se forem utilizados segmentos de 3 elementos? E de 7 elementos? E de 2*y + 1 elementos, com y ≥ 3?
Aula 16 (2015-04-08, quarta-feira) (material para estudo: Algorithm Design, cap. 5, seções 2 e 3: págs. 270–273): Algoritmos de divisão-e-conquista para multiplicação de inteiros grandes (algoritmo de Karatsuba) e matrizes (algoritmo de Strassen).
2015-04-10, sexta-feira: sem aula (professor em Reunião do Colegiado do DC), mas há tarefa de implementação:
Você deve implementar o algoritmo de seleção de Blum et al., que sempre executa em tempo linear.
Para a ordenação dos segmentos de 5 elementos, qualquer algoritmo de ordenação é suficiente, mas uma boa sugestão é a ordenação por inserção.
Para a partição do vetor em torno do pivô, tanto o algoritmo de Hoare quanto o de Lomuto servem.
Após implementar o algoritmo de seleção, escreva e experimente uma versão do Quicksort que o utilize para a escolha do pivô, que no caso deverá ser a mediana.
Lembre que o algoritmo de seleção em questão já particiona o vetor ao redor do elemento selecionado, de forma que, após a escolha do pivô no Quicksort, não é necessário fazer um particionamento.
Sugestão: no horário da aula, vá ao LEC (que está reservado para a nossa disciplina) e faça essa implementação.
Aula 17 (2015-04-13, segunda-feira) (nota de aula): Limite Ω(n*lg n) para ordenação baseada apenas em comparações; ordenação de vetores de inteiros limitados.
Exercícios:
(Exercício essencial) Escreva o algoritmo discutido em sala que recebe como entrada um vetor V[1..n] de inteiros, todos no intervalo de 1 a "k", e que o ordena segundo a seguinte estratégia:
Crie um vetor auxiliar e conte, para cada "i" de 1 a "k", quantas vezes a chave "i" aparece em "V".
Com base no vetor auxiliar acima, compute, para cada chave "i", a primeira posição DO VETOR ORDENADO que é igual a "i".
Com base na informação acima, percorra "V" do início ao fim e, para cada elemento V[i] = x, coloque V[i] na primeira posição livre para chaves de valor "x" (lembre de incrementar o valor dessa posição, para que os próximos elementos de chave "x" sejam colocados na posição correta).
Qual é a complexidade assintótica do tempo de execução do algoritmo acima? E a do uso de memória?
Escreva o algoritmo discutido em sala que recebe como entrada um vetor V[1..n] no qual cada chave "i" de 1 a "n" ocorre exatamente uma vez, e que ordena esse vetor em tempo O(n) e usando O(1) de memória auxiliar.
Aula 18 (2015-04-15, quarta-feira) (nota de aula): ordenação por contagem ("counting sort"); ordenação por campos ou dígitos ("radix sort").
Aula 19 (2015-04-17, sexta-feira): revisão para a segunda parte da AP1.
Aula 20 (2015-04-20, segunda-feira) (nota de aula): projeto de algoritmos por programação dinâmica: números de Fibonacci; linha de montagem.
EXERCÍCIO ESSENCIAL: escreva um algoritmo eficiente para encontrar a melhor maneira de cortar uma haste de tamanho "n" em pedaços, de forma a maximizar o lucro obtido. Tanto o tamanho da haste original quanto o de cada pedaço final é um número natural, e, para todo "i" de 1 a "n", um pedaço de tamanho "i" tem preço p[i].
2015-04-22, quarta-feira: AP1, parte 2.
Aula 21 (2015-04-24, sexta-feira) (nota de aula): o Problema do Corte de Haste: soluções por divisão-e-conquista, memoização e programação dinâmica "bottom-up".
Aula 22 (2015-04-27, segunda-feira) (nota de aula): o Problema da Multiplicação de Cadeias de Matrizes; o Problema da Mochila 0-1 (início da discussão).
EXERCÍCIO ESSENCIAL: resolver o problema da mochila 0-1 (ver nota de aula).
Aula 23 (2015-04-29, quarta-feira) (nota de aula): o Problema da Mochila 0-1; o Problema da Subsequência Comum Máxima (início da discussão).
EXERCÍCIO ESSENCIAL: resolver o LCS (ver nota de aula).
2015-05-01, sexta-feira: sem aula (Feriado Nacional – Dia do Trabalho).
Aula 24 (2015-05-04, segunda-feira) (nota de aula): o Problema da Subsequência Comum Máxima; o Problema da Árvore de Busca Ótima (início da discussão).
EXERCÍCIO ESSENCIAL: resolver o problema da árvore de busca ótima (ver nota de aula).
Aula 25 (2015-05-06, quarta-feira) (nota de aula): o Problema da Árvore de Busca Ótima.
EXERCÍCIO ESSENCIAL: verificar se o algoritmo dado em sala é Ω(n³) ou o(n³).
2015-05-08, sexta-feira (nota de aula): sem aula (professor em Reunião do Colegiado do DC), mas com nota de aula sobre conjuntos disjuntos.
EXERCÍCIO ESSENCIAL: estudar a nota de aula.
Aula 26 (2015-05-11, segunda-feira) (nota de aula): Caminhos mínimos entre todos os pares de vértices de um grafo.
EXERCÍCIO ESSENCIAL: escreva o algoritmo de Floyd-Warshall, conforme exercício 1.b da nota de aula.
Aula 27 (2015-05-13, quarta-feira) (nota de aula): Um Problema de Seleção de Atividades; Algoritmos Gulosos.
EXERCÍCIO ESSENCIAL: Escreva o algoritmo guloso O(n*lg n) do exercício 4 da nota de aula.
Aula 28 (2015-05-15, sexta-feira) (nota de aula de 2014.2 ⇒ mas veja os exercícios abaixo primeiro!): Escalonamento de tarefas.
EXERCÍCIO ESSENCIAL: escreva o algoritmo O(n²) que foi discutido em sala (caso necessário, você pode recapitular a definição/notação do problema no início da nota de aula). A resposta está no item 5 da nota de aula.
EXERCÍCIO INTERESSANTE: tente escrever uma variação O(n*lg n) do algoritmo que foi discutido em sala. Dica: se o tempo "x" está livre e os tempos x+1, x+2, ..., x+k estão ocupados, mantenha-os todos num mesmo conjunto.
Aula 29 (2015-05-16, sábado, aula extra): exercícios e tira-dúvidas sobre programação dinâmica.
Aula 30 (2015-05-18, segunda-feira) (nota de aula de 2014.2; definições envolvendo grafos): o Problema da Árvore Geradora Mínima; o Algoritmo de Kruskal.
Algoritmo escrito em sala (usa conjuntos disjuntos):
==============================================================================
Algoritmo: agm_Kruskal
Entrada: G = (V,E) e w : E → R.
Saída: um conjunto "A" de arestas.
------------------------------------------------------------------------------
01. Ordene as arestas de G em ordem crescente de peso.
02. PARA CADA vértice "v" // PARA i DE 1 A n
03. | criar_conjunto(v) // | criar_conjunto(i)
04. A := conjunto vazio
05. PARA cada aresta e = {x,y}, em ordem crescente de peso
06. | SE consultar_conjunto(x) != consultar_conjunto(y)
07. | | A := A U {e}
08. | | unir_conjuntos(x,y)
09. | | SE |A| = |V| - 1
10. | | | "break" // sair do laço
11. RETORNE A.
==============================================================================
Exercícios:
(Exercício essencial) prove, de forma análoga àquela do algoritmo de Kruskal, que é correta a estratégia "comece do grafo inteiro e, para cada aresta, da mais pesada à mais leve, remova-a sse essa remoção não tornar o grafo resultante desconexo".
O algoritmo de Prim é outro algoritmo guloso para o problema da AGM.
A partir de um certo vértice "v" dado como entrada,
o algoritmo inicializa C := {v} e então repete o seguinte,
até que C seja igual a V (que é o conjunto de vértices do grafo de entrada):
"dentre as arestas com uma extremidade em C e outra em V \ C,
selecione uma aresta e = {u,v} de peso mínimo,
e faça C := C U {u,v}".
Usando o conceito de "pré-solução ótima / pré-AGM",
prove que essa estratégia é correta,
e, depois disso, escreva um algoritmo O(m*lg n)
que a materialize (sendo m = |E| e n = |V|).
Escreva uma argumentação detalhada de que o algoritmo de Kruskal, na forma apresentada acima, executa em tempo O(m*lg n).
2015-05-20, quarta-feira: AP2, parte 1.
Aula 31 (2015-05-22, sexta-feira) (nota de aula de 2014.2; definições envolvendo grafos): o Problema de Caminhos Mínimos a partir de um único vértice; estratégia, correção e tempo de execução do algoritmo de Dijkstra (versão com vetor, O(n²), e versão com heap, O((n+m)*lg n); esboço de solução da AP2.1.
Exercícios:
(Exercício essencial) A nota de aula contém uma versão do algoritmo de Dijkstra que usa um vetor para armazenar as estimativas de distância aos vértices. Escreva a variação, discutida em sala, que usa um "heap" para o mesmo propósito. O algoritmo deve computar não apenas as distâncias a partir do vértice de origem, mas também os caminhos mínimos dele aos demais vértices.
Prove que, se as arestas puderem ter pesos negativos, então o algoritmo de Dijkstra nem sempre funciona.
Aula 32 (2015-05-25, segunda-feira) (nota de aula de 2014.2): o algoritmo guloso de codificação ótima de Huffman.
Exercícios:
(Exercício essencial) Certifique-se de entender os lemas 3, 4 e 5 da nota de aula, bem como a relação entre eles e o algoritmo 6. Entenda também por quê o algoritmo executa em tempo O(n*lg n).
Explique como a mesma estratégia pode ser implementada com duas filas, ao invés de um "heap", CASO OS CARACTERES DE ENTRADA JÁ ESTEJAM ORDENADOS DO MENOS PARA O MAIS FREQUENTE. Dica: use uma fila para os caracteres originais, e outra para os caracteres compostos pela união de outros dois. Escreva um algoritmo que implemente essa ideia, e mostre que ele executa em O(n).
Aula 33 (2015-05-27, quarta-feira): tira-dúvidas para a AP2.2.
Aula 34 (2015-05-29, sexta-feira) (nota de aula de 2014.2): Problemas (abstratos); Problemas de Decisão; Problemas Concretos; Representação de entradas em problemas concretos.
2015-06-01, segunda-feira: AP2, parte 2.
2015-06-03, quarta-feira: sem aula (professor adoentado).
Aula 35 (2015-06-05, sexta-feira) (nota de aula de 2014.2): Resolução de problemas concretos em tempo polinomial; a Classe P; Aceitação em tempo polinomial; equivalência entre aceitação e decisão em tempo polinomial.
Exercícios:
(Exercício essencial) Considere a seguinte versão de decisão do Problema da Mochila: dados "n" objetos, de valores naturais v_1 a v_n e pesos também naturais p_1 a p_n, e dadas ainda uma capacidade de mochila "C" e um valor "V", a maior soma de valores de objetos passíveis de serem carregados na mochila em questão é no máximo "V"?
Considere agora uma versão concreta do algoritmo acima, onde a entrada é fornecida na forma "{v_1/p_1;v_2/p_2;...;v_n/p_n},C,V", naturalmente codificada por meio de uma sequência de bits. Em particular, observe que, sendo os números fornecidos na base dois, a forma acima utiliza apenas os 7 símbolos "0 1 { } ; , /" (excluídas as aspas), os quais podem portanto ser codificados utilizando-se um código de tamanho fixo de 3 bits.
Considere, agora, o seguinte algoritmo para o problema concreto acima:
====================================================================== Algoritmo: mochila_concreto Entrada: uma sequência de bits S[1..t]. Saída: 0 ou 1. ---------------------------------------------------------------------- 1. Verifique se a sequência "S" codifica uma entrada válida; caso não, retorne 0; caso sim, coloque a entrada em vetores v[1..n] e p[1..n] de números naturais, e em variáveis naturais "C" e "V". 2. Encontre o valor X de uma solução ótima para a entrada (v,p,C) da versão de otimização do Problema da Mochila, por meio do algoritmo de programação dinâmica visto em sala (aula 23). 3. SE X ≤ V ENTÃO RETORNE 1. 4. SENÃO RETORNE 0. FIM_SE ======================================================================Assim sendo:
O algoritmo acima resolve o problema concreto em questão em tempo polinomial (em relação ao tamanho "t" da entrada)?
E se, na codificação da entrada, ao invés da base dois, for utilizada a base 1 (na qual um número "n" é representado por uma sucessão de "n" 1's), o algoritmo acima resolve o problema concreto em tempo polinomial sobre "t"?
Aula 36 (2015-06-08, segunda-feira) (nota de aula de 2014.2): Algoritmos de Verificação; a Classe NP; exemplos de problemas em NP; P ⊆ NP.
Exercício essencial: o exercício 7 da nota de aula.
Aula 37 (2015-06-10, quarta-feira) (classe NPC 2014.2, SAT-CIRCUITOS 2014.2): problemas NP-difíceis; problemas NP-completos; o problema da Satisfatibilidade de Circuitos (SAT-CIRCUITOS); SAT-CIRCUITOS ∈ NP.
Exercício essencial: o exercício 4 da nota de aula sobre SAT-CIRCUITOS.
Aula 38 (2015-06-12, sexta-feira) (nota de aula de 2014.2): o problema da Satisfatibilidade de Fórmulas (SAT); SAT ∈ NPC.
Exercício essencial: Qual é a fórmula correspondente ao circuito C_6 (definido no exercício 4 da nota de aula sobre SAT-CIRCUITOS) na redução de SAT-CIRCUITOS para SAT? Escreva-a de forma completa, e avalie se ela de fato corresponde ao circuito. A prova do teorema 6 da nota de aula de hoje lhe faz sentido e convence?
Aula 39 (2015-06-15, segunda-feira) (Cormen, 2ª ed., §34.4; exemplo de material online): o problema da Satisfatibilidade de Fórmulas 3-CNF (3-SAT, ou 3-CNF-SAT); 3-SAT ∈ NPC.
Exercício essencial: Dada a entrada ¬ (A ⇔ (B ∧ B)) para SAT, qual é a entrada correspondente para 3-SAT? Certifique-se de entender que as entradas têm a mesma resposta, e que a construção leva tempo polinomial.
Aula 40 (2015-06-17, quarta-feira) (Cormen, 2ª ed., §34.5; exemplo de material online): o problema de decisão Clique: Clique ∈ NP, 3-SAT ≤p Clique; o problema de decisão Conjunto Independente (CI): CI ∈ NP, 3-SAT ≤p CI.
Exercício essencial: Mostre que Clique ≤p CI. Tente escrever a redução em detalhe.
2015-06-19, sexta-feira: sem aula (professor em Reunião do Colegiado do DC).
Aula 41 (2015-06-20, sábado) (Cormen, 2ª ed., §34.5; exemplo de material online para CV; para SS, sugiro o Cormen): o problema de decisão Cobertura por Vértices (CV): CV ∈ NP, Conjunto Independente ≤p CV; o problema de decisão Soma de Subconjunto (SS): SS ∈ NP, 3-SAT ≤p SS.
Exercício essencial: Escreva em detalhes uma redução direta de 3-SAT para Cobertura por Vértices.