Elementos de Programação
[cursos: MEBM e LMAC]
Exame Escrito B - 1ª data - 07/01/2010 - 09h00m    Duração: 2h30m

Nome:
Número:
Curso:

Grupo I   (3.0 valores)

Usando apenas as funções sobre listas First,Rest,Length,Append{},[[.]] bem como adição, subtracção e multiplicação sobre números naturais e a função Prime (recorde que Prime[i] devolve o i-ésimo número primo), desenvolva imperativamente em Mathematica uma função fact que, quando recebe como argumento um número natural positivo n retorna a lista dos expoentes dos seus factores primos (na posição i da lista deve surgir o expoente do i-ésimo primo na factorização de n). Nomeadamente, pretende-se que fact[20]seja {2,0,1}, e que fact[33]seja {0,1,0,0,1}.

intdiv=Function[{x,y},Module[{q},
q=0;
While[x≥(q+1)y,
q=q+1
];
{q,x-q y}
]];

fact=Function[n,Module[{m,r,i,k,qt,rt,e},
m=n;
r={};
k=0;
i=1;
e=0;
While[m≠1,
{qt,rt}=intdiv[m,Prime[i]^(e+1)];
If[rt==0,e=e+1,
r=Append[r,e];
m=qt;
i=i+1
]
];
r
]];

Grupo II   (1.5+2.5 valores)

a) Considere grafos dirigidos em que cada arco tem associado um custo (inteiro positivo). 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 cada grafo seja representado por um par {n,w}, onde n é o número de nós e w a lista de arcos do grafo, e cada arco é uma lista com 3 elementos, origem, destino, e custo:

	semarcos[n]: grafo com n nós e sem arcos;
	arco[g,o,d,k]: adiciona ao grafo g um arco de o para d com custo associado k;
	dim[g]: número de nós do grafo g;
	arcoQ[g,o,d]: True sse existe em g um arco de o para d	;
	custo[g,o,d]: custo do arco de o para d no grafo g ;
	sementrada[g,d,k]: True sse não existe em g um arco a chegar a d com custo não superior a k; 
	wfgQ[g]: True sse g é um grafo bem formado.

semarcos=Function[n,{n,{}}];
arco=Function[{g,o,d,k},{g[[1]],Append[g[[2]],{o,d,k}]}];
dim=Function[g,g[[1]]];
arcoQ=Function[{g,o,d},Apply[Or,Map[Function[t,t[[1]]==o&&t[[2]]==d],g[[2]]]]];
custo=Function[{g,o,d},Select[g[[2]],Function[t,t[[1]]==o&&t[[2]]==d]][[1,3]]];
sementrada=Function[{g,d,k},
Apply[And,Map[Function[t,t[[2]]≠d||t[[3]]>k],g[[2]]]]];
wftQ=Function[g,
ListQ[g]&&Length[g]==2&&IntegerQ[g[[1]]]&&g[[1]]≥0&&ListQ[g[[2]]]&&Apply[And,Map[Function[t,ListQ[t]&&Length[t]==3&&IntegerQ[t[[1]]]&&IntegerQ[t[[2]]]&&IntegerQ[t[[3]]]&&1≤t[[1]]≤g[[1]]&&1≤t[[2]]≤g[[1]]&&t[[3]]>0],g[[2]]]]
];

b) Especifique equacionalmente apenas a operação sementrada.  
Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função itins que recebe um grafo g, dois nós o e d, e um custo máximo m, e devolve a lista de todos os caminhos no grafo com origem em o e destino em d cujo custo total não exceda m (pode representar um caminho como uma lista de nós).

(* Clear para limpar a implementação anterior *)
Clear[sementrada,semarcos,arco];

sementrada[semarcos[_],_,_]:=True;
sementrada[arco[g_,_,d_,k1_],d_,k2_]:=(k1>k2)&&sementrada[g,d,k2];
sementrada[arco[g_,_,_,_],d_,k_]:=sementrada[g,d,k];

itins=Function[{g,o,d,m},Module[{estende,cams,ncams},
estende=Function[p,Module[{nk,j,cam,n,ps},
{cam,n}=p;
nk=Table[n+custo[g,Last[cam],i],{i,dim[g]}];
ps={};
j=1;
While[j≤dim[g],
If[nk[[j]]≤m,
ps=Append[ps,{Append[cam,j],nk[[j]]}]];
j=j+1
];
ps
]];

cams={};
newcams={{{o},0}};
While[newcams≠{},
cams=Join[cams,newcams];
newcams=Apply[Join,Map[estende,newcams]]
];
Select[cams,Function[p,d==Last[p[[1]]]]]
]];

Grupo III   (1.0+2.0 valores)

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

dignumRec=Function[w,
If[w=={},0,
10*dignumRec[Most[w]]+Last[w]
]];

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

dignumFun=Function[w,Module[{f},
f=Function[p,Module[{ds,n},{ds,n}=p;{Rest[ds],First[ds]+10 n}]];

Nest[f,{w,0},Length[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[{x,y},Module[{u,v},
u=x;
v=0;
While[u≠y,
u=u-1;
v=v+1
];
v
]];

C1:True
C2:v==x-y

Fácil ... com invariante INV: v == x - u