Fundamentos da Programaç˜ao de Computadores

Universidade do Minho
Escola de Engenharia
Departamento de Sistemas de Informação
Fundamentos
da
Programação de Computadores
Licenciatura em Tecnologias e Sistemas de Informação
1º Ano — 1º Semestre
Ano Lectivo 2008/2009
— Projecto 04 —
Data de Lançamento: 27 de Outubro de 2008
Data Limite de Entrega: 3 de Novembro de 2008 (12:00)
Prof. Filipe de Sá-Soares
Outubro de 2008
Observações
ˆ A resolução do Projecto pode ser efectuada individualmente ou em grupo. No caso
de resolução por grupo, os grupos de trabalho devem ser compostos por dois elementos. Adicionalmente, estabelece-se que os grupos sejam formados por elementos
pertencentes ao mesmo turno PL.
ˆ Por norma, a resolução do Projecto deve ser auto-contida, ou seja, os alunos não
devem colaborar uns com os outros na resolução dos problemas propostos, excepto
no caso da resolução em grupo, em que os alunos que formam o grupo colaboram entre
si na resolução do projecto. Se, a tı́tulo excepcional, ocorrerem colaborações com
outros alunos para a resolução dos problemas propostos, tal deve ser explicitamente
indicado nos resultados submetidos (ver ponto adiante).
ˆ A submissão dos resultados alcançados na resolução do Projecto deve ser realizada
via moodle, até à data e hora indicadas anteriormente. Cada aluno deverá submeter
o seu trabalho, quer o mesmo tenha sido elaborado individualmente quer em grupo.
Não serão aceites submissões para além dessa data/hora.
ˆ Os resultados a submeter devem constar de um ficheiro de texto (formato ASCII).
O nome do ficheiro deve ser composto pelos seguintes campos: identificação do projecto (na forma “Pii”, em que “ii” é o número do projecto), caracter lowline, números
de aluno dos seus autores, separados por lowline, e extensão .txt. Para o caso de projectos resolvidos de forma individual, apenas deverá ser indicado um número de aluno
(correspondente ao aluno que o resolveu).
O corpo desse ficheiro principiará com a identificação do projecto, seguindo-se a indicação do(s) número(s) e nome(s) do(s) aluno(s) que resolveu(ram) os problemas
propostos e de eventuais colaborações (números e nomes). Depois, deverão surgir as
respostas aos problemas propostos, com a devida sinalização da questão a que se refere cada resposta, e sem alteração de ordem (caso não responda a uma questão, não
deixe de sinalizar a identificação dessa questão, apesar de não fornecer resposta).
Seguidamente, dá-se um exemplo do inı́cio de um desses ficheiros de texto, cuja
designação deveria ser P01 12345 12346.txt. Note que nesse exemplo, não foi dada
resposta à questão A.1.ii e não existiram colaborações extra-grupo.
Projecto 01
Autores
12345 - Filipe de Sá-Soares
12346 - Miguel Abrunhosa de Brito
Colaboraç~
oes
sem colaboraç~
oes
A.1.i - 25
A.1.ii A.1.iii - erro
..
.
ˆ Sempre que for solicitada a escrita de procedimentos, não deixe de evidenciar a
aplicação das boas práticas de programação.
2
Questões
A. Avaliação de Pares e Listas
1. Indique o valor de cada uma das seguintes expressões:
i.
ii.
iii.
iv.
v.
vi.
vii.
viii.
ix.
(car (cons (+ 2 3) (- 5 9)))
(cdr 6)
(car (cons (cons 1 2) (cons 3 4)))
(cdr (cons (cons 1 2) (cons 3 4)))
(cdr (car (cons (cons 1 2) (cons 3 4))))
(cdr (cdr (cons (cons 1 2) (cons 3 4))))
(pair? #t)
(pair? (car (cons 1 2)))
(pair? (cons (+ 4 7) (car (cons 8 3))))
2. Considere que se avaliaram as seguintes expressões:
(define nil (list))
(define exer (cons (cons 1 nil) (cons 2 (cons 3 nil))))
Indique o valor de cada uma das seguintes expressões:
i.
ii.
iii.
iv.
v.
vi.
vii.
viii.
ix.
x.
(car nil)
(cdr nil)
(cons 6 nil)
(cons 6 (cons 7 nil))
exer
(car exer)
(cdr exer)
(car (car exer))
(car (car (car exer)))
(car (cdr (cdr exer)))
3. Considere que se avaliaram as seguintes expressões:
(define nil (list))
(define trem (cons (cons (cons 1 nil) nil)
(cons (cons 2 (cons 3 (cons 4 nil)))
(cons 2 (cons 3 nil)))))
Usando apenas car, cdr e trem, escreva expressões cujos valores sejam:
i.
ii.
iii.
iv.
(1)
1
(2 3)
(3)
4. Usando apenas cons, nil e inteiros (não use list), escreva expressões que,
quando avaliadas, produzam os seguintes resultados:
i. (())
3
ii. (4 8 9)
iii. (4 8 (9))
iv. (3 (4 5) ((6)))
5. Usando apenas list e inteiros (não use cons nem nil), escreva expressões que,
quando avaliadas, produzam os seguintes resultados:
i.
ii.
iii.
iv.
(())
(4 8 9)
(4 8 (9))
(3 (4 5) ((6)))
6. Considere que se avaliou a seguinte expressão:
(define outl (list 1 (list 2 3 4) (list 5 (list 6 7) 8) 9))
Indique o valor de cada uma das seguintes expressões:
i.
ii.
iii.
iv.
v.
vi.
vii.
viii.
ix.
x.
xi.
xii.
xiii.
xiv.
outl
(car outl)
(cdr outl)
(null? (cdr outl))
(car (car outl))
(null? (car (car outl)))
(car (car (cdr outl)))
(cdr (car (cdr outl)))
(car (cdr (car (cdr (cdr outl)))))
(cadr outl)
(caadr outl)
(cdddr outl)
(cdaddr outl)
(cddaddr outl)
7. Considere que os valores de a, b, c e d são:
a ⇒ (())
b ⇒ (4 8 9)
c ⇒ (4 8 (9))
d ⇒ (1 (2 3) ((4)))
Quais são os valores das seguintes expressões?
(nota: os procedimentos length, list-ref e append encontram-se definidos
na secção 2.2.1 da referência principal da unidade curricular)
i.
ii.
iii.
iv.
v.
vi.
vii.
viii.
(length a)
(length b)
(length d)
(list-ref d 2)
(list-ref d 0)
(list-ref d 1)
(list-ref d 4)
(append a b)
4
ix.
x.
xi.
xii.
xiii.
xiv.
xv.
xvi.
xvii.
(cons a
(append
(cons b
(append
(length
(cons b
(length
(append
(length
b)
b d)
d)
b b)
(append b b))
b)
(cons b b))
c c)
(append c c))
B. Escrita de Procedimentos sobre Listas
1. Escreva um procedimento (repetir elem nvezes) que retorne uma lista composta por nvezes o elemento elem.
Exemplos:
(repetir 4 2) ⇒ (4 4)
(repetir 4 0) ⇒ ()
2. Escreva um procedimento (contém? lista elem) que retorne #t se elem estiver contido (ao nı́vel mais elevado) em lista e #f caso contrário. Use equal?
para comparar elementos.
Exemplos:
(contém? (list 1 2 3) 3) ⇒ #t
(contém? (list 1 2 3) 4) ⇒ #f
(contém? (list 1 (list 2 3 2)) 2) ⇒ #f
(contém? (list) 4) ⇒ #f
3. Escreva um procedimento (remover-duplicados lista) que retorne uma lista
formada pelos elementos de lista, mas sem duplicados. Assuma que as listas
são formadas por inteiros.
Exemplos:
(remover-duplicados (list 4 5 6 4 5 6)) ⇒ (4 5 6)
(remover-duplicados (list 7 7 7 7 7 7 7)) ⇒ (7)
(remover-duplicados (list 3 3 3 4 4 4)) ⇒ (3 4)
C. Introdução à Abstracção de Dados
1. Explique em que consiste a abstracção de dados.
2. Aponte algumas das vantagens da abstracção de dados, exemplificando com
situações concretas.
3. Explique o que é um contrato.
4. Enumere e explique o papel de cada um dos componentes de uma abstracção
de dados.
5. O que se quer significar com a expressão “barreira de abstracção”?
6. Numa abstracção de dados, quais são os únicos procedimentos que atravessam
a barreira de abstracção?
5
D. Escrita de Abstracções de Dados
Fazendo uso de abstracção de dados, escreva um programa em Scheme que permita
manipular vectores no espaço cartesiano. Para além dos habituais procedimentos
para criação de vectores e acesso às suas coordenadas, disponibilize procedimentos
que permitam visualizar um vector de acordo com o formato (x,y,z), determinar
se dois vectores são iguais, calcular a norma de um vector, adicionar vectores, multiplicar um vector por um escalar, determinar o produto interno de dois vectores e
averiguar se dois vectores são ortogonais.
Para cada um dos procedimentos indique, sob a forma de comentários Scheme, o
contrato de tipos (ou assinatura do procedimento) e a sua função no âmbito da
abstracção.
Prova de Avaliação Experimental
ˆ Para os alunos avaliados segundo o perfil P1 ou segundo o perfil P2, a prova de
avaliação experimental do presente projecto decorrerá na semana que se inicia a 3 de
Novembro de 2008, tendo lugar na sessão PL em que o aluno se encontrar inscrito.
ˆ A realização da prova de avaliação experimental deverá ser efectuada com recurso
ao moodle, pelo que cada aluno deve garantir previamente o correcto acesso à sua
conta na comunidade moodle FPC, sob pena de não poder realizar a prova.
ˆ Quando se apresentarem à prova de avaliação experimental, os alunos devem ser
capazes de responder às questões do presente projecto sem necessitarem de recorrer
ao interpretador Scheme.
ˆ A não comparência de um aluno avaliado segundo o perfil P1 ou segundo o perfil P2
à prova de avaliação experimental traduz-se na atribuição de uma classificação de
0 (zero) valores nessa prova.
6