Carregando...

DISCIPLINA Listagem de Ementa/Programa

PROJETO E ANÁLISE DE ALGORITMOSDISCIPLINA 117536

VER OFERTA

ÓrgãoCIC Departamento de Ciência da Computação
Código117536
DenominaçãoProjeto e Análise de Algoritmos
NívelGraduação
Vigência1971/2
Pré-requisitos MAT 113034 Cálculo 1 E
CIC 117889 Tecnicas de Programação 1 OU
MAT 113034 Cálculo 1 E
CIC 116319 ESTRUTURAS DE DADOS OU
MAT 200107 Cálculo 1 - Semipresencial E
CIC 116319 ESTRUTURAS DE DADOS
Ementa

Fundamentos matemáticos para análise de algoritmos; Análise assintótica de algoritmos; Paradigmas de projeto de algoritmos; Algoritmos eficientes para ordenação, comparação de sequências, problemas em grafos; Fundamentos de complexidade computacional, redução entre problemas, classes P e NP, problemas NP-Completos.

Programa

1. Fundamentos matemáticos para análise de algoritmos:
1.1. Indução Finita;
1.2. Crescimento de funções;
1.3. Notação Assintótica (O,o,Omega,omega,Theta);
1.4. Relações de Recorrência; resolução por substituição(indução) e por iteração;

2. Análise assintótica de algoritmos (conceitos a serem exemplificados no item 4.):
2.1. Modelos de computação;
2.2. Cotas superiores e inferiores;
2.3. Algoritmos ótimos;

3. Paradigmas de projeto de algoritmos (conceitos a serem exemplificados no item 4.):
3.1. Projeto por indução;
3.2. Divisão-e-conquista;
3.3. Algoritmos gulosos;
3.4. Programação Dinâmica;

4. Algoritmos eficientes:
4.1. Algoritmos para ordenação: bubble-sort, insertion-sort, merge-sort, heap-sort, quick-sort;
4.2. Cota inferior para ordenação por comparações;
4.3. Seleção do k-ésimo e da mediana em tempo linear;
4.4. Busca binária;
4.5. Árvore de busca ótima e fatoração ótima para multiplicação de matrizes;
4.6. Comparação de sequências: maior subsequência comum, algoritmo Knuth-Morris-Pratt para busca de substring; distância de edição; algoritmo Smith-Waterman;
4.7. Conceito de Análise Amortizada (por exemplo, algoritmo KMP);
4.8. Algoritmos em Grafos: busca em largura e profundidade; caminho mínimo e algoritmos de Dijkstra e Bellman-Ford; árvore espalhada mínima e algoritmos e Prim e Kruskal; todos os caminhos mínimos e algoritmo de Floyd-Warshall; fluxo máximo e algoritmo de Ford-Fulkerson;
4.9. Algoritmos geométricos: envoltória convexa: algoritmo da Marcha de Jarvis; ordenação angular e o algoritmo Graham Scan;
4.10. Cota inferior para envoltória convexa por redução;

5. Fundamentos de complexidade computacional:
5.1. Redução entre problemas e transferência de cotas;
5.2. Classe P;
5.3. Algoritmos não-determinísticos; Verificação polinomial de solução;
5.4. Classe NP;
5.5. NP-Completude;
5.6. Exemplos: SAT, Clique em grafos, Problema da mochila, Soma de subconjuntos, 3-coloração, Caminho e circuito hamiltonianos, Caixeiro viajante, e outros.

Bibliografia

T. Cormen, C. Leiserson, R. Rivest e C. Stein, 2a, Algoritmos: Teoria e Prática, Campus, 2002
S. Dasgupta, C. Papadimitriou e U. Vazirani, 1a, Algoritmos, McGraw-Hill, 2009
U. Manber, 1a, Introduction to Algorithms: a Creative Approach, Addison-Wesley, 1989
M. Sipser, 2a, Introdução à Teoria da Computação, Thompson, 2007
F. Preparata e M. Shamos, 1a, Computational Geometry, Springer, 1985