UFC - Universidade Federal do Ceará

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

Semestre: 2015.2
Horário: Segundas, Quartas e Sextas 08:00-10:00
Local: Auditório, Bloco 909
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 - Teste1 (4-Setembro) / Prova1 (14-Setembro) / Temas (notação assintótica, recorrências e divisão e conquista)
Lista 2 - Teste2 (9-Outubro) / Prova2 (19-Outubro) / Temas (programação dinâmica e algoritmos gulosos)
Lista 3 - Teste3 (13-Novembro) / Prova3 (23-Novembro) / Temas (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

InsertionSort: estimativa do tempo de um algoritmo
Notação Assintótica (O, Omega e Theta)
Recorrências, Árvore de recursão e o Método Mestre

Divisão e conquista

MergeSort
HeapSort
QuickSort (código C)
Limites inferiores para ordenação
CountingSort e RadixSort (código C)
Seleção do k-ésimo mínimo elemento: caso médio linear
Seleção do k-ésimo mínimo elemento: pior caso linear (código C)
Outros algoritmos de divisão e conquista: Karatsuba e Strassen

Programação dinâmica

Definição + Subestrutura Ótima
Problema da Linha de Montagem
Multiplicação de Sequências de Matrizes
Subsequência Comum mais Longa
Distância de Edição
Problema da Mochila (com/sem repetição)
Algoritmo de Floyd-Warshall (todas as distâncias em um grafo)

Algoritmo guloso

Definição
Um problema de escalonamento simples
Um problema de escalonamento menos simples
Código de Huffman

Classes de problemas

Livro-texto:

T. H. Cormen, C. E. Leiserson e R. L. Rivest, Algoritmos - Teoria e Prática, Editora Campus, 2014.
Dasgupta, Vazirani, Papadimitriou, Algoritmos, Editora McGraw Hill, 2011.

Bibliografia adicional:

M.Sipser, Introdução a Teoria da Computação, Thomson, 2007
J. Edmonds, Como Pensar sobre algoritmos, Editora LTC, 2010
T. Cormen, Desmistificando Algoritmos, Editora Campus, 2013
R. Sedgewick e P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 1996
V. Dobrushkin, Métodos para Análise de Algoritmos, Editora LTC, 2012

Material disponivel

Paulo Feofilof. Transparências da disciplina (cedidas pelo professor do IME-USP)
Paulo Feofilof. Homepage de Análise de Algoritmos (excelente material)