Análise de Algoritmos | Aulas | Dicionário | Índice

Piso, logaritmos, etc.

What I hear, I forget.
What I see, I remember.
What I do, I understand.

— Confucius

Este apêndice é uma lista de exercícios de aquecimento. As seções 1 a 5 tratam de algumas funções elementares importantes para a análise de algoritmos. A seção 6 trata de indução matemática e de fórmulas fechadas para algumas somas importantes. A seção 7 examina alguns algoritmos simples escritos em pseudocódigo. A seção 8 trata de erros de português que muitos estudantes cometem ao escrever sobre assuntos que exigem precisão e clareza. A seção 9 mostra como apresentar um raciocínio dedutivo rigoroso, do tipo que é usado em provas/demonstrações de matemática.

1. Piso e teto

Veja as definições de piso e teto no Dicionário.

1. Mostre que, para qualquer número inteiro positivo n tem-se (n−1)/2 ≤ ⌊n/2⌋ ≤ n/2.
2. Mostre que, para qualquer número inteiro positivo n tem-se n/2 ≤ ⌈n/2⌉ ≤ (n+1)/2.
3. Prove que ⌊n/2⌋ + ⌈n/2⌉ = n para todo número natural n.
4. Prove que n²/2 ≤ ⌊n/2⌋² + ⌈n/2⌉² ≤ n²/2 + ½ para todo número natural n.
5. É verdade que ⌈½ (n−1)⌉ = ⌊n/2⌋ para todo número natural positivo n? É verdade que ⌊½ (n−1)⌋ = ⌈n/2⌉ − 1 para todo número natural positivo n?
6. Compare e critique as duas afirmações a seguir. Afirmação 1: O candidato estará eleito se obtiver (pelo menos) metade mais um dos votos. Afirmação 2: O candidato estará eleito se obtiver mais da metade dos votos.

2. Logaritmos

1. Explique o significado da expressão log_3/2 n.
2. É verdade que log₃ n = log₁₀ n / log₁₀ 3? Justifique.
3. Prove que  3^log n = n^log 3  para qualquer n positivo e qualquer base dos logaritmos.

3. Piso e teto de logaritmos

1. Suponha que n é um inteiro positivo n. É verdade que ⌊lg n⌋ é o maior inteiro k tal que 2^k ≤ n?  É verdade que ⌈lg n⌉ é o menor inteiro k tal que 2^k ≥ n?
2. Seja n um inteiro maior que 1. É verdade que ⌊lg n⌋ ≥ lg (n−1)?  É verdade que ⌈lg n⌉ ≤ lg (n+1)?
3. Suponha que n é um número natural não-nulo. É fato que lg ⌊n/2⌋ ≤ lg n − 1?  É fato que lg ⌈n/2⌉ ≤ lg n?
4. Prove que para qualquer número racional r maior que 1 tem-se ⌊lg r⌋ ≤ lg ⌊r⌋ ≤ lg r ≤ lg ⌈r⌉ ≤ ⌈lg r⌉.

4. Funções inversas

Uma função g é inversa de uma função f se f(g(n)) = g(f(n)) = n. Em outras palavras, y = f(x) se e somente se x = g(y).

1. Dê as inversas das funções  n+7,  7n,  n/5,  √n,  n⁷,  n^−1/7.
2. Dê as inversas das funções  7ⁿ,  7^log₅ n,  7⁵ⁿ,  7⁵ⁿ,  7^n², log₅ n,  log₅ log₇ n,  (log₅ n)².

5. Comparação de funções

1. Prove que √n < n se n > 1.
2. Compare a função (3ⁿ)² com a função 3^(n²). (A segunda também pode ser escrita sem os parênteses: 3^n².) Qual é a maior? Qual a menor?
3. Compare as funções n!, 2^n² e 2ⁿ. Qual é a maior? Qual a menor?
4. Compare as funções nⁿ, n! e n^n/2. Qual é a maior? Qual a menor?

6. Somas e indução matemática

Use indução matemática para fazer os seguinte exercícios.

1. Prove por indução matemática que 1 + 2 + ⋯ + n = n(n+1)/2 para todo número natural n. Em seguida, escreva um algoritmo recursivo que calcule 1 + 2 + ⋯ + n. [Solução]
2. Suponha que r é um número real maior que 1. Prove que r⁰ + r¹ + r² + ⋯ + rⁿ = (rⁿ⁺¹ − 1)/(r − 1) .
3. Calcule o valor da soma  2⁰ + 2¹ + 2² + ⋯ + 2ⁿ.
4. Prove por indução matemática que 1⋅2¹ + 2⋅2² + 3⋅2³ + ⋯ + n⋅2ⁿ = (n − 1) 2ⁿ⁺¹ + 2.
5. Prove por indução matemática que 2² + 2⁴ + 2⁶ + ⋯ + 2²ⁿ = 4 (2²ⁿ − 1) / 3 para todo número natural positivo n.
6. Quantos são os subconjuntos do conjunto  { 0, 1, … , m }?
7. Prove o seguinte fato por indução: para todo número natural não-nulo n tem-se 1² + 2² + 3² + ⋯ + n² = n (n+1) (2n+1)/6.
8. Prove (por indução) que n < 2ⁿ para todo número natural n. Prove (por indução) que n < 2^n/2 quando n > 4. Prove que lg n < n/2
9. Para qualquer número natural não-nulo n, a soma 1/1 + 1/2 + ⋯ + 1/n é conhecida como n-ésimo número harmônico e denotada por H_n. Verifique experimentalmente que  ln n < H_n < 1 + ln n . Encontre a prova dessas desigualdades em seu livro de Cálculo favorito.
10. Prove a seguinte afirmação por indução matemática: para todo número natural positivo n, o número 11ⁿ − 6 é divisível por 5.
11. Para todo número natural n, tem-se 1³ + 2³ + ⋯ + n³ = (1 + 2 + ⋯ + n)². Prove essa identidade por indução matemática.
12. Prove por indução matemática que 1/(1×3) + 1/(3×5) + ⋯ + 1/((2n − 1) (2n + 1)) = n/(2n + 1) para todo número natural n ≥ 1.

