Elementos de Programação 					
[cursos: MEBM e LMAC]
Exame Escrito B - 2ª data - 30/01/2015 - 15h00         Duração: 2h30m

Nome:
Número:
Curso:

Grupo I   (5 valores)

Usando apenas as funções sobre listas First, Last, Rest, Most, Length, Prepend, Append, {}, [[.]], desenvolva imperativamente em Mathematica uma função lincolQ que, quando recebe como argumento uma matriz quadrada m retorna True se alguma linha de m for igual a alguma coluna, e False caso contrário. Nomeadamente, pretende-se que 
lincolQ[{{8,4,10},{6,8,9},{4,8,0}}] seja False, e 
lincolQ[{{8,4,10},{6,8,9},{4,8,8}}] seja True pois a segunda coluna é igual à terceira linha.

lincolQ=Function[m,Module[{b,i,j,k},
b=False;
i=1;
While[!b&&i≤Length[m],
j=1;
While[!b&&j≤Length[m],
b=True;
k=1;
While[b&&k≤Length[m],
If[m[[i,k]]==m[[k,j]],k=k+1,b=False]
];
j=j+1
];
i=i+1
];
b
]];

Grupo II   (4+4 valores)

Considere imagens (rectângulos formados por píxeis, em que cada píxel tem associada uma cor) e filmes (sequências não vazias de imagens). As operações identificadas são:

img[n,m,f]: imagem com n*m píxeis em que o píxel i,j tem associada a cor f[i,j];
dim[im]: par de valores que determina o número de píxeis da imagem im;
pix[im,i,j]: cor associada ao píxel i,j da imagem im;
altera[im,i,j,c]: imagem que resulta de im colocando a cor c na píxel i,j;
difs[im1,im2]: lista de todas as diferenças entre as imagens im1 e im2, da mesma dimensão, correspondendo cada diferença a um triplo {i,j,c} onde c, a cor associada ao píxel i,j na imagem im2, é distinta da cor associada ao mesmo píxel na imagem im1;
filminic[im]: filme que tem apenas a imagem inicial im;
juntaim[fil,im]: filme que resulta de juntar a imagem im no final do filme fil;
prim[fil]: imagem inicial do filme fil;
ult[fil]: última imagem do filme fil;
duracao[fil]: número de imagens do filme fil;
avanca[fil]: filme que resulta de fil eliminando a sua imagem inicial;
imQ[e]: determina se e é uma imagem bem formada;
filQ[e]: determina se e é um filme bem formado.
 
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 imagem seja representada por uma lista da forma {n,m,mat} onde mat é uma matriz com n linhas e m colunas de entradas inteiras (cada inteiro representa uma cor), e cada filme com k+1 imagens seja representado por uma lista da forma {im0,{alt1,...,altk},imk} onde im0 é a imagem inicial, imk a imagem final, e altj é a lista das diferenças entre a imagem imj-1 e a imagem imj.

