Fundamentosde Programação
Soluçãodo segundoteste
16 de Janeirode 2006
Nota
9:00-10:30
Número:
Nome:
Turma:
Escreva o seu número em todas as folhas do teste. O espaço das respostas deve ser limitado ao
espaço fornecido para cada pergunta. O teste tem 9 páginas com 11 questões; a cotação de
cada questão encontra-se indicada entre parêntesis. Boa sorte!
Questão Cotação Classificação
1
1.5
2
1
3
1.5
4
1.5
5
1.5
6
1
7
1.5
8
3
9
2
10
2
11
3.5
1. (1.5) Diga quais as fases do desenvolvimento de um programa, descrevendo sucintamente (2 a
3 linhas) cada uma delas.
● Análise do problema: o programador, juntamente com o cliente, estuda o problema a resolver
●
●
●
●
com o objectivo de determinar exactamente o que o programa deve fazer.
Desenvolvimento de uma solução: determinação de como vai ser resolvido o problema.
Desenvolvimento de um algoritmo e definição abstracta dos tipos de informação usados. Deve
usar-se a metodologia do topo para a base. Vantagens: controle da complexidade e obtenção
de um algorimo modular.
Codificação da solução: 1) tradução do algoritmo para uma LP, e implementação dos tipos de
informação; 2) depuração, i.e., correcção de erros sintácticos e semânticos; 3) finalização da
documentação que vem sido produzida desde a primeira fase.
Testes: definição de uma bateria de testes com o objectivo de “garantir” que o programa
funciona correctamente em todas as situações possíveis.
Manutenção: fase que decorre depois do programa estar em funcionamento. A manutenção
pode ser necessária por dois tipos de razões: 1) descoberta de erros; 2)
modificações/actualizações nas especificações do programa.
2. (1.0) Diga o que entende por objecto com estado. Como é caracterizado esse estado?
Um objecto com estado é um objecto cujo comportamento depende da sua história. O seu
estado é caracterizado por uma ou mais variáveis de estado.
Pág. 3/11
AlunoNº __________________
3. (1.5) Diga quais os métodos de passagem de parâmetros que estudou, descrevendo cada um
deles.
Foram estudados dois métodos de passagem de parâmetros, i.e., formas de associar os
parâmetros concretos aos parâmetros formais:
● Passagem por valor: a cada parâmetro formal é associado o valor do parâmetro concreto
correspondente. Método unidireccional: a alteração do parâmetro formal não afecta o
parâmetro concreto.
● Passagem por referência: a cada parâmetro formal é associada a localização em memória
do parâmetro concreto correspondente. Método bidireccional: uma vez que o parâmetro
formal e o parâmetro concreto ocupam a mesma zona de memória, a alteração do
parâmetro formal afecta o parâmetro concreto.
4. (1.5) Qual o método de gestão de memória usado em Scheme? Descreva esse método.
É o método da recolha de lixo (“garbage collection”). Este método é aplicado quando a
quantidade de memória disponível no amontoado desce para além de um determinado limiar, e
tem duas fases:
● Fase de marcação: todas as células de memória que podem ser alcançadas a partir do
ambiente global, ou de informação mantida pelo interpretador, são marcadas como não
sendo lixo.
● Fase de varrimento: todas as células de memória (das inicialmente atribuídas ao amontoado)
que não foram marcadas na fase anterior são devolvidas ao amontoado.
Pág. 4/11
AlunoNº __________________
5. (1.5) Diga quais os paradigmas de programação que estudou e caracterize cada um deles.
● Programação funcional: os programas são encadeamentos de procedimentos, cada um dos
quais devolve um valor, como uma função matemática.
● Programação imperativa: os programas são sequências de instruções, cada uma das quais
produz um efeito, i.e., altera uma entidade computacional.
● Programação com objectos: baseada na noção de objecto, i.e., entidade computacional que
apresenta um estado (caracterizado por um conjunto de variáveis de estado) e um conjunto de
procedimentos que permitem manipular esse estado, designados por métodos. Os objectos
recebem mensagens, e usam o método adequado para responder a cada tipo de mensagem.
6.
(1.0) Escreva um procedimento que recebe um vector de inteiros e devolve o produto dos
elementos do vector.
(define (produto-elementos-vector v)
(define (produto-aux v corrente ultimo-el prod-ac)
(if (> corrente ultimo-el)
prod-ac
(produto-aux v
(+ corrente 1)
ultimo-el
(* (vector-ref v corrente) prod-ac))))
(let ((ultimo-el (- (vector-length v) 1)))
(produto-aux v 0 ultimo-el 1)))
Pág. 5/11
AlunoNº __________________
7. (1.5) Considere a seguinte definição:
> (define (soma-lista lst)
(define (soma-aux lst total)
(if (null? lst)
total
(soma-aux (rest lst)
(+ (first lst) total))))
(soma-aux lst 0))
Desenhe o diagrama de ambientes originados pela avaliação da forma
(soma-lista '(1 2))
Análogo ao exemplo apresentado na secção 8.3.3 do livro
(avaliação com definições internas – processo iterativo)
Pág. 6/11
AlunoNº __________________
8. Considere a seguinte interacção:
> (define est1 (cons 1 (cons 2 ())))
> (define est2 (cons 1 (cons 2 ())))
a) (1.0) Desenhe, usando a notação de caixas e ponteiros, as estruturas criadas.
est1
> 1
> 2
est2
>
1
> 2
b) (0.5) Qual o valor devolvido por cada uma das seguintes expressões?
> (equal? est1 est2)
#t
> (eq? est1 est2)
#f
c) (1.0) Represente as alterações produzidas nas estruturas pela seguinte interacção:
> (define p (cons 0 ()))
> (set-cdr! (cdr est1) p)
> (set-cdr! (cdr est2) est1)
est1
>
p
1
> 2
1
> 2
> 0
est2
>
d) (0.5) Qual o valor devolvido por cada uma das seguintes expressões?
> est1
(1 2 0)
> est2
(1 2 1 2 0)
9. (2.0) Defina um procedimento chamado transforma! que recebe como argumentos uma
lista e uma operação aplicável aos elementos da lista. O seu procedimento deve alterar
destrutivamente a lista recebida, aplicando a operação a todos os elementos dessa lista. Por
exemplo,
> (define lst (list 1 2 3))
> (transforma! lst (lambda (x) (* 3 x)))
> lst
(3 6 9)
(4
Pág. 7/11
AlunoNº __________________
(define (transforma! lst op)
(if (not (null? lst))
(begin
(set-car! lst (op (car lst)))
(transforma! (cdr lst) op))))
10. (2.0) Defina uma classe que corresponde a uma urna de votação. A sua classe deve receber a
lista dos possíveis candidatos e manter como estado interno o número de votantes em cada
candidato. Os elementos desta classe podem receber dois tipos de mensagens: 1) o nome de um
candidato (um símbolo), aumentando em 1 o número de votos nesse candidato; 2) o símbolo
resultado, devolvendo os resultados da votação até ao momento (use o comando display
para mostrar os resultados). Por exemplo,
> (define urna (cria-urna '(A B C))
> (urna 'resultados)
c – 0
b - 0
a - 0
> (urna 'C)
> (urna 'A)
> (urna 'B)
> (urna 'A)
> (urna 'B)
> (urna 'A)
> (urna 'C)
> (urna 'A)
> (urna 'resultados)
c – 2
b - 2
a - 4
Pág. 8/11
AlunoNº __________________
(define (cria-urna candidatos)
;o procedimento seguinte devolve uma lista em que cada elemento
; é um par cujo 1ºelemento é o nome do candidato e o 2º o nº de
;votos no candidato (zero no início). Por exemplo,
; (inicializa-resultados '(A B C)) devolve ((c . 0) (b . 0) (a . 0))
(define (inicializa-resultados candidatos)
(define (inicializa-aux candidatos resultados)
(if (null? candidatos)
resultados
(inicializa-aux (rest candidatos)
(cons (cons (first candidatos) 0)
resultados))))
(inicializa-aux candidatos ()))
(let ((resultados (inicializa-resultados candidatos)))
(define (vota cand resultados)
(if (eq? cand (car (first resultados)))
(set-cdr! (first resultados)
(add1 (cdr (first resultados))))
(vota cand (rest resultados))))
(define (mostra-resultados resultados)
(if (not (null? resultados))
(begin
(display (car (first resultados)))
(display " - ")
(display (cdr (first resultados)))
(display "
")
(mostra-resultados (rest resultados)))
(newline)))
(lambda (mens)
(cond ((member mens candidatos)
(vota mens resultados))
((eq? mens 'resultados)
(mostra-resultados resultados))
(else (error "urna: pedido desconhecido"))))))
Pág. 9/11
AlunoNº __________________
11.
a) (1.5) Considere o tipo de informação info-aluno, cujos elementos são constituídos por um
número de aluno (um inteiro), e o nome do aluno (uma “string”). Defina o tipo abstracto de
informação info-aluno.
1) Definição das operações básicas:
Construtor:
cria-info-aluno: |N x string --> info-aluno
cria-info-aluno(num, nome) devolve o elemento do tipo info-aluno cujo número é num, e cujo
nome é nome.
Selectores:
número-aluno: info-aluno --> |N
número-aluno(aluno) devolve o número do aluno aluno.
nome-aluno: info-aluno --> string
nome-aluno(aluno) devolve o nome do aluno aluno.
Reconhecedor:
info-aluno?: universal --> lógico
info-aluno?(x) devolve verdadeiro se e só se x for do tipo info-aluno.
Teste:
alunos=?: info-aluno x info-aluno --> lógico
alunos=?(al1, al2) devolve verdadeiro se e só se al1 e al2 representarem o mesmo aluno.
2) Representação interna: Um elemento do tipo info-aluno é representado por um par cujo
primeiro elemento é o número do aluno e cujo segundo elemento é o nome do aluno.
3) Implementação das operações básicas:
(define cria-info-aluno cons)
(define numero-aluno car)
(define nome-aluno cdr)
(define (info-aluno? x)
(and (pair? x)
(integer? (car x))
(string? (cdr x))))
(define alunos=? equal?)
Pág. 10/11
AlunoNº __________________
Pág. 11/11
AlunoNº __________________
b) (2.0) Escreva um procedimento, procura, que recebe uma árvore binária de procura cujas
raízes são do tipo info-aluno, e um inteiro, e procura na árvore o aluno que tem como
número o inteiro recebido, devolvendo o seu nome. Se não for encontrado nenhum aluno com
o número dado, o seu procedimento deve devolver a “string” vazia. O algoritmo de procura
na árvore deve tirar partido do facto de se tratar de uma árvore binária de procura. A árvore foi
criada usando o número de aluno como elemento a comparar.
(define (procura arv num)
(cond ((arvore-vazia? arv) "")
((= num (numero-aluno (raiz arv)))
(nome-aluno (raiz arv)))
((< num (numero-aluno (raiz arv)))
(procura (arv-esq arv) num))
(else (procura (arv-dir arv) num))))