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

• 28/7: A maioria do material didático (vídeo e pdfs) ficarão disponíveis na página do Google Classroom (ainda não criada). Nesta página você encontrará sugestões de leitura dos tópicos que serão cobertos no curso, além de exercícios. Os exercícios são considerados parte do conteúdo da disciplina.
• 28/7: o critério de avalição também será colocado na página do Google Classroom.

Horário das aulas e atendimento

• Aulas
  • segunda-feira,   19-21h.
  • quarta-feira,  21-23h.
  
  


• Atendimento:
  • PED (Caroline): TBA.
  • PAD (Renan): TBA.

Objetivos

1. Análise assintótica de complexidade de algorimos
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. Vários algoritmos e técnicas para problemas de natureza computacional

Programa da disciplina

• Algoritmos, modelos de computação, análise de complexidade
  Leitura: [CLRS] Capítulo 1, 3
• 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, [3] Capítulo 4
• Indução matemática - revisão
  Leitura: [Manber] Capítulo 2
• 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, 15.5; [3] Seção 15.1. Note que o problema tratado na Seção 15.1 é diferente na segunda e na terceira edição. Eu apresentarei o da terceira edição (referência [3]).
• Algoritmos gulosos
  Leitura: [CLRS] Seções 16.1, 16.2, 16.3

Listas de Exercícios

Abaixo estão várias listas de exercícios. Elas foram compiladas pelo professor Pedro Rezende e acrescentei alguns. Além de servir para maior fixação do material apresentado em classe, o conteúdo dos exercícios é considerado parte integrante do material visto e tratado como parte coberta da matéria. A entrega deles não será cobrada. Entretanto, para o bom aprendizado da disciplina é necessário que cada aluno tente fazer individualmente os exercícios e só depois discutir em grupo. Dúvidas ou dificuldades devem ser discutidas com o docente ou o PED/PAD.

1. Lista 1 [Básico]([CLRS] Capítulo 1): Exercícios 1.2-2, 1.2-3; Problema 1-1.
2. Lista 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. Lista 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. Lista 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. Lista 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 b., 4-4 a., c., d., e., f., h., i..
6. Lista 6 [Projeto de algoritmos por indução] ([Manber] Capítulo 5): Exercícios 5.6, 5.12, 5.14, 5.15, 5.25a.
7. Lista 7 [Ordenação] ([Manber] Capítulo 6): Exercícios 6.14, 6.22, 6.23, 6.24, 6.25, 6.29.
8. Lista 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. Lista 9 [Quicksort] ([CLRS] Capítulo 7): Exercícios 7.2-2, 7.2-3; Problemas 7-3, 7-4.
10. Lista 10 [Ordenação] ([Manber] Capítulo 6): Exercícios 6.11, 6.21 6.34.
11. Lista 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. Lista 12 [Estatísticas de ordem] ([CLRS] Capítulo 9): Exercícios 9.2-4, Problemas: 9-1a.,b,c;
13. Lista 13 [Estatísticas de ordem] ([CLRS] Capítulo 9): Exercícios 9.1-1, 9.3-3, 9.3-5, 9.3-7, 9.3-8, 9.3-9.
14. Lista 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-4, 15-6, 15-7. Extra
15. Lista 15 [Algoritmos gulosos] ([CLRS] Capítulo 16): Exercícios 16.1-1, 16.1-2, 16.1-3, 16.1-5 , 16.1-4, 16.2-3,16.2-4, 16.2-5, 16.3-1, 16.3-4, 16.3-7, 16.3-8; Problemas: 16-1. Aula

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 material que disponibilizarei aqui foi baseado no deles com algumas adaptações, modificações e erros introduzidos por mim.

Deixo claro que 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.

O material será disponibilizado na página do Google Classroom.

Referências Bibliográficas

Os livros-texto do curso são as referências [1] (ou [2]) e [4] (na parte de projeto de algoritmos por indução).

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, Introduction to Algorithms , McGraw-Hill, 2009.

A referência [3] é a terceira edição do livro.
Ela é a que apresenta algumas diferenças em relação às anteriores (este comentário se aplica apenas aos capítulos que envolvem tópicos desta disciplina).

Eis as diferenças que percebi (olhando apenas o índice):

• Capítulo 4 (é mais longo e nas edições anteriores chama-se Recorrências enquanto aqui chama-se Divide-and-Conquer);
• Seção 15.1 (usa um exemplo mais simples que das edições anteriores).

Você pode usar [3] como livro-texto, se quiser.

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

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.