UFC - Universidade Federal do Ceará

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

Semestre: 2016.2
Horário: Segundas, Quartas e Sextas 08:00-10:00
Local: Auditório, Bloco 916
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 (graficos)

Listas de Exercícios

Lista 1 - Teste1 (18-Setembro) / Prova1 (28-Setembro) / Temas (notação assintótica, recorrências e divisão e conquista) (C++)
Lista 2 - Teste2 (21-Outubro) / Prova2 (28-Outubro) / Temas (programação dinâmica e algoritmos gulosos) (C++)
Lista 3 - Teste3 (28-Novembro) / Prova3 (02-Dezembro) / Temas (complexidade computacional) (SOLUÇÃO)

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++)
Limites inferiores para ordenação
CountingSort e RadixSort (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++)
Outros algoritmos de divisão e conquista: Karatsuba e Strassen

Programação dinâmica

Definição + Subestrutura Ótima
Subsequência Comum mais Longa (C++)
Distância de Edição (C++)
Multiplicação de Sequências de Matrizes (C++)
Problema da Mochila (C++)
Algoritmo de Floyd-Warshall (C++) (entrada)

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)