Disciplina Discipline MAC5711
Análise de Algoritmos

Analysis of Algorithms

Área de Concentração: 45134

Concentration area: 45134

Criação: 14/06/2019

Creation: 14/06/2019

Ativação: 14/06/2019

Activation: 14/06/2019

Nr. de Créditos: 8

Credits: 8

Carga Horária:

Workload:

Teórica

(por semana)

Theory

(weekly)

Prática

(por semana)

Practice

(weekly)

Estudos

(por semana)

Study

(weekly)

Duração Duration Total Total
4 2 4 12 semanas 12 weeks 120 horas 120 hours

Docentes Responsáveis:

Professors:

Arnaldo Mandel

Cristina Gomes Fernandes

Yoshiharu Kohayakawa

Marcel Kenji de Carli Silva

Objetivos:

A disciplina tem por objetivo: rever algoritmos clássicos, fazer a análise do seu desempenho e desenvolver a capacidade de classificar problemas computacionais e algoritmos de acordo com a sua complexidade.

Justificativa:

O projeto de algoritmos é uma atividade fundamental na computação e a análise é parte indispensável nesse projeto.

Conteúdo:

1) Notação assintótica. 2) Recorrências. 3) Mergesort. 4) Quicksort. 5) Filas de prioridade e heapsort. 6) Ordenação em tempo linear. 7) Programação dinâmica. 8) Algoritmos elementares para grafos. 9) Árvore geradora mínima. 10) Caminhos mínimos. 11) Complexidade computacional.

Forma de Avaliação:

Média ponderada das notas em listas de exercícios, projetos e provas.

Observação:

Bibliografia:

1. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 2nd.ed., MIT Press & McGraw-Hill, 2001. 2. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Algoritmos: Teoria e Prática, Campus, 2002. 3. J. Kleinberg and E. Tardos, Algorithm Desing, Addison-Wesley, 2006. 4. A.V. Aho and J.D. Ullman, Foundations of Computer Science, Computer Science Press, 1992. 5. G. Brassard and P. Bratley, Fundamentals of Algorithmics, Prentice Hall, 1996. 6. U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.