Elementos de Programação 					
[cursos: MEBM e LMAC]
Exame Escrito B - 2ª data - 09/02/2011 - 15h    Duração: 2h30m

Nome:
Número:
Curso:

Grupo I   (3.0 valores)

Dadas duas listas u e v, o coeficiente de ajuste de u a v é o comprimento do maior prefixo de u cujos elementos ocorrem em v pela mesma ordem. 
Usando apenas as funções sobre listas First,Last,Rest,Most,Length,Prepend,Append,{},[[.]], desenvolva imperativamente em Mathematica uma função ajuste que, quando recebe como argumento duas lista de números u e v retorna o valor do coeficiente de ajuste de u a v. Nomeadamente, pretende-se que ajuste[{1,2,3},{3,1,3,2}] seja 2, ajuste[{1,1,1,4},{3,1,5,1,4,1,4}]seja 4, e ajuste[{4,5,1,1},{2,5,1,1}]seja 0.

ajuste=Function[{u,v},Module[{i,j,ok},
i=1;
j=1;
While[i≤Length[u]&&j≤Length[v],
ok=False;
While[!ok&&j≤Length[v],
If[u[[i]]==v[[j]],ok=True];
j=j+1
];
If[ok,i=i+1]
];
i-1
]];

Grupo II   (2.0+2.0 valores)

a) Considere grafos dirigidos cujos nós são numerados de 1 a n, onde n é o número de nós do grafo. Desenvolva em Mathematica uma implementação que disponibilize as operações seguintes sobre este tipo de grafos, escolhendo uma implementação eficiente de modo a que um grafo com n nós seja representado por uma lista da forma {w1,...,wn} onde cada wi é a lista dos nós que são destino de uma aresta com origem no nó i:

	semarestas[n]: grafo com n nós e sem arestas;
	juntarestas[g,wo,d]: adiciona ao grafo g arestas com origem em cada um dos nós da lista wo e destino no nó d;
	dim[g]: número de nós do grafo g;
	origens[g,d]: lista dos nós do grafo g que são origem de uma aresta cujo destino é o nó d;
	acessiveis[g,o]: lista dos nós para os quais existe um caminho (composto por zero ou mais arestas) a partir do nó o no grafo g ;
	wfgQ[g]: True sse g é um grafo bem formado.

semarestas=Function[n,Table[{},{n}]];
juntarestas=Function[{g,wo,d},
Table[If[MemberQ[wo,i],Append[g[[i]],d],g[[i]]],{i,Length[g]}]];
dim=Length;
origens=Function[{g,d},
Select[Range[Length[g]],Function[o,MemberQ[g[[o]],d]]]];
acessiveis=Function[{g,o},Module[{dests},
dests=Function[w,
Union[w,Apply[Union,Map[Function[x,g[[x]]],w]]]];
FixedPoint[dests,{o}]]];
wfgQ=Function[g,
ListQ[g]&&Apply[And,Map[ListQ,g]]&&
Apply[And,Map[Function[x,IntegerQ[x]&&x>0&&x≤Length[g]],Flatten[g]]]];

b) Especifique equacionalmente apenas a operação origens.  
Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função fecho que quando recebe um grafo g devolve o seu fecho reflexivo e transitivo, isto é, o grafo com os mesmos nós que g em que existe uma aresta do nó o para o nó d se e só se existe um caminho em g de o para d.

(* Clear para limpar a implementação anterior *)
Clear[semarestas,juntarestas,origens];

origens[semarestas[_],_]:={};
origens[juntarestas[g_,wo_,d_],d_]:=Join[wo,origens[g,d]];
origens[juntarestas[g_,_,_],d_]:=origens[g,d];

fecho=Function[g,Module[{n,i,wd,ng},
n=dim[g];
ng=semarestas[n];
i=1;
While[i≤n,
wd=acessiveis[g,i];
While[wd≠{},
ng=juntarestas[ng,{i},First[wd]];
wd=Rest[wd]
];
i=i+1
];
ng
]];

Grupo III   (1.0+2.0 valores)

a) Considere a função definida recursivamente da seguinte forma

pmaRec=Function[w,If[Length[w]≤1,Length[w],
If[Last[w]>w[[pmaRec[Most[w]]]],Length[w],pmaRec[Most[w]]]
]];

Usando apenas as funções Apply,Map,Nest,FixedPoint,If, a abstracção funcional Function e ainda as operações sobre listas First,Last,Rest,Most,Length,Prepend,Append,{},[[.]] e a construção de listas por enumeração {},{.},{.,.},etc. desenvolva funcionalmente uma função pmaFun equivalente a pmaRec.

pmaFun=Function[w,Module[{aux},
aux=Function[u,If[u[[1,2]]>u[[2,2]],
Prepend[Rest[Rest[w]],First[u]],Rest[u]]];

If[w=={},0,Nest[aux,Table[{i,w[[i]]},{i,1,Length[w]}],Length[w]-1][[1,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,n},Module[{c,u},
c=0;
u=w;
While[u≠{},
If[First[u]==n,c=c+1];
u=Rest[u]
];
c
]];

C1:True
C2:c==Count[w,n]

Fácil ... com invariante INV: Count[w,n]==Count[u,n]+c