GRUPO: Núcleo de Formação Teórica

OBJETIVOS GERAIS DA DISCIPLINA: Introduzir as técnicas básicas de eficiência de algoritmos, com cálculo de tempo de pior caso e tempo médio. Isto é feito com a apresentação de um grande número de algoritmos que servem de ponto de partida para o desenvolvimento de novos algoritmos. Considera-se também uma introdução ao estudo comparativo dos principais métodos de computação, particularmente nos aspectos de complexidade de tempo e de espaço de problemas computacionais.

EMENTA DO PROGRAMA:

- Análise de Algoritmos –  Tempo de Execução - Notação assintótica

- Técnicas de estruturação de Algoritmos.

- Algoritmos de Ordenação, 

- Estruturas de dados elementares e avançadas

- Programação dinâmica – algoritmos gulosos

- Algoritmos de Busca em grafos.

DESCRIÇÃO DO PROGRAMA: 

1. Fundamentos

• Algoritmos – Análise de Algoritmos  – Tempo de Execução no pior caso e caso médio  Projeto de Algoritmos

• Crescimento de funções – notação assintótica

• Recorrência 

• Análise probabilistica e algoritmos aleatórios

2. Algoritmos de Ordenação

• Heapsort

• Quicksort

• Ordenação em tempo linear

• Medianas e estatísticas de ordem

3. Estrutura de Dados Elementares

• Pilhas, filas, listas, ponteiros e objetos

• Tabela Hash

• Arvores binárias

• Estatisticas de ordem dinâmicas

4. Técnicas Avançadas de Projeto e Análise

• Programação dinâmica

• Algoritmos Gulosos

5. Estruturas de Dados Avançadas

• Arvores B

• Heaps binomiais

• Heaps de Fibonacci

• Estruturas de dados para conjuntos – Algoritmos de Manipulação de Conjuntos

6. Algoritmos de grafos

• Algoritmos elementares de grafos

• Arvores espalhadas mínimas

• Caminhos mais curtos – de única origem e de todos os pares

• Algoritmo de Floyd-Warshall

• Algoritmo de Johnson para grafos esparsos

• Fluxo Máximo – Método de Ford-Fulkerson

• Emparelhamento bipartido máximo

• Algoritmos de push-relabel

BIBLIOGRAFIA:

01. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, MIT Press, 3ª Edição,  2009.
(Edição em portugues : “Algoritmos-Teoria e Prática”, Editora Campus 2003)

02. David Harel and Yishai Feldman. Algorithmics: The Spirit of Computing, 3a Edição, Addison Wesley, 2004. 

03. Steven S. Skiena: The Algorithm Design Manual.  Springer, 2a Edição., 2008. 

04. Donald E. Knuth. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1.  (Series in Computer Science & Information Processing) Addison-Wesley Professional, 2011. 

05 Bernhard Korte, Jens Vygen. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics), 4a Edição, 2010.

06. Vijay V. Vazirani. Approximation Algorithms. Addison-Wesley 2001