Elementos de Programação
[cursos: MEBM e LMAC]
Exame Escrito B - 2ª data - 03/02/2010 - 09h00m    Duração: 2h30m

Nome:
Número:
Curso:

Grupo I   (3.0 valores)

Usando apenas as funções sobre listas First,Rest,Length,Append,{},[[.]], desenvolva imperativamente em Mathematica uma função freq que, quando recebe como argumento uma lista de números retorna uma lista consistindo, pela ordem da primeira ocorrência de cada valor, de pares {v,n}, em que v é um valor na lista dada e n o número de ocorrências desse valor. Nomeadamente, pretende-se que freq[{0,5,0,1,0,0,5}]seja {{0,4},{5,2},{1,1}}, indicando que o valor 0 ocorre quatro vezes, o valor 5 ocorre duas vezes, e o valor 1 ocorre uma vez.

Grupo II   (1.5+2.5 valores)

a) Considere tabelas consistindo de um conjunto de índices e de uma lista não vazia de valores associada a cada índice. Desenvolva em Mathematica uma implementação que disponibilize as operações seguintes sobre este tipo de tabelas, escolhendo uma implementação eficiente de modo a que cada tabela seja representada por um par {w,f}, onde w é uma lista representando o conjunto de índices da tabela, e f uma função que associa a cada possível índice a lista dos elementos que lhe estão associados:

	nova: tabela vazia, sem índices nem valores;
	junta[t,i,v]: junta à tabela t o novo valor v associado ao 
			índice (eventualmente novo) i;
	apaga[t,v]: remove da tabela t todas as ocorrências do 
			valor v;
	indices[t]: conjunto de índices da tabela t;
	valores[t,i]: lista de valores da tabela t associados ao 
			índice i;
	numvals[t]: número total de valores na tabela t; 
	disjuntaQ[t]: True sse nenhum valor da tabela t surge 
			associado a dois ou mais índices diferentes.

b) Especifique equacionalmente apenas a operação apaga.  
Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função listaord que devolve a lista ordenada de todos os valores de t, assumindo que a lista de valores associada a cada índice de t já está ordenada.

Grupo III   (1.0+2.0 valores)

a) Considere a sucessão definida recursivamente da seguinte forma

golombRec=Function[n,
If[n==1,1,1+golombRec[n-golombRec[golombRec[n-1]]]]
];

Usando apenas as funções Apply,Map,Nest,FixedPoint,If, a abstracção funcional Function e ainda as operações sobre listas Prepend,Append,First,Last,Rest,Most,Length,[[.]] e 
a construção de listas por enumeração {},{.},{.,.},etc. desenvolva funcionalmente uma função golombFun equivalente a golombRec.  Nota: pode utilizar as operações sobre números que desejar.

b) Usando o cálculo de Hoare, verifique que o programa P seguinte está (parcialmente) correcto face à condição inicial C1 e à condição objectivo C2 indicadas.

P=Function[{x},Module[{u,y,z},
If[EvenQ[x],
u=x;z=0,
u=x-1;z=1
];
y=0;
While[u≠0,
u=u-2;
y=y+1
];
y
]];

C1:True
C2:y==((x-z)/2)