Exercício 1.20 - Máximo divisor comum: ordem aplicativa e ordem normal

Exercício 1.20

O processo que um procedure gera é, obviamente, dependente das regras usadas pelo interpretador. Por exemplo, considere o procedure iterativo gcd apresentado. Suponha que interpretássemos esse procedure usando ordem normal de avaliação, conforme explicado na seção 1.1.5. (A ordem normal de avaliação para o if é descrita no exercício 1.5). Usando o método da substituição (para a ordem normal), ilustre o processo gerado ao avaliar (gcd 206 40) e indique o as operações remainder que são de fato realizadas. Quantas operações remainder são realizadas na avaliação em ordem normal de (gcd 206 40)? E na ordem aplicativa?

Resposta:

Para resolver o exercício vamos supor que remainder é uma primitiva.
Ordem aplicativa

Abaixo é mostrada a avaliação da expressão usando ordem aplicativa. A operação remainder é efetuada 4 vezes.

Agora, façamos a avaliação usando ordem normal

Vemos, portanto, que, na ordem normal, há 18 avaliações de remainder, enquanto na ordem aplicativa há apenas 4.
OBS: O código mostrado não fica bem formatado com a largura de coluna padrão do blog. Para facilitar o acompanhamento, sugiro que copie e cole o mesmo para um editor que destaca a sintaxe. Atualmente, estou usando PLT-Racket para resolver os exercícios.

SICP - Exercícios 1.16 a 1.19 - Exponenciação, Multiplicação, e Fibonacci em tempo logarítmico

Exercício 1.16
Projete um procedure que desenvolva um processo iterativo de exponenciação que use uma sucessão de quadrados e também use um número logarítmico de passos, assim como fast-expt. (Dica: usando a observação de que (b^n/2)² = (b²)^n/2, mantenha, junto com o expoente n e a base b, uma variável de estado adicional a, e defina a transformação de estado de tal maneira que o produto abⁿ se mantenha constante de estado para estado. No início, tem-se a igual a 1, e a resposta é dada pelo valor de a ao final do processo. Em geral, a técnica de definir uma quantidade invariante, que não se altera de estado para estado, é uma maneira poderosa de se pensar sobre o projeto de algoritmos iterativos.)
Solução: A dica já diz tudo. Vamos ao código:

Veja que a invariante se mantém nas duas chamadas recursivas a fast-expt-iter. Para a primeira, temos a(b²)^n/2 = abⁿ. Já na segunda, temos (ab)b^n-1 = abⁿ.

Exercício 1.17: O algoritmo de exponenciação desta seção é baseado em executar a exponenciação por meio de repetidas multiplicações. De maneira similar, é possível pensar na multiplicação de inteiros por meio de adições repetidas. O seguinte procedure de multiplicação (que assume que nossa linguagem é capaz apenas de realizar adições, e não multiplicações), é análogo ao procedure expt:

Tal algoritmo tem um número de passos linear em b. Agora, suponha que a linguagem inclua, além da adição, as operações double, que dobra um inteiro, e halve, que divide um inteiro (par) por 2. Usando essas operações, projete um procedure análogo a fast-expt, que use um número de passos logaritmico.
Solução: Vamos chamar nosso procedure fast-mult. Vou copiar o código de fast-expt, para que possamos realizar as substituições necessárias.

Para chegar à definição de fast-mult a b, vamos observar as analogias:

	Exponenciação	Multiplicação
Linear em	n	b
Operação repetida	multiplicação	adição
Condição de parada	n = 0	b = 0
Resposta de parada ("elemento neutro")	1	0
Recursão em	bn = (bn/2)2	ab = 2(a(b/2))

Agora, fica fácil ver as analogias. Para chegar de fast-expt a fast-mult, subsituímos b por a, n por b, 1 por 0 (na primeira cláusula do cond), sqr por double e, finalmente, * por +. O resultado é mostrado a seguir:

Para os efeitos desse exercício, halve e double são primitivas. Como elas não o são de fato, tivemos que defini-las.

