Conteúdo desta página

• Avisos importantes
• Horário das aulas e atendimento
• Objetivos
• Programa da disciplina
• Listas de exercícios
• Material didático
• Avaliação
• Datas importantes
• Referências bibliográficas

Avisos importantes

Para ver as notas finais clique aqui.

• 12/12: as notas finais estão disponíveis no link acima. A revisão será quinta-feira 13/12 às 17h na minha sala.

  Observação: Isto encerra esta instância desta disciplina. Não haverá nenhum outro tipo de avaliação complementar. A avaliação foi feita estritamente baseada no desempenho de cada aluno nas provas como previsto no critério fornecido no início do semestre.
  

• 10/12: a matéria da P3 consiste de algoritmos de caminhos mínimos, reduções e classes de complexidade.
• 29/11: farei um atendimento extra na terça 4/12 17h na minha sala.
• 21/11: as notas da P2 estão disponíveis no link acima. A revisão será amanhã às 17h na sala 43. Depois da revisão, farei o atendimento usual.
• 30/10: o plantão de dúvidas da semana que vem será feito na terça-feira 6/11 no horário usual.
• 30/10: ATENÇÃO! A matéria da prova P2 vai até Árvore Geradora Mínima (AGM). Os tópicos das aulas de 6/11 e 8/11 não serão cobrados na prova. Em princípio, a matéria da prova é cumulativa, mas a ênfase será em programação dinâmica, algoritmos gulosos, algoritmos em grafos (BFS, DFS, ordenação topológica) e AGM.
• 11/10: ATENÇÃO! As notas da P1 estão disponíveis no link acima. Se houver tempo, farei uma breve correção da prova em sala de aula. A revisão será hoje no horário de atendimento.
• 20/8: ATENÇÃO! Não haverá aula nem atendimento dia 30/8.
• 1/8: ATENÇÃO! O início das aulas será dia 14 de agosto de 2018.

  De 06 a 10 de agosto, teremos mais uma edição da Semana de Computação (Secomp). Trata-se de um evento acadêmico organizado pelas entidades estudantis AAACEC, CACo e Conpec, com o apoio do Instituto de Computação (IC), que tem por objetivo estreitar o relacionamento de estudantes da área de computação com tecnologias e temas de pesquisa relevantes na área, assim como aproximá-los da indústria de TI e de seus principais temas de interesse. Maiores detalhes acerca da programação estão no site .

  A participação dos alunos matriculados em MO417 será considerada parte das atividades acadêmicas em substituição às aulas desta semana.

  Além disso, os alunos deverão ler o Capítulo 1 do livro-texto CLRS (referência [3]; [1] ou [2] também serve).

• 25/7: IMPORTANTE! Consulte esta seção freqüentemente ao longo do semestre!

Horário das aulas e atendimento

• Aulas
  • terça-feira e quinta-feira, 14-16h, sala CC51 (sala 351 do IC 3) .
  
  
• Atendimento
• quinta-feira, 17-19h, sala 43, IC01.


• Observações:
  • passados 15 minutos do horário de início do atendimento, não havendo alunos aguardando, o atendimento fica automaticamente cancelado.

Objetivos

1. Análise de complexidade assintótica de algoritmos.
2. Projeto de algoritmos eficientes e elegantes para vários problemas computacionais básicos.
3. Natureza recursiva de vários problemas e como explorá-la para projetar algoritmos eficientes.
4. Complexidade computacional e classes de problemas.

Programa da disciplina

• Algoritmos, modelos de computação, análise de complexidade
  Leitura: [CLRS] Capítulo 1, 3
• Indução matemática - revisão
  Leitura: [Manber] Capítulo 2
• Somas, crescimento de funções e análise assintótica
  Leitura: [CLRS] Capítulo 3, [Manber] Capítulo 3
• Divisão-e-conquista
  Leitura: [CLRS] Seção 2.3, Capítulo 4 (em [3])
