1. EXERCÍCIO: mostre que t(n) = O(n), onde t é definida por t(1) = a t(n) = b + t(piso(n/2)) + t(teto(n/2)), sendo a e b constantes positivas quaisquer. =============================================================== --------------------------- SOLUÇÃO --------------------------- (Observação (NÃO FAZ PARTE DA SOLUÇÃO): na prática, as constantes são escolhidas durante a consideração da base e do passo, onde descobrimos quais restrições devem ser satisfeitas pelas constantes. A redação abaixo foi possível porque, antes, nós fizemos essa consideração, e então descobrimos as restrições relevantes.) Temos que mostrar que existem c > 0 e n_0 > 0 tais que, para todo n >= n_0, t(n) <= c*n. Nós mostraremos primeiramente que existem c > 0, d > 0 e n_0 > 0 tais que, para todo n >= n_0, t(n) <= c*n - d. Obviamente, como d > 0 => c*n - d <= c*n, então nós teremos demonstrado o resultado desejado. Sejam então d = b, c = a+b, e n_0 = 1. (Observação: quaisquer d >= b e c >= a + d seriam suficientes.) * Base (n = 1): Temos que mostrar que t(1) <= c*1 - d. De fato, temos: t(1) = a = (a+b)*1 - b = c*1 - d, CQD. * Hipótese de indução: t(n') <= c*n' - d, para todo n' < n. * Passo (n > 1): temos que mostrar que t(n) <= c*n - d. De fato, temos: t(n) = b + t(piso(n/2)) + t(teto(n/2)) <= b + c*piso(n/2) - d + c*teto(n/2) - d --> pela HI = d + c*piso(n/2) - d + c*teto(n/2) - d --> pois d = b = c*piso(n/2) + c*teto(n/2) - d = c*n - d, CQD. --------------------------- SOLUÇÃO --------------------------- =============================================================== 2. OBSERVAÇÃO: a "moral do exercício" acima é que, certas vezes, o palpite da solução de uma equação de recorrência está certo, mas parece difícil prová-lo por indução diretamente; frequentemente, porém, é possível provar o resultado facilmente trocando-se a tese a ser provada (por indução) por uma mais forte. No caso acima, por exemplo, a adição de um termo negativo à inequação da tese facilitou a demonstração do resultado, sem, obviamente, comprometer a correção do argumento. Observe, porém, que a adição do termo negativo somente foi efetiva porque a equação recorrente principal possui duas ocorrências da função "t" do lado direito, de forma que, no passo da indução, o termo negativo adicionado aparece duas vezes, e uma das ocorrências fica "livre" para utilizarmos no argumento. O exercício abaixo exemplifica demonstrações simples do tipo f = Ômega(g). 3. EXERCÍCIO: Mostre que t(n) = Ômega(lg n), sendo "t" definida por t(n) = 1, se n = 1; t(n) = t(piso(n/2)) + 5, se n > 1. =============================================================== --------------------------- SOLUÇÃO --------------------------- Temos que mostrar que existem c > 0 e n_0 > 0 tais que, para todo n >= n_0, 0 <= c*lg n <= t(n). Sejam c = 1 e n_0 = 1. Obviamente, para todo n >= n_0, temos 0 <= lg n = c*lg n. Resta, portanto, apenas provar que c*lg n <= t(n) para todo n >= n_0. Nós o faremos por indução em n: * BASE (n=1): temos que mostrar que c*lg 1 <= t(1). De fato, temos: c*lg 1 = c*0 = 0 <= 1 = t(1), CQD. * HIPÓTESE DE INDUÇÃO: c*lg n' <= t(n'), para todo n' < n. * PASSO (n>1): temos que mostrar que c*lg n <= t(n). De fato, temos: t(n) = t(piso(n/2)) + 5 >= c*lg(piso(n/2)) + 5 --> pela HI, já que n > 1 => piso(n/2) < n. = lg(piso(n/2)) + 5 >= lg(n/2) - 1 + 5 --> pois lg(piso(x)) >= lg(x)-1; veja o lema abaixo. = lg(n/2) + 4 = lg(n) - lg(2) + 4 = lg(n) - 1 + 4 > lg(n) = c*lg(n), CQD. --------------------------- SOLUÇÃO --------------------------- =============================================================== O lema abaixo prova um resultado simples utilizado na solução acima: 4. LEMA: para todo real x >= 1, lg(piso(x)) >= lg(x) - 1. =============================================================== --------------------------- SOLUÇÃO --------------------------- Seja k = lg(piso(x)). Temos então: 2^(k+1) = 2*(2^k) = 2*piso(x) --> pois 2^(lg y) = y, para todo y. = piso(x) + piso(x) >= piso(x) + 1 --> pois x >= 1 >= teto(x) >= x e, aplicando lg dos dois lados, obtemos: k + 1 >= lg(x) <=> lg(piso(x)) + 1 >= lg(x) <=> lg(piso(x)) >= lg(x) - 1, CQD. --------------------------- SOLUÇÃO --------------------------- =============================================================== O lema abaixo exemplifica o fato de que, para mostrarmos que f = O(g), nem sempre é necessário provar uma indução com n_0 = 1. 5. LEMA: t(n) = O(lg n), sendo "t" definida como no exercício 3, isto é, t(n) = 1, se n = 1; t(n) = t(piso(n/2)) + 5, se n > 1. ==================================================================== --------------------------- DEMONSTRAÇÃO --------------------------- (Observação (NÃO FAZ PARTE DA SOLUÇÃO): observe que NÃO EXISTE c > 0 tal que 1 = t(1) <= c*lg(1) = 0. Entretanto, observe que não é necessário definir n_0 = 1; de fato, n_0 pode ser escolhido tão grande quanto desejado, e, assim, abaixo nós o escolhemos grande o suficiente se demonstrar a base da indução.) Temos que mostrar que existem c > 0 e n_0 > 0 tais que, para todo n >= n_0, t(n) <= c*lg n. De fato, sejam c = 6 e n_0 = 2. Nós mostraremos o resultado por indução em n: * BASE (n = 2 ou 3): temos que mostrar que t(n) <= c*lg n. a) n=2: temos: t(2) = t(piso(2/2)) + 5 = t(1) + 5 = 6 = 6*lg 2, CQD. b) n=3: temos: t(3) = t(piso(3/2)) + 5 = t(1) + 5 = 6 < 6*lg 3, CQD. * HIPÓTESE DE INDUÇÃO: t(n') <= c*lg n', para todo n' < n. * PASSO (n >= 4): temos que mostrar que t(n) <= c*lg n. Temos: t(n) = t(piso(n/2)) + 5 <= 6*lg(piso(n/2)) + 5 --> pela HI, já que piso(n/2) < n. <= 6*lg(n/2) + 5 --> pois lg(piso(x)) <= lg(x) para todo x real. = 6*lg(n) - 6* lg(2) + 5 = 6*lg(n) - 6 + 5 < 6*lg(n), CQD. --------------------------- DEMONSTRAÇÃO --------------------------- ==================================================================== 6. EXERCÍCIO: a) A demonstração acima continuaria correta se eliminássemos o caso n=3 da base? b) Mostre que não existe nenhum caso faltando na base da indução da demonstração acima.