MAC5811 Projeto e Análise de Algoritmos

ATENÇÃO: O exame será no dia 2 de maio, quarta-feira, das 14 às 19 horas, na sala de reuniões do Bloco C.

Está disciplina vale 4 créditos e consiste de uma avaliação que faz parte dos antigos Exames Preliminares do Doutorado em Ciência da Computação.

A matrícula na disciplina está aberta até dia 9 de março, sexta-feira, e deve ser feita na Secretaria da Pós-Graduação (sala 23-B) do IME.

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

1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, 3nd. ed. ed., MIT Press & McGraw-Hill, 2009.
2. J. Kleinberg and É. Tardos, Algorithm Design, Addison-Wesley, 2005.
3. Compêndio de exercícios de análise de algoritmos, Departamento de Ciência da Computação do IME-USP.

Examinadores

• Arnaldo Mandel
• Cristina Gomes Fernandes
• José Augusto Ramos Soares