2017 1 ECP AAC 2B A1

Prévia do material em texto

�FACULDADE POLITÉCNICA DE CAMPINAS��Rua Luiz Otávio, 1281 – Pq. Sta. Cândida – Campinas – SP – 13.087-018
http://www.policamp.edu.br – (19) 3756-2300��
ENGENHARIA DE COMPUTAÇÃO
9º SEMESTRE
ANÁLISE DE ALGORITMOS E COMPUTABILIDADE
 
LISTA DE EXERCÍCIOS
 
Projete o algoritmo mais eficiente que você conseguir para encontrar a mediana de um vetor de n elementos. Análise sua complexidade de tempo.
Escreva um algoritmo que ordena uma lista de n itens dividindo-a em três sublistas de aproximadamente n/3 itens, ordenando cada sublista recursivamente e intercalando as três sublistas ordenadas. Analise seu algoritmo e estime qual é o seu consumo de tempo.
Sejam X[1 . . n] e Y [1 . . n] dois vetores, cada um contendo n números ordenados. Escreva um algoritmo O(log n) para encontrar a mediana de todos os 2n elementos nos vetores X e Y.
 Mediana: depois de ordenados os valores por ordem crescente ou decrescente, a mediana é:
 - o valor que ocupa a posição central, se a quantidade desses valores for ímpar;
 - a média dos dois valores centrais, se a quantidade desses valores for par.
Considere o seguinte algoritmo, sendo n ≥ 0 e inteiro:
(1) s ( 0
(2) para i ( 1 até n faça
(3) 	s ( s + i * i
(4) devolve s;
(a) Qual a resposta dada ao executar este algoritmo?
(b) Qual é a operação básica?
(c) Quantas vezes essa operação é executada?
(d) Qual é a classe de eficiência desse algoritmo?
(e) Existe um algoritmo melhor que responda ao mesmo problema? Descreva-o ou mostre que tal algoritmo não existe
Multiplicação de números
Quanto tempo é necessário para multiplicar dois números naturais (como 3141592653589793238462643383 e 1414213562373095048801688724209, por exemplo)?   
Se os números têm m e n dígitos respectivamente, o algoritmo usual consome tempo proporcional a mn. No caso de m = n, o consumo de tempo é, portanto, proporcional a n2. 
É difícil imaginar um algoritmo mais rápido que o usual se m e n forem pequenos (menores que 500, digamos).  Mas existe um algoritmo que é bem mais rápido quando m e n são grandes (como acontece em criptografia, por exemplo). 
Usaremos notação decimal para representar números naturais. Diremos que um dígito é qualquer número menor que 10.  Diremos que um número natural u tem no máximo n dígitos se u < 10n.  
Problema da multiplicação:  Dados números naturais u e v com no máximo n dígitos cada, calcular (a expansão decimal) do produto uv. 
Ideia básica do algoritmo de Karatsuba e Ofman
Sejam u e v dois números com no máximo n dígitos cada. Suponha, por enquanto, que n é par. Seja p o número formado pelos n/2 primeiros dígitos (dígitos mais significativos) de u e seja q o número formado pelos n/2 últimos dígitos (dígitos menos significativos) de u. 
Assim, temos: u   =   p 10n/2 + q. 
Defina r e s analogamente para v, de modo que v = r 10n/2 + s.  
Teremos então uv  =  pr 10n + (ps+qr) 10n/2 + qs (*).
A expressão acima reduz a multiplicação de dois números com no máximo n dígitos cada a quatro multiplicações (a saber, p por r, p por s, q por r e q por s) de números com no máximo n/2 dígitos cada.  Infelizmente, essa redução não é suficiente para tornar a multiplicação mais eficiente. 
Agora observe que os três números de que precisamos do lado direito de (*) — a saber  pr,  (ps+qr)  e  qs — podem ser obtidos com apenas três multiplicações, pois 
ps + qr   =   y  −  pr  −  qs ,    sendo  y  =  (p+q)(r+s),  
e portanto a equação (*) pode ser substituída por 
uv   =   pr 10n + ( y − pr − qs) 10n/2 + qs. 
É bem verdade que essa equação envolve duas adições e duas subtrações adicionais, mas essas operações consomem muito menos tempo que as multiplicações.  Se n não é par, basta trocar n/2 por k = teto(n/2)�.  
Teremos então  u = p 10k + q  e  v = r 10k + s  e portanto, 
uv  =  pr 102k + ( y − pr − qs) 10k + qs. 
Essa é a base do algoritmo. 
Exemplo:  Quero multiplicar 6514202 por 9898989.  O resultado das contas pode ser resumido assim: 
65142
 4853 → p+q
02 → u = p104 + q
	9898989 → v = r104 + s 
64383		 → pr
 37771778 → qs 9978 → r+s
 48423234 → y = (p+q)(r+s)
 10007617 → y−pr−qs
64484013941778→ uv = pr108 + (y−pr−qs)104 + qs 
Suponha que o algoritmo de Karatsuba e Ofman leva 1 minuto para multiplicar dois números de n dígitos cada.
Quanto tempo levará para multiplicar dois números de 10n dígitos cada? 
Faça uma estimativa análoga para o algoritmo de multiplicação usual. 
Atividade Individual
Nota: 2
Entregar: código-fonte.
Implementação: Linguagem C.
Data de entrega: 05/06/2017
Nome do arquivo para entrega: 2017_1_AAC_RA_NOME_2B_A1, onde RA é o número do RA do aluno e NOME é o nome do aluno.
Campinas/2015
� teto(x) 
O único inteiro i tal que  i−1 < x ≤ i.  A notação correta para teto(x) é  ⌈x⌉.  
_1407861632.doc