Exercício 1.18
Usando os resultados dos exercícios 1.16 e 1.17, desenvolva um procedure que gere um processo iterativo para a multiplicação de dois inteiros em termos de adições, multiplicações por 2 (double), e divisões por 2 (halve), e que use um número logarítmico de passos.
Solução: Agora, temos um análogo ao procedure fast-expt-iter, do exercício 1.16. Basta notar que ab = (2a)(b/2). Vamos usar, além de a e b, a variável de estado adicional x. No início, temos x = 0. A invariante que iremos preservar de é x+ab.

Os códigos de fast-mult-iter e fast-expt-iter apresentam, portanto, exatamente a mesma estrutura. Assim, podem ser abstraídos por procedures de ordem superior (tradução livre para higher order procedures). Isso será visto na próxima seção.

Exercício 1.19 Existe um algoritmo inteligente para computar os números de Fibonacci em um número logarítmico de passos. Lembre-se da transformação das variáveis de estado a e b no processo de fib-iter da seção 1.2.2: a ← a + b e b ← a. Denomine T essa transformação, e observe que aplicando-se T repetidamente por n vezes, começando com 1 e 0, produz o par Fib(n+1) e Fib(n). Em outras palavras, os números de Fibonacci são produzidos aplicando-se Tⁿ, a enésima potência da transformação T, começando com o par (1, 0). Agora, considere que T seja caso especial com p=0 e q=1 numa família de transformações T_pq, onde T_pq transforma o par (a, b) de acordo com a ← bq + aq + +ap e b ← bq + aq. Mostre que, se aplicarmos a transformação T_pq duas vezes, o efeito é o mesmo de se usar uma única transformação T_p'q', da mesma família, e compute p' e q' em termos de p e q. Isso nos dá uma maneira explícita de achar o quadrado de transformações dessa família, e assim podemos computar Tⁿ usando uma sucessão de quadraturas, como no procedure fast-expt. Junte isso tudo e complete o seguinte procedure, que roda em um número logarítmico de passos.

