UFC - Bacharelado em Ciência da Computação

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

Semestre: 2012.1
Horário: Terças e Quintas 08:00-10:00
Local: sala de reuniões - Bloco 910
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 (complexidade computacional)

Trabalhos de Implementação

Trabalho 1 (entrega dia ??/??)

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 parcial em ??/??/09, às 08:00h (inclui toda a matéria vista até então)
segunda parcial em ??/??/09, às 08:00h (inclui toda a matéria vista desde a primeira prova)
terceira parcial em ??/??/09, às 08:00h (inclui toda a matéria vista desde a segunda prova)

AF em ??/??/09 às 08:00 (inclui toda a matéria)

2o chamada das parciais em ??/??/09 às 08:00 (inclui toda a matéria - será ao final do semestre)
2o chamada da AF em ??/??/09 às 08:00 (inclui toda a matéria)

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)
Michael Sipser. Capítulo 7 do Livro "Introdução a Teoria da Computação"
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)