Projeto e Análise de Algoritmos
Conceitos básicosMetodo de provas: Indução
Diane [email protected]
Instituto de InformáticaUniversidade Federal de Goiás
Notações
∀ = para todo∃ = existe! = único∏ = produto∑ = soma⇒ = implica⇔ = se e somente se | = dividetq = tal que
Notaçõesℕ = conjunto dos inteiros naturais = {0, 1, 2, ...}ℤ = conjunto dos inteiros = {0, ±1, ±2, ...}ℚ = conjunto dos números racionais
= {x : ∃ a, b ∈ ℤ, (b ≠ 0) tal que x=a÷b}= {x : ∃ a, b ∈ ℤ, (b ≠ 0) tal que bx=a}
ℝ = conjunto dos números reais
ℕ*= conjunto dos naturais positivos = {1, 2, ...}
ℝ+= conjunto dos números reais não-negativos= { x ∈ ℝ : x ≥ 0}
Funções: Pisos e Tetos
Seja x ∈ ℝ. Denotamos o maior inteiro menor que ou igual a x por ⌊x⌋
(piso)e
o menor inteiro maior que ou igual a x por ⌈x⌉ (teto).
x-1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x+1
Funções: Pisos e TetosPropriedades
Seja n ∈ ℤ. ⌊n/2⌋ + ⌈n/2⌉ = n
Sejam x ∈ ℝ+, a, b ∈ ℕ*.
⌈⌈n/a⌉/b⌉ = ⌈n/ab⌉⌊⌊n/a⌋/b⌋ = ⌊n/ab⌋
⌊a/b⌋ ≤ (a + (b-1))/b⌈a/b⌉ ≤ (a - (b-1))/b
Funções: Aritmética modular
Teorema: Sejam a ∈ ℤ e n ∈ ℕ*.
∃! q ∈ ℤ e r ∈ ℕ, 0 ≤ r < n tais quea = qn + r,
O quociente da divisão de a por n, q, é o piso de a/n.
Notação: a div n = q = ⌊a/n⌋ O resto da divisão de a por n, r, é dado por a-
⌊a/n⌋*nNotação: a mod n = r = a-⌊a/n⌋*n
Funções: Fatoriais
Definição recursiva de n!
0! = 1
(n+1)! = (n+1)*n! para n≥0
Exemplo3! = 3*2! = 3*2*1! = 3*2*1*0! = 3*2*1*1
3! = 6
Funções: Exponenciais
Para todos os valores a ≠ 0, m, n reais, temos as seguintes identidades
a0 = 1a1 = a
a-1 = 1/a(am)n = amn = (an)m
aman = am+n
Funções: Exponenciais
Temos que: ex ≥ 1+x
para |x| ≤ 1, 1+x ≤ ex ≤ 1+x+x2
ex =1+x+(x2)
e x=1x x2
2 !x3
3!...=∑
i=0
∞ xi
i !
limn∞
1 xnn
=e x
Funções: Logaritmos
Notações
lg n = log2 n (logaritmo binário)
ln n = loge n (logaritmo natural)
lgk n = (lg n)k (exponenciação)
lg lg n = lg(lg n) (composição)
Funções: Logaritmos
Notações
n se i = 0lg(i)n = lg(lg(i-1)n) se i > 0 e lg(i-1)n > 0
indefinido se i > 0 e lg(i-1)n < 0ou lg(i-1)n é indefinido
lg* n = min{i≥0 : lg(i)n ≤ 1} (log estrela)
{
Funções: Logaritmos
Propriedades
Para todo a > 0, b > 0, c > 0 e n
logc (ab) = log
c a + log
c b
logb an = n log
b a
logb a = log
c a /log
c b
a = blogba
alogbn = nlogba
Funções: Somatórias
∑i=1
n
i∗2i=n−1∗2k12 , parak≥1
H n=∑i=1
n 1i
H né o k−ésimo númeroharmonico
ln n≤H n≤1ln n
∑i=1
n
H i=n1H n−n
Funções: Somatórias
ExpandindoeContraindoSomas
S2=∑k=1
n
k 2=∑j=1
n
∑k= j
n
k
=∑j=1
n nn1− j−1 j2
=12 ∑j=1
n
nn1∑j=1
n
j− j2
S2=12nn 1
2n1− 1
2S2
S2=16n2n1n1
Funções: Somatórias
Dividindo as Somas
∑k=n0
n
k2=∑k=1
n
k2−∑k=1
n0−1
k2
=16n2n1n1− 1
6n0−12n0−11n0
=16
[ nn12n1−n0 n0−12n0−1 ]
Notação Assintótica: Definição O
Sejam f, g : ℝ → ℝ (ou ℕ → ℕ) duas funções.Dizemos que:
f(n) ∈ О(g(n)) se exitem duas constantes positivas
c, n0 > 0 tais que
| f(n) | ≤ c∗|g(n)| ∀n ≥ n0.
Notação Assintótica: Definição
Sejam f, g : ℝ → (ou ℝ ℕ → )ℕ duas funções.Dizemos que:
f(n) ∈(g(n)) se exitem duas constantes positivas
c, n0 > 0 tais que
c | ∗ g(n) | | f(n) | ≤ ∀n ≥ n0.
Notação Assintótica: Definição
Sejam f, g : ℝ → (ou ℝ ℕ → )ℕ duas funções.Dizemos que:
f(n) ∈ (g(n)) se
f(n) ∈ О(g(n)) e f(n) ∈(g(n))
Notação: Por abuso de linguagem, dizemos que f(n) = (g(n))
Notação Assintótica: Polinômios
Um polinômio em n de grau d é dado da forma
Observação: P(n) = (nd)
Dizemos que uma função é limitada polinomialmente se f(n) = O(nk)
para alguma constante k
P n=∑i=0
d
ai ni , ad≠0
Notação Assintótica:Polinômios e Exponenciais
Para todas constantes reais a e b, a >1, temos
Conclusão
nb = O(an)
limn∞
nb
an=0
Notação Assintótica: Fatorial e log
n! = O(nn)n! = (2 n)
log(n!) = (n log n)
para qualquer a > 0.lg n = O(na)
lgk n = (lg n)k = O(na) para qualquer k
Notação Assintótica: Somatórias
Dividindo as Somas
∑k=n0
n
k2=∑k=1
n
k2−∑k=1
n0−1
k2
=16n2n1n1− 1
6n0−12n0−11n0
=16
[ nn12n1−n0 n0−12n0−1 ]
Metodos de provas: p ⇒ q
Prova direita p ⇒ q
Prova por contraposição ¬p ¬q⇒
Prova por contradição ¬( p ∧ ¬q )
Metodos de provas
Prova por Construção
Contre-exemplo
Prova por casos
INDUÇÃO
Prova direita: p ⇒ q
TeoremaSejam f, g, h : ℝ → ℝ (ou ℕ → ℕ) três funções.
Se f(n) ∈ О(g(n)) e g(n) ∈ О(h(n))então f(n) ∈ О(h(n))
Prova feita em sala de aula.
Prova por contraposta: ¬p ¬q⇒
Reformulação du TeoremaSejam f, g, h : ℝ → ℝ (ou ℕ → ℕ) três funções.
Se f(n) ∉ О(h(n)) então f(n) ∉ О(g(n)) OU g(n) ∉ О(h(n))
Prova por contradição: ¬(p ∧ ¬q)
Teorema: O número é irracional
Prova feita em sala de aula.
2
Prova por Construção
TeoremaExistem s e t dois inteiros tais que 5s+7t=1.
Contre-exemplo
Afirmação falsaSejam f, g: ℝ → ℝ (ou ℕ → ℕ) duas funções.
Se f(n) ∈ О(g(n)) então g(n) ∈ О(f(n)).
Prova feita em sala de aula.
Prova por casos
max(a, b) ≥ a
Prova por Indução
Problema:
Seja P uma propriedade. Queremos ver que P(n) é verdadeira
para todo os inteiros naturais n.
Prova por Indução
BASE Prove que P(1) é verdadeira
HIPOTESIS DE INDUÇÃOSuponha que P(k) é verdadeiro
para algum
PASSO DE INDUÇÃOMostre que P(k+1) é verdadeira
INDUÇÃO
Teorema Seja n um inteiro positivo então n < 2n.
Corolario
lg n ∈ o(n)provar por contradição que n ∉ O(lg n)
/* * Ordena um vetor. * O comprimento do vetor é denotado por comprimento[A]. */INSERTION-SORT(A)1. para j ← 2 até comprimento[A] faça2. chave ← A[j]3. // Inserir A[j] na seqüência ordenada A[1..j-1]4. i ← j-15. enquanto i > 0 e A[i] > chave faça6. A[i+1] ← A[i]7. i ← i-18. fim-enquanto9. A[i+1] ← chave10. fim-para
Linha Custo Vezes
c1 nc2 n-1
3. // Comentário 0 n-1c4 n-1
c5
c6c7 “0c9 n-10 n-1
1. para j← 2 até n2. chave ← A[j]
4. i ← j-1
5. enquanto i > 0 e ∑jtj
A[i] > chave faça6. A[i+1] ← A[i] ∑
j(t
j-1)
7. i ← i-1
8. fim-enquanto ∑jtj
9. A[i+1] ← chave10. fim-para
SELEÇÃO-SORT(A)1. para i ← 1 até comprimento[A]-1 faça2. //achamos o iesimo menor valor do vetor3. menor ← i4. para j ← i+1 até comprimento[A] faça5. se V[j] < V[menor] 6. então menor ← j7. fim-se8. fim-para9. se menor ← i10. //trocamos os valores de V[menor] e V[i]11. então aux ← V[menor]12. V[menor] ← V[i]13. V[i] ← aux14. fim-se15. fim-para
BOLHA(A)1. para i ← 1 até comprimento[A]-1 faça2. para j ← 1 até comprimento[A]-i faça3. se A[j] > A[j+1])4. //troca A[j] com A[j+1]5. então aux ← A[j]6. A[j] ← A[j+1]7. A[j+1] ← aux8. fim-se9. fim-para10. fim-para
BOLHA-MELHOR(A)1. ultimatroca ← comprimento[A]2. troca ← 13. enquanto ultimatroca > 1 faça2. para j ← 1 até ultimatroca-1 faça3. se A[j] > A[j+1]4. //troca A[j] com A[j+1]5. então aux ← A[j]6. A[j] ← A[j+1]7. A[j+1] ← aux8. troca ← j8. fim-se9. fim-para10. ultimatroca ← troca11. troca ← 110. fim-enquanto