PAA Aula 7

Prévia do material em texto

bruno.conceicao@ufop.edu.br
Prof. Bruno César Cota Conceição
Projeto e análise de Algoritmos
 Aula 7
Projeto de algoritmos por Redução e Conquista
(Incremental) - Combinatória básica
Estudo de caso: gerando permutações
Estudo de caso: gerando permutações
Estudo de caso: gerando permutações
Estudo de caso: gerando permutações
Estudo de caso: gerando permutações
Temos aqui um exemplo de
achar as permutações de
um conjunto S.
Estudo de caso: gerando permutações
Temos aqui um exemplo de
achar as permutações de
um conjunto S.
Como que eu encontro todas as permutações?
Estudo de caso: gerando permutações
Estudo de caso: gerando permutações
Estudo de caso: gerando permutações
Estudo de caso: gerando permutações
Estudo de caso: gerando permutações
Estudo de caso: gerando permutações
Pensar de forma indutiva e quebrando em
subproblemas!!!
Proposta de algoritmo para gerar permutações
 Anova permutação gerada "np" só
deve ser incluída no conjunto
resposta se tiver o mesmo tamanho
do número de elementos iniciais
permutados. 
Proposta de algoritmo para gerar permutações
 Anova permutação gerada "np" só
deve ser incluída no conjunto
resposta se tiver o mesmo tamanho
do número de elementos iniciais
permutados. 
Assim, geramos apenas as
permutações de tamanho N,
excluindo as permutações
intermediárias de tamanho menor
Proposta de algoritmo para gerar permutações
Proposta de algoritmo para gerar permutações
Proposta de algoritmo para gerar permutações
Proposta de algoritmo para gerar permutações
Proposta de algoritmo para gerar permutações
Estudo de caso: Gerando combinações (subconjuntos)
Estudo de caso: Gerando combinações (subconjuntos)
Estudo de caso: Gerando combinações (subconjuntos)
Estudo de caso: Gerando combinações (subconjuntos)
Percebam que {1,3} e {3,1} são o mesmo subconjunto
Estudo de caso: Gerando combinações (subconjuntos)
Estudo de caso: Gerando combinações (subconjuntos)
Estudo de caso: Gerando combinações (subconjuntos)
Algoritmo: Gerando combinações (subconjuntos)
Algoritmo: Gerando combinações (subconjuntos)
Vamos realizar o passo indutivo e identificar os subproblemas que temos aqui.
Algoritmo: Gerando combinações (subconjuntos)
Algoritmo: Gerando combinações (subconjuntos)
Perceba que o número de
combinações do s´ vai ser a
metade do número de
combinações do s.
 Porque eu adiciono o e a
cada elemento.
Algoritmo: Gerando combinações (subconjuntos)
1 - acho o
resultado do
subproblema
Algoritmo: Gerando combinações (subconjuntos)
1 - acho o
resultado do
subproblema
2 - Tenho o
resultado do
subproblema
dobrado.
Algoritmo: Gerando combinações (subconjuntos)
1 - acho o
resultado do
subproblema
2 - Tenho o
resultado do
subproblema
dobrado.
Retrono o resultado final
Custo do Algoritmo: Gerando combinações 
Custo do Algoritmo: Gerando combinações 
Esse é o custo, é o melhor caso e o pior caso, então ele é theta de alguma coisa.
Custo do Algoritmo: Gerando combinações 
Através do método da expansão:
Custo do Algoritmo: Gerando combinações 
Através do método da expansão:
Custo do Algoritmo: Gerando combinações 
Através do método da expansão:
Custo do Algoritmo: Gerando combinações 
Referências:
Créditos ao professor Vinícius Dias pelo material disponibilizado.
 LEVITIN, Anany. Introduction to the Design and Analysis of Algorithms. 3a edition. Editora
Addison Wesley;
2. CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford.
Introduction to Algorithms. 3a edition. Editora The MIT Press;
3. ERICKSON, Jeffe. Algorithms. 1st edition. June 2019.
Disponível em: https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf
4. KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. Editora Addison Wesley.
5. DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algorithms. Editora
McGraw-Hill.
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788563308535/pageid/0
6. MANBER, Udi. Introduction to Algorithms: A Creative Approach. 1st edition. Editora
AddisonWesley
7. DE, A. et al. [s.l: s.n.]. Disponível em: <http://waltenomartins.com.br/ap_aa_v1.pdf>. Acesso em: 4 out. 2023.