PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2009.2
Horário: 2as-feiras e 4as-feiras de 15 às 17 horas
Local: 774L (2as e 4as)
ANÁLISE DE ALGORITMOS (INF 1721)
Objetivos: Desenvolver a capacidade de avaliar a complexidade e
a qualidade dos algoritmos propostos para um determinado
problema. Conhecer os algoritmos básicos para as classes mais
importantes de problemas tratados em computação.
CONTEÚDO
- Parte I Análise de Algoritmos
· Complexidade de Algoritmos: estimativa do tempo de
processamento, crescimento assintótico, notação , somas e relações
de recorrência, divisão e conquista.
· Algoritmos de busca e ordenação: árvores de busca,
heaps, união e busca, hashing, busca binária, ordenação
por inserção, ordenação por intercalação, ordenação rápida,
ordenação por caixas.
· Algoritmos em grafos: caminhamento, caminhos
eulerianos, caminho mais curto, árvores geradoras, componentes
conexos, caminhos hamiltonianos, cortes, fluxos em redes.
- Parte II Complexidade de Problemas
· Reduções e NP-completude: reduções , reduções
polinomiais, máquinas de Turing, não-determinismo, teorema de
Cook, NP-completude, provas de NP-completude,
hierarquia em complexidade computacional.
· Técnicas e Conceitos Básicos: algoritmos
aproximados, algoritmos aproximativos, garantia de qualidade, busca
heurística, algoritmos heurísticos × algoritmos exatos,
enumeração implícita e branch-and-bound, paralelismo.
BIBLIOGRAFIA
-
LIVRO TEXTO:
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest e C. Stein, Introduction
to Algorithms, Second edition, The MIT Press, Boston, 2001.
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest e C. Stein,
Algoritmos: Teoria e Prática, Campus, Rio de Janeiro, 2002.
-
T.H. Cormen, C.E. Leiserson e R.L. Rivest, Introduction
to Algorithms, McGraw-Hill, New York, 1990.
-
S. Dasgupta, C. Papadimitriou, e U. Vazirani, Algorithms,
McGraw Hill, New York, 2008. Disponível na URL: http://www.cs.berkeley.edu/ vazirani/algorithms.html
-
J. Kleinberg e E. Tardos, Algorithm Design, Addison Wesley, New York, 2005.
-
U. Manber, Algorithms: A Creative Approach,
Addison-Wesley, 1989.
-
R.E. Tarjan, Data Structures and Network Algorithms,
SIAM, 1983.
-
E. Horowitz e S. Sahni, Fundamentals of Computer Algorithms,
Computer Science Press, 1978-89.
-
R.K. Ahuja, T.L. Magnanti e J.B.Orlin,
Network Flows, Prentice Hall, 1993.
-
M. Garey e D. S. Johnson,Computers and
Intractability: A Guide to the Theory of NP-Completeness
W.H.Freeman and Company, 1979.
-
A. Aho e J. Ullman, Foundations of Computer Science,
Freeman, 1992.
-
S. Baase, Computer Algorithms,
Addison-Wesley, 1988.
-
R. Sedgewick,Algorithms,
Addison-Wesley, 1988.
-
G. Brassard e P. Bratley, Algorithmics: Theory and Practice, Prentice-Hall, 1988.
-
A. Aho, J. Hopcroft e J. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
AVALIAÇÃO
Serão realizadas três provas (P1, P2, P3), dois trabalhos, (T1 e T2) e,
se necessário um exame final (EX). As notas destas provas e trabalhos
determinam o grau MF. O critério de aprovação segue:
| MF = |
| 2P1 +4P2 +4P3 +3T1 +2T2 |
|
| 15 |
|
-
Se MF ³ 5.0 - Aprovado.
- Se MF < 5.0 - O aluno deverá fazer o exame (EX) e
terá nota final calculada pela a expressão:
-
Se NF ³ 5.0 - Aprovado.
Nota final = NF;
- Senão (NF < 5.0) - Reprovado.
Nota final = NF;
Datas:
P1 - 23/9 4a. feira 9-11 546L;
P2 - 4/11 4a. feira 9-11 546L;
P3 - 9/12 4a. feira 9-11 546L;
EX - 16/12 4a. feira 9-11 546L;
T1 - 23/11 (disponível em 23/9)
T2 - 21/12 (disponível em 23/11)
This document was translated from LATEX by HEVEA.