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

Exercícios preliminares

"Os logaritmos permanecem importantes
para muitas aplicações científicas e técnicas."

— pérola do jornal O Estado de São Paulo
por volta de agosto de 1998

"But you know what I don't understand?"
To which David replies, "Logarithms?"
Then, reacting to Maddie's look: "What? You understood those?"

— Moonlighting TV show

"The greatest shortcoming of the human race is
our inability to understand the exponential function."

— Albert A. Bartlett, "Arithmetic, Population and Energy", YouTube video

O primeiro grupo de exercícios examina algumas funções elementares importantes para a análise de algoritmos.   O segundo grupo examina alguns algoritmos simples.  O terceiro trata de indução matemática e recursão.

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. Compare e critique as duas proposições a seguir. Proposição 1: "O candidato estará eleito se obtiver metade mais um dos votos válidos". Proposição 2: "O candidato estará eleito se obtiver mais da metade dos votos válidos".

Logaritmos

Explique o significado da expressão "log_3/2 n".

Piso e teto de logaritmos

Veja a definição de lg n no dicionário.

1. Prove ou desprove as seguintes conjeturas:  para todo inteiro positivo n,
   • ⌊lg n⌋  é o maior inteiro k tal que 2^k ≤ n ;
     
   • ⌈lg n⌉  é o menor inteiro k tal que n ≤ 2^k.
2. Prove ou desprove as seguintes conjeturas:  para todo inteiro positivo n,
   • ⌊lg n⌋  ≥  lg (n−1) ;
   • ⌈lg n⌉  ≤  lg (n+1) .
3. Prove ou desprove as seguintes conjeturas:  para todo natural não nulo n,
   • lg ⌈n/2⌉  ≤  lg n ;
   • lg ⌊n/2⌋  ≤  lg n − 1 .

Inversas composicionais

Uma função g é inversa composicional 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).  Dê as inversas composicionais das funções  

n+7 ,  7n ,  n/5 ,  n⁷ ,  n^1/7 ,  n⁻¹ ,  n⁻⁷ .

Dê as inversas composicionais das funções  

7ⁿ ,  7^log₅n ,  7⁵ⁿ ,  7⁵ⁿ ,  7ⁿ² ,  log₅ n ,  log₅ log₇ n ,  (log₅ n)² .

Comparação de funções

Compare as funções n!, 2ⁿ e 2^n².  Qual é a maior? Qual a menor?

Contagem de iterações

Quanto vale k no fim do seguinte procedimento?

Contagem de iterações

Qual o valor de S no final de cada um dos fragmentos de código abaixo?

Intercalação de sequências ordenadas

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 o vetor A[p..r] de modo que ele fique em ordem crescente.

Para que valores de p, q e r o problema faz sentido?

Algoritmos equivalentes

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.

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?

Recursão

Escreva um algoritmo recursivo que encontre o valor de um elemento máximo de um vetor.

Inducão matemática

1. Prove, por indução em k, que  2⁰ + 2¹ + ··· + 2^k  =  2^k+1−1.
2. Prove o seguinte fato por indução:  Para todo número natural não nulo n tem-se   1² + 2² + 3² + ··· + n²  ≤  n³.
3. 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 .

URL of this site: http://www.ime.usp.br/~pf/analise_de_algoritmos/
Last modified: Fri Jul 1 10:13:16 BRT 2011
Paulo Feofiloff
Departamento de Ciência da Computação
Instituto de Matemática e Estatística da USP