pr-1-asa-2013-1

Prévia do material em texto

IC/UFF - Ana´lise e S´ıntese de Algoritmos - Primeira Prova - 2013/1
Questa˜o 1: Falso ou verdadeiro? (justifique)
(a) (1,0) Se a complexidade de pior caso de um algoritmo A que resolve um problema P e´ T (n) =
O(n log n), enta˜o o limite inferior assinto´tico `(n) de P satisfaz `(n) = Ω(n log n).
(b) (1,0) O algoritmo de ordenac¸a˜o QUICKSORT tem complexidade de pior caso T (n) = Θ(n2) quando
todos os n elementos do vetor de entrada sa˜o iguais.
Questa˜o 2: Considere o seguinte algoritmo:
func¸a˜o miste´rio(y, z)
entrada: nu´meros naturais y e z
x← 0;
enquanto z > 0 fac¸a
se z mod 2 = 1 enta˜o x← x+ y fim-se; (z mod 2 calcula o resto da divisa˜o de z por 2)
y ← 2y; z ← bz/2c;
fim-enquanto
retorne(x);
fim-func¸a˜o
(a) (1,0) O que faz o algoritmo acima? (justifique)
(b) (1,0) Calcule a complexidade de pior caso do algoritmo acima, contando o nu´mero de somas x + y.
Descreva as entradas que levam o algoritmo ao pior caso.
Questa˜o 3: Resolva os itens abaixo.
(a) (2,0) Elabore um algoritmo para o seguinte problema: Dado um vetor V [1..n] com n elementos,
determine um subvetor V [i..j] de V [1..n] tal que: (a) V [i] ≤ V [i+ 1] ≤ . . . ≤ V [j]; (b) o valor j − i+ 1 e´
ma´ximo. Este problema e´ conhecido como subsequeˆncia cont´ıgua ordenada mais longa.
(b) (1,0) Calcule a complexidade de pior caso do algoritmo acima.
Questa˜o 4: E´ dado o algoritmo recursivo abaixo:
ALGORITMO(L, i, j)
se i = j enta˜o retorne (L[i], L[i])
sena˜o se j = i+ 1 enta˜o
se L[i] < L[j] enta˜o retorne (L[i], L[j])
sena˜o retorne (L[j], L[i])
sena˜o
m← b(i+ j)/2c
(a, b)← ALGORITMO(L, i,m)
(c, d)← ALGORITMO(L,m+ 1, j)
se a < c enta˜o min ← a sena˜o min ← c
se b > d enta˜o max ← b sena˜o max ← d
retorne(min,max )
Considere a chamada externa ALGORITMO(L, 1, n), para um vetor de entrada L com n elementos.
Seja T (n) o nu´mero de comparac¸o˜es que ALGORITMO realiza quando existem n elementos no vetor de
entrada.
(a) (1,0) Escreva as equac¸o˜es de recorreˆncia que definem T (n), de acordo com o algoritmo acima.
(b) (2,0) Resolva a recorreˆncia do item (a) pelo me´todo das substituic¸o˜es sucessivas, supondo que n e´
uma poteˆncia de 2. Depois, prove por induc¸a˜o que a fo´rmula fechada obtida esta´ correta.