CI709 - Análise de Algoritmos

Primeiro semestre de 2006

local: Anf. na 4a e PC05 na 6a

Sumário: Conteúdo -- Bibliografia -- Avaliação -- Listas de exercícios -- Programa -- Calendario -- Notas -- Atendimento

Conteúdo:

Elementos de análise assintótica
Análise de desempenho (pior caso e caso médio) de alguns algoritmos clássicos: ordenação, hashing, manipulação de árvores binárias, algoritmos sobre de cadeias de caracteres, matrizes polinômios, grafos e aritmética inteira.
Técnicas de projeto de algoritmos: divisão-e-conquista, programação dinâmica, algoritmos gulosos, algoritmos probabilísticos.
Noções da teoria de complexidade: as classes P, Np, e CoNP.
Análise experimental de algoritmos

Objetivos: Carga horária: 60 Créditos: 4 Responsável: Jair.

Bibliografia:

T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 2nd.ed.ed., MIT Press & McGraw-Hill, 2001.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C.Stein, Algoritmos: Teoria e Prática, Campus, 2002.
R. Sedgewick, P Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, 1996.
D.E. Knuth, The Art of Computer Programming: Sorting and Searching, e ed., Reading, Mass.: Addison-Wesley, c1998.
U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.

Sistema de avaliação:

Media ponderada de media das listas com peso 1, e media de 2 provas com peso 4.

Calendário

06/03 - Início das aulas
14/04 - Feriado: Sexta-feira santa
21/04 - Feriado: Tiradentes
10/05 - Prova 1 conteúdo das aulas 01 -- 12
12/05 - Prazo para cancelamento de matrícula
23/06 - Prova 2: conteúdo das aulas 16 -- 29
26/06 - Último dia letivo

 
      January 2006            February 2006              March 2006     
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
      1  2  3  4  5  6  7               1  2  3  4               1  2  3  4 
      8  9 10 11 12 13 14      5  6  7  8  9 10 11      5  6  7  8  9 10 11 
     15 16 17 18 19 20 21     12 13 14 15 16 17 18     12 13 14 15 16 17 18 
     22 23 24 25 26 27 28     19 20 21 22 23 24 25     19 20 21 22 23 24 25 
     29 30 31                 26 27 28                 26 27 28 29 30 31 
                                                        

      April 2006                May 2006                June 2006      
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
                        1         1  2  3  4  5  6                  1  2  3 
      2  3  4  5  6  7  8      7  8  9 10 11 12 13      4  5  6  7  8  9 10 
      9 10 11 12 13 14 15     14 15 16 17 18 19 20     11 12 13 14 15 16 17 
     16 17 18 19 20 21 22     21 22 23 24 25 26 27     18 19 20 21 22 23 24 
     23 24 25 26 27 28 29     28 29 30 31              25 26 27 28 29 30 
     30

Listas de exercícios

Tópicos das aulas

Aula 01 - Problema computacional. Representação. Complexidade de tempo. Pior caso. Caso Médio. Aula 02 - Notação assintótica: O, Omega, Teta, o, omega. Aula 03 - Notação assintótica: exemplos. Aula 04 - Recorrências: solução exata - Merge Sort Aula 05 - Recorrências: estimativas. Aula 06 - Heap/HeapSort. Aula 07 - Quicksort. Aula 08 - Cota inferior para ordenação. Algoritmos de tempo linear para ordenação. Aula 09 - Mediana e outras ordens em tempo linear. Aula 10 - Busca. Caso médio da busca binária. Aula 11 - Árvores binárias de busca. Aula 12 - Árvores balanceadas de busca. Aula 13 - Hashing. Aula 14 - Prova Aula 15 - Discussão da prova Aula 16 - Programação dinâmica. Aula 17 - Programação dinâmica. Aula 18 - Método Guloso. Aula 19 - Análise amortizada. Aula 20 - union-find Aula 21 - union-find Aula 22 - Algoritmos probabilísticos. Aula 23 - Algoritmos probabilísticos. Aula 24 - P e NP. Aula 25 - NP-completude. Aula 26 - Prova Aula 27 - Análise experimental de algoritmos. Aula 28 - Análise experimental de algoritmos. Aula 29 - Análise experimental de algoritmos. Aula 30 - prova sub

Horário de atendimento aos alunos:

- 3a. das 13:30 as 16:00hs
- 4a. das 17:30 as 19:00hs
- ou em horário agendado previamente por email: se eu nao responder o seu email num prazo razoável ele pode ter sido decaptado pelo spamassassin. Esse não será o caso se você enviá-lo pelo seu endereço da universidade.
NÃO ATENDO EM DIA DE PROVA.