View
129
Download
0
Category
Preview:
Citation preview
1
BCC 101 – Matemática Discreta I
Recursão / Indução
BCC101 - Matemática Discreta - DECOM/UFOP
Recursão/Indução
Método usada para resolver uma classe de problemas, em que cada instância tem um tamanho (n ∈ N)
Construa a solução para instâncias do problema de tamanho 0
Supondo conhecida a solução do problema para instâncias de tamanho n, sendo n arbitrário, construa a solução para instâncias de tamanho (n+1)
BCC101 - Matemática Discreta - DECOM/UFOP 2
base da recursão
passo recursivo
Números Naturais
Conjunto dos números naturais
N = {0,1,2,3, …}
pode ser definido recursivamente como
0 ∈ N n ∈ N → (n+1) ∈ N
Gramática: N -> 0 | suc N
Tipo de dado (em Haskell)
data Nat = Zero | Suc Nat
BCC101 - Matemática Discreta - DECOM/UFOP 3
Fatorial
Fatorial: n! = 1x2x…x(n-1)xn0!= 1 (base)n!= n · (n -1)! (recursão)
EX: 5!
4
recursão
= 5 · 4!
= 5 · 4 · 3!
= 5 · 4 · 3 · 2! = 5 · 4 · 3 · 2
· 1! = 5 · 4 · 3 · 2 · 1
· 0!
base
= 5 · 4 · 3 · 2 · 1 · 1
Exercícios
Defina recursivamente os conjuntos:1. Pares = {0,2,4,…}
2. O conjunto potência de A : P (A ).
3. O conjunto de todos os bitstrings Bs
4. O conjunto de bitstrings palindromos Pal
5. O conjunto de todas as listas de valores de um dado tipo A
BCC101 - Matemática Discreta - DECOM/UFOP 5
Sequências
Sequência de potências de 2: an = 2n,
n≥0
pode ser definida recursivamente como:
a0 = 1
an = 2 an-1 n>0
Sequência: 3 0 3 0 3 0 …
pode ser definida recursivamente como:
a0 = 3 a1 = 0
an = an-2 n>1BCC101 - Matemática Discreta - DECOM/UFOP 6
Fibonacci
Fibonacci
fib 0 = 0
fib 1 = 1
fib n = fib (n -1) + fib (n -2)
Esse algoritmo é O(2n ) porque ao passar de n para n-1 efetuamos 2 chamadas recursivas da função, e cada uma usa, por sua vez, duas outras chamadas recursivas, e assim por diante.7
Exercícios
Considere a definição recursiva:
f(0) = 1 f(n+1) = 3 f(n)
Determine f(1), f(2), f(3), f(4)Encontre uma fórmula direta para f(n)
Defina recursivamente as sequências:
1.an = 3n+2 n≥0
2.1 -1 1 -1 1 …
3.an = n2
BCC101 - Matemática Discreta - DECOM/UFOP 8
Coeficientes Binomiais (n,k)
Coeficientes binomiais ocorrem em diversas aplicações:
Combinatória/Probabilidade C (n,k) = número de maneiras de escolher k elementos de um conjunto com n elementos
Algebra: C (n,k) = coeficiente do k esimo termo na expansão binômio de grau n: (x + y )n
9
k
nknC ),(
Notação usada comumente:
Coeficientes Binomiais (n,k)
A maneira mais eficiente de computar todos os C (n,k) até um determinado n é via o triângulo de Pascal.
O triângulo de Pascal é construído colocando 1 no topo (inicialização) e todo elemento seguinte é definido recursivamente como a soma dos números à direita e à esquerda desse número, na linha anterior. Se tal número não existe, é considerado 0.10
11
combinação n k e Triângulo Pascal
1
12
combinação n k e Triângulo Pascal
1
1 1
13
combinação n k e Triângulo Pascal
1
1 1
1 2 1
14
combinação n k e Triângulo Pascal
1
1 1
1 2 1
1 3 3 1
15
combinação n k e Triângulo Pascal
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
16
combinação n k e Triângulo Pascal
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
17
combinação n k e Triângulo Pascal
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
18
combinação n k e Triângulo Pascal
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Q: Fórmula recursiva para C (n,k)?
n = linha0123456
0 k = coluna diagonal 1 2
3
4 5 6
Coeficientes Binomiais (n,k)
Resposta: Use o triângulo de Pascal.
Base: O topo do triângulo é 1. Portanto, C (0,0) = 1. Se falta um número, ele é considerado 0. Isso dá origem a C (n,k) = 0 se k < 0, ou k > n.
Recursão: Cada valor é a soma dos números à direita e à esquerda na linha anterior:
C (n,k) = C (n -1,k-1) + C (n -1,k )19
Coeficientes Binomiais (n,k)
Resumindo:
20
Máximo Divisor Comum - mdc
O algoritmo de Euclides usa o fato: mdc(x,y) = mdc(y, x mod y)
21
contrário caso
if
),mod,(
0 ,),(
yxymdc
yxyxmdc
supomos aqui que x > 0
Exercícios
Defina recursivamente:
1. an , a ∈ R, n ∈ N
2.
BCC101 - Matemática Discreta - DECOM/UFOP 22
Tamanho do problema A generalização apropriada nem sempre é óbvia.
Exemplo: problema relativo a um tabuleiro de xadrez com 64 quadrados. Como esse problema pode ser generalizado?
Uma classe de problemas com instâncias de tamanho n, tal que uma instância é n = 64
Uma classe de problemas em que uma instância é um tabuleiro de tamanho n×n. O tamanho da instância é n; o problema original é uma instância de tamanho n = 8
Restringir a classe a problemas as casos em que o tamanho do tabuleiro é 2n. O problema original é uma instância de tamanho n = 3
BCC101 - Matemática Discreta - DECOM/UFOP 23
Triominós
Considere um tabuleiro com tamanho 2n x 2n no qual exatamente um quadrado está coberto.
BCC101 - Matemática Discreta - DECOM/UFOP 24
um triominó de formato L é feito de 3 quadrados:
Quantos triominós de formato L são necessários para cobrir os quadrados restantes, sem que triominós se sobreponham.
Triominós - solução para 23 x 23
BCC101 - Matemática Discreta - DECOM/UFOP 25
Triominós Caso base (n=0):
O tabuleiro tem dimensão 20x20 = 1x1, isto é, exatamente 1 quadrado, que já está coberto. Portanto, são necessários 0 triominós para cobrir os quadrados restantes: trio(0) = 0
Passo indutivo: Considere um tabuleiro de dimensões 2n+1x2n+1
Suponha que é possível cobrir qq tabuleiro de dimensões 2nx2n com trio(n) triominós
Devemos mostrar como explorar essa hipótese para obter a solução para o caso 2n+1x2n+1
BCC101 - Matemática Discreta - DECOM/UFOP 26
Triominós
Um tabuleiro 2n+1x2n+1 pode ser subdividido em 4 tabuleiros 2nx2n, traçando-se uma linha horizontal e uma vertical que se cruzam no meio.
Em uma desses 4 tabuleiros, há um quadrado que já está coberto. Pela nossa hipótese, os demais quadrados desse tabuleiro podem ser cobertos com k triominós.
Nenhum dos 3 outros tabuleiros 2nx2n tem um quadrado coberto. Como aplicar a hipótese aos 3 outros tabuleiros?
A idéia é colocar um triominó na junção desses 3
BCC101 - Matemática Discreta - DECOM/UFOP 27
Triominós
BCC101 - Matemática Discreta - DECOM/UFOP 28
Agora a hipótese pode ser aplicada para cobrir os quadrados restantes de cada uma dos 3 outros subtabuleiros. Então trio(n+1) = 4 trio(n) +1 (n>0).
trio(0) = 0trio(n+1) = 4 trio(n) +1
Exercício Torres de Hanoi
(Edouard Lucas - 1883)
29
Um templo da cidade de Hanoi tem 3 torres de diamante, em uma das quais foram empilhados n discos de ouro, de maneira que os discos diminuem de tamanho da base para o topo da torre. Os monges do templo trabalham sem cessar para transferir os discos da torre em que foram inicialmente colocados para uma das outras duas torres --- mas nunca um disco de maior raio pode ser colocado sobre outro de raio menor.
Encontre uma definição recursiva para o número de movimentos de discos que são necessários para transferir n discos da torre A para a torre C, usando a torre B.
Recommended