prova1-2013.1-George Marconi

Prévia do material em texto

Universidade Federal da Bahia (UFBA)
Instituto de Matema´tica (IM)
Departamento de Cieˆncia da Computac¸a˜o (DCC)
MATA 52 - Ana´lise e Projetos de Algoritmos - Prof. George Lima
2013.1 - 18/07/2013 - Prova 1 - Durac¸a˜o: 17:00h - 19:00h
Nome: GABARITO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1. Demonstre que n3 + n log2 n + 10n = O(n
3) [1 pt]
Devemos mostrar que existem constantes c > 0, n0 > 0 tal que n
3 + n log2 n + 10n ≤ cn3, para
todo n ≥ n0.
n3 + n log2 n + 10n ≤ cn3 ⇒ 1 +
log2 n
n2
≤ c
A relac¸a˜o acima e´ verdadeira para n ≥ n0 = 2 e c ≥ 54 , o que completa a demonstrac¸a˜o.
2. Sabe-se que a func¸a˜o f(n) = n2 + 10n + 5 descreve o comportamento temporal de um dado
algoritmo A cujo tamanho de entrada e´ dado, em bits, pela func¸a˜o g(n). Fornec¸a para cada uma
das alternativas abaixo a complexidade de tempo de A usando notac¸a˜o Θ e indique para cada
caso se A tem comportamento polinomial ou exponencial: [1,5 pt]
A complexidade de um algoritmo e´ dada pelo seu custo computacional expresso em func¸a˜o do
tamanho de sua entrada. Desta forma, deve-se determinar a func¸a˜o f(g(n)). Para cada um dos
casos, temos:
(a) g(n) = log2 n. Isto implica que f(g(n)) = (log2 n)
2 + 10 log2 n+ 5 = Θ(log
2 n), o que indica
que A tem custo polinomial em func¸a˜o de sua entrada.
(b) g(n) = 10n+ 15. Neste caso, e´ fa´cil de ver que f(g(n)) = (10n+ 15)2 + 10(10n+ 15) + 5 =
Θ(n2) e, portanto, A tem custo polinomial.
(c) g(n) = 2n. Como f(g(n)) = 22n + 10 2n + 5 = Θ(4n), A tem custo exponencial.
3. Resolva a seguinte recorreˆncia T (n) = 2T (n2 ) + n log n [1,5 pt]
Usando o me´todo da a´rvore, percebemos que o custo de cada n´ıvel i = 0, 1, . . . , log2 n− 1 e´ dado
por n log2
n
2i
. Desta forma, o custo total da a´rvore e´ dado por
log2 n−1∑
i=0
n log2
n
2i
= n
log2 n−1∑
i=0
log2 n−
log2 n−1∑
i=0
i
 =
= n
(
log22 n−
(log2 n− 1) log2 n
2
)
=
n
2
(log22 n− log2 n) = Θ(n log2 n)
Notar que na˜o se pode usar o me´todo mestre para resolver esta questa˜o, pois na˜o existe constante
positiva c < 1 tal que
n log
n
2
< cn log n
e esta e´ uma condic¸a˜o necessa´ria para aplicar o caso 3 do teorema.
4. Considere uma matriz nume´rica A de dimensa˜o 2n × 2n, n ∈ Z. Os elementos de A esta˜o
dispostos em ordem crescente, isto e´, ai,j ≤ ai,j+1 (0 < i ≤ n, 0 < j ≤ n − 1 ) e ai,j ≤ ai+1,j
(0 < i ≤ n− 1, 0 < j ≤ n). Considere a te´cnica divisa˜o e conquista e responda:
(a) Desenvolva um algoritmo para encontrar um elemento x em A. [2 pts] Pode-se usar pesquisa
bina´ria devido a` ordem em que os elementos ai,j da matriz A esta˜o dispostos. Inicialmente,
localiza-se a linha l que pode conter o elemento x. Posteriormente, pesquisa-se por x nesta
linha.
i← 1;
j ← 2n;
c← 2n;
while i < j do
l←
⌈
i+j
2
⌉
;
if x = al,c then return (l, c);
else if x ≤ al,c then j ← l − 1;
else i← l + 1;
i← 1;
j ← 2n;
while i ≤ j do
c←
⌈
i+j
2
⌉
;
if x = al,c then return (l, c);
else if x ≤ al,c then j ← c− 1;
else i← c + 1;
return −1;
Pesquisa bina´ria aplicada a todas as ce´lulas da matriz pode tambe´m ser realizada. Para
tanto, considere que as func¸o˜es lin(p) e col(p) fornecem a linha e coluna da p-e´sima ce´lula
da matriz. Neste caso, a pesquisa bina´ria pode ser aplica ao intervalo 1 a 22n.
(b) Encontre a fo´rmula de recorreˆncia do algoritmo desenvolvido [0,5 pt] Para se buscar a linha
l, algoritmo comporta-se de acordo com T (N) = T (N/2) + Θ(1), onde N e´ o nu´mero de
linhas. Analogamente, T (N) = T (N/2) + Θ(1) expressa o comportamento do algoritmo
para encontrar a posic¸a˜o do elemento na linha l. Desta forma, o algoritmo executa 2T (N)
passos, ou seja, 2T (N) = 2T (N/2) + Θ(1), o que implica que, T (N) = T (N/2) + Θ(1)
tambe´m expressa seu comportamento como um todo.
(c) Fornec¸a a complexidade do algoritmo em notac¸a˜o Θ [0,5 pt] De acordo com a expressa˜o
acima, o algoritmo executa T (N) = Θ(logN) passos. Como N = 2n, temos que T (n) =
Θ(n) passos.
5. Sobre o quickSort, responda:
(a) Ilustre o funcionamento do algoritmo aplicado a` sequeˆncia 8, 3, 1, 5, 10, 3, 2, 11 [1 pt]
8, 3, 1, 5, 10, 3, 2, 11
8, 3, 1, 5, 2, 3, 10, 11
3, 3, 1, 5, 2 |8| 10, 11
3, 3, 1, 2, 5 |8| 10, 11
2, 3, 1 |3| 5 |8| 10, 11
2, 1, 3 |3| 5 |8| 10, 11
1 |2| 3 |3| 5 |8| 10, 11
1 |2| 3 |3| 5 |8| |10| 11
(b) Fornec¸a uma sequeˆncia de 10 nu´meros que leva ao pior caso de execuc¸a˜o considerando que
o pivoˆ e´ sempre o primeiro elemento da sequeˆncia [1 pt]
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
(c) Fornec¸a a relac¸a˜o de recorreˆncia que representa o caso me´dio de execuc¸a˜o [1 pt] Como
ha´ n poss´ıveis formas de particionamento da sequeˆncia a ser ordenada e a func¸a˜o de par-
ticionamento tem custo Θ(n), a recorreˆncia para um dado particionamento i e´ T (n) =
T (n − 1) + T (i) + Θ(n). Assumindo que cada um dos particionamentos e´ igualmente
prova´vel, o valor esperado do custo do algoritmo e´ dado por
T (n) =
1
n
n−1∑
i=0
(T (n− i− 1) + T (i) + Θ(n))
Considerando a simetria dos poss´ıveis particionamentos e como sabemos que 1n
∑n−1
i=0 Θ(n) =
Θ(n), a expressa˜o acima pode ser escrita como
T (n) =
2
n
n−1∑
i=0
T (i) + Θ(n)