Recursão: Progressão Aritmética, Conjunto de Cadeias e Função

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Recursão
1. Uma progressão aritmética é uma sequência da forma a, a + d, a + 2d, a + 3d, …, isto é, a sequência começa com o número a e cada termo sucessivo é obtido do 
anterior adicionado d (a diferença comum entre dois termos quaisquer). A progressão aritmética geral pode ser definida recursivamente por a1 = a e ak + 1 = ak + d 
para k ≥ 1. Nesse contexto, encontre a solução geral para a progressão aritmética assinalando a alternativa correta. 
R: Resposta: alternativa b.
A sequência começa com o número 𝑎 e cada termo sucessivo é obtido do anterior adicionado
𝑑 (a diferença comum entre dois termos quaisquer). Por exemplo,
(i) 𝑎 = 5, 𝑑 = 3: 5,8,9,11, …
(ii) 𝑎 = 2, 𝑑 = 5: 2,7,12,17, …
(iii) 𝑎 = 1, 𝑑 = 0: 1,1,1,1,1, …
A progressão aritmética geral pode ser definida recursivamente por 𝑎1 = 𝑎 𝑒 𝑎𝑘+1 =
𝑎𝑘 + 𝑑 para 𝑘 ≥ 1.
A solução é 𝑎𝑛 = 𝑎 + (𝑛 − 1)d
2.Para descrever os elementos de um conjunto, encontramos usualmente três mecanismos:
R: D. 
𝑆 = {𝑎𝑏𝑐, 𝑎𝑎𝑏𝑐𝑐, 𝑎𝑎𝑎𝑏𝑐𝑐𝑐, … }
{
𝑎𝑏𝑐 ∈ 𝑆
𝑠𝑒 𝑥 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑥𝑐 ∈ 𝑆
é incorreta, pois 𝑛 = 0 implica que 𝑎
𝑛𝑏𝑐
𝑛 = 𝑎
0𝑏𝑐
0 = 𝑏 e, portanto, 𝑏 deve pertencer à base
da indução e ao conjunto.
𝑆 = {𝑏, 𝑎𝑏𝑐, 𝑎𝑎𝑏𝑐𝑐, 𝑎𝑎𝑎𝑏𝑐𝑐𝑐, … }
{
𝑏 ∈ 𝑆
𝑠𝑒 𝑥 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑥 ∈ 𝑆 𝑒 𝑥𝑐 ∈ 𝑆
é incorreta, pois o passo indutivo 𝑠𝑒 𝑥 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑥 ∈ 𝑆 𝑒 𝑥𝑐 ∈ 𝑆 permite definir uma
sequência de caracteres inválida, por exemplo, 𝑠𝑒 𝑏 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑏 ∈ 𝑆 𝑒 𝑏𝑐 ∈ 𝑆, mas tanto ab
quanto bc não pertencem ao conjunto desejado.
𝑆 = {𝑏, 𝑎𝑏, 𝑏𝑐, 𝑎𝑏𝑐, 𝑎𝑎𝑏, 𝑏𝑐𝑐, … }
{
𝑏 ∈ 𝑆
𝑠𝑒 𝑥 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑥 ∈ 𝑆 𝑒 𝑥𝑐 ∈ 𝑆
é incorreta, pois tanto a enumeração quanto a definição indutiva não correspondem ao
conjunto desejado. O passo indutivo 𝑠𝑒 𝑥 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑥 ∈ 𝑆 𝑒 𝑥𝑐 ∈ 𝑆 permite definir uma
sequência de caracteres inválida, por exemplo, 𝑠𝑒 𝑏 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑏 ∈ 𝑆 𝑒 𝑏𝑐 ∈ 𝑆, mas tanto ab
quanto bc não pertencem ao conjunto desejado.
𝑆 = {𝑎𝑏𝑐, 𝑎𝑎𝑏𝑐, 𝑎𝑏𝑐𝑐, … }
{
𝑎𝑏𝑐 ∈ 𝑆
𝑠𝑒 𝑥 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑥 ∈ 𝑆 𝑒 𝑥𝑐 ∈ 𝑆
é incorreta pois tanto a enumeração quanto a definição indutiva não correspondem ao
conjunto desejado. 𝑛 = 0 implica que 𝑎
𝑛𝑏𝑐
𝑛 = 𝑎
0𝑏𝑐
0 = 𝑏 e, portanto, 𝑏 deve pertencer à
base da indução e ao conjunto. Também o passo indutivo 𝑠𝑒 𝑥 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑥 ∈ 𝑆 𝑒 𝑥𝑐 ∈ 𝑆
permite definir uma sequência de caracteres inválida, por exemplo, 𝑠𝑒 𝑎𝑏𝑐 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑎𝑏𝑐 ∈
𝑆 𝑒 𝑎𝑏𝑐𝑐 ∈ 𝑆, mas tanto aabc quanto abcc não pertencem ao conjunto desejado.
𝑆 = {𝑏, 𝑎𝑏𝑐, 𝑎𝑎𝑏𝑐𝑐, 𝑎𝑎𝑎𝑏𝑐𝑐𝑐, … }
{
𝑏 ∈ 𝑆
𝑠𝑒 𝑥 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑥𝑐 ∈ 𝑆
é a única que permite definir de maneira correta o conjunto a partir da base 𝑏 ∈ 𝑆 pela
aplicação sucessiva do passo de indução. Por exemplo, para as próximas duas palavras do
conjunto desejado, temos 𝑠𝑒 𝑏 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑏𝑐 ∈ 𝑆 e 𝑠𝑒 𝑎𝑏𝑐 ∈ 𝑆, 𝑒𝑛𝑡ã𝑜 𝑎𝑎𝑏𝑐𝑐 ∈ 𝑆.
3. ​​​​​​​​​​​​​​A recursão pode ser usada para definir sequências, funções e conjuntos. As sequências podem ser definidas a partir do primeiro termo da sequência, a0, e de uma 
regra para encontrar um termo a partir do anterior, an+1. Quando definimos uma sequência recursivamente, especificamos como os seus termos são encontrados a partir de 
termos anteriores.
Nesse contexto, considere a sequência definida por:
a1=2
a2=2
a3=6
an=3 * an-3, Para n > 3
Calcule a4, a5, a6 e assinale a alternativa correta:
R: A. 6, 6, 18.
𝑎4 = 3 ∗ 𝑎4−3 = 3 ∗ 𝑎1 = 3 ∗ 2 = 6.
𝑎5 = 3 ∗ 𝑎5−3 = 3 ∗ 𝑎2 = 3 ∗ 2 = 6.
𝑎6 = 3 ∗ 𝑎6−3 = 3 ∗ 𝑎3 = 3 ∗ 6 = 18.
4. O conjunto de todas as cadeias (palavras ou strings) de comprimento finito de símbolos sobre um alfabeto A é denotado por A*. A definição recursiva de A* é:
I - A cadeia vazia, denotada por ε , pertence a A*.
II - Um único símbolo qualquer de A pertence a A*.
III - Se x e y são cadeias em A*, então a concatenação xy também pertence a A*.
Dado o alfabeto A=｛0,1,2｝, apresente as cinco menores cadeias de A*:
R: E. ε,0,1,2,00
Pela regra I, temos, inicialmente A*=｛ε｝
Pela regra II, temos que A*={ε,0,1,2}
Pela regra III, temos que A*={ε,0,1,2,00}
5. Considerando que usamos duas etapas para definir uma função com o conjunto dos números inteiros não negativos como seu domínio, a saber: passo base, em que 
especificamos o valor da função em zero; e o passo recursivo, em que fornecemos uma regra para encontrar seu valor em um número inteiro a partir dos valores nos 
números inteiros menores. Neste contexto, suponha que fseja definida recursivamente por: f0 = 3, fn + 1 = 2fn + 3, encontre f1, f2, f3ef(4), assinalando a alternativa 
correta.
R: Resposta: alternativa c.
A partir da definição recursiva, temos que:
𝑓(1) = 2 𝑓(0) + 3 = 2 . 3 + 3 = 9
𝑓(2) = 2 𝑓(1) + 3 = 2 . 9 + 3 = 21
𝑓(3) = 2 𝑓(2) + 3 = 2 . 21 + 3 = 45
𝑓(4) = 2 𝑓(3) + 3 = 2 . 45 + 3 = 93