Análise e
Técnicas de Algoritmos
Jorge César
Abrantes de Figueiredo
Período: 2008.2
Avisos:
Horário: T102 e X082
Sala: CD107
Ementa: Análise de Complexidade de algoritmos. Análise Assintótica.
Divisão-e-conquista. Problemas de otimização. Algoritmos gulosos. Programaçao
dinâmica. Backtracking. Problemas NP-Completos. Aplicações.
Objetivos: Curso voltado para
o estudo de técnicas e análise de algoritmos. Em especial, o curso contemplará
várias técnicas de criação de algoritmos, o estudo da complexidade
computacional de algoritmos, além de vários exemplos de
algoritmos para a solução de problemas importantes e comumente encontrados na
prática.
Avaliação: A avaliação
constará de 3 exames parciais. A nota final corresponde a média aritmética das
3 notas parciais. Todo aluno tem direito a fazer apenas uma reposição. Não
existe a figura de reposição da menor nota. O aluno pode olhar a prova e
discutir a sua nota até 10 dias após a sua publicação. As datas dos exames de avaliação já estão definidas:
Planejamento das Aulas: O curso está dividido em três partes. A primeira parte enfatiza os
fundamentos e conceitos básicos de algoritmos. A segunda parte contempla
técnicas avançadas de projeto e análise de algoritmos. A última parte é
dedicada a aplicações de algoritmos, bem como ao estudo dos problemas
NP-Completos. O detalhamento do programa é o seguinte:
Parte I
1.
Motivação para o estudo de Algoritmos
Função dos algoritmos na computação. Conceitos
básicos. Exemplos.
2.
Corretude de Algoritmos
Prova por indução. Invariantes de laço.
Corretude de algoritmos recursivos e não-recursivos.
3.
Análise da complexidade de algoritmos
Análise assintótica. Complexidade de tempo.
Análise de algoritmos simples. Relação de recorrência. Análise de algoritmos
recursivos.
4.
Análise de Algoritmos de Ordenação
Algoritmos baseados em comparação. Complexidade
de algoritmos de ordenação. Outros algoritmos.
Parte II
5.
Divisão-e-conquista
Idéia geral. Exemplos. Análise.
6.
O Método Guloso
Introdução aos problemas de otimização. A
estratégia gulosa. Exemplos clássicos: mochila fracionária e cálculo do trôco.
Códigos de Huffman. Complexidade de algoritmos gulosos.
7.
Programação dinâmica
Idéia central. Exemplos clássicos: mochila
binária, multiplicação de matrizes, subseqüência máxima. Complexidade de
algoritmos de programação dinâmica.
8. Backtracking e Branch-and-Bound
Idéia geral. Exemplos.
Parte III
9.
Algoritmos sobre grafos
Algoritmos elementares. Árvore de cobertura
mínima. Ordenação topológica. Caminho mais curto de origem única. Caminho mais
curto de todos os pares.
10. Casamento de
Padrões
Principais algoritmos. Complexidade dos
algoritmos.
11. Outras Aplicações
Outras aplicações como: Criptografia, programação
linear, etc.
12. Problemas
NP-Completos
P e NP. Redutibilidade. Problemas NP-Completos.
Teorema de Cook. Problema SAT. Como provar que um problema é NP-Completo.
Bibliografia:
Planejamento de Aulas:
Aula |
Data |
Assunto Planejado |
Notas de Aula |
1 |
09/09/08 |
Apresentação do Curso. |
|
2 |
12/09/08 |
Motivação para o estudo de algoritmos.
Introdução informal. Corretude de Algoritmos. |
|
3 |
16/09/08 |
Corretude de algoritmos. |
|
4 |
19/09/08 |
Análise assintótica. Análise de algoritmos simples. |
|
5 |
23/09/08 |
Relação de recorrência: introdução |
|
6 |
26/09/08 |
Relação de recorrência (cont.). Análise de
algoritmos recursivos. |
|
7 |
30/09/08 |
Divisão e Conquista: conceitos básicos e exemplos simples. |
|
8 |
03/10/08 |
||
9 |
07/10/08 |
Análise de algoritmos de ordenação |
|
10 |
10/10/08 |
Prova 1 |
|
11 |
14/10/08 |
Problemas de otimização. Método guloso. Mochila fracionária. |
|
12 |
17/10/08 |
Método guloso: outras aplicações. |
|
13 |
21/10/08 |
PD: Conceitos básicos. Exemplos introdutórios. |
|
14 |
24/10/08 |
PD: A mochila binária e variações. |
|
15 |
28/10/08 |
PD: Menor distância de edição, subseqüência máxima. |
|
16 |
31/10/08 |
PD: multiplicação de matrizes |
|
17 |
04/11/08 |
Grafos: conceitos básicos. Busca em Grafos. |
|
18 |
07/11/08 |
Backtracking: Conceitos Básicos |
|
19 |
11/11/08 |
Branch-and-Bound |
|
20 |
14/11/08 |
Aula de Revisão |
|
21 |
18/11/08 |
Prova 2 |
|
22 |
21/11/08 |
Algoritmos de grafos: Ordenação topológica e componentes fortemente
conectados |
|
23 |
25/11/08 |
Algoritmos de grafos: menor caminho de origem única. Floyd-Warshall. |
|
24 |
28/11/08 |
Algoritmos de
grafos: Árvore de cobertura mínima. |
|
25 |
02/12/08 |
Fluxo em Redes; Emparelhamento |
|
26 |
05/12/08 |
Cliques, Conjunto Independente de vértices e cobertura de vértices. |
|
27 |
09/12/08 |
NP-Completude |
|
28 |
12/12/08 |
NP-Completude |
|
29 |
16/12/08 |
Aula de Revisão |
|
30 |
19/12/08 |
Prova 3 |
|
31 |
06/02/09 |
Aula de Reposição |
|
32 |
10/02/09 |
Reposição |
|
33 |
13/02/09 |
|
|
34 |
17/02/09 |
Prova Final |
|