img=Function[{n,m,f},{n,m,Table[f[i,j],{i,1,n},{j,1,m}]}];
dim=Most;
pix=Function[{im,i,j},im[[3,i,j]]];
altera=Function[{im,i,j,c},Module[{res},
res=im;
res[[3,i,j]]=c;
res
]];
difs=Function[{im1,im2},Select[Apply[Join,Table[{i,j,im2[[3,i,j]]},{i,1,im1[[1]]},{j,1,im1[[2]]}]],
Function[t,im1[[3,t[[1]],t[[2]]]]≠t[[3]]]
]];
filminic=Function[im,{im,{},im}];
juntaim=Function[{fil,im},{fil[[1]],Append[fil[[2]],difs[fil[[3]],im]],im}];
prim=First;
ult=Function[fil,fil[[3]]];
duracao=Function[fil,1+Length[fil[[2]]]];
avanca=Function[fil,{First[FixedPoint[Function[par,If[par[[2]]=={},par,{altera[par[[1]],par[[2,1,1]],par[[2,1,2]],par[[2,1,3]]],Rest[par[[2]]]}]],{fil[[1]],fil[[2,1]]}]],
Rest[fil[[2]]],fil[[3]]}];
posnatQ=Function[n,IntegerQ[n]&&n>0];
imQ=Function[e,ListQ[e]&&Length[e]==3&&posnatQ[e[[1]]]&&posnatQ[e[[2]]]&&MatrixQ[e[[3]]]&&Length[e[[3]]]==e[[1]]&&Length[e[[3,1]]]==e[[2]]&&Apply[And,Map[IntegerQ,Flatten[e[[3]]]]]];
filQ=Function[e,ListQ[e]&&Length[e]==3&&imQ[e[[1]]]&&imQ[e[[3]]]&&e[[1,1]]==e[[3,1]]&&e[[1,2]]==e[[3,2]]&&ListQ[e[[2]]]&&
Apply[And,Map[Function[w,ListQ[w]&&Apply[And,Map[Function[t,ListQ[t]&&Length[t]==3&&Apply[And,Map[IntegerQ,t]]&&1≤t[[1]]≤e[[1,1]]&&1≤t[[2]]≤e[[1,2]]],w]]],e[[2]]
]
]&&
Apply[And,Table[Union[difs[prim[Nest[avanca,e,i-1]],prim[Nest[avanca,e,i]]]]==Union[e[[2,i]]],{i,1,Length[e[[2]]]}]]&&
prim[Nest[avanca,e,Length[e[[2]]]]]==e[[3]]
];

b) Especifique equacionalmente apenas as operações altera e prim.  

Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função morph que quando recebe duas imagens im1 e im2 constrói um filme que começa com a imagem  im1 e termina com a imagem im2, contendo imagens intermédias que fazendo evoluir im1 para im2 introduzido em cada nova imagem uma das diferenças entre elas. Por exemplo, poderia ter-se:

Remove[img,filminic,junta,altera,prim];

altera[img[n_,m_,f_],i_,j_,c_]:=img[n,m,Function[{a,b},If[a==i&&b==j,c,f[i,j]]]];
prim[filminic[im_]]:=im;
prim[junta[fil_,_]]:=prim[fil];

morph=Function[{im1,im2},Module[{fil,nov,im,c},
nov=difs[im1,im2];
im=im1;
fil=filminic[im];
c=1;
While[c≤Length[nov],
im=altera[im,nov[[c,1]],nov[[c,2]],nov[[c,3]]];
fil=juntaim[fil,im];
c=c+1
];
fil
]];

Grupo III   (4+3 valores)

a) Considere a seguinte definição recursiva. 

r=Function[{w,o},If[o=={},{},
Prepend[r[w,Rest[o]],{Append[w,o[[1]]],Rest[o]}]]];
q=Function[p,If[p=={},{},
Join[r[p[[1,1]],p[[1,2]]],q[Rest[p]]]]];
f=Function[{p,n},If[n==0,p,
q[f[p,n-1]]]];
g=Function[p,If[p=={},{},
Prepend[g[Rest[p]],p[[1,1]]]]];
h=Function[{w,n},g[f[{{{},w}},n]]];

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, Length, Prepend, Append, Table, Select, Count, Join, Flatten, {}, [[.]] e a construção de listas por enumeração {}, {.}, {.,.}, etc. desenvolva funcionalmente em Mathematica um programa fun equivalente a h.

fun=Function[{w,n},Module[{h,k},
h=Function[p,Apply[Join,Map[k,p]]];
k=Function[p,Table[{Append[p[[1]],p[[2,i]]],Drop[p[[2]],i]},{i,1,Length[p[[2]]]}]];

Map[First,Nest[h,{{{},w}},n]]
]];

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

Function[x,Module[{y,b,e},
y=x;
b=True;
e=0;
While[b,
If[y==1,b=False,
If[OddQ[y],y=y-1,
y=y/2;e=e+1]
]
];
e
]];

C1:x==(2^k)
C2:e==k

Fácil ... com invariante INV: y*(2^e) == (2^k)&&(b||y==1).