Elementos de Programação 					
[cursos: MEBM e LMAC]
Exame Escrito A - 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 compr que, quando recebe como argumento uma lista de números retorna uma sua versão comprimida consistindo, pela mesma ordem, numa lista de pares {v,n}, em que v é um valor na lista dada e n o número de ocorrências consecutivas desse valor. Nomeadamente, pretende-se que compr[{0,0,0,0,1,2,2,0}]seja {{0,4},{1,1},{2,2},{0,1}}, indicando que primeiro o valor 0 ocorre quatro vezes, depois o valor 1 por uma vez, depois o valor 2 por duas vezes, e finalmente o valor 0 por uma vez.

compr=Function[w,Module[{r,i,q,k,v},
k=Length[w];
r={};
i=1;
While[i≤k,
v=w[[i]];
q=1;
i=i+1;
While[i≤k&&v==w[[i]],
i=i+1;
q=q+1
];
r=Append[r,{v,q}]
];
r
]];

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 (sem repetições) de todos os valores da tabela, e f uma função que associa a cada valor possível uma lista representando os índices a que o valor está associado:

	nova: tabela vazia, sem índices nem valores;
	junta[t,i,v]: junta à tabela t o novo valor v associado ao índice (eventualmente novo) i;
	limpa[t,i]: remove da tabela t o índice i e todos os valores que lhe estão associados;
	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.

nova={{},Function[v,{}]};
junta=Function[{t,i,v},
{If[MemberQ[t[[1]],v],t[[1]],Append[t[[1]],v]],
Function[u,If[u==v,Append[t[[2]][u],i],t[[2]][u]]]}];
limpa=Function[{t,i},
{Select[t[[1]],Function[v,Select[t[[2]][v],Function[j,j≠i]]≠{}]],
Function[v,Select[t[[2]][v],Function[j,j≠i]]]}];
indices=Function[t,Apply[Union,Map[t[[2]],t[[1]]]]];
valores=Function[{t,i},Select[t[[1]],Function[v,MemberQ[t[[2]][v],i]]]];
numvals=Function[t,
Apply[Plus,Map[Length,Map[t[[2]],t[[1]]]]]];
disjuntaQ=Function[t,Apply[And,Map[Function[v,Length[t[[2]][v]]<2],t[[1]]]]];

b) Especifique equacionalmente apenas a operação valores.  
Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função ordlista que devolve a lista de todos os valores de t ordenada, assumindo que, para quaisquer índices distintos i e j, ou todos os valores associados a i são menores ou iguais que todos os valores associados a j, ou todos os valores associados a j são menores ou iguais que todos os valores associados a i.

(* Clear para limpar a implementação anterior *)
Clear[valores,nova,junta];

valores[nova,_]:={};
valores[junta[t_,i_,v_],i_]:=Append[valores[t,i],v];
valores[junta[t_,_,_],i_]:=valores[t,i];

ordlista=Function[t,Module[{tabs,vals,inser,aux},
tabs=Function[{i,j},valores[t,i][[1]]≤valores[t,j][[1]]];
vals=Function[{x,y},x≤y];
inser=Function[{w,c},Module[{r,i,j,ok},
r={};
i=1;
While[i≤Length[w],
j=1;
ok=False;
While[!ok&&j≤Length[r],
If[c[r[[j]],w[[i]]],j=j+1,
ok=True]
];
If[ok,r=Insert[r,w[[i]],j],
r=Append[r,w[[i]]]];
i=i+1
];
r
]];

aux=inser[indices[t],tabs];
Apply[Join,Map[Function[i,inser[valores[t,i],vals]],aux]]
]];

Grupo III   (1.0+2.0 valores)

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

thuemorseRec=Function[n,
If[n==0,0,
If[EvenQ[n],thuemorseRec[n/2],1-thuemorseRec[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,Length,[[.]] e a construção de listas por enumeração {},{.},{.,.},etc. desenvolva funcionalmente uma função thuemorseFun equivalente a thuemorseRec.  Nota: pode utilizar as operações sobre números que desejar.

thuemorseFun=Function[n,Module[{aux},
aux=Function[w,
If[OddQ[Length[w]],Append[w,1-Last[w]],
Append[w,w[[1+Length[w]/2]]]
]
];

Last[Nest[aux,{0},n]]]]

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},
u=x;
If[OddQ[u],
u=u-1
];
y=0;
While[u≠0,
y=y+1;
u=u-2
];
y
]];

C1:EvenQ[x]
C2:y==(x/2)

Fácil ... com invariante INV: y == ((x - u)/2)