117536 - Projeto e Análise de Algoritmos

Table of Contents

Quadro de avisos:

  • Uma longa noite aprendendo
  • Plano de Ensino
  • Notas de aulas (em constante atualização)
  • Todos os emails enviados ao professor devem conter a expressão [PAA] no assunto da mensagem.
  • [2018-08-28 Ter 09:35]: Primeira lista de exercícios (pdf)
    • O gabarito será divulgado no dia [2018-09-13 Qui]
      • [2018-09-13 Qui 11:36]: Gabarito (pdf)
  • [2018-09-21 Sex 09:23]: Gabarito da prova 1 (pdf)
  • [2018-09-28 Sex 17:56]: A revisão da prova 1 será feita no dia [2018-10-02 Ter 20:30]–[2018-10-02 Ter 21:00]
  • [2018-10-22 Seg 10:32]: Palestra "Surprising Mathematics". Prof. Piergiorgio Odifreddi
    • Data: 24 de outubro de 2018
    • Local: Auditório da FT/UnB
    • Divulgação UnB/TV: link

Quadro de Notas

  Matrícula Prova 1 Prova 2 Prova 3 Faltas(*) Faltas (%) Nota Final Menção
1 110121058 4.0     3 9.68 1.33  
2 120006634 4.5     3 9.68 1.50  
3 120130424 2.0     7 22.58 0.67  
4 130047660 2.0     2 6.45 0.67  
5 130135640       6 19.35 0.00  
6 130154989       5 16.13 0.00  
7 140030395 5.5     2 6.45 1.83  
8 140045023       8 25.81 0.00 TR
9 140146407       2 6.45 0.00  
10 140153641 5.0     1 3.23 1.67  
11 140155571 3.0     3 9.68 1.00  
12 140159401 7.0       0.00 2.33  
13 140161244 7.5     1 3.23 2.50  
14 140168915 7.0     1 3.23 2.33  
15 140170723 5.0     1 3.23 1.67  
16 140177043 5.5     3 9.68 1.83  
17 150018371 4.5     1 3.23 1.50  
18 150023031 6.0       0.00 2.00  
19 150032552 7.5     3 9.68 2.50  
20 150038381       8 25.81 0.00 SR
21 150078676 3.5     1 3.23 1.17  
22 150080727 5.5     1 3.23 1.83  
23 150115474 6.0     5 16.13 2.00  
24 150117531 5.0       0.00 1.67  
25 150126689 6.5     2 6.45 2.17  
26 150129921 4.5     6 19.35 1.50  
27 150132085 5.5     1 3.23 1.83  
28 150132425 4.0     2 6.45 1.33  
29 150143290 8.5       0.00 2.83  
30 150143362 6.0     6 19.35 2.00  
31 150143672 5.0     1 3.23 1.67  
32 150145608 5.0     1 3.23 1.67  
33 150153538 3.5       0.00 1.17  
34 150154135 5.0       0.00 1.67  
35 160005256 8.0     1 3.23 2.67  
36 160007607 6.5     5 16.13 2.17  
37 160019311 9.0     4 12.90 3.00  
38 160025737 10.0     1 3.23 3.33  
39 160031672 9.0     1 3.23 3.00  
40 160036691 4.5     4 12.90 1.50  
41 160046688 3.0     1 3.23 1.00  
42 160071852 6.5     1 3.23 2.17  
43 160117461       9 29.03 0.00 SR
44 180046322 2.5       0.00 0.83  
45 180135287       17 54.84 0.00 SR

(*) Última atualização: [2018-10-18 Qui 18:40]

