nandayot/19190002787-analise-de-algoritmo

Gitbook criado para fazer minhas anotações sobre a disciplina de Projeto e Análise de Algoritmo 1 que estou cursando no 4 semestre de Ciência da Computação na UFMS

description
Gitbook criado para fazer minhas anotações sobre a disciplina de Projeto e Análise de Algoritmos que estou cursando no 4º semestre de Ciência da Computação na UFMS.

Introdução

Objetivo

Desenvolver nos estudantes a capacidade de avaliar a complexidade e a qualidade dos algoritmos propostos para diversos problemas computacionais.

Estudar os algoritmos básicos para as classes mais importantes de problemas tratados em Computação.

Compreender a importância da implementação e a sensibilidade do comportamento dos algoritmos levando em consideração parâmetros importantes tais como tempo de execução, memória usada, comunicação entre processos, etc.

Conhecer as potencialidades e as limitações do conhecimento algorítmico atual.

Apresentar as tendências da pesquisa na área de algoritmos.

Ementa

Introdução à Análise de Algoritmos

• Crescimento e Notação Assintótica de Funções
• Indução, Recorrências, Demonstração de Correção de Algoritmos.

Técnicas de Desenvolvimento de Algoritmos:

• Divisão e Conquista
• Método Guloso
• Programação Dinâmica.
• As classes P e NP. NP-completude e Reduções.

Programação

1. Papel dos algoritmos em Computação
2. Preliminares
3. Crescimento de funções
4. Divisão e conquista
5. Heapsort
6. Quicksort
7. Ordenação em tempo linear
8. Medianas e k-ésimo menor elemento
9. Programação dinâmica
10. Algoritmos gulosos
11. Algoritmos em grafos
12. Complexidade de problemas, NP-completude e redução polinomial

Bibliografia

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein, Introduction to Algorithms, 3a. ed., MIT Press, 2009
2. P. Feofiloff. Minicurso de Análise de Algoritmos, http://www.ime.usp.br/∼pf/livrinho-AA/AA-BOOKLET.pdf, 2011
3. J. Kleinberg e E. Tardos, Algorithms Design, Addison-Wesley, 2006
4. 4. U. Manber, Algorithms: A Creative Approach, Addison-Wesley, 1989
5. R. Sedgewick, Algorithms, Addison-Wesley, 2004

Conteúdo tirado dos slides do professor da disciplina Fábio Henrique Viduani Martinez - FACOM/UFMS; Todos os créditos reservados a ele.