Disciplina: Projeto e Análise de Algoritmos – BCC241 – 2/2013
Turmas: 11
Prof. Anderson Almeida Ferreira
Horário: 13h30 às 15h10
Segunda-feira e quarta-feira: Sala 209 - Pavilhão de Aulas
Ementa:
Medidas de complexidade.
Análise assintótica de complexidade.
Medidas empíricas.
Análise de algoritmos iterativos e recursivos.
Noções de teoria da complexidade.
Estratégias de projeto de algoritmos:
divisão e conquista,
método guloso,
programação dinâmica,
backtracking,
branch&bound,
probabilísticos.
Objetivos:
Ao final do curso espera-se que os alunos possuam os seguintes conhecimentos e habilidades:
Dados dois algoritmos, compará-los quanto aos diferentes critérios de desempenho, identificando o melhor
Dado um problema, identificar, entre as diversas estratégias estudadas, aquela(s) que melhor se aplica(m) e implementá-la(s)
Conteúdo Programático:
Apresentação do Curso.
Panorama e Conceitos Básicos.
Medidas de Complexidade (tempo, espaço). Análise Assintótica.
Algoritmos Probabilísticos.
Divisão e Conquista (D&C).
D&C e Análise: Teorema Mestre.
D&C e Cota Inferior : MergeSort.
D&C e Probabilístico: Medianas, QuickSort
D&C e Empírico: Exponencial
Gulosos:
Conceitos.
Árvores Geradoras Mínimas - Prim & Kruskal.
Código de Huffman
Cláusula de Horn
Problema da Mochila
Seleção de atividades
Programação Dinâmica (PD):
Conceitos.
DAG
Maior Sequência Crescente
Distância de Edição
Problema da Mochila
Multiplicação de Cadeia de Matrizes
Classes de Complexidade
Problemas de Busca: Decisão e Otimização
Classe P
Classe NP
Problemas NP-Difíceis
Problemas NP-Completos
Redução de Problemas
Busca Exaustiva e Busca Exaustiva Inteligente (Backtracking & Branch-and-Bound)
Algoritmos Aproximados
Processo Avaliativo:
Provas teóricas:
Prova I - 13/11/2013 - Valor 10 pontos - Peso 2
Prova II - 18/12/2013 - Valor 10 pontos - Peso 2
Prova III - 05/02/2014 - Valor 10 pontos - Peso 3
Exame Especial - 17/02/2014 - Valor 10 pontos
Trabalhos e exercícios práticos - Valor 10 pontos - Peso 3
[DPV] Algoritmos, S. Dasgupta, C. Papadimitriou, U. Varizani, McGraw-Hill, 2009. Versão gratuita em inglês disponível em (http://www.cs.berkeley.edu/~vazirani/algorithms.html).
[Silva] Projeto e Análise de Algoritmos, Elton Silva, Apostila do Curso, 2010.
[CLRS] Algoritmos: Teoria e Prática, Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Cliford Stein. 2a. edição, 2001.
Complementar
[Hrom] Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms. Jurai Hromkovi?, 2005.
[LLM] Mathematics for Computer Science, Eric Lehman, Tom Leighton, Albert Meyer, 2010. (Disponível em http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/).
[Shafer] A Pratical Introduction to Data Structures and Algorithms Analysis (C++ or Java), Clifford Shaffer, 2011 (Disponível em http://people.cs.vt.edu/~shaffer/Book/)
[BB] Fundamentals of Algorithmics, Gilles Brassard and Paul Bratley, Prentice Hall, 1996.