Elementos de Programação 					
[cursos: MEBM e LMAC]
Exame Escrito A - 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 repsQ que, quando recebe como argumento uma lista de números determina se é verdadeiro ou falso que todos os elementos da lista se repetem pelo menos outra vez. Nomeadamente, pretende-se que 
repsQ[{0,1,0}]seja False, já que o elemento 1 surge na lista apenas uma vez, e que 
repsQ[{2,1,2,0,0,1,1,1}]seja True.

repsQ=Function[w,Module[{u,nu,ok,eok,e},
ok=True;
u=w;
While[ok&&u≠{},
e=First[u];
eok=False;
u=Rest[u];
nu={};
While[u≠{},
If[First[u]==e,eok=True,nu=Append[nu,First[u]]];
u=Rest[u]
];
If[eok,u=nu,ok=False]
];
ok
]];

Grupo II   (4+4 valores)

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

id: função identidade em (Subscript[ℕ, 0]);
espec[f,x,y]: função semelhante a f mas que vale y no ponto x;
aval[f,x]: valor da função f no ponto x;
numdefs[f]: número de pontos onde a função f não é a identidade;
comp[g,f]: função composta g após f;
funQ[e]: determina se e representa ou não uma função quasi-identitária em (Subscript[ℕ, 0]) bem formada.
 
a) Desenvolva em Mathematica uma implementação que disponibilize as operações sobre este tipo de dados, escolhendo uma implementação eficiente de modo a que cada função quasi-identitária seja representada como uma lista da forma {{x1,y1},...{xn,yn}} onde x1,...,xn são os valores onde a função não é a identidade, 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)=n caso contrário, deve ser representada por 
                          {{0,1},{3,0},{5,1}}.

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

b) Especifique equacionalmente apenas a operação aval.  
Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função injectivaQ que quando recebe uma função quasi-identitária determina se ela é ou não uma função injectiva. 
Nomeadamente, para a função função f tal que f(0)=1, f(3)=0 e f(n)=n caso contrário, deve obter-se como resultado False pois f(0)=f(1)=1. Para a função função g tal que g(0)=3, g(3)=0 e g(n)=n caso contrário, deve obter-se como resultado True.

Remove[aval,id,espec];

aval[id,x_]:=x;
aval[espec[f_,x_,y_],x_]:=y;
aval[espec[f_,_,_],z_]:=aval[f,z];

injectivaQ=Function[f,Module[{num,d,rs,ok,x,y},
num=numdefs[f];
x=0;
d=0;
rs={};
ok=True;
While[ok&&d<num,
y=aval[f,x];
If[y≠x,
If[aval[f,y]==y||MemberQ[rs,y],ok=False,
d=d+1;rs=Append[rs,y]
]];
x=x+1
];
ok
]];

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 mindelpal que, quando recebe como argumento uma lista calcula o menor número de elementos que é necessário apagar da lista para formar um palíndromo. Uma lista diz-se um palíndromo se é igual quando se tomam os seus elementos do fim para o início.
Nomeadamente, pretende-se que mindelpal[{1,0,1}] seja 0 pois a lista é um palíndromo e portanto não é necessário apagar elementos, e que mindelpal[{2,2,3,2,4}] seja 2 pois a lista não é um palíndromo, nem se pode tornar um palíndromo apagando um dos seus elementos, mas torna-se no palíndromo {2,2,2} se apagarmos os  elementos 3 e 4.

palindromoQ=Function[w,Apply[And,Table[w[[i]]===w[[-i]],{i,1,Length[w]/2}]]];

mindelpal=Function[w,Module[{passo,len,dels},
len=Length[w];
passo=Function[par,Module[{i,listas},
{i,listas}=par;
If[i==len||Apply[Or,Map[Function[x,palindromoQ[Last[x]]],listas]],par,
{i+1,Apply[Join,Map[dels,Select[listas,Function[x,x[[1]]≤Length[x[[2]]]]]]]}
]
]];
dels=Function[x,
Table[{k,Delete[x[[2]],k]},{k,x[[1]],Length[x[[2]]]}]
];

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

C1:Last[w]==0
C2: r==0

Fácil com invariante INV: 
Last[w] = = 0 && r = = (∏_(i=1)^(n-1))Abs[w[[i]]]