7. Iterações e pseudocódigo

Usaremos um estilo de pseudocódigo quase igual ao de CLRS e CLRS. A instrução de atribuição será indicada pelo walrus operator :=.  O operador de igualdade será representado por =, como se faz há séculos na matemática.

1. Quanto vale k no fim do seguinte procedimento?

   1 . k := 0

   2 . para i := 1 até n

   3 .ooo para j := i até n

   4 .oooooo k := k+1

2. Qual o valor de x no final do seguinte fragmento de código?

   1 . x := 0

   2 . para i := 1 até n

   3 .ooo para j := 1 até i

   4 .oooooo x := x+1

3. Suponha n é uma potência de 2. Qual o valor de S ao final do seguinte fragmento de código?

   1 . S := 0

   2 . i := n

   3 . enquanto i > 0

   4 .ooo para j := 1 até i

   5 .oooooo S := S+1

   6 .ooo i := ⌊i/2⌋

4. Qual o valor de S no final do seguinte fragmento de código?

   1 . T := 0

   2 . i := n

   3 . enquanto i > 0

   4 .ooo para j := 1 até n

   5 .oooooo T := T+1

   6 .ooo i := ⌊i/2⌋

5. Escreva um algoritmo iterativo para resolver o seguinte problema: dado um vetor A[p .. r] e um índice q tais que A[p .. q] e A[q+1 .. r] estão em ordem crescente, rearranjar A[p .. r] de modo que ele fique em ordem crescente.  Para que valores de p, q e r o problema faz sentido?
6. Cada um dos algoritmos abaixo recebe um inteiro positivo e devolve outro inteiro positivo. Os dois algoritmos são equivalentes: devolvem o mesmo número se receberem um mesmo n.

   Soma-Quadrados-A (n)

   1 . x := 0

   2 . para j := 1 até n

   3 .ooo x := x + j 2

   4 . devolva x

   Soma-Quadrados-B (n)

   1 . x := n (n+1) (2n+1)

   2 . x := x/6

   3 . devolva x

   Digamos que uma operação aritmética é uma adição, subtração, multiplicação ou divisão. Quantas operações aritméticas o primeiro algoritmo faz? Quantas operações aritméticas o segundo algoritmo faz? Qual dos dois algoritmos é mais eficiente?

8. Português e matemática

A análise de algoritmos depende de uma boa comunicação escrita. Para se comunicar bem, escreva sentenças curtas e diretas. Use pontuação (vírgula, ponto-e-vírgula, ponto final) corretamente. Não seja prolixo. Evite sentenças vagas ou ambíguas. Seja preciso e específico. Não use palavras rebuscadas e evite falar bonito. Use palavras simples e corriqueiras, mas escolha as palavras apropriadas para cada tarefa. Palavras são como as ferramentas de um operário: cada tarefa pede uma determinada ferramenta.

1. Quais das seguintes frases estão corretas?  (a) Seja um número inteiro n.  (b) Seja n um número inteiro.  Justifique sua resposta.
2. Quais das seguintes frases estão corretas?  (a) Suponha que n é maior que 2.  (b) Considere que n é maior que 2.  (b) Assuma que n é maior que 2.  Justifique sua resposta.
3. Quais das seguintes frases estão corretas?  (a) Concluímos que n corresponde a 99.  (b) Concluímos que n equivale a 99.  (c) Concluímos que n é igual a 99.  Justifique sua resposta.
4. Quais das seguintes frases estão corretas?  (a) 2n + 6 = 0 -> n = −3.  (b) 2n + 6 = 0 => n = −3.  (c) 2n + 6 = 0, e portanto n = −3.  (d) 2n + 6 = 0, donde n = −3.  Justifique sua resposta.
5. Quais das seguintes frases estão corretas?  (a) Em seguida, "i" é incrementado.  (b) Em seguida, i é incrementado.  (c) Em seguida, 'i' é incrementado.  Justifique sua resposta.

9. Provas e demonstrações

A análise de algoritmos exige uma certa dose de matemática. Em particular, exige um mínimo de habilidade para ler e escrever provas (demonstrações) de teoremas. (Um teorema é qualquer afirmação matemática.) Sugiro seguir as seguintes recomendações:

1. Antes de começar uma prova, escreva Teorema: e enuncie a afirmação que você pretende provar. Vale a pena fazer isso mesmo que o enunciado esteja implícito no parágrafo anterior.
2. Se o teorema for do tipo se e somente se, trate as partes se e somente se como se fossem dois teoremas independentes.
3. No enunciado do teorema, separe claramente a hipótese da tese. A prova do teorema deve começar com a frase que descreve a hipótese e terminar com a frase que descreve a tese.
4. Comece a prova escrevendo Prova:. Organize a prova como uma sequência lógica de pequenos passos que levam da hipótese à tese.
5. Não tente explicar ao leitor como você raciocinou para obter a prova do teorema. Não tente descrever o caminho que você percorreu para construir a prova. O leitor não está interessado em seu processo mental. Você só precisa convencer o leitor de que o teorema é verdadeiro.
6. Escreva a prova em português; não use os símbolos ->, =>, ∴ e ∃. Para indicar o fim da prova, escreva CQD.

Veja minha página O que é uma prova matemática?