8 DividirConquistar PAA2004 6T

Programa do PA
1. Resolução de Problemas e
Tipos de Problemas

Dividir & Conquistar

2. Fundamentos
3. Notação Assintótica e
Classe de Eficiência

Introdução

4. Análise Matemática de
Algoritmos

6. Força Bruta

Técnicas de Projeto de Algoritmos

7. Dividir & Conquistar

5. Análise Empírica de
Algoritmos

8. Decrementar & Conquistar

Aula 8
Alessandro L. Koerich

9. Transformar & Conquistar
10. Compromisso Tempo-Espaço

Fundamentos da Análise da Eficiência de Algoritmos

11. Programação Dinâmica
15. Teorema do Limite
Inferior

12. Estratégia Gulosa
13. Backtracking & Branch and
Bound

Pontifícia Universidade Católica do Paraná (PUCPR)

7o

Ciência da Computação – Período
Engenharia de Computação – 5o Período

16. Árvores de Decisão
17. Problemas P, NP e NPC

14. Algoritmos Aproximados

Técnicas de Projeto de
Algoritmos
Alessandro L. Koerich ([e-mail])

Limitações
Eng./Ciência da Computação - Proj. e Anál. de Algoritmos - 2004

Plano de Aula
“

Introdução

“

Teorema Mestre

“

Mergesort & Quicksort

“

Busca Binária

“

Multiplicação de Matrizes

“

Par mais Próximo e Convex Hull

“

Resumo

Alessandro L. Koerich ([e-mail])

Eng./Ciência da Computação - Proj. e Anál. de Algoritmos - 2004

Introdução

3

“

É provavelmente uma das mais conhecidas estratégias de projeto de algoritmos

“

Os algoritmos Dividir & Conquistar funcionam de acordo com um plano geral

Alessandro L. Koerich ([e-mail])

Introdução
1.

Dividir a instância do problema em duas ou mais instâncias menores

2.

Resolver as instâncias menores recursivamente 3.

“

4

O paradigma de dividir e conquistar envolve 3 passos: Problema
Dividir

Conquistar

subproblema subproblema
Solução

Combinar

Eng./Ciência da Computação - Proj. e Anál. de Algoritmos - 2004

Eng./Ciência da Computação - Proj. e Anál. de Algoritmos - 2004

Projeto de Algoritmos D&C

Obter a solução para as instâncias originais
(maiores) através da combinação destas soluções. Alessandro L.