Análise de Algoritmos - Indução Finita

Analise de Algoritmos

Indução finita

– p. 1/20

Indução finita

Princıpio da inducao matematica:

Seja A um conjunto de números naturais tal que asseguintes propriedades são válidas:

0 ! A, e

para cada natural n, se {0, 1, 2, . . . , n} " A

então n+ 1 ! A.

Então A = N.

– p. 2/20

Indução finita

Na prática, o princípio da indução é usado paraprovar afirmações do tipo “para todo natural n, apropriedade P (n) é verdadeira”, onde P é umapropriedade que depende de algum parâmetrointeiro. A prova é feita da seguinte forma.

– p. 3/20

Indução finita

Seja A = {n : P é verdadeira para n}.

1. Base da indução: mostramos inicialmente que0 ! A, ou seja, P é verdadeira para n = 0.

2. Hipótese de indução: assumimos que{0, 1, 2, . . . , n} " A, ou seja, que P é verdadeirapara cada natural 0, 1, 2, . . . , n.

3. Passo da indução: mostramos que n+ 1 ! A,ou seja, que P é verdadeira para n+ 1.

– p. 4/20

Indução finita

Pelo princípio da indução, A = N. Logo, P éverdadeira para todo n.

– p. 5/20

Indução finita - em outras palavras

O princípio da indução finita pode também serdescrito da seguinte forma:

“Se uma afirmação P , que envolve um parâmetrointeiro n, é verdade para n = 0, e se para n # 1, ahipótese de que P é verdadeira para todo inteiro$ n implica que P é verdadeira para n+ 1, então P

é verdadeira para todo natural n.

– p. 6/20

Indução finita - exemplos

Mostre que 1+ 2+ · · ·+n = n(n+1)2 , para todo n # 1.

– p. 7/20



1. Base da indução: para n = 1 temos 1 = 1(1+1)2 .

– p. 7/20



1. Base da indução: para n = 1 temos 1 = 1(1+1)2 .

2. Hipótese de indução: assumimos que1 + 2 + · · ·+ k = k(k+1)

2 , para todo k $ n.

– p. 7/20



3. Passo da indução:

– p. 8/20



3. Passo da indução:

1 + 2 + · · ·+ n+ (n+ 1) = (1 + 2 + · · ·+ n) + (n+ 1)

=n(n+ 1)

2+ (n+ 1)

=n(n+ 1) + 2(n+ 1)

2

=(n+ 1)(n+ 2)

2

– p. 8/20


Afirmação: o número de diagonais de um polígonoconvexo P de n # 3 lados é d = n(n%3)

2 .

– p. 9/20



2 .

Prova: Por indução em n. A afirmação éclaramente verdadeira para n = 3.

– p. 9/20



2 .


Sejam v1, v2, . . . , vn os vértices de P , enumeradosem uma ordem cíclica.

– p. 9/20



2 .


Sejam v1, v2, . . . , vn os vértices de P , enumeradosem uma ordem cíclica. Considere o polígono P &

de n% 1 lados formado pelos vérticesv1, v2, . . . , vn%1. Note que P & é convexo.

– p. 9/20


Seja d& o número de diagonais de P &.

– p. 10/20


Seja d& o número de diagonais de P &.Por hipótese de indução,

d& =(n% 1)(n% 4)

2.

– p. 10/20



d& =(n% 1)(n% 4)

2.

Mas, d = d& + (n% 2).

– p. 10/20



d& =(n% 1)(n% 4)

2.

Mas, d = d& + (n% 2). Logo,

d =(n% 1)(n% 4)

2+ (n% 2) =

n(n% 3)

2.

– p. 10/20


Proposição: Seja G uma árvore com v # 1 vérticese a arestas então a = v % 1.

– p. 11/20



Prova: Por indução em a.

– p. 11/20



Prova: Por indução em a. Se a = 0 então v = 1,pois v # 1 e G é conexo. Logo, a = v % 1 nestecaso.

– p. 11/20



Prova: Por indução em a. Se a = 0 então v = 1,pois v # 1 e G é conexo. Logo, a = v % 1 nestecaso.

Suponha que a # 1. Seja e uma aresta de G.Como G é uma árvore, o grafo G% e é formado porexatamente duas componentes, digamos G1 e G2.Além disso, G1 e G2 são árvores.

– p. 11/20


Sejam v1 e a1 o número de vértices e arestas deG1. Defina v2 e a2 similarmente para G2.

