Elementos de Programação 					
[cursos: MEBM e LMAC]
Exame Escrito B - 1ª data - 18/01/2012 - 15h    Duração: 2h30m

Nome:
Número:
Curso:

Grupo I   (6 valores)

A matriz de Vandermonde de grau n associada aos coeficientes (Subscript[a, 1]), ... , (Subscript[a, k]) é dada por 

(({{1, (Subscript[a, 1]), ((Subscript[a, 1])^2), ((Subscript[a, 1])^3), ..., ((Subscript[a, 1])^n)}, {1, (Subscript[a, 2]), ((Subscript[a, 2])^2), ((Subscript[a, 2])^3), ..., ((Subscript[a, 2])^n)}, {1, (Subscript[a, 3]), ((Subscript[a, 3])^2), ((Subscript[a, 3])^3), ..., ((Subscript[a, 3])^n)}, {..., ..., ..., ..., ..., ...}, {1, (Subscript[a, k]), ((Subscript[a, k])^2), ((Subscript[a, k])^3), ..., ((Subscript[a, k])^n)}})).

Usando apenas as funções sobre listas First, Last, Rest, Most, Length, Prepend, Append, {}, [[.]], desenvolva imperativamente em Mathematica uma função vandermonde que, quando recebe como argumento um número natural n e uma lista de coeficientes w retorna a matriz de Vandermonde de grau n associada aos coeficientes em w. 
Nomeadamente, pretende-se que vandermonde[n,{(Subscript[a, 1]), ... , (Subscript[a, k])}]seja precisamente a matriz descrita acima.

vandermonde=Function[{n,w},Module[{mat,lin,i,j},
mat={};
i=1;
While[i≤Length[w],
lin={};
j=0;
While[j≤n,
lin=Append[lin,w[[i]]^j];
j=j+1
];
mat=Append[mat,lin];
i=i+1
];
mat
]];

Grupo II   (2.5+1.5 valores)

Considere eventos e calendários. Cada evento é determinado por uma data (ano, mês e dia) e um descritivo. Um calendário é uma colecção de eventos. As operações relevantes identificadas são:

evt[ano,mes,dia,des]: devolve o evento respectivo;
data[e]: devolve a data (ano, mês, dia) do evento e;
descr[e]: devolve o descritivo do evento e;
calnovo: calendário sem eventos agendados;
junta[e,c]: calendário que resulta de adicionar o evento e ao calendário c;
anocal[c,ano]: lista dos eventos calendarizados em c para esse ano;
anos[c]: lista dos anos com eventos calendarizados em c.
 
a) Desenvolva em Mathematica uma implementação que disponibilize as operações sobre estes tipos de dados, escolhendo uma implementação eficiente de modo a que cada evento seja representado como uma lista da forma {ano,mes,dia,des} onde ano, mes, dia são inteiros apropriados e des uma string; e um calendário representado como uma lista ordenada por ordem crescente do ano e mês da forma {(Subscript[mc, 1]),...,(Subscript[mc, k])} onde cada (Subscript[mc, i]), representando um mês de calendário, é da forma {ano,mes,evs} em que evs é a lista não vazia dos eventos calendarizados para esse ano e mes.

evt=Function[{ano,mes,dia,des},{ano,mes,dia,des}];
data=Function[e,Take[e,3]];
descr=Function[e,e[[4]]];
calnovo={};
junta=Function[{e,c},Module[{nc,i,found,same},
i=1;
found=False;
same=False;
While[!found&&i≤Length[c],
If[c[[i,1]]<e[[1]]||(c[[i,1]]==e[[1]]&&c[[i,2]]<e[[2]]),i=i+1,
found=True;
same=(c[[i,1]]==e[[1]]&&c[[i,2]]==e[[2]])
]
];
nc=c;
If[same,nc[[i,3]]=Append[c[[i,3]],e],nc=Insert[c,{e[[1]],e[[2]],{e}},i]];
nc
]];
anocal=Function[{c,ano},Module[{ac},
ac=Select[c,Function[w,w[[1]]==ano]];
If[ac=={},{},Apply[Join,Map[Function[w,w[[3]]],ac]]]
]];
anos=Function[c,Union[Map[First,c]]];

b) Especifique equacionalmente apenas a operação anocal.  
Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma uma função futuro que quando recebe um calendário c e um ano ano devolve o calendário que se obtém de c eliminando todos os eventos calendarizados para anos anteriores a ano.

(* Clear para limpar a implementação anterior *)
Clear[calnovo,junta,anocal];
anocal[calnovo,_]:={};
anocal[junta[e_,c_],ano_]:=If[data[e][[1]]==ano,Append[anocal[c,ano],e],anocal[c,ano]];

futuro=Function[{c,ano},Module[{as,w,nc},
as=Select[anos[c],Function[a,a≥ano]];
w=Apply[Join,Map[Function[a,anocal[c,a]],as]];
nc=calnovo;
While[w≠{},
nc=junta[First[w],nc];
w=Rest[w]
];
nc
]];

Grupo III   (1.0+2.0 valores)

a) Usando apenas operações aritméticas e Booleanas, as funções Apply, Map, Nest, 
FixedPoint, If, a abstracção funcional Function e ainda as operações sobre listas First, Last, Rest, Most, Drop, Take, Table, Length, Prepend, Append, {}, [[.]] e a construção de listas por enumeração {}, {.}, {.,.}, etc. desenvolva funcionalmente uma função tups que, quando recebe como argumento uma lista w de inteiros positivos retorna a lista de todas as listas da forma {(Subscript[x, 1]), ... , (Subscript[x, n])} onde cada (Subscript[x, i]) é um inteiro tal que 1 ≤ (Subscript[x, i])≤ w[[i]]  e n é o comprimento da lista w. Nomeadamente, pretende-se que tups[{1,4,2}] seja  
{{1,1,1},{1,1,2},{1,2,1},{1,2,2},
{1,3,1},{1,3,2},{1,4,1},{1,4,2}}.

tups=Function[w,Module[{adsuc,topos},
topos=Function[u,u==Take[w,-Length[u]]];
adsuc=Function[u,
Append[u,Table[If[topos[Drop[Last[u],i]],If[Last[u][[i]]<w[[i]],Last[u][[i]]+1,1],Last[u][[i]]],{i,1,Length[w]}]]
];

Nest[adsuc,{Table[1,{Length[w]}]},Apply[Times,w]-1]
]];

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[w,Module[{u,r,i},
u={};
r=0;
i=Length[w];
While[i≠0,
If[w[[i]]≠3,r=r+1,
u=Append[u,3];r=r+2
];
i=i-1
];
{u,r}
]];

C1:True
C2:r==Length[w]+Length[u]

Fácil ... com invariante INV: i+ r = = Length[w]+Length[u].