• Recorrências e métodos de resolução
  Leitura: [CLRS] Capítulo 4
• Projeto de algoritmos por indução
  Leitura: [Manber] Seções 5.2, 5.3, 5.4, 5.5, 5.7, 5.8, 5.9, 6.11.1, 6.11.2
• Busca binária e variações
  Leitura: [Manber] Seção 6.2
• Algoritmos de ordenação: selection sort, insertion sort e mergesort
  Leitura: [CLRS] Capítulo 2, [Manber] Seção 6.4
• Algoritmos de ordenação: heapsort
  Leitura: [CLRS] Capítulo 6, [Manber] Seção 6.4
• Filas de prioridade
  Leitura: [CLRS] Capítulo 6, [Manber] Capítulo 6
• Algoritmos de ordenação: mergesort e quicksort
  Leitura: [CLRS] Capítulo 2 e 7, [Manber] Seção 6.4
• Cota inferior de ordenação
  Leitura: [CLRS] Capítulo 8,[Manber] Seção 6.4
• Algoritmos lineares para ordenação
  Leitura: [CLRS] Capítulo 8, [Manber] Seção 6.4
• Estatísticas de ordem (order statistics)
  Leitura: [CLRS] Capítulo 9, [Manber] Seção 6.5
• Programação dinâmica
  Leitura: [CLRS] Seções 15.2, 15.3, 15.4 e Seção 15.1 (em [3]). Note que o problema tratado na Seção 15.1 é diferente na segunda e na terceira edição. Apresentarei o da terceira edição (referência [3]).
• Algoritmos gulosos
  Leitura: [CLRS] Seções 16.1, 16.2, 16.3
• Grafos: conceitos, busca em largura e busca em profundidade
  Leitura: [CLRS] Seções 22.1 a 22.3
• Grafos: ordenação topológica
  Leitura: [CLRS] Seção 22.4
• Grafos: componentes fortemente conexos
  Leitura: [CLRS] Seção 22.5
• Grafos: árvore geradora mínima
  Leitura: [CLRS] Capítulo 23
• Estrutura de dados para conjuntos disjuntos
  Leitura: [CLRS] Seções 21.1 a 21.3
• Grafos: caminhos mínimos
  Leitura: [CLRS] Capítulo 24
• Redução entre problemas
• Classes de problemas: P, NP, NP-completo. Provas de NP-completude.

Listas de Exercícios

Abaixo estão indicados vários exercícios do CLRS (referência [3]) e do Manber (referência [4]). Note que o Manber possui vários exercícios resolvidos. Exercícios adicionais serão sugeridos durante o semestre.

Sugere-se que cada aluno tente resolver individualmente os exercícios e só depois discutir em grupo. Dúvidas ou dificuldades devem ser discutidas com o docente.