– p. 12/20



Claramente, a1 < a e a2 < a. Por hipótese deindução, a1 = v1 % 1 e a2 = v2 % 1.

– p. 12/20




Mas a = a1 + a2 + 1 e v = v1 + v2.

– p. 12/20




Mas a = a1 + a2 + 1 e v = v1 + v2. Logo,

a = (v1 % 1) + (v2 % 1) + 1 = v % 1.

– p. 12/20

Indução finita - cuidados

Ao utilizarmos a indução finita devemos estaratentos aos seguintes detalhes:

– p. 13/20



Base da indução

– p. 13/20



Base da indução

Aplicação da hipótese de indução

– p. 13/20

Indução finita - exercícios

Provar as seguintes afirmações:1. 1 + 3 + 5 + · · · + (2n% 1) = n2, 'n # 1.2. 1 + 2 + 22 + · · · + 2n = 2n+1 % 1, 'n # 0.

3. a1 + a1.r + a1.r2 + · · · + a1.rn!1 = a1.(rn!1)

r!1 , 'n # 1.

4. 12 +

14 +

18 + · · · + 1

2n < 1, para n # 1.

5. 12 + 22 + · · · + n2 = n(n+1)(2n+1)6 , 'n # 1.

6. Para qualquer inteiro n, o número 22n % 1 é divisível por3.

7. A soma dos ângulos internos de um polígono convexocom n lados é S = (n% 2)180o.

– p. 14/20


8. O número de vértices V , arestas E e faces F de ummapa planar conexo satisfazem a equação:

V % E + F = 2.

9. Um número (em sua representação decimal) é múltiplode 3 se e somente se a soma de seus dígitos é múltiplode 3.

10. Considere n # 3 retas em posições gerais no plano (ouseja, quaisquer duas retas se cruzam e quaisquer trêsretas se cruzam em pontos distintos). Prove que pelomenos uma região que elas formam é um triângulo.

– p. 15/20


11. Considere n # 3 retas em posições gerais no plano.Prove que elas formam pelo menos n% 2 triângulos.

12. Considere o conjunto S = {1, 2, . . . , 2n} dos 2nprimeiros números naturais. Mostre que qualquersubconjunto de S com n+ 1 elementos contém doiselementos um dos quais é múltiplo do outro.

13. É possível colorir as regiões formadas por qualquernúmero de retas no plano com apenas duas cores detal forma que regiões vizinhas recebam cores distintas.

– p. 16/20

Analise de Algoritmos

Princípio da casa do pombo

–p. 17/20

Princípio da casa do pombo

Princıpio da casa do pombo:

Se A e B são conjuntos finitos com |A| > |B|,então não existe função bijetora de A para B.

Em outras palavras, se tentarmos associarelementos de A (os “pombos”) com elementos deB (suas “casas”), mais cedo ou mais tarde teremosque colocar mais de um pombo em alguma casa.

– p. 18/20

Princípio da casa do pombo - Exercícios

1. Quantas pessoas são necessárias para se ter certezaque pelo menos duas delas fazem aniversário nomesmo mês?

– p. 19/20



2. Quantas cartas precisam ser tiradas de um baralhoconvencional de 52 cartas para garantir que duas delasserão do mesmo naipe?

– p. 19/20




3. Mostre que em qualquer grupo de n # 2 pessoasexistem 2 pessoas com o mesmo número de amigos nogrupo.

– p. 19/20




3. Mostre que em qualquer grupo de n # 2 pessoasexistem 2 pessoas com o mesmo número de amigos nogrupo.

4. Seja P = {p1, p2, p3, p4, p5} um conjunto de pontosdistintos no plano, com coordenadas inteiras positivas.Mostre que algum par tem um ponto médio que temcoordenadas inteiras.

– p. 19/20


5. Suponha que façamos 50 disparos em um alvoquadrado de 70cm de lado. Se todos os disparosatingem o alvo, mostre que existem dois disparos cujadistância é no máximo 15cm.

6. Mostre que existe uma potência de 3 que termina com001.

7. Dado um conjunto A ( {1, 2, . . . , 100} de 10 inteiros,mostre que existem dois subconjuntos disjuntos nãovazios de A com a mesma soma de seus membros.

8. Há 25 garotos e 25 garotas sentados em torno de umamesa redonda de 50 lugares. Mostre que existe umapessoa cujos dois vizinhos são garotas.

– p. 20/20

Education

Análise de Algoritmos - Indução Finita