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

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

Semestre: 2012.2
Horário: Segundas, Quartas e Sextas 08:00-10:00
Local: Auditório da Matemática, 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:

Plano de Aula
Notas
Monitores: Rennan Ferreira Dantas e Eurinardo Rodrigues Costa

Listas de Exercícios

Lista 1 (notação assintótica, recorrências e divisão e conquista) (TESTE: Dia 20-set) (PROVA: Dia 27-set)
Lista 2 (programação dinâmica)
Lista 3 (algoritmos gulosos e complexidade computacional)

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

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)