lista0-Introdução a logica para computação

Prévia do material em texto

Lista 0: Induc¸a˜o e Recursa˜o
Lo´gica para Computac¸a˜o 2017.1
Prof. Francicleber Martins Ferreira
Data de entrega: 24 de Marc¸o no hora´rio da aula
1 Recursa˜o
Exemplo 1. Dada uma a´rvore bina´ria cheia, qual o nu´mero de no´s na altura
n? Defina esse nu´mero recursivamente e deˆ uma fo´rmula alge´brica fechada (sem
recursa˜o). Defina recursivamente o nu´mero de no´s de uma a´rvore bina´ria cheia
de altura n. Apresente tambe´m uma fo´rmula alge´brica sem utilizar recursa˜o.
Soluc¸a˜o. Uma a´rvore bina´ria cheia e´ uma a´rvore bina´ria em que todo no´ tem
exatamente dois filhos ou nenhum (no caso das folhas) e que no´s no mesmo n´ıvel
possuem exatamente o mesmo nu´mero de filhos. Seja h : N → N uma func¸a˜o
que, dada uma altura n, retorna o nu´mero de no´s nessa altura. Na altura 0, ha´
apenas a raiz, portanto h(0) = 1, na altura seja h(n) o nu´mero de no´s na altura
n. Note que todo no´ na altura n+ 1 e´ filho que algum no´ na altura n e todo no´
na altura n tem exatamente dois filhos. Logo, quantidade no´s na altura n+ 1 e´
o dobro da quantidade de no´s na altura n, ou seja, h(n + 1) = 2h(n).
h(0) = 1 (1)
h(n + 1) = 2h(n) (2)
Vamos agora examinar o comportamento dessa func¸a˜o para os primeiros
nu´meros:
h(0) = 1 = 20, h(1) = 2 = 21, h(2) = 4 = 22, h(3) = 8 = 23, h(4) = 16 = 24, . . .
Pelo padra˜o esboc¸ado, podemos conjecturar que
h(n) = 2n
Podemos provar que essa igualdade vale por induc¸a˜o (veja exerc´ıcio abaixo).
Seja f : N → N a func¸a˜o que, dado um nu´mero n, retorna a quantidade de
no´s da a´rvore bina´ria cheia de altura n. Quando n = 0, existe apenas um no´, a
raiz, logo f(0) = 1. Note que uma a´rvore bina´ria cheia de altura n+ 1 pode ser
obtida de uma a´rvore bina´ria de altura n adicionando dois novos filhos a cada
folha. Logo, a quantidade de no´s em uma a´rvore de altura n+ 1 e´ a quantidade
de no´s em uma a´rvore de altura n mais a quantidade de no´s na altura n+ 1, ou
seja f(n + 1) = f(n) + h(n + 1) = f(n) + 2n+1.
f(0) = 1 (3)
f(n + 1) = f(n) + 2n+1 (4)
1
Novamente, vamos examinar essa o comportamento dessa func¸a˜o:
f(0) = 1, f(1) = 1+21 = 3, f(2) = 1+21+22 = 7, f(3) = 1+21+22+23 = 15, . . .
Facilmente vemos que
f(n) =
n∑
i=0
2n,
podemos provar por induc¸a˜o (veja exerc´ıcio abaixo) que
f(n) = 2n+1 − 1.
Questa˜o 1. Sejam h e f as func¸o˜es definidas recursivamente no exemplo ante-
rior. Mostre por induc¸a˜o que:
• h(n) = 2n,
• f(n) = 2n+1 − 1.
Questa˜o 2. Defina recursivamente o nu´mero de no´s de uma a´rvore k-a´ria cheia
de altura n. Exiba uma fo´rmula alge´brica fechada e mostre por induc¸a˜o que
a fo´rmula que voceˆ propoˆs esta´ correta com respeito a` definic¸a˜o recursiva que
voceˆ definiu.
Questa˜o 3. Ao nascer, um determinado fungo demora dois segundos para atin-
gir a maturidade. Assim que atinge a maturidade, ele se reproduz dando origem
a um fungo rece´m-nascido, e gera um novo fungo a cada segundo. Colocamos um
fungo rece´m-nascido em um tubo de ensaio. Deˆ uma definic¸a˜o recursiva para a
quantidade de fungos no tubo de ensaio apo´s t segundos (defina recursivamente
a func¸a˜o f : N→ N tal que f(t) e´ o nu´mero de fungos apo´s t segundos).
OBS: Note que, assim que ele atinge a maturidade ele se reproduz, logo,
apo´s 2 segundos havera´ 2 fungos.
Questa˜o 4. Ao nascer, um determinado fungo demora m segundos para atingir
a maturidade. Assim que atinge a maturidade, ele se reproduz dando origem a k
fungos rece´m-nascidos, e se reproduz novamente a cada m′ segundos. Colocamos
n fungos rece´m-nascidos em um tubo de ensaio. Deˆ uma definic¸a˜o recursiva para
a quantidade de fungos no tubo de ensaio apo´s t segundos?
2 Induc¸a˜o sobre os Naturais
Demonstre os seguintes teoremas por induc¸a˜o.
Questa˜o 5. Para todo natural n ∈ N, ∑ni=0 i3 = n2(n+1)24 .
Questa˜o 6. Para todo natural n ∈ N, n ≥ 1,∑ni=1 i(i+1)2 = n(n+1)(n+2)(3n+5)12 .
Questa˜o 7. Para todo natural n ∈ N, n ≥ 1, kn − 1 e´ divis´ıvel por k − 1.
2