Algoritmos - Poli-Elétrica - 2- Métodos de Projeto e Recursão

Prévia do material em texto

Escola Politécnica da Universidade de São Paulo 
Algoritmos e Estruturas de Dados 
para Engenharia Elétrica 
Métodos de Projeto de Algoritmos e 
Recursão 
PCS3110 
Agenda 
  Introdução 
  Rastreamento de algoritmos 
  Algoritmo de Euclides 
  Método da força-bruta 
  Método dividir para conquistar 
  Recursão 
2 
Introdução 
  Projetar algoritmos requer 
•  Entendimento do problema a ser resolvido 
•  Avaliação da necessidade de eficiência computacional 
•  Adoção de métodos de projeto 
•  Uso de estruturas de dados adequadas 
3 
Rastreamento 
  Rastrear uma algoritmo ("Trace") 
•  Simular a execução do algoritmos 
  Para que serve 
•  Verificar se o algoritmo funciona como esperado para 
as entradas simuladas 
•  Descobrir erros que estejam ocorrendo 
•  Entender o funcionamento de algoritmos escritos por 
outras pessoas! 
4 
Exemplo de algoritmo 
  Seja Max-3 um algoritmo que encontra o maior 
dentre 3 números a, b e c 
Max-­‐3(a,b,c)	
  
1  maior	
  =	
  a	
  
2  if	
  b	
  >	
  maior	
  //se	
  b	
  >	
  maior	
  atualiza	
  maior	
  
3  	
  	
  	
  maior	
  =	
  b	
  	
  
4  if	
  c	
  >	
  maior	
  //se	
  c	
  >	
  maior	
  atualiza	
  maior	
  
5  	
  	
  	
  maior	
  =	
  c	
  
6  return	
  maior	
  
5 
Avalie as condições de funcionamento do algoritmo 
(domínio para o qual o algoritmo se aplica) 
Rastreamento de Max-3 
Passo 
T 
Passo 
Alg. 
Entrada 
a,b,c 
maior b > maior c > maior Max-3 
1 1, 5, 3 
2 1 1 
3 2 TRUE 
4 3 5 
5 4 FALSE 
6 6 5 
6 
Propriedades do algoritmo Max-3 
  Finitude: o algoritmo termina sua execução após a 
execução de exatamente seis passos 
  Unicidade: o “trace” exemplifica a unicidade, pois 
há uma única sequência de execução válida. 
  Entradas: os valores “a=1”, “b=5” e “c=3” 
representam entradas para o algoritmo. 
  Saídas: o resultado do algoritmo é dado pelo valor 
final retornado, maior = 5. 
  Generalidade: aplicável para vários valores de 
entradas. 
•  Para os valores de a= 2, b= 5 e c= 7 execute a simulação 
do algoritmo (“trace”) e visualize a generalidade do 
algoritmo submetendo-o a outros conjuntos de dados. 
7 
Exemplo de algoritmo 
  Exemplo: Max, encontra o máximo de uma 
sequência S com n elementos 
8 
Max(S)	
  
1  large	
  =	
  S[1]	
  
2  for	
  i	
  =	
  2	
  to	
  S.tamanho	
  
3  	
  	
  if	
  S[i]	
  >	
  large	
  //	
  há	
  valor	
  maior	
  que	
  large	
  
4  	
  	
  	
  	
  	
  large	
  =	
  S[i]	
  
5  return	
  large	
  
Rastreamento de Max 
  Entrada: sequência 3, 5, 7 n = 3 
  Saída: máximo da sequência 
9 
Passo 
T 
Passo 
Alg. 
i large S[i] S[i] > large Max S n 
1 3,5,7 3 
2 1 3 
3 2 2 
4 3 5 TRUE 
5 4 5 
6 2 3 
7 3 7 TRUE 
8 4 7 
9 2 4 
10 5 7 
Passo 
T 
Passo 
Alg. 
i large S[i] S[i] > large Max S n 
1 3,5,7 3 
2 1 3 
3 2 2 
4 3 5 TRUE 
5 4 5 
6 2 3 
7 3 7 TRUE 
8 4 7 
9 2 4 
10 5 7 
Rastreamento de Max 
  Entrada: sequência 3, 5, 7 n = 3 
  Saída: máximo da sequência 
10 
Algoritmo de Euclides 
  O máximo divisor comum de dois números 
inteiros (m e n , e n ≠ 0) é o maior inteiro que 
divide ambos os números 
  Exemplo: MDC(105, 30) = 15 
  Exemplo de uso 
•  Uma fração m / n está na sua forma mínima se MDC 
(m, n) = 1 
11 
 3 2 
105 30 15 
15 0 
MDC 
Algoritmo de Euclides 
  O divisor b de um número a, sendo b ≠ 0 é q, tal 
que a = b * q 
•  q é denominado quociente. 
•  b | a  b divide a 
•  b | a  b não divide a 
12 
Lema: Se b | a, então a = b * q + r , onde r é o resto da 
divisão inteira, e 0 < r < b 
Algoritmo de Euclides 
  Teorema 
  A aplicação sucessiva do teorema permite 
escrever o algoritmo para cálculo do MDC 
•  Observando que MDC (x, 0) = x 
13 
Se a é um inteiro não negativo e b é um inteiro positivo e 
 a = b * q + r com 0 ≤ r < b 
 então 
 MDC (a,b) = MDC (b,r) 
Algoritmo de Euclides 
14 
MDC(a,b)	
  
1  if	
  a	
  <	
  b	
  //	
  troca	
  a	
  com	
  b	
  
2  	
  	
  aux	
  =	
  a	
  
3  	
  	
  a	
  =	
  b	
  
4  	
  	
  b	
  =	
  aux	
  
5  while	
  b	
  ≠	
  0	
  
6  	
  	
  r	
  =	
  a	
  mod	
  b	
  
7  	
  	
  a	
  =	
  b	
  
8  	
  	
  b	
  =	
  r	
  
9  return	
  a	
  
Método força-bruta 
  O projeto do algoritmo MDC(a,b) segue uma 
proposta de construção sequencial 
•  Usamos apenas os conceitos envolvidos e o 
resultado do teorema 
  se (a = bq + r) então mdc(a,b) = mdc(b,r) 
•  Construção do algoritmo centralizada num laço 
  Calcula resto r da divisão de a por b seguido da atualização 
de a e b por b e r 
•  O rastreamento do algoritmo é sequencial 
15 
Rastreamento de MDC(10,45) 
Passo 
T 
Passo 
Alg. a b aux r a < b b ≠ 0 Mdc 
1 10 45 
2 1 TRUE 
3 2 10 
4 3 45 
5 4 10 
6 5 TRUE 
7 6 5 
8 7 10 
9 8 5 
10 5 TRUE 
11 6 0 
12 7 5 
13 8 0 
14 5 FALSE 
15 9 5 
16 
Rastreamento de MDC(10,45) 
17 
Passo 
T 
Passo 
Alg. a b aux r a < b b ≠ 0 Mdc 
1 10 45 
2 1 TRUE 
3 2 10 
4 3 45 
5 4 10 
6 5 TRUE 
7 6 5 
8 7 10 
9 8 5 
10 5 TRUE 
11 6 0 
12 7 5 
13 8 0 
14 5 FALSE 
15 9 5 
Decomposição de problemas 
  Técnica através da qual um problema complexo 
pode ser decomposto em outros mais simples 
  Dividir para conquistar 
•  Uma técnica de decomposição 
•  Problema original é decomposto em outros de 
mesmo tipo, mais simples, até que cada um admita 
uma solução direta 
•  A composição das soluções obtidas permite obter a 
solução final do problema original 
•  Exemplo: Recursividade 
18 
Método dividir para conquistar 
  Considere o cálculo de 5! 
  Podemos tornar o cálculo mais fácil se, em vez 
de 5!, usarmos 4! 
  Assim, podemos fazer 
5! = 5 . 4! 
  Da mesma forma, podemos continuar o 
raciocínio 
4! = 4 . 3! 3! = 3 . 2! ..... 
19 
Dividir para conquistar e recursão 
  O método dividir para conquistar constitui a base 
de projetos de algoritmos recursivos 
  Procedimento recursivo: é aquele que chama 
a si mesmo, direta ou indiretamente 
  Algoritmo recursivo: contém um procedimento 
recursivo 
20 
Dividir para conquistar e recursão 
  Algumas funções matemáticas são definidas de 
forma recursiva 
•  Exemplos clássicos 
  Fatorial: 0! = 1 
 n! = n . (n – 1)! (n > 0) 
 
  Fibonacci: fib(0) = 1 e fib(1) = 1 
 fib(n) = fib(n – 1) + fib(n – 2) (n > 1) 
 
21 
Recursividade 
  É necessária uma condição de término para o 
algoritmo (finitude) 
  Todo algoritmo recursivo apresenta alguma 
situação na qual o procedimento não chama a si 
mesmo 
•  Esta situação chama-se caso base 
22 
Método dividir para conquistar e 
recursão 
  Voltando ao cálculo de 5! 
5! = 5 . 4! 
 4! = 4 . 3! 
 3! = 3 . 2! 
 2! = 2 . 1! 
 1! = 1 . 0! 
 0! = 1 
23 
Problema mais simples 
Solução direta (caso base) 
1! é mais simples que 2!, que é mais simples que 3!, etc.. 
Algoritmo fatorial recursivo 
  O algoritmo acima produz o valor de n!, n ≥ 0. 
24 
Fatorial(n)	
  
1  if	
  n	
  ==	
  0	
  //caso	
  base	
  
2  	
  	
  	
  	
  return	
  1	
  	
  
3  return	
  n*fatorial(n-­‐1)	
  
Rastreamento 
25 
Passo 
T 
Passo 
Alg. 
n n==0 Fatorial Observações 
1 4 1a. Chamada n=4 
2 1 FALSE 
3 3 4*Fatorial(3) passo não completado 
4 3 2a. Chamadan=3 
5 1 FALSE 
6 3 3*Fatorial(2) passo não completado 
7 2 3a. Chamada n=2 
8 1 FALSE 
9 3 2*Fatorial(1) passo não completado 
10 1 4a. Chamada n=1 
11 1 FALSE 
Rastreamento 
  A seta dupla indica início e término de execução 
de um mesmo comando 
26 
Passo 
T 
Passo 
Alg 
n n==0 Fatorial Observações 
12 3 1*Fatorial(0) passo não completado 
13 0 5a. Chamada n=0 
14 1 TRUE 
15 3 1 valor devolvido 
16 3 1 1*Fatorial(0)= 1 valor devolvido 
17 3 2 2*Fatorial(1)= 2 valor devolvido 
18 3 3 3*Fatorial(2)= 6 valor devolvido 
19 3 4 4*Fatorial(3)= 24 valor devolvido 
Algoritmo mdc recursivo 
  Vimos o MDC sequencial, agora veremos o 
MDC-Recursivo 
  Condição de término do máximo divisor comum 
mdc 
•  (a,b)  (mdc de a e b, 0) 
  Escreva um algoritmo recursivo que encontre o 
mdc entre inteiros a e b (MDC-Recursivo (a,b)) 
27 
Algoritmo mdc recursivo 
28 
MDC-­‐Recursivo(a,b)	
  
1  if	
  a	
  <	
  b	
  	
  	
  	
  //	
  inverte	
  a	
  com	
  b	
  
2  	
  	
  aux	
  =	
  a	
  
3  	
  	
  a	
  =	
  b	
  
4  	
  	
  b	
  =	
  aux	
  
5  if	
  b	
  ==	
  0	
  
6  	
  	
  	
  return	
  a	
  
7  return	
  MDC-­‐Recursivo(b,	
  a	
  mod	
  b)	
  	
  	
  
Dividir para conquistar e Recursão 
  Considere o problema das Torres de Hanói 
•  Deseja-se transferir n discos do pino A para o pino C 
usando o pino B como auxiliar seguindo as regras 
  Podemos mover apenas 1 disco por vez 
  Um disco de diâmetro maior nunca poderá ficar sobre um 
disco de diâmetro menor 
29 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói 
•  Chamaremos Hanoi(n,A,B,C) o problema de transferir 
n discos de A para C usando B como pino auxiliar 
•  Como resolver Hanoi(n,A,B,C)? 
30 
A B 
Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
C 
Dividir para conquistar e Recursão 
  Torres de Hanói 
•  Pensando em divisão e conquista 
  Se conseguir colocar em B os discos vermelho, verde, laranja 
e roxo seguindo a regra, saberemos responder a pergunta 
31 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói 
•  Pensando em divisão e conquista 
  Se conseguir colocar em B os discos vermelho, verde, laranja 
e roxo seguindo a regra, saberemos responder a pergunta 
  Isto significa que se sabemos resolver o movimento do meio o 
