02Conceitosbasicos

Projeto e Análise de Algoritmos
Conceitos básicos
Metodo de provas: Indução
Diane Castonguay [e-mail] Instituto de Informática
Universidade Federal de Goiás

Notações
∀
∃
!
∏
∑
⇒
⇔
| tq = para todo
= existe
= único
= produto
= soma
= implica
= se e somente se
= divide
= 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 Tetos
Propriedades
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 que a = 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⌋*n
Notaçã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
Exemplo
3! = 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 = 1
1
a =a a-1 = 1/a
(am)n = amn = (an)m aman = am+n

Funções: Exponenciais
2

∞

3

i

x x x e =1 x  ...=∑
2 ! 3! i=0 i ! x Temos que: ex ≥ 1+x para |x| ≤ 1, 1+x ≤ ex ≤ 1+x+x2 ex =1+x+(x2) n x x lim 1  =e n n∞

Funções: Logaritmos
Notações
lg n

= log2 n (logaritmo binário)

ln n

= loge n

lgk n

= (lg n)k (exponenciação)

(logaritmo natural)

lg lg n = lg(lg n) (composição)

Funções: Logaritmos

lg(i)n =

*

{

Notações

n se i = 0