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

Nome:
Número:
Curso:

Grupo I   (6 valores)

A matriz alternante associada aos coeficientes (Subscript[a, 1]), ... , (Subscript[a, n]) e às funções (Subscript[f, 1]), ... , (Subscript[f, k]) é dada por 

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

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

alternante=Function[{as,fs},Module[{mat,lin,i,j},
mat={};
i=1;
While[i≤Length[as],
lin={};
j=1;
While[j≤Length[fs],
lin=Append[lin,fs[[j]][as[[i]]]];
j=j+1
];
mat=Append[mat,lin];
i=i+1
];
mat
]];

Grupo II   (5+3 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;
diacal[c,ano,mes,dia]: lista dos eventos calendarizados em c para a data dada por ano, mes, dia;
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 da forma {(Subscript[ac, 1]),...,(Subscript[ac, k])} onde cada (Subscript[ac, i]), representando um ano de calendário, é da forma {ano,evs} em que evs é a lista não vazia dos eventos calendarizados para esse ano.

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]],i=i+1,
found=True;
same=(c[[i,1]]==e[[1]])
]
];
nc=c;
If[same,nc[[i,2]]=Append[c[[i,2]],e],nc=Insert[c,{e[[1]],{e}},i]];
nc
]];
diacal=Function[{c,ano,mes,dia},Module[{ac},
ac=Select[c,Function[w,w[[1]]==ano]];
If[ac=={},{},Select[ac[[1,2]],Function[e,e[[2]]==mes&&e[[3]]==dia]]]
]];
anos=Function[c,Map[First,c]];

b) Especifique equacionalmente apenas a operação diacal.  
Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função agregar que quando recebe dois calendários (Subscript[c, 1]) e (Subscript[c, 2]) devolve o calendário que contém todos os eventos calendarizados em (Subscript[c, 1]) e (Subscript[c, 2]).

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

agregar=Function[{c1,c2},Module[{as,w,c},
as=Union[anos[c1],anos[c2]];
w=Apply[Join,
Map[Function[a,Apply[Join,Apply[Join,Table[Join[diacal[c1,a,m,d],diacal[c2,a,m,d]],{m,1,12},{d,1,31}]]]],as]];
c=calnovo;
While[w≠{},
c=junta[First[w],c];
w=Rest[w]
];
c
]];

Grupo III   (2+4 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 bins que, quando recebe como argumento um número natural n retorna a lista de todas as listas de 0s e 1s de comprimento n. Nomeadamente, pretende-se que bins[3] seja  
{{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1}, {1,1,0},{1,1,1}}.

bins=Function[n,Module[{adsuc,uns},
uns=Function[w,Apply[And,Map[Function[x,x==1],w]]];
adsuc=Function[w,
Append[w,Table[If[uns[Drop[Last[w],i]],1-Last[w][[i]],Last[w][[i]]],{i,1,n}]]
];

Nest[adsuc,{Table[0,{n}]},2^n-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=0;
While[i≠Length[w],
i=i+1;
If[w[[i]]==5,u=Append[u,5],
r=r+1
]
];
{u,r}
]];

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

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