UFC - Mestrado e Doutorado em Ciência da Computação

Construção e Análise de Algoritmos (CKP747)

Semestre: 2009.1
Horário: Segundas e Quartas 16:00-18:00
Local: sala 1064-A Bloco 915
Atendimento: Na minha sala, em qualquer horário, desde que com reserva antecipada. Uma reserva pode ser feita via correio eletrônico ou na sala de aula.

Avisos Importantes:

Listas de Exercícios

Lista 1 (notação assintótica, recorrências e divisão e conquista)
Lista 2 (programação dinâmica)
Lista 3 (algoritmos gulosos)
Lista 4 (classes de complexidade de tempo, reduções e aproximabilidade)

Ementa:

Um algoritmo é um processo sistemático para a resolução de um problema em um computador. O objetivo desse processo é a obtenção do resultado de um problema a partir da manipulação de certas informações inicialmente conhecidas e de novas informações obtidas ao longo da execução do algoritmo. O conteúdo deste curso é formado por diversas técnicas de projeto de algoritmos. A ementa do curso é a seguinte:

Introdução

Introdução
Recursividade
Princípio da indução matemática
As notações O, Ômega e Teta
Estimativa de tempo de execução de algoritmos (complexidade)
Algoritmos ótimos

Divisão e conquista

Definição
Problema de ordenação
"MergeSort": Ordenação por intercalação
"QuickSort"
Limites inferiores para ordenação

Programação dinâmica

Definição + Subestrutura Ótima
Multiplicação de cadeias de matrizes
Cálculo da maior subcadeia comum
Todas as distâncias em um grafo
Problema da mochila

Algoritmo guloso

Definição
Um problema simples de escalonamento
Código de Huffman
Coloração de vértices

Classes de problemas

Introdução
Classe P
Classe NP
Redução polinomial
Classes NP-Completo e NP-Difícil

Avaliação:

primeira em 15/04/09, às 16:00h (inclui toda a matéria vista até então)
segunda em 22/06/09, às 16:00h (inclui toda a matéria vista desde a primeira prova)

Livro-texto:

T. H. Cormen, C. E. Leiserson e R. L. Rivest, Introduction to Algorithms, MIT Press e McGraw-Hill, 1990.
T. H. Cormen, C. E. Leiserson e R. L. Rivest, Algoritmos - Teoria e Prática, Editora Campus, 2002.

Bibliografia adicional:

R. Sedgewick e P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 1996
N. Ziviani, Projeto de Algoritmos, com Implementações em Pascal e C, 2a edição, Thomson, 2004.
A. V. Aho e J. D. Ullman, Foundations of Computer Science, W. H. Freeman Company, 1992.
Jayme L. Szwarcfiter, Algoritmos em Grafos, Editora Campus, 1987.
M.Sipser, Introdução a Teoria da Computação, Thomson, 2007

Material disponivel

Paulo Feofilof. Transparências da disciplina (cedidas pelo professor do IME-USP)
Paulo Feofilof. Homepage de Análise de Algoritmos (excelente material)
Papadimitriou e Vazirani, 2006. Livro "Algorithms" (muito bom)
Programação Dinâmica. Linha de Montagem e Multiplicação de Sequência de Matrizes

Material adicional

Marcelo Henriques de Carvalho et al, Uma Introdução Sucinta a Algoritmos de Aproximação, UFMS, UFRJ, UNICAMP, USP, 2001 (link)

Yoshiharu Kohayakawa, José Augusto R. Soares, Demonstrações Transparentes e Impossibilidade de Aproximações, IME-USP, 1995 pdf)