UFC - Departamento de Computação

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

Semestre: 2021.1
Horário: Segundas e Quartas 08:00-10:00
Local: Aulas Remotas
Atendimento: Por meio do SIGAA da disciplina ou por email.

Apresentação:

Listas de Exercícios

Lista 1 (notação assintótica, recorrências e divisão e conquista) (C++) (SOLUÇÃO)
Lista 2 (programação dinâmica e algoritmos gulosos) (C++)
Lista 3 (algoritmos gulosos e 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

Introdução - InsertionSort (C++) (slides)
Notação Assintótica (O, Omega e Theta) (slides)
Recorrências, Árvore de recursão e o Método Mestre (slides)

Divisão e conquista

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

Programação dinâmica

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

Algoritmos gulosos

Definição
Um problema de escalonamento simples (slides)
Um problema de escalonamento menos simples (slides)
Mochila Fracionária (slides)
Código de Huffman (slides)
Algoritmo de Dijkstra para Menor Caminho (C++) (entrada) (slides)
Algoritmos de Kruskal e Prim para Árvore Geradora Mínima (C++) (entrada) (slides)

Classes de problemas

Introdução
Classes P e NP (slides)
Redução polinomial (slides)
Classes NP-Completo e NP-Difícil (slides)

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:

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)