PUC-Rio Departamento de Informática Prof. Marcus Vinicius S. Poggi de Aragão Período: 2003.1 Horário: 2as-feiras e 4as-feiras de 17 às 19 horas Local: 452L (2as) - 452L (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 Teoria da Complexidade
· 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.
Parte III Tratamento de Problemas NP-completos.
· 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 e R.L. Rivest, Introduction
to Algorithms, McGraw-Hill, New York, 1990.
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.
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.
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 (graus P1, P2 e P3), que são
utilizadas para obter o grau G1 juntamente com o grau TP de 2 trabalhos
práticos pequenos e o grau TG um trabalho grande. Estes trabalhos
podem ser feitos em grupo de dois. Um exame
final (EX) será realizado por aqueles que não forem aprovados
com o grau G1. A nota final será calculada de acordo com a fórmula
e com o critério de aprovação abaixo: