Projeto e Análise de Algoritmos
Celso Carneiro Ribeiro
http://www.inf.puc-rio.br/~celso
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
1
Parte 1
Introdução
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
2
Alguns exemplos
•
•
•
•
•
Totalizar uma folha de pagamento
Ordenar uma lista de números
Multiplicar dois números inteiros
Multiplicar duas matrizes
Dado um tabuleiro de xadrez, obter o melhor
movimento para as peças brancas.
• Obter o conjunto de rotas ótimas para um determinado
número de veículos, que devem distribuir um certo
número de produtos em determinados pontos de venda
de certas cidades.
• Dado um programa R escrito em uma linguagem L e
uma entrada X qualquer para R, decidir se R termina se
for submetido à entrada X.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
3
O que é um algoritmo?
• Do dicionário Aurélio: processo de cálculo ou de resolução
de um grupo de problemas semelhantes, em que se
estipulam, com generalidade e sem restrições, regras
formais para a obtenção do resultado, ou da solução do
problema.
• Conjunto predeterminado e bem definido de regras e
processos destinados à solução de um problema, com um
número finito de etapas.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
4
O que é um algoritmo?
•
Sequência finita de instruções elementares e bem definidas (nãoambíguas), que levam à solução de um problema específico.
•
Operações válidas
– Definidas (some 6 ou 7 a x)
– Efetivas ( x  2 ou y   ) (aritmética de inteiros versus reais)
•
Término em tempo finito (procedimento computacional)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
5
Qual algoritmo utilizar para resolver um problema?
Quando se resolve um
problema, é necessário
decidir-se pelo algoritmo a
ser utilizado.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
6
Exemplo 1: Multiplicação de dois números inteiros com n dígitos
Algoritmo 1: ~n2
45
19
405
45
855
Setembro 2004
Algoritmo 2: ~n2
45 19
22 38
19

11
76
76
Algoritmo 3: ~n1.59
5 152 152
2 304 
1 608 608
855
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
7
Exemplo 2: MDC – Algoritmo ingênuo
Entrada: x, y  Z*
Saída: MDC(x, y) = Max{ z  Z |  a,b  Z, x = az, y=bz }
Function mdc(x, y: integer): integer
var t: integer
início
se x<y então t  x
senão t  y
enquanto (x mod t <>0) ou (y mod t<>0) faça t  t-1;
mdc  t
fim
fim_function
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
8
Exemplo 2: MDC – Algoritmo de Euclides
MDC (54180, 13125) = ?
4
7
1
4
3
54180
13125
1680
1365
315
105
1680
1365
315
105
0
MDC (54180, 13125) = 105
Function mdc_e(x, y: integer): integer
início
se y=0 então mdc_ex
senão
mdc_emdc_e(y, x mod y)
fim
fim_function_mdc_e
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
9
Exemplo 2: MDC
Algoritmo ingênuo realiza 13020
Algoritmo de Euclides realiza 5
Setembro 2004
iterações.
iterações!
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
10
Exemplo 2: MDC – Algoritmo de Euclides
Eliminação da recursão
function mdc(x, y: integer): integer
var t: integer
início
enquanto y<>0 faça
início
t x mod y
x y
y t
fim
mdc_e_i  x
fim
fim_function_mdc
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
11
Exemplo 3: Cálculo do n-ésimo elemento da seqüência de Fibonacci
Seqüência de Fibonacci:
an = an-1 + an-2
a0 = 0
a1 = 1
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
12
Exemplo 3: Cálculo do n-ésimo elemento da seqüência de Fibonacci
Algoritmo 1
function fib1(n)
se n<2
então retorne n
senão retorne fib1(n-1) + fib1(n-2)
fim_function_fib1
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
13
Exemplo 3: Cálculo do n-ésimo elemento da seqüência de Fibonacci
Algoritmo 2
function fib2(n)
i0
j1
para k=1 até n faça
j  i+j
i  j-i
fim_para
retorne j
fim_function_fib2
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
14
Exemplo 3: Cálculo do n-ésimo elemento da seqüência de Fibonacci
Algoritmo 3
function fib3(n)
i  1, j  0, k  0, h  1
enquanto n>0 faça
se n é ímpar então
t  j.h
j  i.h + j.k + t
i  i.k + t
fim_se
t  h2
h  2.k.h + t
k  k2 + t
n  n div 2
fim_enquanto
retorne j
fim_function_fib3
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
15
Exemplo 3: Cálculo do n-ésimo elemento da seqüência de Fibonacci
Cálculo da complexidade
• fib1(n) = fib1(n-1) + fib1(n-2)
• Cada chamada de fib1: O(1)
• T(n) é o número de chamadas de fib1 para o cálculo do nésimo termo
T (n)  T (n  1)  T (n  2)  1
T (0)  T (1)  1
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
16
Exemplo 3: Cálculo do n-ésimo elemento da seqüência de Fibonacci
Cálculo da complexidade
• Parte homogênea: solução da forma rn
r n  r n 1  r n 2  0  r 2  r  1  0
r
1 5
2
n
1  5 
1  5 
T ( n)  a 

b



2
2




n
• Parte não-homogênea: métodos dos coeficientes
indeterminados (termo não homogêneo=1)
A  A  A  1  A  1
n
n
1  5 
1  5 
T ( n)  a 

b


 1
2
2




T (0)  1
T (1)  1
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
17
Exemplo 3: Cálculo do n-ésimo elemento da seqüência de Fibonacci
Cálculo da complexidade
1 5
a
5
1 5
b
5
n 1
n 1

1  5  
2 1  5 
T ( n) 

 
  1
2  
5  2 



  1  5 n 
 
T (n)  O 
 

2
 

Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
18
Exemplo 3: Cálculo do n-ésimo elemento da seqüência de Fibonacci
Cálculo da complexidade
• S(n): número de somas efetuadas para calcular n-ésimo termo
• S(n) = S(n-1) + S(n-2) + 1
n
0 1 2 3 4 5
6
7
8
9
10
11
12
13
14
15
S(n) 0 0 1 2 4 7 12 20 33 54 88 143 232 376 609 1596
limn
S (n)
 1.618
S (n  1)
O(1.618n )
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
19
Exemplo 3: Cálculo do n-ésimo elemento da seqüência de Fibonacci
Cálculo da complexidade
Algoritmo 2:
1 5 

~ 

2


~n
Algoritmo 3:
~ log n
Algoritmo 1:
n
f100: 21 dígitos decimais
Pascal, CDC Cyber 835:
Algoritmo 1:
Algoritmo 2:
Algoritmo 3:
Setembro 2004
n=102
n=108
_
109 anos
1 ½ ms 25 minutos
½ ms
2 ms
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
20