Programação

Procedures and Processes
Data Abstraction

Tema 02
Procedimentos e Processos

1.Modelo de Substituição

Usamos o Modelo de Substituição para perceber o que acontece durante a avaliação de um procedimento, aplica-mos um procedimento composto e avalia-mos o corpo do processo, substituíndo cada parâmetro pelo correspondente operando.

Vamos usar o modelo de substituição neste exemplo: 1) Substituímos n por 2.
2) (+ (* 2 2) 1) =
3) (+ 4 1) =
4) 5

2. Factorial
N! = n * (n - 1) * (n - 2) * (n – 3)....3...2....1
N! = n * (n – 1)! = Recursividade
(define (factorial n)
(* n ( factorial ( - n 1))))
(factorial 3)
(* 3 (factorial (- 3 1)))
(* 3 (factorial 2 ))
(* 3 ( * 2 (factorial (- 2 1))))
(* 3 ( * 2 (factorial 1)))
(* 3 ( * 2 1))
(* 3 2)
6

=> Caso Recursivo

Fase expansão

Fase contração

2.1 Predicados e Special Forms
Predicados
Ex: (= 3 3) => #t
(True)
(= 3 7) => #f
(False)
Special Forms
(if (= 4 4) 2 3) => 2
(if (= 4 5) 2 3) => 3

= Predicado
= Consequência
= Alternativa

3. Algoritmos Recursivos
Estratégia:
1) Encontrar um procedimento que resolva uma versão mais simples do problema;
2) Decomposição do problema e determinar os casos recursivos;
3) Determinar os casos base.

Forma geral dos algoritmos recursivos (define (st n)
(if (< n 1)
=> Testar um caso base
0
=> Caso base
(+ (* 3 n) (st (- n 1))))) => Caso recursivo

4. Algoritmos Iterativos
Um algoritmo iterativo usa espaço costante.

Produto selector.
Ex:
(make-rac) ;make-rac:inteiro->constructor
(number ) Selectores
(denom )

Abstração de Pares
Existe uma ligação entre o constructor e o selector: (car (cons )) =>
(car (cons )) =>
Estes pares obdecem à propriedade de
“closure”, podemos usar o resultado de um par para formamos um novo par.
(cons (cons 1 2) 3)

Listas
Lista é um conjunto de dados que pode conter um número ilimitado de items.
E tem as seguintes propriedades:
-car: parte de um par em