Programa do PA
1. Resolução de Problemas e
Tipos de Problemas
Força Bruta
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 7
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
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
14. Algoritmos Aproximados
15. Teorema do Limite
Inferior
16. Árvores de Decisão
17. Problemas P, NP e NPC
Técnicas de Projeto de
Algoritmos
Alessandro L. Koerich ([email protected])
Limitações
Ciência/Engenharia de Computação
Aula Anterior
Proj. Anal. Algoritmos/2004
Plano de Aula
“
Análise de Algoritmos Recursivos
“
Introdução
“
Recorrências
“
Selection Sort e Bubble Sort
“
Busca Seqüencial e String Matching
“
Par mais Próximo e Convex Hull
“
Busca Exaustiva
“
Resumo
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
2
3
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
4
Introdução
Introdução
Força Bruta
“
“
“
A “força” é de um computador e não do
intelecto de alguém
“
“Somente faça”
“
Geralmente, a estratégia de “força bruta” é uma
das mais fáceis de aplicar
é a mais simples das estratégias de projeto
Pode ser definida como:
Uma solução direta para resolver um problema,
geralmente baseada diretamente no enunciado
do problema e nas definições dos conceitos
envolvidos
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
5
Alessandro L. Koerich ([email protected])
Exemplos:
“
Calculando an (a > 0, n sendo um inteiro não negativo)
“
Calculando n!
“
Multiplicação de duas matrizes n por n
“
Selection Sort
“
Busca seqüencial
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
Proj. Anal. Algoritmos/2004
6
Força Bruta
Força Bruta
“
Ciência/Engenharia de Computação
justificativa
7
“
Apesar de ser raramente uma fonte de
algoritmos eficientes ou brilhantes, a técnica
força bruta é uma importante estratégia de
projeto de algoritmos
“
Força bruta é aplicável a uma ampla variedade
de problemas
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
8
Força Bruta
Força Bruta
justificativa
“
justificativa
É empregado em muitas tarefas algorítmicas
elementares porém importantes:
“
Soma de n números
“
Encontrar o maior elemento em uma lista
“
Etc...
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
9
“
Para alguns problemas importantes (ordenação,
busca, multiplicação de matrizes, string
matching), a técnica de força bruta fornece
algoritmos razoáveis, de valor prático e sem
limitações quanto ao tamanho da instância.
“
O esforço para projetar um algoritmo mais
eficiente pode não ser justificável se somente
algumas poucas instâncias de um problema
necessitarem ser resolvidas (velocidade
aceitável)
Alessandro L. Koerich ([email protected])
Força Bruta
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
10
Problemas de Ordenação
justificativa
“
Mesmo ineficiente em geral , pode ser útil para
resolver problemas com instâncias pequenas
“
Aplicação da técnica força bruta em problemas
de ordenação.
“
Propósito teórico e educacional.
“
Dada uma lista de n elementos ordenáveis
(números, caracteres, strings), rearranjá–los
em ordem crescente
Qual seria o método mais direto para resolver o
problema da ordenação?
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
11
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
12
Selection Sort
“
Começamos varrendo o arranjo inteiro para
encontrar o menor elemento e permutá–lo com
o primeiro elemento
“
Então, varremos a lista, começando pelo
segundo elemento, para encontrar o menor
dentre os n–1 últimos elementos e permutá–lo
com o segundo elemento
Selection Sort
“
A0 ≤ A1 ≤ . . . ≤ Ai–1 | Ai, . . ., Amin, . . ., An–1
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
Os n–i últimos elementos
Elementos na posição
definitiva
“
Alessandro L. Koerich ([email protected])
Generalizando, na i-ésima passagem pela lista,
o algoritmo procura pelo menor item entre os
n–i últimos elementos e permuta o com Ai.
13
Após n–1 passos, a lista está ordenada
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Selection Sort
“
Pseudo–Código
Alessandro L. Koerich ([email protected])
Proj. Anal. Algoritmos/2004
15
14
Selection Sort
“
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
Tempo de execução
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
16
Selection Sort
“
Exemplo
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
17
Bubble Sort
“
Comparar elementos adjacentes de uma lista e
permutá–los se eles estiverem fora de ordem.
“
Fazendo isso repetidamente, acabamos “empurrando”
(bubbling up) o maior elemento para a última posição
da lista.
“
A próxima passagem “empurra” o segundo maior e
assim por diante, até após n–1 passos, a lista ser
ordenada.
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Bubble Sort
“
Pseudo–Código
Alessandro L. Koerich ([email protected])
Proj. Anal. Algoritmos/2004
19
18
Bubble Sort
“
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
Tempo de execução
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
20
Bubble Sort
“
Conclusão Parcial
Exemplo
Uma primeira aplicação da estratégia
força bruta geralmente resulta em um
algoritmo que pode ser melhorado com
uma quantidade modesta de esforço.
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
21
Alessandro L. Koerich ([email protected])
Duas outras aplicações da estratégia força
bruta.
Proj. Anal. Algoritmos/2004
“
Compara elementos sucessivos de uma dada
lista com um dada chave de busca até:
“
Problema de buscar um item de um dado valor em
uma dada lista
“
encontrar um elemento similar (busca bem
sucedida) ou
“
Problema da comparação de strings
“
a lista ser exaurida sem encontrar um elemento
similar (busca mal sucedida)
“
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
23
22
Busca Seqüencial
Busca Seqüencial e String Matching
“
Ciência/Engenharia de Computação
Truque: anexar a chave de busca no final da
lista ¨ evita testar final da lista a cada iteração
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
24
Busca Seqüencial
“
Pseudo–Código
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
25
Busca Seqüencial
“
A busca seqüencial fornece uma ilustração
excelente do método força bruta, com sua
característica força (simplicidade) e fraqueza
(eficiência inferior)
“
T(n) = Θ(n)
“
Pior caso
“
Melhor caso.
Alessandro L. Koerich ([email protected])
String Matching
“
“
2.
Movendo da esquerda a direita, comparar cada
caractere do padrão com o respectivo caractere no
texto até
“
“
3.
Proj. Anal. Algoritmos/2004
26
String Matching
Isto é , encontrar i, o índice do caractere mais a
esquerda da primeira substring casada no
texto, tal que ti=p0,...,ti+j=pj,..., ti+m-1 = pm-1
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
Algoritmo Força Bruta
1.
Alinha padrão no início do texto
Dada uma string de n caracteres chamada de
texto, e uma string de m caracteres (m ≤ n)
chamada padrão, encontrar uma substring do
texto que “case” com o padrão.
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
27
Todos os caracteres sejam coincidentes (busca bem sucedida);
ou
Uma combinação errônea seja detectada
Enquanto o padrão não for encontrado, e o texto não
for percorrido integralmente, realinhar o padrão uma
posição a direita e repetir Passo 2
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
28
String Matching
“
Pseudo–Código
“
Eficiência: Θ(mn)
Alessandro L. Koerich ([email protected])
String Matching
“
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
29
Alessandro L. Koerich ([email protected])
Par mais Próximo (Closest Pair)
“
Problema: encontrar os dois pontos mais
próximos em um conjunto de n pontos em um
espaço k-dimensional
“
Algoritmo: Computar as distâncias entre cada
par de pontos Pi=(xi,yi) e Pj=(xj,yj):
Exemplo
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
30
Par mais Próximo (Closest Pair)
d ( Pi , Pj ) = ( xi − x j ) 2 + ( yi − y j ) 2
Distância Euclidiana
Alessandro L. Koerich ([email protected])
“
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
31
Eficiência: Θ(n2)
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
32
Convex Hull
“
Problema: encontrar o menor polígono convexo
confinando n pontos sobre o plano
“
Algoritmo: Para cada par de pontos p1 e p2
determinar se todos os outros pontos recaem
no mesmo lado da linha reta entre p1 e p2
“
Eficiência: O(n3)
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
33
Convex Hull
Alessandro L. Koerich ([email protected])
Convex Hull
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
35
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
34
Convex Hull
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
36
Prós e Contras
Prós
“ Ampla aplicabilidade
“ Simplicidade
“ Fornece algoritmos razoáveis para alguns
problemas importantes
“
“
“
“
Contras
busca
string matching
Multiplicação de matrizes
Fornece algoritmos padrão para tarefas
computacionais simples.
“
“
Prós e Contras
“
Raramente fornece algoritmos eficientes
“
Alguns algoritmos força bruta são
inaceitavelmente vagarosos
“
Não tão construtivo/criativo quanto outras
técnicas de design.
soma/produto de n números
Encontrar max/min em uma lista
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
37
Alessandro L. Koerich ([email protected])
Busca Exaustiva
“
“
Muitos problemas importantes necessitam
encontrar um elemento com propriedades
especiais em um domínio que cresce
exponencialmente (ou mais rapidamente) com
um tamanho de instância.
Uma solução força bruta para um problema
envolvendo a busca por um elemento com um
propriedade especial, geralmente entre objetos
combinatoriais tais como permutações,
combinações, ou subconjunto de um conjunto
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
39
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
38
Busca Exaustiva
“
Muitos destes problemas são de otimização:
encontrar valores de elementos (parâmetros)
que maximizem ou minimizem certas
características desejáveis.
“
Busca exaustiva é simplesmente uma estratégia
de força bruta para problemas combinatoriais.
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
40
Caixeiro Viajante
Busca Exaustiva
Método
“ Construir uma maneira de listar todas as
soluções potenciais para o problema de uma
maneira sistemática
“
“
Todas as soluções estão eventualmente listadas
Nenhuma solução é repetida
“
Avaliar as soluções, uma a uma, talvez,
desqualificando as não práticas e mantendo a
melhor encontrada até o momento
“
Quando a busca terminar, anunciar o vencedor.
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
41
Traveling salesman problem
“
Dadas n cidades com distâncias conhecidas
entre cada par, encontrar o trajeto mais curto
que passe por todas as cidades exatamente uma
vez antes de retornar a cidade de origem.
“
Alternativamente: Encontrar o circuito
Hamiltoniano mais curto em um grafo
conectado e ponderado.
Alessandro L. Koerich ([email protected])
Caixeiro Viajante
Exemplo
a
8
c
5
3
7
b
4
Custo
2+3+7+5 = 17
2+4+7+8 = 21
8+3+4+5 = 20
8+7+4+2 = 21
5+4+3+8 = 20
5+7+3+2 = 17
d
“
Alessandro L. Koerich ([email protected])
42
Traveling salesman problem
Trajeto
“ a→b→c→d→a
“ a→b→d→c→a
“ a→c→b→d→a
“ a→c→d→b→a
“ a→d→b→c→a
“ a→d→c→b→a
2
Proj. Anal. Algoritmos/2004
Caixeiro Viajante
Traveling salesman problem
“
Ciência/Engenharia de Computação
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
43
Eficiência: (n–1)!
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
44
Problema da Mochila
Problema da Mochila
Knapsack Problem
Dados n itens:
“ Pesos: w1 w2 … wn
“ Valores: v1 v2 … vn
“ Uma mochila (knapsack) de capacidade W
Knapsack Problem
“
A solução exaustiva para este problema
consiste em considerar “todos” os
subconjuntos do conjunto de n itens dados,
calculando o peso total de cada subconjunto
para identificar subconjunto praticáveis
Encontrar o subconjunto mais valioso de itens
que caibam dentro da mochila (knapsack)
e
“
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
45
Encontrar um subconjunto com o valor mais
elevado entre eles
Alessandro L. Koerich ([email protected])
Problema da Mochila
Exemplo
Alessandro L. Koerich ([email protected])
Proj. Anal. Algoritmos/2004
47
46
Knapsack Problem
“
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
Problema da Mochila
Knapsack Problem
“
Ciência/Engenharia de Computação
Exemplo
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
48
Problema da Mochila
Problema da Mochila
Knapsack Problem
Suconjunto Peso Total Valor Total
{1}
2
$20
{2}
5
$30
{3}
10
$50
{4}
5
$10
{1,2}
7
$50
{1,3}
12
$70
{1,4}
7
$30
{2,3}
15
$80
{2,4}
10
$40
{3,4}
15
$60
{1,2,3}
17
not feasible
{1,2,4}
12
$60
{1,3,4}
17
not feasible
{2,3,4}
20
not feasible
{1,2,3,4}
22
not feasible
Exemplo
item peso
1
2
2
5
3
10
4
5
Alessandro L. Koerich ([email protected])
valor
$20
$30
$50
$10
capacidade
mochila W=16
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
49
Alessandro L. Koerich ([email protected])
Problema da Mochila
Como o número de subconjuntos de um
conjunto de n elementos é 2n, a busca exaustiva
leva a um algoritmo Ω(2n).
“
Assim, tanto para o problema do caixeiro
viajante quanto da mochila, a busca exaustiva
leva a algoritmos que são extremamente
ineficientes
“
Estes problemas são chamados de problemas
NP–difícil.
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
51
Proj. Anal. Algoritmos/2004
50
Problema da Atribuição
Knapsack Problem
“
Ciência/Engenharia de Computação
Eficiência: ???
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
52
Problema da Atribuição
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
53
Comentários Finais
“
Força bruta é uma estratégia direta para
resolver um problema, geralmente baseada
diretamente no enunciado do problema e
definições dos conceitos envolvidos.
“
Os principais méritos de uma estratégia força
bruta são a ampla aplicabilidade e simplicidade
“
O principal demérito é uma baixa eficiência da
maioria dos algoritmos força bruta.
Alessandro L. Koerich ([email protected])
Comentários Finais
“
Uma primeira aplicação do método força bruta
geralmente resulta em um algoritmo que pode ser
melhorado com uma modesta quantidade de esforço.
“
Os seguintes algoritmos podem ser considerados como
exemplos de estratégias força bruta:
“
Algoritmos para multiplicação de matrizes baseados na
definição
“
Ordenação por seleção
“
Busca seqüencial
“
Algoritmos de busca de string direto
Alessandro L. Koerich ([email protected])
“
Busca exaustiva é uma estratégia força bruta
para problemas combinatoriais.
“
Ele sugere gerar todos os objetos
combinatoriais do problema, selecionar aqueles
que satisfaçam as restrições do problema e
então, encontrar um objeto desejado.
“
Exemplos de problemas típicos que podem ser
resolvidos por busca exaustiva:
“
Proj. Anal. Algoritmos/2004
55
Proj. Anal. Algoritmos/2004
54
Comentários Finais
“
Ciência/Engenharia de Computação
Ciência/Engenharia de Computação
Caixeiro viajante
Mochila
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
56
Comentários Finais
“
Algoritmos de Busca exaustiva são executados
em uma quantidade de tempo realística
somente para instâncias muito pequenas
“
Em muitos casos existem alternativas muito
melhores!
“
“
“
“
Próxima Aula
“
Estratégia Dividir & Conquistar
shortest paths
minimum spanning tree
assignment problem
Em alguns casos, busca exaustiva (ou variação)
é a única solução conhecida
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
57
Alessandro L. Koerich ([email protected])
Ciência/Engenharia de Computação
Proj. Anal. Algoritmos/2004
58