PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2006.2
Horário: 2as-feiras e 4as-feiras de 9 às 11 horas
Local: 422L (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.
- LIVRO TEXTO (português):
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.
-
J. Kleinberg e E. Tardos, Algorithm Design, Addison Wesley, New York, 2005.
-
M. Garey e D. S. Johnson,Computers and
Intractability: A Guide to the Theory of NP-Completeness
W.H.Freeman and Company, 1979.
-
U. Manber, Algorithms: A Creative Approach,
Addison-Wesley, 1989.
-
R.K. Ahuja, T.L. Magnanti e J.B.Orlin,
Network Flows, Prentice Hall, 1993.
-
A. Aho e J. Ullman, Foundations of Computer Science,
Freeman, 1992.
-
R.E. Tarjan, Data Structures and Network Algorithms,
SIAM, 1983.
-
E. Horowitz e S. Sahni, Fundamentals of Computer Algorithms,
Computer Science Press, 1978-89.
-
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 = |
| 3P1 +3P2 +5P3 +2T1 +2T2 |
|
| 15 |
|
O aluno poderá optar por não fazer os trabalhos de implementação, o que
deverá ser comunicado ao professor por email para a conta ``poggi@inf.puc-rio.br''
com assunto (subject) ``AA062 Trabalhos'' até a data de realização da P2. Nesse caso
o grau MF é calculado da seguinte forma:
-
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 - 13/9 4a. feira 9-11 422L;
P2 - 18/10 4a. feira 9-11 422L;
P3 - 29/11 4a. feira 9-11 422L;
EX - 6/12 4a. feira 9-11 422L;
This document was translated from LATEX by HEVEA.