Complexidade de Algoritmos (1/03)

Programa da Disciplina

Objetivos:

• Desenvolver a capacidade de avaliar a complexidade e a qualidade dos algoritmos propostos para um determinado
  problema.
• Estudar os algoritmos básicos para as classes mais importantes de problemas tratados em computação.
• Compreender a importância da implementação e a sensibilidade do comportamento dos algoritmos à ela.
• Conhecer as potencialidades e as limitações do conhecimento algorítmico atual.
• Apresentar as tendências da pesquisa na área.

Ementa:

• Parte I - Projeto de Algoritmos
  Indução Matemática: Princípio de indução, indução forte, outras induções, provas por indução, erros comuns em indução, algoritmos e indução e definições indutivas.
  Projeto de Algoritmos por Indução: Teoremas, provas por indução e os algoritmos associados. Problemas: busca, ordenação, sequências em grafos: percorrimento em largura, em profundidade, árvores, caminhos eulerianos, caminho mais curto;   programação dinâmica.
  
• Parte II - 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, análise amortecida.
  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.
  Estruturas de Dados Avançadas: Árvores AVL, árvores vermelho-e-preta, listas de prioridade (heaps), d-heaps, heap binomial, heap de Fibonacci.
  Métodos Básicos: Programação dinâmica, método guloso, matróides, enumeração implícita, programação linear e inteira.
  
• Parte III - 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 IV - Tratamento de Problemas NP-completos/NP-difíceis.
  Técnicas e Conceitos Básicos: Algoritmos aproximados, algoritmos aproximativos, garantia de qualidade, busca
  heurística, algoritmos heurísticos versus algoritmos exatos, enumeração implícita e branch-and-bound.
  Tópicos Avançados: Formulações em programação linear inteira, formulações de fluxo, relaxação lagrangeana, método do subgradiente, heurísticas duais.
  

Bibliografia:

• Baase S. e Van Gelder A., Computer Algorithms: Introduction to Design and Analysis (3rd ed), Addison-Wesley, 2000.*
• Cormen, T., Leiserson, C., Rivest, R. e C. Stein, Introduction to Algorithms (2nd ed), MIT Press, 2001.*
  
• Manber U., Algorithms: A Creative Approach, Addison-Wesley, 1989.
• Aho, Alfred V. , Hopcroft, John E.  e Ullman, Jeffrey D., The design and analysis of computer algorithms, Reading: Addison-Wesley, 1974. 470p.
• Sedgewick R., Algorithms. Addison-Wesley, 1988
• Garey, M. Johnson, D., Computers and Intractability: a guide to the theory of NP-Completeness, Freeman, 1979.
• Ahuja R.K., Magnanti T.L. e Orlin J.B.,  Network Flows. Prentice Hall, 1993.