117536 - Projeto e Análise de Algoritmos

Table of Contents

Quadro de avisos:

  • Plano de Ensino
  • Uma longa noite aprendendo
  • Notas de Aulas
  • Todos os emails enviados ao professor devem conter a expressão [PAA] no assunto da mensagem.
  • [2018-03-07 Qua 11:25]: Aula de revisão com Felipe Rodopoulos
    • Dia e horário da aula: [2018-03-08 Qui 18:00]–[2018-03-08 Qui 19:00]
    • Tema da aula: Fundamentos matemáticos para a análise de algoritmos
      • Apêndices A e B da bibliografia principal (Cormen)
    • Local da aula: PJC BT 028
  • [2018-03-08 Qui 18:51]: Lista de exercícios de revisão: pdf (gabarito: pdf)
  • [2018-03-22 Qui 18:18]: Primeira lista de exercícios: pdf (gabarito: pdf)
  • [2018-04-06 Sex 22:56]: Gabarito da primeira prova (pdf)
  • [2018-04-25 Qua 18:23]: Aulas no LINF enquanto os pavilhões estiverem fechados.
  • [2018-05-14 Seg 13:19]: Revisão da prova 1 em [2018-05-29 Ter 21:00]–[2018-05-29 Ter 22:00]
  • [2018-05-14 Seg 20:53]: Gabarito de exercícios sobre grafos: pdf
  • [2018-05-21 Seg 10:56]: Gabarito da segunda prova (pdf)

Quadro de Notas

Matrícula Prova 1 Prova 2 Prova 3 Faltas(*) Faltas (%) Nota Final Menção
110035771       25 80.65 0.00 SR
110121058 2.0     6 19.35 0.67  
120012979 5.0     2 6.45 1.67  
120044919 5.0     1 3.23 1.67  
120120585 3.5     15 48.39 1.17 SR
120123631       25 80.65 0.00 SR
120127377 6.0     4 12.90 2.00  
120137232 8.5     3 9.68 2.83  
120137691 5.0     3 9.68 1.67  
120137852 5.0     4 12.90 1.67  
130007714 5.0     2 6.45 1.67  
130009130 1.5     3 9.68 0.50  
130040304 6.5     3 9.68 2.17  
130111236 6.0     6 19.35 2.00  
130123293 5.0     4 12.90 1.67  
130154253 5.5     4 12.90 1.83  
140031111 6.5     1 3.23 2.17  
140033262 4.0     4 12.90 1.33  
140133151 4.5     4 12.90 1.50  
140135839 5.5     5 16.13 1.83  
140140522 8.5     3 9.68 2.83  
140151010 5.0     1 3.23 1.67  
140153233 8.5     2 6.45 2.83  
140158995 7.5     5 16.13 2.50  
140159118 3.0     6 19.35 1.00  
140159355 5.5     5 16.13 1.83  
140160299 8.0     5 16.13 2.67  
150033010 7.5     1 3.23 2.50  
150044615 2.5     1 3.23 0.83  
150045123 7.5     5 16.13 2.50  
150058349 7.5     2 6.45 2.50  
150121814 6.5     4 12.90 2.17  
150126000 6.0     6 19.35 2.00  
150128215 8.0     4 12.90 2.67  
150137885 4.5     1 3.23 1.50  
150143753 7.0     6 19.35 2.33  
150145331 5.0     4 12.90 1.67  
150147384 6.5     3 9.68 2.17  
150149026       11 35.48 0.00 TR
160056659 6.0     3 9.68 2.00  

(*) Última atualização: [2018-06-21 Qui 18:46]