problema está resolvido! 
32 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói 
•  Pensando em divisão e conquista 
  Se conseguir colocar em B os discos vermelho, verde, laranja 
e roxo seguindo a regra, saberemos responder a pergunta 
  Isto significa que se sabemos resolver o movimento do meio o 
problema está resolvido! 
33 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói: solução 
•  Para resolver Hanoi(n,A,B,C) basta 
34 
A B C 
Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
Dividir para conquistar e Recursão 
  Torres de Hanói: solução 
•  Para resolver Hanoi(n,A,B,C) basta 
  Resolver Hanoi(n-­‐1,A,C,B) 
(transferir n-1 discos de A para B usando C como auxiliar) 
35 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói: solução 
•  Para resolver Hanoi(n,A,B,C) basta 
  Resolver Hanoi(n-­‐1,A,C,B) 
  Mover disco n de A para C 
36 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói: solução 
•  Para resolver Hanoi(n,A,B,C) basta 
  Resolver Hanoi(n-­‐1,A,C,B) 
  Mover disco n de A para C 
  Resolver Hanoi(n-­‐1,B,A,C) 
(transferir n-1 discos de B para C usando A como auxiliar) 
37 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói: solução 
•  Para resolver Hanoi(n,A,B,C) basta 
  Resolver Hanoi(n-­‐1,A,C,B) 
  Mover disco n de A para C 
  Resolver Hanoi(n-­‐1,B,A,C) 
38 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C 
A B C 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói 
•  Para resolver Hanoi(n,A,B,C) dividimos o problema 
em dois problemas menores 
  Hanoi(n-­‐1,A,C,B) e Hanoi(n-­‐1,B,A,C)	
  
39 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C A B C 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói 
•  Para resolver Hanoi(n,A,B,C) dividimos o problema 
em dois problemas menores 
  Hanoi(n-­‐1,A,C,B) e Hanoi(n-­‐1,B,A,C)	
  
  Para resolver Hanoi(n-­‐1,A,C,B) posso dividí-lo em dois 
problemas menores 
•  Hanoi(n-­‐2,A,B,C) e Hanoi(n-­‐2,C,A,B)… 
40 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói 
•  Para resolver Hanoi(n,A,B,C) dividimos o problema 
em problemas sucessivamente menores... 
  Quando parar de dividir???? 
41 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói 
•  Para resolver Hanoi(n,A,B,C) dividimos o problema 
em problemas sucessivamente menores... 
  Quando parar de dividir???? 
42 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C A B C 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói 
•  Para resolver Hanoi(n,A,B,C) dividimos o problema 
em problemas sucessivamente menores... 
  Quando parar de dividir???? 
  Quando soubermos a solução direta do problema!!! 
•  Hanoi(1,_,_,_)	
  
43 Baseado no material de MAC122 produzido pelo Prof. Paulo Feofiloff 
A B C 
Dividir para conquistar e Recursão 
  Torres de Hanói 
•  Em http://www.matematica.br/ihanoi/ você encontra 
um applet que simula as Torres de Hanoi 
44 
A B C 
Algoritmo de Hanoi 
  Torres de Hanói 
45 
Hanoi(n,origem,auxiliar,destino)	
  
1  if	
  n	
  ==	
  1	
  	
  //	
  caso	
  base	
  
2  	
  	
  print(“mover	
  disco”	
  n	
  “de”	
  origem	
  “para”	
  destino)	
  
3  else	
  if	
  n	
  >	
  1	
  	
  //	
  passo	
  recursivo	
  
4  	
  	
  Hanoi(n-­‐1,origem,destino,auxiliar)	
  	
  //	
  Hanoi(n-­‐1,A,C,B)	
  
5  	
  	
  print(“mover	
  disco”	
  n	
  “de”	
  origem	
  “para”	
  destino)	
  
6  	
  	
  Hanoi(n-­‐1,auxiliar,origem,destino)	
  	
  //	
  Hanoi(n-­‐1,B,A,C)	
  	
  
A B C 
1 
2 
3 
4 
5 
Exercício 
  Rastrear o algoritmo Hanoi(3,	
  A,	
  B,	
  C)	
  
46 
Algoritmos: métodos de projeto 
  Força bruta 
  Dividir para conquistar 
  Outros métodos 
•  Programação dinâmica Método Guloso (greedy) 
47