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
  • [2018-11-14 Qua 15:01]: Gabarito da prova 2 (pdf)
  • [2018-11-26 Seg 14:50]: Link para a Prova 3
  • [2018-11-27 Ter 11:03]: Uma caneta S-pen (samsung) foi encontrada na aula passada (sala PJC BT 028). O dono pode recuperá-la comigo (foto): sala 3 (prédio CIC/EST).
  • A revisão de menção será feita em [2018-12-13 Qui 13:30]–[2018-12-13 Qui 15:00]

Quadro de Notas

  Matrícula Prova 1 Prova 2 Prova 3 Faltas(*) Faltas (%) Nota Final Menção
1 110121058 4.0 5.5 6.5 3 9.68 5.33 MM
2 120006634 5.0 3.5 6.5 5 16.13 5.00 MM
3 120130424 3.5 0.0   11 35.48 1.17 II
4 130047660 2.0 7.5 5.5 3 9.68 5.00 MM
5 130135640       14 45.16 0.00 SR
6 140030395 5.5 3.5 6.5 4 12.90 5.17 MM
7 140045023       8 25.81 0.00 TR
8 140146407   4.5 6.5 3 9.68 3.67 MI
9 140153641 5.0 3.0 7.5 2 6.45 5.17 MM
10 140155571 3.0 4.0 5.0 5 16.13 4.00 MI
11 140159401 7.5 9.5 10.0   0.00 9.00 SS
12 140161244 7.5 6.0 3.5 2 6.45 5.67 MM
13 140168915 7.0 8.0   2 6.45 5.00 MM
14 140170723 5.0 4.0 7.5 1 3.23 5.50 MM
15 140177043 5.5 4.5 5.0 6 19.35 5.00 MM
16 150018371 4.5 8.0 5.5 1 3.23 6.00 MM
17 150023031 6.0 5.5 7.5   0.00 6.33 MM
18 150032552 8.5 6.5 7.5 3 9.68 7.50 MS
19 150078676 3.5 6.0 5.5 3 9.68 5.00 MM
20 150080727 5.5 6.5 5.5 2 6.45 5.83 MM
21 150115474 6.0 5.0 6.5 6 19.35 5.83 MM
22 150117531 5.0 7.5 4.0   0.00 5.50 MM
23 150126689 6.5 8.0 5.5 3 9.68 6.67 MM
24 150129921 4.5     9 29.03 1.50 TR
25 150132085 5.5 5.5 4.5 1 3.23 5.17 MM
26 150132425 4.0 8.5 4.5 2 6.45 5.67 MM
27 150143290 8.5 10.0 10.0   0.00 9.50 SS
28 150143362 6.0 7.5 8.5 6 19.35 7.33 MS
29 150143672 5.0 6.5 4.0 1 3.23 5.17 MM
30 150145608 5.0 5.0 7.0 1 3.23 5.67 MM
31 150153538 3.5 5.0 6.5 1 3.23 5.00 MM
32 150154135 5.0 9.5 7.0   0.00 7.17 MS
33 160005256 8.0 6.5 8.0 2 6.45 7.50 MS
34 160007607 6.5 8.5   7 22.58 5.00 MM
35 160019311 9.0 8.5   4 12.90 5.83 MM
36 160025737 10.0 8.0 6.5 2 6.45 8.17 MS
37 160031672 9.0 7.0 6.5 2 6.45 7.50 MS
38 160036691 4.5 7.0 8.0 5 16.13 6.50 MM
39 160046688 3.0 5.0   3 9.68 2.67 II
40 160071852 6.5 4.0 5.5 2 6.45 5.33 MM
41 160117461       14 45.16 0.00 SR
42 180046322 2.5     2 6.45 0.83 II
43 180135287       22 70.97 0.00 SR

(*) Última atualização: [2018-12-13 Qui 16:04]

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 e Floyd-Warshall
    1. Leituras sugeridas:
      1. Seções 25.1 e 25.2, Cormen2009
  22. [2018-11-01 Qui] Algoritmo de Johnson
    1. Leituras sugeridas:
      1. Seção 25.3, Cormen2009
  23. [2018-11-06 Ter] Aula de exercícios
  24. [2018-11-08 Qui] Aula de exercícios
  25. [2018-11-13 Ter] Prova 2

    Gabarito da prova 2 (pdf)

    [2018-11-15 Qui] Feriado

DONE As classes P e NP <2018-11-20 Ter>

  1. Leituras sugeridas:
    1. Seções 34.1 e 34.2, Cormen2009

DONE NP-Completude <2018-11-22 Qui>

  1. Leituras sugeridas:
    1. Seção 34.3, Cormen2009

DONE Atendimento em sala <2018-11-27 Ter>

  1. Leituras sugeridas:
    1. Seções 34.4 e 34.5, Cormen2009

DONE Revisão da prova 2 <2018-11-29 Qui>

  1. Leituras sugeridas:
    1. Seção 34.5, Cormen2009

DONE Atendimento em sala <2018-12-04 Ter>

DONE Prova 3 <2018-12-06 Qui> (link)

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
  • [manberAlgorithms] Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA (1989).
  • [everythingAA] @BookleteverythingAA, author = Jeff Erickson, title = Algorithms, year = 2009, url = http://www.uiuc.edu/~jeffe/teaching/algorithms/
  • [PracticalAA2014] Dana Vrajitoru, Practical Analysis of Algorithms, Springer International Publishing (2014).
  • [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-12-13 Qui 16:05

Validate