Calendário de aulas:

  1. [2018-08-14 Ter] Introdução e Motivação: Algoritmos de ordenação
    1. Leituras sugeridas:
      1. Seções 2.1 e 2.2, Cormen2009
        1. Exercícios: 2.1-3, 2.1-4, 2.2-2, 2.2-3 e 2.2-4.
  2. [2018-08-16 Qui] Algoritmos de ordenação: Merge Sort
    1. Leituras sugeridas:
      1. Seção 2.3, Cormen2009
        1. Exercícios: 2.3-3, 2.3-4, 2.3-5, 2.3-6 e 2.3-7.
  3. [2018-08-21 Ter] Notação Assintótica
    1. Leituras sugeridas:
      1. Capítulo 3, Cormen2009
        1. Exercícios: 3.1-1 - 3.1-8
        2. Exercícios adicionais e anotações de aula: pdf
  4. [2018-08-23 Qui] Equações de recorrência
    1. Leituras sugeridas:
      1. Seção 4.3 e 4.4, Cormen2009
  5. [2018-08-28 Ter] Teorema Mestre
    1. Leituras sugeridas:
      1. Seção 4.5, Cormen2009
        1. Exercícios: 4.5-1, 4.5-3,
    2. Primeira lista de exercícios (pdf)
  6. [2018-08-30 Qui] Teorema Mestre
    1. Leituras sugeridas:
      1. Seção 4.6, Cormen2009
  7. [2018-09-04 Ter] Heapsort
    1. Leituras sugeridas:
      1. Capítulo 6, Cormen2009
        1. Exercícios: 6.1-1, 6.1-2, 6.1-3, 6.1-4, 6.3-3, 6.4-3, 6.4-4.
      2. Notas de aula: pdf
  8. [2018-09-06 Qui] Quicksort
    1. Leituras sugeridas:
      1. Capítulo 7, Cormen2009
        1. Exercícios: 7.2-2, 7.2-3, 7.4-1, 7.4-2, 7.4-3, 7.4-5.
      2. Notas de aula: pdf
  9. [2018-09-11 Ter] Ordenação em tempo linear
    1. Leituras sugeridas:
      1. Capítulo 8, Cormen2009
      2. Notas de aula: pdf
  10. [2018-09-13 Qui] Aula de exercícios
    1. Gabarito da lista 1 (pdf)
  11. [2018-09-18 Ter] Aula de exercícios
  12. [2018-09-20 Qui] Prova 1
    1. Gabarito (pdf)

      [2018-09-25 Ter] Semana Universitária

      [2018-09-27 Qui] Semana Universitária

  13. [2018-10-02 Ter] Programação Dinâmica
    1. Leituras sugeridas:
      1. Seções 15.1 e 15.2, Cormen2009
  14. [2018-10-04 Qui] Programação Dinâmica
    1. Leituras sugeridas:
      1. Seção 15.3, Cormen2009
  15. [2018-10-09 Ter] Algoritmos gulosos
    1. Leituras sugeridas:
      1. Capítulo 16, Cormen2009
  16. [2018-10-11 Qui] Algoritmos em Grafos: Busca em largura
    1. Leituras sugeridas:
      1. Seções 22.1 e 22.2, Cormen2009
  17. [2018-10-16 Ter] Algoritmos em Grafos: Busca em profundidade
    1. Leituras sugeridas:
      1. Seções 22.3, 22.4 e 22.5, Cormen2009
  18. [2018-10-18 Qui] Árvore geradora mínima: Algoritmos de Kruskal e Prim
    1. Leituras sugeridas:
      1. Capítulo 23, Cormen2009
  19. [2018-10-23 Ter] Algoritmo de Bellman-Ford
    1. Leituras sugeridas:
      1. Seções 24.1 e 24.2, Cormen2009
  20. [2018-10-25 Qui] Algoritmo de Dijkstra
    1. Leituras sugeridas:
      1. Seções 24.3 e 24.5, Cormen2009
  21. [2018-10-30 Ter] Caminho mínimo entre todos os pares de vértices
    1. Leituras sugeridas:
      1. Seção 25.1, Cormen2009
  22. [2018-11-01 Qui] Algoritmo de Floyd-Warshall
    1. Leituras sugeridas:
      1. Seção 25.2, Cormen2009
  23. [2018-11-06 Ter] Algoritmo de Johnson
    1. Leituras sugeridas:
      1. Seção 25.3, Cormen2009
  24. [2018-11-08 Qui] Aula de exercícios
  25. [2018-11-13 Ter] Prova 2

    [2018-11-15 Qui] Feriado

  26. [2018-11-20 Ter] As classes P e NP
    1. Leituras sugeridas:
      1. Seções 34.1 e 34.2, Cormen2009
  27. [2018-11-22 Qui] NP-Completude e redutibilidade
    1. Leituras sugeridas:
      1. Seção 34.3, Cormen2009
  28. [2018-11-27 Ter] Problemas NP-Completos
    1. Leituras sugeridas:
      1. Seções 34.4 e 34.5, Cormen2009
  29. [2018-11-29 Qui] Problemas NP-Completos
    1. Leituras sugeridas:
      1. Seção 34.5, Cormen2009
  30. [2018-12-04 Ter] Aula de exercícios
  31. [2018-12-06 Qui] Prova 3

    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).
    • [tacp3] Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison Wesley Longman Publishing Co., Inc. (1998).
    • [patashnik.04:_concr] Graham, Knuth, & , Concrete mathematics : a foundation for computer science, Addison-Wesley (2004).
    • [CLRS_Solutions_Manual] @UnpublishedCLRS_Solutions_Manual, author = Michelle Bodnar and Andrew Lohr, title = Introduction to Algorithms - Solutions Manual, year = 2015
    • [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).
    • [rosen.12:_discr] Discrete mathematics and its applications, McGraw-Hill (2012).

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

Email: contato@flaviomoura.mat.br

Created: 2018-10-22 Seg 22:11

Validate