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

Nome:
Número:
Curso:

Grupo I   (6 valores)

Uma matriz diz-se de Vandermonde se é da forma 

(({{1, (Subscript[a, 1]), ((Subscript[a, 1])^2), ((Subscript[a, 1])^3), ..., ((Subscript[a, 1])^n)}, {1, (Subscript[a, 2]), ((Subscript[a, 2])^2), ((Subscript[a, 2])^3), ..., ((Subscript[a, 2])^n)}, {1, (Subscript[a, 3]), ((Subscript[a, 3])^2), ((Subscript[a, 3])^3), ..., ((Subscript[a, 3])^n)}, {..., ..., ..., ..., ..., ...}, {1, (Subscript[a, k]), ((Subscript[a, k])^2), ((Subscript[a, k])^3), ..., ((Subscript[a, k])^n)}}))

onde n é um inteiro positivo e  (Subscript[a, 1]), ... , (Subscript[a, k]) são coeficientes.

Usando apenas as funções sobre listas First, Last, Rest, Most, Length, Prepend, Append, {}, [[.]], ListQ, MatrixQ, desenvolva imperativamente em Mathematica um predicado vandermondeQ que, quando recebe como argumento uma expressão e, determina se e é ou não uma matriz de Vandermonde.

vandermondeQ=Function[{e},
Module[{ok,i,j,a},
If[MatrixQ[e]&&Length[e[[1]]]>1,
ok=True;
i=1;
While[ok&&i≤Length[e],
a=e[[i,2]];
j=1;
While[ok&&j≤Length[e[[i]]],
ok=(e[[i,j]]==a^(j-1));
j=j+1
];
i=i+1
];
ok,
False]
]];

Grupo II   (5+3 valores)

Considere grafos não dirigidos cujos nós são numerados de 1 a n, onde n é o número de nós do grafo, e cujas arestas são coloridas. As operações relevantes identificadas são:

semarestas[n]: grafo com n nós e sem arestas;
aresta[g,o,c,d]: adiciona ao grafo g uma aresta de cor c a ligar os nós o e d;
dim[g]: número de nós do grafo g;
colarestaQ[g,o,c,d]: True sse existe no grafo g uma aresta de cor c a ligar os nós o e d;
cores[g]: lista das cores usadas para colorir as arestas de g;
subgrafo[g,cores]: grafo que se obtém de g eliminando todas as arestas cuja cor não esteja na lista cores;
gbfQ[e]: True sse g é um grafo bem formado.
 
a) Desenvolva em Mathematica uma implementação eficiente das operações sobre este tipo de dados, de modo a que um grafo com n nós seja representado por uma matriz quadrada de dimensão n×n cuja entrada  na linha i coluna j é a lista das cores das arestas que ligam os nós i e j.

semarestas=Function[n,Table[{},{n},{n}]];
aresta=Function[{g,o,c,d},Module[{ng},
ng=g;
ng[[o,d]]=Append[ng[[o,d]],c];
If[o≠d,ng[[d,o]]=Append[ng[[d,o]],c]];
ng]];
dim=Length;
colarestaQ=Function[{g,o,c,d},
MemberQ[g[[o,d]],c]];
cores=Function[g,
Union[Flatten[g]]];
subgrafo=Function[{g,cores},Module[{n},
n=dim[g];
Table[Select[g[[o,d]],Function[c,MemberQ[cores,c]]],{o,1,n},{d,1,n}]]];
gbfQ=Function[e,ListQ[e]&&
Apply[And,Map[Function[w,ListQ[w]&&Length[w]==Length[e]&&Apply[And,Map[Function[x,ListQ[x]],w]]],e]]&&Apply[And,Flatten[Table[e[[o,d]]==e[[d,o]],{o,1,Length[e]},{d,1,o-1}]]]
];

b) Especifique equacionalmente apenas a operação cores.  
Desenvolva em Mathematica, sobre a camada de abstracção acima desenvolvida e assegurando a independência da implementação, uma função maxdif que quando recebe um grafo de arestas coloridas g calcula o comprimento do maior caminho em g que se pode obter sem repetir a cor das arestas percorridas.

(* Clear para limpar a implementação anterior *)
Clear[semarestas,aresta,cores];
cores[semarestas[_]]:={};
cores[aresta[g_,o_,c_,d_]]:=Union[cores[g],{c}];

maxdif=Function[g,Module[{n,c,passoum,passotodos},
n=dim[g];
c=cores[g];
passoum=Function[cam,Map[Function[p,Append[Prepend[Rest[cam],DeleteCases[First[cam],p[[1]]]],p[[2]]]],
Select[Apply[Join,Table[{cam[[1,i]],j},{i,1,Length[cam[[1]]]},{j,1,n}]],Function[p,colarestaQ[g,Last[cam],p[[1]],p[[2]]]]]]];
passotodos=Function[w,Module[{nw},
nw=Apply[Join,Map[passoum,w]];
If[nw=={},w,nw]
]];

Max[Map[Length,FixedPoint[passotodos,Table[{c,o},{o,1,n}]]]]-2
]];

Grupo III   (2+4 valores)

a) Considere o programa imperativo tupsI. 

tupsI = Function[n, Module[{poe, i, r},
    poe = Function[{w, e}, Module[{k, u},
       k = 1;
       u = {};
       While[k ≤ Length[w],
        u = Append[u, Prepend[w[[k]], e]];
        k = k + 1
       ];
       u
    ]];
    i = 0;
    r = {{}};
    While[i ≠ n,
     i = i + 1;
     r = Join[poe[r, 0], poe[r, 1]]
    ];
    r
]];
    
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, Table, Length, Prepend, Append, Join, {}, [[.]] e a construção de listas por enumeração {}, {.}, {.,.}, etc. desenvolva funcionalmente um programa tupsF equivalente a tupsI.

tupsF=Function[n,Module[{expande},
expande=Function[w,Join[Map[Function[u,Prepend[u,0]],w],Map[Function[u,Prepend[u,1]],w]]];

Nest[expande,{{}},n]
]];

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[n,Module[{k,r},
r=1;
k=1;
While[k≠n+1,
r=r+r;
k=k+1
];
r
]];

C1:True
C2:r==(2^n)

Fácil ... com invariante INV: r = = (2^(k-1)).