Projeto e Análise de Algorítimos

Universidade Federal do Piauí – UFPI
Universidade Aberta do Piauí – UAPI
Bacharelado em Sistemas de Informação
Professor: Ricardo Viana
Disciplina: Projeto e Análise de algoritmos
Avaliação
1. Suponhamos 2 algoritmos de ordenação, A e B. Vamos executá-los na mesma máquina. A é executado em 8*n etapas, enquanto B necessita de 128*log n. Qual dos dois é melhor? Em que condições? (Considere log como sendo logaritmo na base 2).

2. Coloque em ordem decrescente de complexidade as principais classes de problemas listadas a seguir.
O(log n); O(n!); O(2n); O(n); O(1); O(n3); O(n2); O(n log n)
R: O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n) < O(n!)
3. Represente as funções a seguir segundo a notação O.
a. 2n + 732n2
R: O(2n)
b. n2 + 50nlogn
R: O(n2)
c. 1523logn + 347nlogn +5372n
R: O(nlogn)
d. (n + 10)!
R: O(n!)
4. Use uma árvore de recursão para determinar um limite assintótico para as seguintes recorrências. A seguir, use o método mestre para verificar a corretude da árvore de recursão. a. T(n) = 3T(n/4) + n2 a = 3; b = 4; f(n) = n² nlog3..4 < n² -> O(n²)
b. T(n) = 9T(n/3) + n a = 9; b = 3; f(n) = n nlog9..3 = n² > n -> O(n²)

5. Encontre a melhor ordem de multiplicação para as seguintes matrizes:
a. A1 (10x20), A2 (20x15), A3 (15x25), A4 (25x10)
Matriz M:
0 3000 6750 8250
0 0 7500 6750
0 0 0 3750
0 0 0 0
Matriz S:
0 1 2 2
0 0 2 2
0 0 0 3
0 0 0 0
Parentização:
(A0((A1A2)(A3A4)))

6. Encontre o código de Huffman, ou seja, a árvore de prefixo para as seguintes frequências de caracteres. Após isso, especifique o código de cada caractere, a quantidade de bits que será enviada na mensagem e a porcentagem de ganho quando comparado ao envio de caracteres propriamente ditos e ao código binário de tamanho fixo. a. a: 45, e:28, c:14, f:35, g:10, r:7, h:1, p:3, t:8
153
65 e:28 f:35 a:45

88
43
18 t:8 g:10 c:14

25
11
r:7

4 h:1 e=00

f=01

a=10

t=1100

g=1101

c=1110

p:3

r=11110

h=111110

p=111111

Bits enviados = 28*2+35*2+45*2+8*4+10*4+14*4+7*5+1*6+3*6 = 403