MAC 5711 Análise de Algoritmos

A disciplina manterá uma lista eltrônica. Inscreva-se visitando esta página.
Home page da lista eletrônica de MAC 5711.

O arquivo das mensagens da lista encontra-se nesta página.

O arquivo das questões do Exame Preliminar de Análise de Algoritmos para o Doutorado está nesta página.

O livro texto será:

T.H. Cormen, C.E. Leiserson e R.L. Rivest
Introduction to Algorithms
The MIT Press e McGraw-Hill, 1990.
Uma segunda edição deve sair possivelmente ainda este ano.

Outros livros importantes para a disciplina são:

R. Sedgewick
Algorithms in C, Third Edition, Parts 1-4
Addison Wesley, 1998 Second edition, 1990

R. S. Skiena
The Algorithm Design Manual
Springer Telos, 1998 (com CD-ROM).

Muito material referente a este livro pode ser encontrado na teia mundial. Recomendamos em especial visitar as páginas de duas outras disciplinas do IME baseadas neste livro:
MAC 5711 - Análise de Algoritmos
e MAC0338 Análise de Algoritmos (disciplina de graduação)

Recomendamos ainda a consulta às notas desta disciplina, similares ao que desejamos desenvolver aqui:
MACS 406: Design and Analysis of Algorithms
desenvolvida por Manavendra Misra, Colorado School of Mines.
Atenção: muita informação contida nestas páginas não será repetida aqui!

Aula de 10ago99. Introdução. Ordenação por inserção. Seção 1.1.

Aula de 13ago99. Ordenação por inserção (análise) e Ordenação por intercalação. Seções 1.2 e 1.3 (início). Divisão e conquista.

Aula de 17ago99. Análise de Merge-sort. Quicksort, o algoritmo e análise do pior caso. Seções 1.3, 8.1 e 8.2 (parte).
Entregar a primeira lista de exercícios na aula de 24ago99.

Aula de 20ago99. Quicksort, continuação. Seções 8.2 e 8.3.

Aula de 24ago99. Análise do tempo médio de Quicksort. Seção 8.4. Entregar a segunda lista de exercícios na aula de 03set99.

Aula de 27ago99. Capítulo 7, Heapsort. Próximos assuntos: Master Theorem, Seções 4.3 e 4.4. Limites inferiores para ordenação: Seção 9.1. Procure se manter na frente das aulas com a leitura do livro.

A primeira prova da disciplina será realizada no dia 21set99 às 14:00.

Aula de 31ago99. Filas de Prioridade, Seção 7.5. Teorema Master, Seções 4.3 e 4.4. Entregar a terceira lista de exercícios na aula de 14set99.

Aula de 03set99. Limite inferior para ordenação. Ordenação em tempo linear. Capítulo 9. Próximos assuntos: Capítulos 10, 12, 13 e 14.

A primeira prova foi realizada em 21set99.

Programação Dinâmica, Capítulo 16. Aulas de 19out99 e 26out99.

A segunda prova foi realizada em 05nov99.

A primeira fase do projeto deve ser entregue até 05nov99.

Algoritmos Gulosos. Capítulos 17 e 24. Aulas de 29out99 e 09nov99.

Análise amortizada. Capítulo 18. Aula de 12nov99.

Complexidade e problemas NP-completos. Aulas de 16nov99 e 19nov99.

Grafos: representação e algoritmos. Um curso relâmpago. Capítulo 23 e tinturas dos Capítulos 25, 26 e 27. Aula de 23nov99.

A terceira prova acontecerá em 26nov99.

O projeto deve ser entregue até 10dez99.

MAC 5711 Análise de Algoritmos