Elementos de Programação 					
[cursos: MEBM e LMAC]
Exame Escrito B - 2ª data - 30/01/2013 - 15h    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 maxocs que, quando recebe como argumento uma lista de números calcula o maior número de vezes que um valor se repete na lista. Nomeadamente, pretende-se que 
maxocs[{0,1,1,2,0,1}] seja 3, já que o elemento 1 se repete três vezes.

maxocs=Function[w,Module[{u,nu,max,num,e},
max=0;
u=w;
While[u≠{},
e=First[u];
num=1;
u=Rest[u];
nu={};
While[u≠{},
If[First[u]==e,num=num+1,nu=Append[nu,First[u]]];
u=Rest[u]
];
If[num>max,max=num];
u=nu
];
max
]];

Grupo II   (4+4 valores)

Considere funções f:(Subscript[ℕ, 0])⟶(Subscript[ℕ, 0]) que sejam quasi-constantes, ou seja, existe
c ∈ (Subscript[ℕ, 0]) tal que f(n)=c excepto para um número finito de valores n ∈ (Subscript[ℕ, 0]). 
As operações relevantes identificadas são:

const[c]: função constante em (Subscript[ℕ, 0]) que vale c em todos os pontos;
espec[f,x,y]: função semelhante a f mas que vale y no ponto x;
valor[f,x]: valor da função f no ponto x;
default[f]: constante c que corresponde ao valor da função f em quase todos os pontos;
numdefs[f]: número de pontos onde a função f não é constante;
soma[g,f]: função soma (ponto a ponto) de g e f;
funQ[e]: determina se e representa ou não uma função quasi-constante em (Subscript[ℕ, 0])  bem formada.
 
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 função quasi-constante seja representada como uma lista da forma {c,{{x1,y1},...{xn,yn}}} onde c é a constante associada à função, x1,...,xn são os pontos onde a função não vale c, e  y1,...,yn os correspondentes valores da função. 
Nomeadamente, a função f tal que f(0)=f(5)=1, f(3)=0 e f(n)=7 caso contrário, deve ser representada por 
                          {7,{{0,1},{3,0},{5,1}}}.

const=Function[y,{y,{}}];
espec=Function[{f,x,y},
Which[
y==f[[1]]&&valor[f,x]==f[[1]],f,
y==f[[1]]&&valor[f,x]≠f[[1]],{f[[1]],Select[f[[2]],Function[p,First[p]≠x]]},
y≠f[[1]]&&valor[f,x]==f[[1]],{f[[1]],Append[f[[2]],{x,y}]},
y≠f[[1]]&&valor[f,x]≠f[[1]],{f[[1]],Append[Select[f[[2]],Function[p,First[p]≠x]],{x,y}]}
]
];
valor=Function[{f,x},If[MemberQ[Map[First,f[[2]]],x],Select[f[[2]],Function[p,First[p]==x]][[1,2]],f[[1]]]];
default=Function[f,f[[1]]];
numdefs=Function[f,Length[f[[2]]]];
soma=Function[{g,f},
{g[[1]]+f[[1]],
Join[
Select[Map[Function[p,{p[[1]],p[[2]]+valor[f,p[[1]]]}],g[[2]]],Function[p,p[[2]]≠g[[1]]+f[[1]]]],
Map[Function[p,{p[[1]],p[[2]]+g[[1]]}],Select[f[[2]],Function[p,!MemberQ[Map[First,g[[2]]],p[[1]]]]]]
]}
];
natQ=Function[x,IntegerQ[x]&&x≥0];
funQ=Function[e,
ListQ[e]&&Length[e]==2&&IntegerQ[e[[1]]]&&ListQ[e[[2]]]&&
Apply[And,Map[Function[p,ListQ[p]&&Length[p]==2&&natQ[p[[1]]]&&natQ[p[[2]]]&&p[[2]]≠e[[1]]],e[[2]]]]&&
Length[e[[2]]]==Length[Union[Map[First,e[[2]]]]]
];

b) Especifique equacionalmente apenas a operação valor.  
Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função mult que quando recebe duas funções quasi-constantes devolve a função que resulta do produto das duas (ponto a ponto). 
Nomeadamente, a multiplicação consigo própria da função f tal que f(0)=2, f(3)=3 e f(n)=4 caso contrário, deve resultar na função g tal que g(0)=4, g(3)=9 e g(n)=16 caso contrário.

Remove[valor,const,espec];

valor[const[c_],_]:=c;
valor[espec[f_,x_,y_],x_]:=y;
valor[espec[f_,_,_],z_]:=valor[f,z];

mult=Function[{f1,f2},Module[{f,d1,d2,x,y1,y2,c1,c2,num1,num2},
num1=numdefs[f1];
num2=numdefs[f2];
c1=default[f1];
c2=default[f2];
x=0;
d1=0;
d2=0;
f=const[c1*c2];
While[d1<num1||d2<num2,
y1=valor[f1,x];
y2=valor[f2,x];
If[y1≠c1,d1=d1+1];
If[y2≠c2,d2=d2+1];
If[y1*y2≠c1*c2,f=espec[f,x,y1*y2]];
x=x+1
];
f
]];

Grupo III   (4+3 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, Length, Prepend, Append, Table, Select, Count, Union, Flatten, {}, [[.]] e a construção de listas por enumeração {}, {.}, {.,.}, etc. desenvolva funcionalmente uma função coberturaQ que, quando recebe como argumento um natural n e uma lista de naturais w determina se n pode ou não ser obtido como a soma dos elementos de uma sublista de w. 
Nomeadamente, pretende-se que coberturaQ[10,{5,2,7}] seja False pois não é possível obter 10 como a soma de uma sublista, e que  coberturaQ[10,{5,2,7,2,1}] seja True pois 5+2+2+1=10 (no caso, também 7+2+1=10).

coberturaQ=Function[{n,w},Module[{passo,dels},
passo=Function[triplo,Module[{i,ok,listas,nlistas},
{i,ok,listas}=triplo;
If[i==0||ok,triplo,
nlistas=Apply[Join,Map[dels,Select[listas,Function[x,x[[1]]≤Length[x[[2]]]]]]];
{i-1,Apply[Or,Map[Function[x,Apply[Plus,x[[2]]]==n],nlistas]],nlistas}
]
]];
dels=Function[x,
Table[{k,Delete[x[[2]],k]},{k,x[[1]],Length[x[[2]]]}]
];

FixedPoint[passo,{Length[w],Apply[Plus,w]==n,{{1,w}}}][[2]]
]];

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[{n,i},
n=0;
i=0;
While[i≠Length[w],
i=i+1;
If[w[[i]]==0,
n=n+1
]
];
n
]];

C1:First[w]==0
C2: n>0

Fácil com invariante INV: 
First[w] = = 0 && n = = Count[Take[w,i],0]