1. [Básico]([CLRS] Capítulo 1): Exercícios 1.2-2, 1.2-3; Problema 1-1.
2. [Básico]([CLRS] Capítulo 2): Exercícios 2.1-3, 2.1-4, 2.2-2, 2.2-3, 2.3-3, 2.3-5, 2.3-6, 2.3-7; Problema 2-1.
3. [Notação assintótica, crescimento de funções] ([CLRS] Capítulo 3): Exercícios 3.1-1, 3.1-2, 3.1-3, 3.1-4, 3.1-6, 3.1-7, 3.1-8, 3.2-3; Problemas 3-1, 3-2, 3-3, 3-4.
4. [Indução] ([Manber] Capítulo 2): Exercícios 2.1, 2.4, 2.7, 2.9, 2.12, 2.14, 2.15 (substituindo, no enunciado, o número 81 por 49), 2.18 (substituindo, no enunciado, a palavra cycle por circle), 2.19, 2.21. Extra (faça pelo menos a 11 e a 12).
5. [Recorrências] ([CLRS] Capítulo 4): Exercícios 4.1-2, 4.1-5, 4.2-2, 4.2-4, 4.2-5, 4.3-1, 4.3-2, 4.3-4, 4.3-5, 4.4-2; Problemas 4-1, 4-3, 4-5.
6. [Projeto de algoritmos por indução] ([Manber] Capítulo 5): Exercícios 5.6, 5.12, 5.14, 5.15, 5.25a.
7. [Ordenação] ([Manber] Capítulo 6): Exercícios 6.14, 6.22, 6.23, 6.24, 6.25, 6.29.
8. [Heapsort] ([CLRS] Capítulo 6): Exercícios 6.1-4, 6.1-5, 6.2-1, 6.2-2, 6.2-3, 6.2-4, 6.2-6, 6.4-3, 6.4-4, 6.4-5, 6.5-8.
9. [Quicksort] ([CLRS] Capítulo 7): Exercícios 7.2-2, 7.2-3; Problemas 7-3, 7-4.
10. [Ordenação] ([Manber] Capítulo 6): Exercícios 6.11, 6.21, 6.34.
11. [Ordenação em tempo linear] ([CLRS] Capítulo 8): Exercícios 8.1-1, 8.1-2, 8.2-1, 8.2-2, 8.2-3, 8.2-4, 8.3-1, 8.3-3, 8.3-4, 8.4-1, 8.4-2; Problemas: 8-2, 8-3a, 8-6.
12. [Estatísticas de ordem] ([CLRS] Capítulo 9): Exercícios 9.2-1, 9.2-3, 9.2-4, Problemas: 9-1, 9-2;
13. [Estatísticas de ordem] ([CLRS] Capítulo 9): Exercícios 9.1-1, 9.3-1, 9.3-2, 9.3-3, 9.3-5, 9.3-6, 9.3-7, 9.3-8, 9.3-9.
14. [Programação dinâmica] ([CLRS] Capítulo 15): Exercícios 15.2-1, 15.2-2, 15.2-3, 15.3-2, 15.3-3, 15.3-5, 15.4-1, 15.4-2, 15.4-3, 15.4-4, 15.4-5, 15.4-6, 15.5-1, 15.5-2, 15.5-3; Problemas: 15-2, 15-6, 15-7.
15. [Algoritmos gulosos] ([CLRS] Capítulo 16): Exercícios 16.1-1, 16.1-2, 16.1-3, 16.1-4, 16.1-5, 16.2-1, 16.2-2, 16.2-3, 16.2-4, 16.2-5, 16.3-1, 16.3-4, 16.3-7, 16.3-8; Problemas: 16-1.
16. [Representação de grafos]([CLRS] Capítulo 22): Exercícios 22.1-1 a 22.1-6.
17. [BFS]([CLRS] Capítulo 22): Exercícios 22.2-1 a 22.2-9.
18. [DFS]([CLRS] Capítulo 22): Exercícios 22.3-1 a 22.3-12.
19. [Ordenação Topológica]([CLRS] Capítulo 22): Exercícios 22.4-1 a 22.4-5.
20. [Componentes Fortemente Conexos]([CLRS] Capítulo 22): Exercícios 22.5-1 a 22.5-7; Problema 22-1.
21. [AGM - Básico]([CLRS] Capítulo 23): Exercícios 23.1-1 a 23.1-11.
22. [AGM - Prim e Kruskal]([CLRS] Capítulo 21 e 23): Exercícios 21.2-1 a 21.2-2, 21.2-4 a 21.2-6; 23.2-1 a 23.2-5, 23.2-8; Problemas 23-1 e 23-4.
23. [CM - Grafos Orientados Acíclicos]([CLRS] Capítulo 24:) Exercícios 24.2-1 a 24.2-4; Problema 24-2.
24. [CM - Dijkstra]([CLRS] Capítulo 24:) Exercícios 24.3-1 a 24.3-8.
25. [CM - Bellman-Ford]([CLRS] Capítulo 24:) Exercícios 24.1-1 a 24.1-4, 24.1-6.
26. [CM - Sistemas de Diferenças]([CLRS] Capítulo 24:) Exercícios 24.4-1 a 24.4-8, 24.4-10 a 24.4-11.
27. [CM - Floyd-Warshall]([CLRS] Capítulo 25:) Exercícios 25.2-1 a 25.2-9.
28. [Redução e NP-completude] pdf1 e pdf2 (atualizado 5/12 - havia alguns exercícios que não deveriam estar nas listas)

