Faculdade Campo Limpo Paulista
Mestrado em Ciência da Computação
Complexidade de Algoritmos – Avaliação 2
1. (2,0): Resolva a seguinte relação de recorrência.
T(n) = T(n – 1) + 3
T(1) = 3
Pelo método iterativo progressivo.
T(1) = 3
T(2) = T(1) + 3 = 3 + 3 = 6
T(3) = T(2) + 3 = 3 + 3 + 3 = 9
T(4) = T(3) + 3 = 3 + 3 + 3 + 3 = 12
...
T(n) = 3n
1
2. (2,0): Membros antigos da Sociedade de Pitágoras definiram números figurados
como sendo o número de pontos em uma certa configuração geométrica. Os
primeiros números triangulares são 1, 3, 6 e 10 e são semelhantes aos diagramas
das figuras ilustradas abaixo. Ache uma fórmula para Q(n), onde Q(n) é a
quantidade de números triangulares (pontos) para a figura de ordem n. Prove, por
indução, que a sua fórmula está correta.
10 pontos
6 pontos
3 pontos
1 ponto
n
=
1
2
3
4
Percebe-se que a soma dos pontos na figura de ordem n é igual a 1 + 2 + 3 + 4 + ... + n. Logo
propomos Q(n) = n (n + 1) / 2, para n ≥ 1.
Provaremos, por indução em n, que Q(n) é verdadeira.
i) Base.
Para n = 1, a figura tem um ponto. Pela fórmula Q(1) = 1 ( 1 + 1 ) / 2 = 1. Logo, a fórmula é
verdadeira para n = 1.
ii) Hipótese de indução.
Vamos assumir que a fórmula é verdadeira para n – 1, n ≥ 2. Ou seja, estamos assumindo, por
hipótese, que Q(n – 1) = (n – 1) n / 2.
iii) Relação entre a quantidade de pontos da figura de ordem n ( Q(n) ) com a quantidade de
pontos da figura de ordem n – 1 ( Q(n – 1) ).
2
...
...
...
n pontos
Q (n - 1)
Q (n )
Observando o esquema acima, inferimos que Q(n) = Q(n – 1) + n.
iv) Prova do fato de que Q(n – 1) sendo verdadeira implica no fato de que Q(n) é verdadeira.
Q(n) = Q(n – 1) + n.
Q(n) = (n – 1) n / 2 + n.
Q(n) = ( n2 – n + 2 n ) / 2.
Q(n) = (n2 + n ) / 2.
Q(n) = n (n + 1) / 2.
3
3. (2,0): Prove, por indução, que a soma dos ângulos internos de um polígono convexo
de n lados (n ≥ 3) é igual a S(n) = (n – 2) . 180o. Dicas: (i) a base (n = 3) está
resolvida abaixo; (ii) tente expressar a soma dos ângulos internos de um polígono
convexo de n lados como função da soma dos ângulos internos de um polígono
convexo de n - 1 lados.
i) Base.
Para n = 3 temos um triângulo. Pela figura abaixo, infere-se que a + b + c = 180º.
B
o
a + b + c = 180
b
b
A
a
c
C
c
Pela fórmula S(3) = (3 – 2) . 180o = 180º. A fórmula é verdadeira para a base.
ii) Hipótese de indução.
S (n – 1) = (n – 3 ) . 180º, n ≥ 4.
iii) Relação entre a soma dos ângulos internos de um polígono convexo de n lados e tal soma
em um polígono convexo de n – 1 lados.
Pela ilustração acima, infere-se que S(n) = S(n – 1) + 180º.
4
iv) Prova do fato de S(n – 1) ser verdadeira implica que S(n) é verdadeira.
S(n) = S(n – 1) + 180º.
S(n) = (n – 3).180º + 180º.
S(n) = (n – 2).180º.
5
4. Calcule a complexidade do algoritmo a seguir.
Algoritmo A(n)
Entrada: n, inteiro, n ≥ 1.
{
se (n = 1)
retornar 1
senão
retornar A(n/2) + 1
}
T(n)
T(1)
Algoritmo A(n)
Entrada: n, inteiro, n ≥ 1.
{
se (n = 1)
T(n/2)
retornar 1
senão
retornar A(n/2) + 1
}
tempo para fazer 1 soma
T(n) = T(n/2) + 1
T(1) = 0
Esta relação de recorrência é do tipo “dividir para conquistar”, T(n) = aT(n/b) + cnk, cuja
solução está tabelada.
Neste caso a = 1 ( a ≥ 1, OK ), b = 2 ( b ≥ 2, OK ), c = 1 e k = 0 (c e k constantes, OK).
Como a = 1 > bk = 20 = 1, então
T(n) = O ( nk log n ) = O ( log n ).
6
5. (2,0): Aplicando a técnica indutiva de design de algoritmos, escreva um algoritmo
que receba um conjunto A de n inteiros, um inteiro k e determine se existe um
subconjunto B de A tal que a soma dos elementos de B seja igual a k. Por exemplo,
se A = {2, 5, 8, 9, 15, 18} e k = 22 então a resposta do algoritmo deve ser sim
(verdadeiro), pois existe um subconjunto B = {2, 5, 15} cuja soma é igual a 22. Não
é necessário calcular a complexidade do seu algoritmo.
Observação: para facilitar a escrita do algoritmo, considere poder utilizar na sua solução as
seguintes expressões:
• C := A ∪ B: constrói um conjunto C formado pela união dos conjuntos A e B.
• C := A ∩ B: constrói um conjunto C formado pela interseção dos conjuntos A e B.
• A [i]: representa o i-ésimo elemento do conjunto A.
i) Interface
Sub (A, n, k).
ii) Significado
Sendo A um conjunto de n elementos, retorna verdadeiro caso exista um subconjunto de A cuja
soma dos elementos seja igual a k. Caso contrário, retorna falso.
iii) Redução
Comandos
B := A – { A [n] };
se ( Sub (B, n – 1, k) = verdadeiro )
retornar verdadeiro
senão
retornar Sub (B, n – 1, k – A [n] )
iv) Base
A redução ocorre de 1 em 1. Propomos uma base para n = 1. Neste caso, basta comparar A[1]
com k. Se forem iguais retornamos verdadeiro e, caso, contrário, retornamos falso.
Comandos
se ( A [1] = k )
retornar verdadeiro
senão
retornar falso
7
v) Algoritmo
T(n)
Algoritmo Sub (A, n, k)
{
se (n = 1) // BASE
{
se ( A [1] = k )
T(1)
retornar verdadeiro
senão
O (n)
retornar falso
}
senão // REDUÇÃO
T(n - 1)
{
B := A – { A [n] };
se ( Sub (B, n – 1, k) = verdadeiro )
retornar verdadeiro
senão
retornar Sub (B, n – 1, k – A [n] )
}
}
vi) Complexidade
T(n) = 2 T(n – 1) + O(n)
T(1) = 1
Resolvendo-se esta relação de recorrência chega-se a
T(n) = O (2n).
8
T(n - 1)
n
6. (2,0): (opcional1): Prove, por indução, que S (n) = ∑ i 2 é O(n3).
i =1
n
Temos que mostrar que existem c > 0 e N tais que S (n) = ∑ i 2 ≤ c n3 para n ≥ N.
i =1
Base
para i = 1, temos S(1) = 12 = 1 ≤ c 13. Logo c ≥ 1 (para satisfazer a base).
Hipótese de indução
n
S (n − 1) = ∑ i 2 ≤ c (n – 1)3 para n ≥ N.
i =1
Redução
S (n) = 12 + 22 + 32 + ... + (n – 1)2 + n2
S (n - 1) = 12 + 22 + 32 + ... + (n – 1)2
Logo, propomos a redução S(n) = S (n -1) + n2.
Prova de que a validade do teorema para S(n – 1) implica na validade do teorema
para S(n)
S(n) = S (n -1) + n2
S(n) ≤ c (n – 1)3 + n2
Para provarmos o que queremos temos que conseguir mostrar que S(n) ≤ c n3, ou seja,
mostrar que S(n) ≤ c (n – 1)3 + n2 ≤ c n3. Se mostrarmos que existe c > 0 que satisfaz as
condições desta inequação para n ≥ N estará provado.
c (n – 1)3 + n2 ≤ cn3
c (n3 -3n2 + 3n – 1) + n2 ≤ cn3
cn3 -3cn2 + 3cn – c + n2 ≤ cn3
(-3c + 1) n2 + 3cn – c ≤ 0
Seja c = 1. Assim, obtemos
-2n2 + 3n – 1 ≤ 0.
As raízes de -2n2 + 3n – 1 são 1/2 e 1. Como o coeficiente do termo n2 é negativo (parábola
com a “boca” direcionada para baixo) esta inequação é verdadeira para n ≤ 1/2 (não nos
interessa) e para n ≥ 1. Dizemos, portanto, que N = 1.
1
Poderá ser utilizada para substituir algum dos exercícios anteriores.
9
n
Logo, existem c > 0 ( c = 1 ) e N ( N = 1 ) que satisfazem S (n) = ∑ i 2 ≤ c n3 para n ≥ N.
i =1
Está, portanto, provado que
n
S (n) = ∑ i 2 é O(n3).
i =1
10