Elementos de Programação 					
[cursos: MEBM e LMAC]
Exame Escrito A - 2ª data - 29/01/2016 - 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 elemQ que, quando recebe como argumentos uma lista de listas {(Subscript[w, 1]),...,(Subscript[w, n])} e um elemento x retorna True se x ocorre pelo menos i vezes em cada uma das listas (Subscript[w, i]), e False caso contrário. Nomeadamente, pretende-se que  elemQ[{{1,1},{1,0,1},{2,1,1,1}},1] seja True, 
e elemQ[{{1},{1,1},{1,1}},1] seja False.

elemQ=Function[{w,x},Module[{ok,i,j,c},
ok=True;
i=1;
While[ok&&i≤Length[w],
c=0;
j=1;
While[c<i&&j≤Length[w[[i]]],
If[w[[i,j]]==x,c=c+1];
j=j+1
];
If[c<i,ok=False,i=i+1]
];
ok
]];

Grupo II   (4+4 valores)

Considere grafos dirigidos cujos nós são numerados de 1 a n, onde n é o número de nós do grafo, em que a cada nó está associada uma fila de espera, munidos das seguintes operações:

novo[n]: grafo com n nós, todos com filas vazias, e sem arestas;
aresta[g,o,d]: adiciona ao grafo g uma aresta do nó o para o nó d;
entra[g,i,x]: grafo que resulta de g pela entrada do elemento x na fila de espera associada ao nó i; 
sai[g,i]: grafo que resulta de g pela saída do primeiro elemento  da fila de espera associada ao nó i;
prim[g,i]: primeiro elemento  da fila de espera associada ao nó i no grafo g;
comp[g,i]: comprimento da fila de espera associada ao nó i no grafo g;
esvazia[g,i]: grafo que resulta de g esvaziando a fila associada ao nó i;
dim[g]: número de nós do grafo g;
gfQ[g]: True sse g é um grafo de filas de espera bem formado.
 
a) Desenvolva em Mathematica uma implementação que disponibilize as operações sobre este tipo de grafos, escolhendo uma implementação eficiente de modo a que um grafo com n nós seja representado por {{(Subscript[f, 1]),...,(Subscript[f, n])},m} onde cada (Subscript[f, i]) é a lista dos elementos na fila associada ao nó i do grafo, por ordem de chegada, e m é uma matriz n×n tal que a entrada na linha i, coluna j é 1 se existe uma aresta do nó i para o nó j, e é 0 em caso contrário.

novo=Function[n,{Table[{},{n}],Table[0,{n},{n}]}];

aresta=Function[{gf,i,j},Module[{ng},
ng=gf[[2]];ng[[i,j]]=1;{gf[[1]],ng}
]];

entra=Function[{gf,i,x},Module[{nf},
nf=gf[[1]];nf[[i]]=Append[nf[[i]],x];{nf,gf[[2]]}
]];

sai=Function[{gf,i},Module[{nf},
nf=gf[[1]];nf[[i]]=Rest[nf[[i]]];{nf,gf[[2]]}
]];

prim=Function[{gf,i},gf[[1,i,1]]];

comp=Function[{gf,i},Length[gf[[1,i]]]];

esvazia=Function[{gf,i},Module[{nf},
nf=gf[[1]];nf[[i]]={};{nf,gf[[2]]}
]];

dim=Function[gf,Length[gf[[1]]]];

wfQ=Function[e,ListQ[e]&&Length[e]==2&&
ListQ[e[[1]]]&&Apply[And,Map[Function[f,ListQ[f]],e[[1]]]]&&
MatrixQ[e[[2]]]&&Apply[And,Map[Function[x,x==0||x==1],Flatten[e[[2]]]]]&&
Length[e[[1]]]==Length[e[[2]]]==Length[e[[2,1]]]
];

b) Especifique equacionalmente apenas a operação comp.
  
Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função cpfila que quando recebe um grafo de filas de espera g e um nó i, devolve o grafo semelhante a g mas em que todas as filas de espera passam a ser iguais à fila associada ao nó i.

(* Clear para limpar a implementação anterior *)
Clear[comp,novo,aresta,entra];

comp[novo[_],_]:=0;
comp[aresta[gf_,_,_],i_]:=comp[gf,i];
comp[entra[gf_,i_,_],i_]:=comp[gf,i]+1;
comp[entra[gf_,_,_],i_]:=comp[gf,i];

cpfila=Function[{g,k},Module[{n,h,r,e,i},
n=dim[g];
r=g;
i=1;
While[i≤n,
r=esvazia[r,i];
i=i+1
];
h=g;
While[comp[h,k]≠0,
e=prim[h,k];
h=sai[h,k];
i=1;
While[i≤n,
r=entra[r,i,e];
i=i+1
]
];
r
]];

Grupo III   (4+3 valores)

a) Considere a seguinte definição recursiva:

bs=Function[w,Module[{tr,n},
tr=Function[{u,i},
If[i≥Length[u]||u[[i]]>u[[i+1]],i,tr[u,i+1]]
];

n=tr[w,1];
If[n≥Length[w],w,
bs[Join[Take[w,n-1],{w[[n+1]],w[[n]]},Drop[w,n+1]]]]
]];

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 funbs equivalente a bs.

funbs=Function[w,Module[{ftr},
ftr=Function[u,Module[{aux,n},
aux=Function[i,
If[i≥Length[u]||u[[i]]>u[[i+1]],i,i+1]
];

n=FixedPoint[aux,1];
If[n≥Length[u],u,Join[Take[u,n-1],{u[[n+1]],u[[n]]},Drop[u,n+1]]]
]];

FixedPoint[ftr,w]
]];

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

C1:Count[w,x]==0
C2:c==0

Fácil ... com invariante INV: Count[w,x]==0 && c==0.