Elementos de Programação 					
[cursos: MEBM e LMAC]
Exame Escrito A - 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,{},[[.]] bem como as operações aritméticas sobre números naturais e a função PrimeQ, desenvolva imperativamente em Mathematica uma função num que, quando recebe como argumento uma lista de números naturais {(Subscript[e, 1]),...,(Subscript[e, n])} retorna o valor ((Subscript[p, 1])^(Subscript[e, 1]))*...*((Subscript[p, n])^(Subscript[e, n])), onde (Subscript[((Subscript[p, i])), i∈ℕ]) é a sucessão dos números primos (ie, 2, 3, 5, 7, 11, 13 ...). Nomeadamente, pretende-se que num[{2,0,1}]seja 20, e que num[{0,1,0,0,1}]seja 33.

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 uma matriz quadrada cuja entrada na linha i, coluna j é o custo associado ao arco do nó i para o nó j, se existir, e infinito caso contrário:

	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 ;
	semsaida[g,o,k]: True sse não existe em g um arco a 
				partir de o com custo não superior a k; 
	wfgQ[g]: True sse g é um grafo bem formado.

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

Grupo III   (1.0+2.0 valores)

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

digRec=Function[n,
If[n==0,{},
Append[digRec[Quotient[n,10]],Mod[n,10]]]];

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,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.

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=y;
While[u≠0,
u=u-1;
v=v+1
];
v
]];

C1:True
C2:v==x+y