Solução: À primeira vista, esse exercício parece difícil, mas na verdade é um dos mais fáceis até agora... Basta entender o enunciado e saber um pouquinho de aritmética. Vamos lá:
Tpq(a, b) = (bq + aq + ap, bp + aq)
Tpq(Tpq(a, b)) = T2pq(a, b) = Tpq(bq + aq + ap, bp + aq) =
  ( (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p,
    (bp + aq)p + (bq + aq + ap)q )

T2pq(a, b) = ( b(2pq + q2) + a(2q2 + 2pq + p2),
               b(p2 + q2) + a(2pq + q2) )

T2pq(a, b) = ( b(2pq + q2) + a(2pq + q2) + a(p2 + q2),
               b(p2 + q2) + a(2pq + q2) )

Se considerarmos p' = p2 + q2 e q' = 2pq + q2, então temos:
T2pq(a, b) = ( bq' + aq' + ap', bp' + aq' ) = Tp'q'(a, b)
Assim, mostramos que "elevar T_pq ao quadrado" significa aplicar T_p'q', com p' = p2 + q2 e q' = 2pq + q2. O código final para fib-iter fica, portanto:

SICP Exercício 1.15 - Calculando o seno

O seno de um ângulo (especificado em radianos) pode ser computado fazendo uso da aproximação sin x ≈ x, se x é suficientemente pequeno, e da identidade trigonométrica
sin x = 3 sin x/3 - 4 sin3 x/3
para redzir o tamanho do argumento da função seno. (Para os propósitos deste exercício, um ângulo é considerado "suficientemente pequeno" se seu módulo não é maior que 0.1 radianos). Essas ideias são incorporadas nos seguintes procedures:

a. Quantas vezes o procedure p é aplicado quando (sine 12.15) é avaliado?
b. Qual é a ordem de crescimento em espaço e número de passos (como uma função de a) usada pelo processo gerado pelo procedure sine quando a expressão (sine a) é avaliada?
Solução:
a. O procedure p é aplicado 5 vezes. Vamos avaliar a expressão 12.15 manualmente:

De agora em diante, vamos pular as avaliações dos ifs.

Agora, a expansão acabou. Vai começar a redução. Desde já, podemos ver que o procedure p é chamado exatamente 5 vezes. Os passos a seguir são mostrados apenas para que possamos ver todo o cálculo.

b. A ordem de crescimento, em fumção de a, do processo gerado pelo procedure sine quando a expressão (sine a) é avaliada, é log a, tanto em espaço quanto em número de passos.
Primeiramente, vamos chamar de k(a) o número de vezes que o procedure p é chamado, em função de a.
Observando a estrutura do código, podemos chegar à seguinte fórmula.
k(a) = 0, se |a| ≤ 0.1
k(a) = 1 + k(a/3), caso contrário.
Vamos expandir k(a/3):
k(a/3) = 1, se |a|/3 ≤ 0.1, ou seja, se |a| ≤ 0.3
k(a/3) = 1+ k(a/32), caso contrário
Voltando para k(a), podemos dizer:
k(a) = 0, se |a| ≤ 0.1
k(a) = 1, se 1 < |a| ≤ 0.3
k(a/3) = 1+ k(a/32), caso contrário
Ora, tal expansão nos leva a pensar em um padrão. A fórmula fechada para k(a) é
k(a) = 0, se |a| ≤ 0.1
k(a) = teto(log(a/0.1, 3)), caso contrário.
Na fórmula anterior, log(x, y) significa o logaritmo de x na base y, e a função teto(x) é definida como o menor inteiro maior ou igual a x.
Assim, teto(0) = 0, mas teto(0.000001) = 1. De fato, para a=12.15 temos log(121.5, 3) = 4.369070246428542 e, portanto, k(12.15) = 5.
Para responder (finalmente) ao exercício, vamos considerar que as funções cube e p executam um número constante de passos. Isso só é verdade se os argumentos dessas funções não forem muito grandes, mas para o propósito desse exercício podemos assumir tal fato. Daí, fica fácil observar que:

1. k(a) é da ordem de log a
2. O espaço utilizado é proporcional a k(a), portanto sine também é da ordem de log a
   
3. O mesmo vale para o número de passos, uma vez que consideramos (cube a) e (p a) constantes em a

SICP - Exercício 1.14 - Contando o troco... Um pouco de análise de algoritmos

Desenhe a árvore ilustrando o processo gerado pelo count-change da seção 1.2.2 quando está contando o troco para 11 centavos. Quais são as ordens de crescimento de espalo e número de passos usados por esse processo à medida que a quantia a ser trocada aumenta?

Solução: Primeiramente, vamos ao desenho da árvore:

As reticências são para representar um processo que se repete.

Complexidade Espacial
A complexidade espacial do processo gerado por count-change é linear, mais precisamente, Θ(n), com a quantidade a ser trocada. Vejamos: segundo o livro, o espaço é proporcional à altura da árvore que descreve o processo. Sabemos que (count-change n) chama (cc n 5). A altura da árvore se dará pelo caminho (cc n 5) -> (cc n 4) -> (cc n 3) -> (cc n 2) -> (cc n 1) -> (cc (- n 1) 1) -> (cc (- n 2) 1) -> ... (cc 1 1) -> (cc 0 1). A altura é, portanto, da forma n + constante. Assim, temos um processo Θ(n) em espaço.

Complexidade do número de operações
A complexidade do número de operações da ordem de n⁵. Para que possamos chegar a esse resultado, notemos que, como (count-change n) executa somente a expressão (cc n 5), devemos estudar a complexidade desta última expressão. Seja S(n, p) o número de passos realizados por (cc n p), para n≥0 e 0≤p≤5. Definindo como C(n) o número de passos em que estamos interessados, temos:

C(n) = S(n, 5) + constante

Porém, é possível achar uma expressão para S(n, 5).
S(n, 5) = S(n, 4) + S(n-50, 5)

Analogamente,
S(n, 4) = S(n, 3) + S(n-25, 4)
S(n, 3) = S(n, 2) + S(n-10, 3)
S(n, 2) = S(n, 1) + S(n-5, 2)
S(n, 1) = S(n, 0) + S(n-1, 1)

Agora, basta resolver as "recursões", de baixo pra cima...

Primeiro, notamos que o número de passos em p=0 é uma constante.
S(n, 1) = k + S(n-1, 1)
Usando a mesma fórmula para expandir S(n-1, 1), temos
S(n-1, 1) = k + S(n-2, 1) e, portanto,
S(n, 1) = k + (k + S(n-2, 1)) = 2k + S(n-2, 1)
A fórmula geral pode ser vista facilmente:
S(n, 1) = q*k + S(n-q, 1)
Sabemos que a o número de passos quando n é 0 também é constante (vamos chamar de p). Podemos substituir q por n e obter
S(n, 1) = n*k + S(n-n, 1)
S(n, 1) = k*n + p
Portanto, S(n, 1) é Θ(n).

Agora, vamos trabalhar com
S(n, 2) = S(n, 1) + S(n-5, 2)
S(n, 2) = S(n, 1) + S(n-5, 1) + S(n-2*5, 2)
S(n, 2) = S(n, 1) + S(n-5, 1) + S(n-2*5, 1) + S(n-3*5, 2)
A fórmula geral é, portanto:
S(n, 2) = S(n, 1) + S(n-5, 1) + S(n-2*5, 1) + ... + S(n-k*5, 1) + S(n-(k+1)*5, 2)

De maneira geral, sabemos calcular cada um dos termos, com exceção do último. Mas há uma condição especial em que sabemos calcular até mesmo o último termo. Podemos expandir a expressão até o primeiro valor de k tal que n-(k+1)*5 seja menor que zero. Daí, saberemos que, para tal k, S(n - (k+1)*5, 2) será uma constante.

Vamos determinar tal k:

n-5(k+1) < 0
n-5 < 5k
k > n/5-1

Assim, sabemos que o nosso valor de interesse para k é o teto (arredondamento para cima) de n/5. Nessas condições, o somatório para S(n, 2
S(n, 2) = O(n) + O(n-5) + O(n-10) + ... + O(n-5*n/5) + constante
Estamos somando um número dependente de n de termos que também são dependentes de n. Raciocinando informalmente, temos

S(n, 2) = n/5*O(n)
S(n, 2) = O(n²)

Analogamente, podemos calcular as complexidades de S(n, 3), S(n, 4) e, finalmente, C(n) = S(n, 5)

S(n, 3) = n/10*O(n²)
S(n, 3) = O(n³)

S(n, 4) = n/25*O(n³)
S(n, 4) = O(n⁴)

C(n) = S(n, 5) = n/50*O(n⁴)
C(n) = O(n⁵)

Concluindo
O método de calcular troco apresentado é uma simples tradução de um algoritmo recursivo para a linguagem Scheme. Assim sendo, por não tomar os devidos cuidados, repete bastante certos cálculos. Mas nem tudo está perdido, há técnicas para eliminar essas repetições

O raciocínio informal que eu usei pra obter a complexidade n⁵ a primeira vista parece razoavelmente complicado. Lembre-se, porém, que ele é usado pra analisar vários algoritmos diferentes (principalmente do estilo divisão e conquista). Assim sendo, não se preocupe, porque você vai acabar absorvendo a técnica.

SICP - Exercício 1.13 - Termo geral da sequência de Fibonacci

Prove que Fib(n) é o inteiro mais próximo de φⁿ/√5, onde φ = (1+√5)/2. Dica: defina ψ = (1-√5)/2. Use indução e a definição dos números de Fibonacci para provar que Fib(n) = (φⁿ-ψⁿ)/√5.

Solução: Vamos provar por indução que Fib(n) = (φⁿ-ψⁿ)/√5. Temos Fib(0)= 0 =(φ⁰-ψ⁰)/√5, e Fib(1)= 1 = (φ¹-ψ¹)/√5. Juntas, essas afirmações formam a base da indução. Suponhamos que Fib(n) = (φⁿ-ψⁿ)/√5 e, mais ainda, Fib(n+1) = (φⁿ⁺¹-ψⁿ⁺¹)/√5, para todo n não negativo.

Temos, pela definição dos números de Fibonacci:

Fib(n+2) = Fib(n+1) + Fib(n)
Fib(n+2) = (φⁿ⁺¹-ψⁿ⁺¹)/√5 + (φⁿ-ψⁿ)/√5
Fib(n+2) = ((φⁿ⁺¹+φⁿ) - (ψⁿ⁺¹+ψⁿ))/√5
Fib(n+2) = (φⁿ(φ+1) - ψⁿ(ψ+1))/√5

Porém, como φ+1=φ² e ψ+1=ψ² (é verdade, faça as contas...), temos:
Fib(n+2) = (φⁿ⁺²-ψⁿ⁺²)/√5.

Ou seja, provamos por indução que Fib(n)= (φⁿ-ψⁿ)/√5. Mas não é esse o nosso objetivo. O nosso objetivo é mostrar que Fib(n) é o inteiro mais próximo de φⁿ/√5. Para concluir a prova, basta notar que:

1. Fib(n)= φⁿ/√5 - ψⁿ/√5
2. |ψⁿ|/√5 < 0.5, para todo n não-negativo.

SICP - Exercício 1.12 - Triângulo de Pascal

O padrão de números abaixo é denominado triângulo de Pascal.
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1
   ...
Os números nas "arestas" do triângulo são todos 1, e cada número dentro do triângulo é a soma dois dois números sobre ele. Escreva um procedure que compute elementos do triângulo de pascal por meio de um processo recursivo.

Solução: Veja que o enunciado dá todas as dicas para a elaboração de um processo recursivo. O que faremos é uma simples tradução das propriedades enunciadas. Primeiramente, vamos definir que (pascal n p) representa o número na linha n e na coluna p do triângulo. Ambas as contagens começam do zero. Com essa convenção, (pascal n p) é igual à combinação de n elementos, tomados p a p.

Definida a nossa convenção, é só traduzir as regras. Os números das "arestas" são aqueles na primeira coluna ou na última coluna. Portanto, são os que obedecem à condição (or (= p 0) (= p n)). Para os demais, temos (em notação matemática, pascal(n,p) = pascal(n - 1, p - 1) + pascal(n - 1, p). Temos, portanto, o código:

Lembrando que, no "mundo real", deveríamos checar se os argumentos para a função pascal fazem sentido.

SICP - Exercício 1.11

Antes de começar
Como já perceberam, não tenho muita experiência com posts... Acabam saindo sempre muito grandes, mesmo eu tentando dividir em partes. Assim sendo, resolvi desistir da ideia de publicar uma seção por post, e vou começar a publicar um Exercício por post. Afinal de contas, menor que isso não pode ficar, né? Bem, aí vão o enunciado e a solução

Exercício 1.11
Uma função é definida com a regra f(n) = n, se n < 3, e f(n) = f(n-1) + 2f(n-2) + 3f(n-3), se n ≥ 3. Escreva um procedure que compute f por meio de um processo recursivo. Escreva um procedure que computa f por meio de um processo iterativo.

Solução: A solução que gera um processo recursivo é mera tradução da definição para a linguagem Scheme. O código é dado abaixo:

Agora, para a versão de f que gera um processo iterativo. Usando a regra, vemos que f(0) = 0, f(1) = 1, f(2) = 2, f(3) = 4, f(4) = 11, e assim sucessivamente. Vamos fazer uma definição análoga à definição iterativa para cálculo do número de Fibonacci. Se eu começar com a = 0, b = 1 e c = 2, e executar as transformações a -> b, b -> c, e c-> c + 2b + 3a, n vezes, eu termino com a = f(n), b = f(n+1), e c = f(n+2). O código que faz isso é mostrado abaixo (com o cuidado de fazer f funcionar também para números negativos).