DC-UFRPE/Bacharelado em Ciência da Computação/Projeto e Análise de Algoritmos

Programa da Disciplina

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

• 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

• 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

• 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

• 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.