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.

Introdução

3

16/09/08

Corretude de algoritmos.

Corretude

Lista 1

4

19/09/08

Análise assintótica. Análise de algoritmos simples.

Análise

5

23/09/08

Relação de recorrência: introdução

Recorrencia

6

26/09/08

Relação de recorrência (cont.). Análise de algoritmos recursivos.

Ordenação

7

30/09/08

Divisão e Conquista: conceitos básicos e exemplos simples.

Lista 2

8

03/10/08

Análise de algoritmos de ordenação

Divisão e conquista

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.

Guloso

12

17/10/08

Método guloso: outras aplicações.

Lista Guloso

 

13

21/10/08

PD: Conceitos básicos. Exemplos introdutórios.

PD

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.

Lista PD

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

Backtracking

19

11/11/08

Branch-and-Bound

Lista NP/Backtracking

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

Lista de Grafos

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

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