Elementos de Programação 					
[cursos: MEBM e LMAC]
Exame Escrito A - 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 igcolsQ que, quando recebe como argumento uma matriz m retorna True se existem duas colunas de m que são iguais, e False caso contrário. Nomeadamente, pretende-se que 
igcolsQ[{{1,4,1},{6,8,6},{0,8,0}}] seja True pois a primeira e terceira colunas são iguais, e 
igcolsQ[{{8,4,8},{6,6,6},{4,8,8}}] seja False.

igcolsQ=Function[m,Module[{b,j1,j2,i},
b=False;
j1=1;
While[!b&&j1≤Length[m[[1]]],
j2=j1+1;
While[!b&&j2≤Length[m[[1]]],
b=True;
i=1;
While[b&&i≤Length[m],
If[m[[i,j1]]==m[[i,j2]],i=i+1,b=False]
];
j2=j2+1
];
j1=j1+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;
muda[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]]];
muda=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,{muda[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 muda e avanca.  

Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função seq que quando recebe um filme fil devolve a lista das suas imagens.

Remove[img,filminic,junta,muda,avanca];

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

seq=Function[fil,Module[{proj,ims,c},
c=duracao[fil]-1;
ims={prim[fil]};
proj=fil;
While[c≠0,
proj=avanca[proj];
ims=Append[ims,prim[proj]];
c=c-1
];
ims
]];

Grupo III   (4+3 valores)

a) Considere a seguinte definição recursiva. 

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

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 f.

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,ok,e},
y=x;
e=0;
ok=False;
While[!ok,
If[y≠1,
If[OddQ[y],y=y-1,
y=y/2;e=e+1],
ok=True
]
];
e
]];

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

Fácil ... com invariante INV: y*(2^e) == (2^n)&&(!ok||y==1).