Material didático

O material didático (slides) que será usado neste curso foi preparado pelo professor Cid Carvalho de Souza e por Cândida Nunes da Silva. O que disponibilizarei aqui será basicamente o mesmo com algumas adaptações, modificações e erros introduzidos por mim.

Esses slides foram preparados na época da segunda edição do CLRS (referência [2]). A terceira edição do CLRS (referência [3]) tem algumas diferenças em relação à anterior (alguns capítulos foram acrescentados e/ou modificados; a notação usada nos pseudo-códigos é mais similar a códigos de linguagens como Pascal ou C). Os slides não foram atualizados levando em conta essas mudanças (os pseudo-códigos usam o estilo de [2]).

O material serve principalmente como guia e de nenhum modo deve ser usado como única fonte de estudos. Para isso, deve-se consultar a bibliografia.

Os slides estão em arquivos no formato PDF (idênticos aos usados em aula) e serão disponibilizados ao longo do semestre.

• Introdução
• Indução
Na lista de exercícios extra de indução, você pode encontrar uma referência com uma explicação mais detalhada do método (livro do Rosen, mas há outros).
• Notação assintótica e classes de funções.
• Recorrências.
• Projeto de algoritmos por indução/divisão-e-conquista
• Algoritmos de ordenação.
• Cota inferior de ordenação e algoritmos lineares de ordenação.
• Estatísticas de ordem. (a matéria da P1 vai até aqui)
• Programação dinâmica: problema do corte de barra. (última atualização 27/09 17h)
• Programação dinâmica: multiplicação de cadeias de matrizes, subsequência comum de comprimento máximo. (última atualização 8/10 18h)
• Algoritmo guloso: seleção de atividades. (última atualização 9/10 13:45h)
• Algoritmo guloso: árvore de Huffman. (última atualização 11/10 13:45h)
• Grafos e representação (atualizado em 16/10)
• Busca em largura (atualizado em 17/10)
• Busca em profundidade, ordenação topológica (atualizado em 23/10)
• DFS - Componentes fortemente conexos (atualizado em 25/10)
• Árvore geradora mínima, algoritmos de Prim e Kruskal, estrutura de dados para conjuntos disjuntos (union-find) (atualizado em 30/10)
• Caminhos mínimos em grafos orientados acíclicos, algoritmo de Dijkstra, algoritmo de Bellman-Ford, algoritmo de Floyd-Warshall. (atualizado em 6/11)

Redução de problemas e classes de complexidade

• Reduções de problemas. (atualizado 27/11)
• Classes de complexidade. (atualizado 4/12)
• Veja também as notas de aula do Prof. Pedro Rezende. Para um texto mais completo sobre redução de problemas, veja a seção das referências.

Avaliação

• Critério de avaliação .

Datas importantes

• Para se inteirar dos feriados, prazos etc, consulte o calendário da DAC de 2018.
• Consulte o arquivo com o critério (acima) para ver as datas das provas.

Referências Bibliográficas

Os livros-texto do curso são as referências [3] (ou [1] ou [2]) e [4] (em algumas partes da matéria).

1. [Livro-texto] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algoritmos - Teoria e Prática, 2002.
   
2. T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, McGraw-Hill, 2001.

   As referências [1] e [2] são equivalentes e correspondem à segunda edição do CLRS.

3. T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms , McGraw-Hill, 2009.

A referência [3] é a terceira edição do livro.

4. [Livro-texto] U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.
   
   

