Lista09_DefRecursivasIndEstruturalAlgRecursivos[solucao]

Prévia do material em texto

Área de Teoria DCC/UFMG Introdução à Lógica Computacional 2019/02
SOLUÇÃO DE LISTA DE EXERCÍCIOS
Lista 09
(Definições Recursivas e Indução Estrutural, Algoritmos Recursivos)
Leitura necessária:
• Matemática Discreta e Suas Aplicações, 6a Edição (Kenneth H. Rosen):
– Caṕıtulo 4.3: Definições Recursivas e Indução Estrutural
– Caṕıtulo 4.4: Algoritmos Recursivos
Revisão.
1. Responda formalmente as seguintes perguntas:
(a) O que é uma definição recursiva? Quais os elementos essenciais de uma definição recursiva?
Solução do professor: Uma definição recursiva é uma definição de um objeto em termos de
si próprio.
Os elementos essenciais da definição recursiva são:
• um ou mais passos-base, em que se determinam os primeiros objetos que atendem à definição;
e
• um ou mais passos recursivos, em que se determina como construir novos objetos a partir de
objetos que já atendem à definição.
Exerćıcios.
2. (Rosen 4.3.1) Encontre f(1), f(2), f(3) e f(4) se f(n) for definido recursivamente por f(0) = 1 e para
n = 0, 1, 2, . . .:
a) f(n+ 1) = f(n) + 2
Solução do professor:
f(1) = f(0 + 1) = f(0) + 2 = 1 + 2 = 3
f(2) = f(1 + 1) = f(1) + 2 = 3 + 2 = 5
f(3) = f(2 + 1) = f(2) + 2 = 5 + 2 = 7
f(4) = f(3 + 1) = f(3) + 2 = 7 + 2 = 9
b) f(n+ 1) = 3f(n)
1
Solução do professor:
f(1) = f(0 + 1) = 3f(0) = 3 · 1 = 3
f(2) = f(1 + 1) = 3f(1) = 3 · 3 = 9
f(3) = f(2 + 1) = 3f(2) = 3 · 9 = 27
f(4) = f(3 + 1) = 3f(3) = 3 · 27 = 81
c) f(n+ 1) = 2f(n)
Solução do professor:
f(1) = f(0 + 1) = 2f(0) = 21 = 2
f(2) = f(1 + 1) = 2f(1) = 22 = 4
f(3) = f(2 + 1) = 2f(2) == 24 = 16
f(4) = f(3 + 1) = 2f(3) == 216 = 65 536
d) f(n+ 1) = f(n)2 + f(n) + 1
Solução do professor:
f(1) = f(0 + 1) = f(0)2 + f(0) + 1 = 12 + 1 + 1 = 3
f(2) = f(1 + 1) = f(1)2 + f(1) + 1 = 32 + 3 + 1 = 13
f(3) = f(2 + 1) = f(2)2 + f(2) + 1 = 132 + 13 + 1 = 183
f(4) = f(3 + 1) = f(3)2 + f(3) + 1 = 1832 + 183 + 1 = 33 673
3. (Rosen 4.3.3) Encontre f(2), f(3), f(4) e f(5) se f(n) for definido recursivamente por f(0) = −1,
f(1) = 2 e para n = 0, 1, 2, . . .:
a) f(n+ 1) = f(n) + 3f(n− 1)
Solução do professor:
f(2) = f(1 + 1) = f(1) + 3f(0) = 2 + 3 · (−1) = −1
f(3) = f(2 + 1) = f(2) + 3f(1) = −1 + 3 · 2 = 5
f(4) = f(3 + 1) = f(3) + 3f(2) = 5 + 3 · (−1) = 2
f(5) = f(4 + 1) = f(4) + 3f(3) = 2 + 3 · 5 = 17
d) f(n+ 1) = f(n−1)/f(n)
Solução do professor:
f(2) = f(1 + 1) = f(0)/f(1) = −1/2
f(3) = f(2 + 1) = f(1)/f(2) = 2/(−1/2) = −4
f(4) = f(3 + 1) = f(2)/f(3) = (−1/2)/−4 = 1/8
f(5) = f(4 + 1) = f(3)/f(4) = −4/1/8 = −32
4. (Rosen 4.3.7) Dê uma definição recursiva para a sequência {an}, n = 1, 2, 3, ... se
(a) an = 6n.
2
Solução do professor: Primeiro vamos determinar a1.
a1 = 6(1)
= 6
Agora vamos determinar an para n ≥ 2.
an−1 = 6(n− 1)
= 6n− 6
= an − 6
Logo
an = an−1 + 6,
e a resposta final é {
a1 = 6,
an = an−1 + 6, para n ≥ 2.
(b) an = 2n+ 1.
Solução do professor: Primeiro vamos determinar a1.
a1 = 2(1) + 1
= 3
Agora vamos determinar an para n ≥ 2.
an−1 = 2(n− 1) + 1
= 2n− 1
= 2n+ (1− 1)− 1
= (2n+ 1)− 2
= an − 2
Logo
an = an−1 + 2,
e a resposta final é {
a1 = 3,
an = an−1 + 2, para n ≥ 2.
(c) an = 10
n.
3
Solução do professor: Primeiro vamos determinar a1.
a1 = 10
1
= 10
Agora vamos determinar an para n ≥ 2.
an−1 = 10
n−1
=
10n
10
=
an
10
Logo
an = 10an−1
e a resposta final é {
a1 = 10,
an = 10an−1, para n ≥ 2.
(d) an = 5.
Solução do professor: Primeiro vamos determinar a1.
a1 = 5
Agora vamos determinar an para n ≥ 2.
an = 5
Logo a resposta final é {
a1 = 5,
an = 5, para n ≥ 2.
5. (Rosen 4.3.25) Dê uma definição recursiva de:
(a) o conjunto dos inteiros pares.
Solução do professor: {
0 ∈ S,
se x ∈ S então x+ 2 ∈ S e x− 2 ∈ S.
(b) o conjunto dos inteiros positivos congruentes a 2 módulo 3 (ou seja, os inteiros positivos que têm
resto 2 na divisão por 3).
4
Solução do professor: {
2 ∈ S,
se x ∈ S então x+ 3 ∈ S.
(c) o conjunto dos inteiros positivos não diviśıveis por 5.
Solução do professor: {
1 ∈ S, 2 ∈ S, 3 ∈ S, 4 ∈ S,
se x ∈ S então x+ 5 ∈ S.
6. (Rosen 4.3.27) Seja S um subconjunto dos pares ordenados de inteiros, definido recursivamente por
Passo base: (0, 0) ∈ S,
Passo recursivo: Se (a, b) ∈ S, então (a, b+ 1) ∈ S, (a+ 1, b+ 1) ∈ S e (a+ 2, b+ 1) ∈ S.
a) Liste os elementos de S produzidos pelas quatro primeiras aplicações da definição recursiva.
Solução do professor:
• Aplicação 0: S0 = {(0, 0)}.
• Aplicação 1: S1 = S0 ∪ {(0, 1), (1, 1), (2, 1)}.
• Aplicação 2: S2 = S1 ∪ {(0, 2), (1, 2), (2, 2), (3, 2), (4, 2)}.
• Aplicação 3: S3 = S2 ∪ {(0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (6, 3)}.
• Aplicação 4: S4 = S3 ∪ {(0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (6, 4), (7, 4), (8, 4)}.
c) Utilize indução estrutural para mostrar que a ≤ 2b quando (a, b) ∈ S.
Solução do professor:
Passo base. 0 ≤ 2 · 0.
Passo indutivo. Assuma que para um (a, b) ∈ Sk arbitrário tenhamos a ≤ 2b.
As regras do passo recursivo são:
• (a, b+ 1) ∈ S: então a ≤ 2(b+ 1) = 2b+ 2 é verdadeiro porque pela I.H. já temos a ≤ 2b.
• (a + 1, b + 1) ∈ S: então a + 1 ≤ 2(b + 1) = 2b + 2 é o mesmo que a ≤ 2b + 1, o que é
verdadeiro porque pela I.H. já temos a ≤ 2b.
• (a+ 2, b+ 1) ∈ S: então a+ 2 ≤ 2(b+ 1) = 2b+ 2 é o mesmo que a ≤ 2b, o que é verdadeiro
porque pela I.H. temos a ≤ 2b.
7. (Rosen 4.3.29) Dê uma definição recursiva para cada um dos conjuntos de pares ordenados de inteiros
positivos. (Dica: Plote os pontos no plano e procure por linhas que contenham os pontos do conjunto.)
(a) S = {(a, b) | a, b ∈ Z+, a+ b é par}
5
Solução do professor: Uma definição recursiva para este conjunto é a seguinte:{
(1, 1) ∈ S,
se (a, b) ∈ S, então (a+ 2, b) ∈ S, (a+ 1, b+ 1) ∈ S e (a, b+ 2) ∈ S.
(b) S = {(a, b) | a, b ∈ Z+, a ou b é ı́mpar}
Solução do professor: Uma definição recursiva para este conjunto é a seguinte:
{
(1, 1) ∈ S, (1, 2) ∈ S, (2, 1) ∈ S,
se (a, b) ∈ S, então (a+ 2, b) ∈ S e (a, b+ 2) ∈ S.
8. (Rosen 4.3.35) Dê uma definição recursiva para o reverso de uma string. (Dica: primeiro defina o
reverso de uma string vazia λ. Então escreva uma string w de tamanho n+ 1 como xy, onde x é uma
string de tamanho n, e expresse o reverso de w em termos de xR e y.)
Solução do professor: Dada uma string x, seja xR o seu reverso. Dadas duas strings x e y, seja
x · y a concatenação de x com y, i.e., a string formada ao se acoplar y ao final de x. Então o reverso
de uma string s pode ser definido como:
sR =
{
λ, se s é a string vazia,
y · xR, se s = x · y, onde y contém um único caracter.
9. (Rosen 4.3.43) Seja T é uma árvore binária completa (ou seja, uma árvore em que todos os vértices
internos têm exatamente dois vértices filhos), seja n(T ) o número de vértices na árvore T , e seja h(T )
a altura (ou seja, o maior caminho da raiz até uma folha da árvore) de T .
Use indução estrutural para mostrar que n(T ) ≥ 2h(T ) + 1.
Solução do professor: Passo base: A menor árvore binária completa possui apenas um vértice, o
raiz, e neste caso n(T ) = 1 e h(T ) = 0, portanto 1 ≥ 2 · 0 + 1.
Passo indutivo: Assuma que para quaisquer duas árvore binárias completas T1 e T2 tenhamos n(T1) ≥
2h(T1) + 1 e n(T2) ≥ 2h(T2) + 1.
A árvore binária completa T formada tendo um nodo como raiz e como sub-árvores T1 e T2 tem
como número total de nodos o valor n(T ) = 1 + n(T1) + n(T2). Além disso, T tem altura h(T ) =
max (h(T1), h(T2)) + 1.
Assim, podemos derivar:
n(T ) = n(T1) + n(T2) + 1 (usando a fórmula para n(T ))
≥ (2h(T1) + 1) + n(T2) + 1 (pela I.H. em T1)
≥ (2h(T1) + 1) + (2h(T2) + 1) + 1 (pela I.H. em T2)
= 2(h(T1) + h(T2) + 1) + 1
≥ 2(max (h(T1), h(T2)) + 1) + 1 (já que h(T1) + h(T2) ≥ max (h(T1), h(T2)) )
= 2h(T ) + 1 (usando a fórmula para h(T ))
6
10. (Rosen 4.4.11) Dê um algoritmo recursivo para encontrar o mı́nimo de um conjunto finito de números
inteiros, considerando o fato de que o mı́nimo de n números inteirosé o menor entre o último inteiro
da lista e o mı́nimo dos primeiros n− 1 elementos da lista.
Exiba como seu algoritmo encontra o mı́nimo elemento do conjunto {3, 5, 1, 2, 4}.
Solução do professor: O algoritmo é dado a seguir:
procedure smallest(a1, a2, . . . , an : integers)
if n = 1 then return a1
else return min(smallest(a1, . . . , an−1), an)
Para a lista {3, 5, 1, 2, 4}, o algoritmo funciona da seguinte forma:
smallest(3, 5, 1, 2, 4) =
min(smallest(3, 5, 1, 2), 4) =
min(min(smallest(3, 5, 1), 2), 4) =
min(min(min(smallest(3, 5), 1), 2), 4) =
min(min(min(min(smallest(3), 5), 1), 2), 4) =
min(min(min(min(3, 5), 1), 2), 4) =
min(min(min(3, 1), 2), 4) =
min(min(1, 2), 4) =
min(1, 4) =
1
7