MAC5811 Projeto e Análise de Algoritmos
ATENÇÃO: O exame não será mais no Bloco C, o local
do exame será a sala 259 do bloco A.
Está disciplina consiste de uma avaliação que faz parte dos Exames
Preliminares do Doutorado em Ciência da Computação.
Este exame é aplicado nos meses de março e
agosto de cada ano. No 1o. semestre de 2007 o exame de
Análise de Algoritmos (AA) será no dia 2 de março, na sala de
reuniões do Bloco C, com início às 14:00.
Os doutorandos que pretendem se submeter ao exame no primeiro
semestre de 2007 deverão se matricular em
MAC5811. A matrícula deverá ser feita na secretaria da CPG até 5 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
- Alexandre Noma
- Carlos Henrique Aguena Higa
- Daniel Oliveira Dantas
- Fábio Roberto de Miranda
- Jesus Pascual Mena Chalco
- João Carlos Néto
- Karla Roberta Pereira do Nascimento
- Kelly Rosa Braghetto
- Marco Antonio Torrez Rojas
- Paulo Salem da Silva
- Rafael Pereira Luna
- Sandro Pereira Vilela
Examinadores
- Arnaldo Mandel
- José Augusto Ramos Soares
- José Coelho de Pina
Last modified: Fri Mar 2 12:53:38 BRT 2007