Elementos de Programação 					
[cursos: MEBM e LMAC]
Exame Escrito B - 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 ocorr que, quando recebe como argumentos uma lista de listas {(Subscript[w, 1]),...,(Subscript[w, n])} e um elemento x retorna o número de listas em que x ocorre. Nomeadamente, pretende-se que  ocorr[{{1,2},{3,2,2},{1,1,1}},1] seja 2.

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

Grupo II   (4+4 valores)

Considere filas de espera e grafos de filas de espera. Os grafos de filas de espera são 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. Os tipos de dados estão munidos das seguintes operações:

vazia: fila de espera vazia;
entra[f,x]: fila que resulta da entrada do elemento x no fim da fila f;
sai[f]: fila que esulta da saída do primeiro elemento de f; 
comp[f]: comprimento da fila f;
prim[f]: primeiro elemento  da fila de espera f;
fazgrafo[n,w]: grafo com n nós e arestas dadas pelos pares {i,j} constantes da lista w, em que a cada nó está associada uma fila vazia;
porfila[g,i,f]: grafo que resulta de g associando ao nó i a fila f;
lerfila[g,i,]: fila de espera associada ao nó i do grafo g;
arestaQ[g,i,j]: True sse g tem uma resta de i para j;
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 estes tipos, escolhendo uma implementação eficiente de modo a que uma fila de espera seja representada pela lista dos seus elementos, por ordem de chegada, e um grafo com n nós seja representado por {{(Subscript[f, 1]),...,(Subscript[f, n])},w} onde cada (Subscript[f, i]) é a fila associada ao nó i do grafo, e w é uma lista de pares que contém {i,j} sse existe uma aresta do nó i para o nó j.

vazia={};
entra=Append;
sai=Rest;
comp=Length;
prim=First;
fazgrafo=Function[{n,w},{Table[{},{n}],w}];
porfila=Function[{gf,i,f},Module[{fs},
fs=gf[[1]];
fs[[i]]=f;
{fs,gf[[2]]}]];
lerfila=Function[{gf,i},gf[[1,i]]];
arestaQ=Function[{gf,i,j},MemberQ[gf[[2]],{i,j}]];
dim=Function[gf,Length[gf[[1]]]];
gfQ=Function[e,ListQ[e]&&Length[e]==2&&
ListQ[e[[1]]]&&Apply[And,Map[Function[f,ListQ[f]],e[[1]]]]&&
ListQ[e[[2]]]&&
Apply[And,Map[Function[x,ListQ[x]&&Length[x]==2],e[[2]]]]&&
Apply[And,Map[Function[n,IntegerQ[n]&&1≤n≤Length[e[[1]]]],Flatten[e[[2]]]]]
];

b) Especifique equacionalmente apenas a operação lerfila.  
Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função migra que quando recebe um grafo de filas de espera g e um nó i, devolve o grafo semelhante a g que resulta da saída sucessiva de todos os elementos da fila de espera associada ao nó i de g, entrando uma cópia desse elemento na fila associada a cada um dos nós j para os quais exista uma aresta de i para j.

(* Clear para limpar a implementação anterior *)
Clear[lerfila,fazgrafo,entra];

lerfila[fazgrafo[_,_],_]:=vazia;
lerfila[porfila[_,i_,f_],i_]:=f;
lerfila[porfila[g_,_,_],i_]:=lerfila[g,i];

migra=Function[{g,i},Module[{fin,fout,r,n,j,e},
r=porfila[g,i,vazia];
n=dim[g];
j=1;
While[j≤n,
If[arestaQ[g,i,j],
fin=lerfila[r,j];
fout=lerfila[g,i];
While[comp[fout]≠0,
e=prim[fout];
fout=sai[fout];
fin=entra[fin,e]
];
r=porfila[r,j,fin]
];
j=j+1
];
r
]];

Grupo III   (4+3 valores)

a) Considere a seguinte definição recursiva:

ob=Function[w,Module[{mig,n},
mig=Function[{u,i},
If[i>1&&u[[i-1]]≤u[[i]],mig[u,i-1],i]
];

n=mig[w,Length[w]];
If[n≤1,w,
ob[Join[Take[w,n-2],{w[[n]],w[[n-1]]},Drop[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, Union, Flatten, {}, [[.]] e a construção de listas por enumeração {}, {.}, {.,.}, etc. desenvolva funcionalmente uma função funob equivalente a ob.

funob=Function[w,Module[{fmig},
fmig=Function[u,Module[{aux,n},
aux=Function[i,
If[i>1&&u[[i-1]]≤u[[i]],i-1,i]
];

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

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

C1:Select[w,EvenQ]==w
C2:c==Length[w]

Fácil ... com invariante INV: Select[w,EvenQ]==w && c==i-1.