Calendário de aulas:

  1. [2018-03-06 Ter]: Introdução e Motivação
    1. Leituras sugeridas:
      1. Capítulo 1 e Seções 2.1 e 2.2, Cormen2009
      2. Seção 1.4, BaaseG99
      3. Seção 2.1, Levitin2012
  2. [2018-03-08 Qui]: Notação Assintótica
    1. Leituras sugeridas:
      1. Seção 3.1, Cormen2009
      2. Seção 1.5, BaaseG99
      3. Seção 2.2, Levitin2012
  3. [2018-03-13 Ter]: Análise de algoritmos não recursivos
    1. Leitura sugerida:
      1. Seções 2.3 e 4.1, Levitin2012
  4. [2018-03-15 Qui]: Análise de algoritmos recursivos
    1. Leitura sugerida:
      1. Seções 2.4, Levitin2012
  5. [2018-03-20 Ter]: Equações de recorrência
    1. Leitura sugerida:
      1. Apêndice B, Levitin2012
  6. [2018-03-22 Qui]: Prova do Teorema Mestre
  7. [2018-03-27 Ter]: Heapsort (Felipe Rodopoulos)
    1. Slides da aula: pdf
  8. [2018-03-29 Qui]: Quicksort e Merge sort.
  9. [2018-04-03 Ter]: Aula de exercícios (Felipe Rodopoulos)
  10. [2018-04-05 Qui]: Prova 1 (gabarito: pdf)

    [2018-04-10 Ter]: Aula cancelada (Paralisação Nota do Consuni)

  11. [2018-04-12 Qui]: Ordenação em tempo linear
    1. Seções 8.2 e 8.3, Cormen2009
  12. [2018-04-17 Ter]: Representação de grafos e busca em largura (BFS)
    1. Seções 22.1 e 22.2, Cormen2009
      • Exercícios sugeridos: 22.1-1, 22.1-2, 22.1-3, 22.1-5, 22.1-6, 22.1-7, 22.2-1, 22.2-2, 22.2-3, 22.2-4, 22.2-5
  13. [2018-04-19 Qui]: Caminho mínimo
    1. Seção 22.2, Cormen2009
      • Exercícios sugeridos: 22.2-6, 22.2-7, 22.2-8, 22.2-9
  14. [2018-04-24 Ter]: Busca em profundidade (Felipe Rodopoulos)
    1. Seção 22.3, Cormen2009
      • Exercícios sugeridos: 22.3-2, 22.3-3, 22.3-8, 22.3-9, 22.4-1, 22.4-2
      • Slides: pdf
  15. [2018-04-26 Qui]: Componentes fortemente conexas e árvores geradoras míninas (Felipe Rodopoulos)

    1. Local: LINF 4
    2. Seções 22.5 e 23.1, Cormen2009
      • Exercícios sugeridos: 22.5-1, 22.5-2, 22.5-3, 23.1-1, 23.1-2, 23.1-4, 23.1-10
      • Slides: pdf

    [2018-05-03 Qui] (Aula cancelada)

  16. [2018-05-08 Ter] Os algoritmos de Kruskal e Prim
    1. Local: PJC BT 028
    2. Seção 23.2, Cormen2009
      • Exercício sugerido: Faça a análise temporal do algoritmo de Prim, considerando que a lista de prioridades é implementada como um min-heap. E se a lista de prioridades for implementada como um vetor desordenado?
  17. [2018-05-10 Qui] O algoritmo de Dijkstra (Felipe Rodopoulos)
    1. Local: PJC BT 028
    2. Exercícios sugeridos: 24.3-1,24.3-2,24.3-3,24.3-6,24.3-10
    3. Slides: pdf
  18. [2018-05-15 Ter] Aula de exercícios (Felipe Rodopoulos)
    1. Local: PJC BT 028
  19. [2018-05-17 Qui] Prova 2
    1. Local: PJC BT 028
  20. [2018-05-22 Ter] Programação Dinâmica (Introdução)
    1. Local: PJC BT 028
    2. Seção 8.1 Levitin2012
      1. Exercícios sugeridos: 3, 6, 9 (p.290-291)
    3. Seção 15.1 Cormen2009
      1. Exercício sugerido: 15.1-5
  21. [2018-05-24 Qui] Multiplicação de cadeia de matrizes
    1. Local: PJC BT 028
    2. Seção 15.2 Cormen2009
    3. Exercícios sugeridos: todos os exercícios desta seção
  22. [2018-05-29 Ter] Programação Dinâmica e Algoritmos Gulosos

    1. Local: PJC BT 028

    [2018-05-31 Qui] Feriado

  23. [2018-06-05 Ter] O algoritmo de Bellman-Ford
    1. Local: PJC BT 028
    2. Seção 24.1 Cormen2009
    3. Exercícios sugeridos: todos os exercícios desta seção
  24. [2018-06-07 Qui] Caminho mínimo entre todos os pares de vértices
    1. Local: PJC BT 028
    2. Seção 25.1 Cormen2009
    3. Exercícios sugeridos: todos os exercícios desta seção
  25. [2018-06-12 Ter] O algoritmo de Floyd-Warshall (Felipe Rodopoulos)
    1. Local: PJC BT 028
    2. Seção 25.2 Cormen2009
    3. Slides pdf
    4. Exercícios sugeridos: 25.2-1, 25.2-3, 25.2-4 e exercício do slide (Floyd-Warshall recursivo)
  26. [2018-06-14 Qui] As classes P e NP
    1. Local: PJC BT 028
    2. Seções
    3. Exercícios sugeridos:
  27. [2018-06-19 Ter] NP-Completude e redutibilidade
    1. Local: PJC BT 028
    2. Seções
    3. Exercícios sugeridos:
  28. [2018-06-21 Qui] Problemas NP-Completos
    1. Local: PJC BT 028
    2. Seção
    3. Exercícios sugeridos:
  29. [2018-06-26 Ter] Aula de exercícios (Felipe Rodopoulos)
    1. Local: PJC BT 028
  30. [2018-06-28 Qui] Prova 3
    1. Local: PJC BT 028

Bibliography

  • [Cormen2009] Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Third Edition, The MIT Press (2009).
  • [BaaseG99] Baase & Gelder, Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley Longman Publishing Co., Inc. (1999).
  • [Gus97] Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press (1997).
  • [Levitin2012] Levitin, Introduction to the Design and Analysis of Algorithms, Third Edition, Addison-Wesley Longman Publishing Co., Inc. (2012).
  • [AHU83] Aho, Hopcroft & Ullman, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc. (1983).
  • [GK07] Greene & Knuth, Mathematics for the Analysis of Algorithms: Modern Birkhuser Classics, Birkh&\#228;user Basel (2007).
  • [McConnell01] McConnell, Analysis of Algorithms: An Active Learning Approach, Jones and Bartlett Publishers, Inc. (2001).
  • [tacp1] Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison Wesley Longman Publishing Co., Inc. (1997).
  • [Turing1936] Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, 2(42), 230-265 (1936). link.
  • [gries1981] Gries, The Science of Programming, Springer New York (1981).
  • [poaParberry94] Parberry, Problems on Algorithms, Prentice Hall (1995).
  • [KleinbergTardos] Jon Kleinberg, & \'Eva Tardos, Algorithm design, Addison-Wesley (2006).
  • [Weiss14] Weiss, Data Structures and Algorithm Analysis in C++ (4th Edition), Addison-Wesley Longman Publishing Co., Inc. (2014).
  • [curtis03] Curtis, The Classification of Greedy Algorithms, Science of Computer Programming, 49(1-3), 125-157 (2003). link. doi.
  • [Sipser] Sipser, Introduction to the Theory of Computation, International Thomson Publishing (1996).

Author: Prof. Flávio L. C. de Moura

Email: contato@flaviomoura.mat.br

Created: 2018-06-21 Qui 18:48

Validate