Um mapeamento dos tópicos cobertos em sala de aula com os Capítulos dos livros-texto é mostrado na tabela abaixo:



Assunto	Cormen (referências [2]/[3]/[4])(capítulo/seção)	Manber (capítulo/seção)
Crescimento de funções	3	3.1, 3.2
Somas	Apêndice A	3.4
Fórmulas de Recorrência	4	3.5, 3.6
Fundamentos Básicos	Apêndice B, 10 e 21 (21.1 a 21.3)	4
Indução Matemática		2 e 5
Ordenação	6, 7 e 8	6.1 a 6.4
Estatísticas de Ordem	9	6.5
Busca Binária		6.1 a 6.3
Programação dinâmica	15	5.10
Algoritmos Gulosos	16.1 a 16.3	6.6
Algoritmos básicos em Grafos	22.1 a 22.4	7.3 a 7.4
Árvore Geradora Mínima	23	7.6
Caminhos Mínimos	24.1 a 24.3 e 25.1 a 25.2	7.5, 7.7 e 7.8
Reduções de problemas		10
Classes de problemas e provas de NP-completude	34	11

Aqui você encontrará uma errata da versão em português (referência [2]) do livro do Cormen, Leiserson, Rivest e Stein (referência [3]), preparada pelos Professores João Meidanis e Zanoni Dias com auxílio de alunos que cursaram esta disciplina anteriormente.

A página oficial do MIT Press contendo a errata da referência [3] pode ser encontrada aqui.

Além destes livros, existem nas bibliotecas da UNICAMP outras excelentes obras sobre os assuntos que serão referenciados na sala de aula. Dentre estas, destacamos as seguintes referências:

1. G. Brassard e P. Bratley, Algorithmics: theory and practice, Prentice-Hall, 1995.
2. N. Ziviani, Projeto de Algoritmos - 2a edição, Thomson, 2004.
3. A. Aho, J. Hopcroft, J. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
4. D. E. Knuth, The Art of Computer Programming, Addison-Wesley, 1974.
5. J. Kleinberg e É. Tardos, Algorithm Design, Addison-Wesley, 2006.

Redução entre problemas
1. P. J. de Rezende e J. Stolfi. Fundamentos de geometria computacional. Universidade Federal de Pernambuco, Departamento de Informatica, 1994. IX Escola de Computação, Recife, 24 a 31 de julho de 1994.
   Comentário: Uma boa leitura sobre reduções entre problemas.


Referências de Complexidade Computacional
1. C. H. Papadimitriou e K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc.,1982.
   Comentário: Uma boa fonte de referência na parte NP-completude, principalmente para explicar as técnicas de branch-and-bound e apresentar os conceitos básicos de algoritmos aproximados. Possui uma parte de programção linear bem ampla. Pode ser de difícil leitura.
2. E. Horowitz e S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1978.
   Comentário: Outra boa fonte de referência para NP-completude, algoritmos aproximados, algoritmos de branch-and-bound e backtracking.
3. M. Garey e D. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman. 1979.
   Comentário: Uma espécie de referência ``bíblica'' sobre a Teoria da Complexidade, mas não é de fácil leitura.
4. P. J. de Rezende e J. Stolfi. Fundamentos de geometria computacional. Universidade Federal de Pernambuco, Departamento de Informatica, 1994. IX Escola de Computação, Recife, 24 a 31 de julho de 1994.
   Comentário: Uma boa leitura sobre reduções entre problemas (segunda parte do curso).
5. M. Sipser. Introdução à Teoria da Complexidade. Editora Thomson, 2007.
   Comentário: A versão inglesa do livro é muito bem escrita e aborda de forma bem mais aprofundada vários tópicos que são vistos na disciplina.
6. H.R. Lewis e C.H. Papadimitriou. Elementos de Teoria da Computação. Bookman. 2a edição. 2000.
   Comentário: No mesmo nível do livro acima.