document(3)

Prévia do material em texto

Resumo de Algortimos e Indução e Lista 2 -
Números Inteiros e Criptografia
1 Algoritmos e Indução
Axioma 1.1 (Pŕıncipio da Indução). P (1) é verdadeiro e se P (n), então P (n+1)
⇐⇒ para todo x natural tal que x ≥ 1 , P (x) é verdadeiro.
1.1 Algoritmos iterativos - ”com laços”
A(n) = 1 + 2 + · · ·+ (n− 1) + n
AG(n) =
n(n + 1)
2
P (n) : A(n) = AG(n)
Teorema 1.2 (Caso base). P (1) é verdadeiro.
Prova.
V erdadeiro
=⇒ { Trivial }
1 = 1
=⇒ { Álgebra }
1 = 1(1+1)2
=⇒ { Definição de A e AG }
A(1) = AG(1)
=⇒ { Definição de P }
P (1)
Teorema 1.3 (Passo indutivo). Se P (n), então P (n + 1).
Prova.
P (n)
=⇒ { Definição de P }
1
A(n) = AG(n)
=⇒ { Definição de A e AG }
1 + 2 + · · ·+ n = n(n+1)2
=⇒ { Álgebra }
1 + 2 + · · ·+ n = (n+1)((n+1)+1)2 − (n + 1)
=⇒ { Álgebra }
1 + 2 + · · ·+ n + (n + 1) = (n+1)((n+1)+1)2
=⇒ { Definição de A e AG }
A(n + 1) = AG(n + 1)
=⇒ { Definição de P }
P (n + 1)
Teorema 1.4. Para todo x ≥ 1 natural, P (x) é verdadeiro.
Prova.
V erdadeiro
=⇒ { Teoremas anteriores }
P (1) é verdadeiro e se P (n), então P (n + 1).
=⇒ { Prinćıpio da Indução }
Para todo x ≥ 1, P (x) é verdadeiro
1.2 Algoritmos recursivos
Algoritmo recursivo na notação matemática
B(n) =
{
1 n = 1,
2 ·B(n− 1) + 1 c.c.
Algoritmo recursivo em Python
def B(n):
if n==1:
return 1
else:
return 2*B(n-1)+1
2
BR(n) = 2n − 1
Q(n) : B(n) = BR(n)
Teorema 1.5 (Caso base). Q(1) é verdadeiro.
Prova.
V erdadeiro
=⇒ { Trivial }
1 = 1
=⇒ { Álgebra }
1 = 21 − 1
=⇒ { Definição de B e BR }
B(1) = BR(1)
=⇒ { Definição de Q }
Q(1)
Teorema 1.6 (Passo indutivo). Se Q(n), então Q(n + 1).
Prova.
Q(n)
=⇒ { Definição de Q }
B(n) = BR(n)
=⇒ { Definição de BR }
B(n) = 2·(2
n−1)
2
=⇒ { Álgebra }
B(n) = 2
n+1−2
2
=⇒ { Álgebra }
2B(n) + 1 = 2n+1 − 1
=⇒ { Álgebra }
2B((n + 1)− 1) + 1 = 2n+1 − 1
=⇒ { Definição de B e BR }
B(n + 1) = BR(n + 1)
=⇒ { Definição de Q }
Q(n + 1)
3
2 Posśıvel definições da função ”acumuladora”
Algoritmo iterativo na notação matemática com reticências
A(n) = 1 + 2 + · · ·+ n
Algoritmo iterativo na notação matemática
A(n) =
n∑
i=1
i
Algoritmo iterativo em Python
def A(n):
S=0
for i in range(1,n+1):
S=S+i
return S
Algoritmo recursivo na notação matemática
A(n) =
{
1 n = 1,
A(n− 1) + n c.c.
Algoritmo recursivo em Python
def A(n):
if n==1:
return 1
else:
return A(n-1)+n
3 Posśıvel definições da função fatorial
Fatorial(n) = n!
Algoritmo iterativo na notação matemática com reticências
Fatorial(n) = 1 · 2 · · · · n
Algoritmo iterativo na notação matemática
Fatorial(n) =
n∏
i=1
i
4
Algoritmo iterativo em Python
def A(n):
S=1
for i in range(1,n+1):
S=S*i
return S
Algoritmo recursivo na notação matemática
A(n) =
{
1 n = 1,
A(n− 1) · n c.c.
Algoritmo recursivo em Python
def A(n):
if n==1:
return 1
else:
return A(n-1)*n
4 Lista 2
Justifique todas as questões.
1. Para cada par a, b de números naturais abaixo, calcule o seu máximo
divisor comum.
(a) 252 e 180
(b) 6643 e 2873
2. Prove por indução que para todo inteiro n ≥ 1, n3 + 2n é diviśıvel por 3.
3. Prove por indução que para todo inteiro n ≥ 1,
n∑
k=1
k(k + 1) =
n(n + 1)(n + 2)
3
4. O Algoritmo Euclidiano funciona tão bem que é dif́ıcil encontrar pares de
números que o fazem demorar muito.
(a) Encontre dois números cujo mdc é 1, para os quais o Algoritmo Eu-
clidiano efetua exatamente 5 divisões.
(b) Encontre dois números cujo mdc é 1, para os quais o Algoritmo Eu-
clidiano efetua exatamente 6 divisões (dica: estenda a ideia que você
usou na letra a).
5
(c) Descreva um método para resolver o seguinte problema: dado um
natural k, encontrar dois números cujo mdc é 1, para os quais o
Algoritmo Euclidiano efetua exatamente k divisões.
5. Sejam a, b, n ∈ N. Prove cada uma das afirmações abaixo:
(a) a|b e b|a, então a = b;
(b) Se a2 − 2a + 7 é par, então a é ı́mpar.
(c) mdc(n! + 1, (n + 1)! + 1) = 1
6. Diremos que dois números inteiros “estão próximos” entre si sse o valor
absoluto da diferença entre eles for menor ou igual a 2. Por exemplo, 3
está próximo de 5, 10 está próximo de 9, mas 8 não está próximo de 4.
Chamemos de R esta relação.
(a) Desenhe uma representação gráfica de R restrita apenas aos números
naturais de 0 a 10 (incluindo 0 e 10).
(b) Prove ou refute: R é reflexiva.
(c) Prove ou refute: R é simétrica.
(d) Prove ou refute: R é antissimétrica.
(e) Prove ou refute: R é transitiva.
(f) Prove ou refute: R é uma relação de ordem parcial.
(g) Prove ou refute: R é uma relação de equivalência.
6
	Algoritmos e Indução
	Algoritmos iterativos - "com laços"
	Algoritmos recursivos
	Possível definições da função "acumuladora"
	Possível definições da função fatorial
	Lista 2