MAC5811 Projeto e Análise de Algoritmos
Está disciplina consiste de uma avaliação que faz parte dos Exames
Preliminares do Doutorado em Ciência da Computação.
Este exame é aplicado no início e
no meio de cada ano. No 1o. semestre de 2005 o exame de
Análise de Algoritmos (AA) será no dia 4 de março, na sala de
reuniões do Bloco C, com início às 14:00.
Os doutorandos interessados em fazer o exame no primeiro semestre de
2005 deverão matricular-se em MAC5811. A matrícula deverá ser feita na
secretaria da CPG entre os dias 3 e 7 de janeiro.
Exames anteriores de AA podem ser encontrados na página
de Exames
Preliminares de Análise de Algoritmos.
O conteúdo do exame pode ser visto na ementa
de MAC5811.
Principais tópicos do exame são:
- Noções sobre modelos de computação e eficiência de algoritmos.
- Notação assintótica.
- Resolução de recorrências.
- Probabilidade discreta.
- Projeto e análise de algoritmos de divisão-e-conquista.
- Algoritmos de busca e ordenação.
- Projeto e análise de algoritmos de programação dinâmica.
- Projeto e análise de algoritmos gulosos.
- Projeto e análise de algoritmos probabilísticos.
- Projeto e análise de algoritmos de ordenação e busca, medianas e
estatísticas de ordem
- Projeto e análise de algoritmos
sobre cadeias de caracteres, matrizes, polinômios, grafos e aritmética
inteira.
- Uso e análise de estruturas de dados avançadas: árvores de
busca binária, filas com prioridade, hashing, union-find.
- Complexidade computacional.
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.
- Compêndio de exercícios de análise de algoritmos, Departamento de
Ciência da Computação do IME-USP.
Matriculados no 1o. semestre
David Correa Martins Junior
João Henrique Burckas Ribeiro
Marcelo de Moura Amorim
Márcio Katsumi Oikawa
Thiago Teixeira Santos
Esta página é melhor visualizada
com um computador e um monitor.
Toca do coelho.
Last modified: Wed Jan 26 19:47:10 BRST 2005