DC-UFRPE/Bacharelado em Ciência da Computação/Projeto e Análise de Algoritmos
Programa da Disciplina
editar| Nome: | PROJETO E ANÁLISE DE ALGORITIMOS |
| Código: | 14087 |
| Departamento: | Departamento de Computação (DC) |
| Área: | Computação |
| Carga-horária total: | 60 horas |
| Créditos: | 4 |
| Pré-requisitos: | ALGORITMOS E ESTRUTURAS DE DADOS (Cód. 06214) |
Ementa
editar- Medidas de complexidade;
- Análise assintótica de limites de complexidade;
- Técnicas de prova de cotas inferiores;
- Exemplos de análise de algoritmos iterativos e recursivos;
- Técnicas de projeto de algoritmos eficientes;
- Programação dinâmica;
- Algoritmos probabilísticos.
Conteúdo
editar- O que é uma prova matemática?;
- Problemas, instâncias, algoritmos e tempo;
- Análise assintótica: ordens Ο, Ω e Θ;
- Solução de recorrências;
- Recursão;
- Problemas e algoritmos;
- Análise da ordenação por inserção;
- Exemplo de análise probabilística;
- Análise da busca binária;
- Análise do algoritmo Mergesort;
- Análise do algoritmo Quicksort;
- A estrutura heap;
- Análise do algoritmo Heapsort;
- Filas de prioridades;
Bibliografia Básica
editar- CORMEN, Thomas H. et. al. Algoritmos: Teoria e Prática. Editora Campus, 2002;
- FEOFILOFF, Paulo. Algoritmos em Linguagem C. Editora Campus/Elsevier, 2008-2009;
- ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Pascal e C. 2. ed. rev. e ampl. São Paulo: Thomson, 2005.
Bibliografia Complementar
editar- MANBER, U. Introduction to Algorithms: A Creative Approach. Addison Wesley, 1989;
- PATASHNIK, O.; GRAHAM, R. L.; KNUTH, D. E. Matemática Concreta: Fundamentos para a Ciência da Computação. Segunda edição. Rio de Janeiro: LTC, 1995. 475 p;
- BRASSARD, G; BRATLEY, P. Fundamentals of Algorithmics, Prentice Hall, 1996;
- DASGUPTA, S; PAPADIMITRIOU, C.; VAZIRANI, U.V. Algorithms, McGraw-Hill, 2006. Versão em Português (2009);
- KLEINBERG, J; TARDOS, E. Algorithm Design, Addison-Wesley, 2005.