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

Nome:
Número:
Curso:

Grupo I   (6 valores)

A matriz alternante associada aos coeficientes (Subscript[a, 1]), ... , (Subscript[a, n]) e às funções (Subscript[f, 1]), ... , (Subscript[f, k]) é dada por 

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

Usando apenas as funções sobre listas First, Last, Rest, Most, Length, Prepend, Append, {}, [[.]], ListQ, MatrixQ, desenvolva imperativamente em Mathematica um predicado alternanteQ que, quando recebe como argumento uma lista de coeficientes as, uma lista de funções fs, e uma expressão e, determina se e é ou não a matriz alternante associada aos coeficientes em as e às funções em fs.

alternanteQ=Function[{as,fs,e},Module[{ok,i,j},
If[MatrixQ[e]&&Length[e]==Length[as]&&Length[e[[1]]]==Length[fs],
ok=True;
i=1;
While[ok&&i≤Length[as],
j=1;
While[ok&&j≤Length[fs],
ok=(e[[i,j]]==fs[[j]][as[[i]]]);
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;
arestaQ[g,o,d]: True sse existe no grafo g uma aresta 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 lista da forma {w1,...,wn} onde cada wi é uma lista de pares da forma {j,c} representando a existência de uma aresta de cor c a ligar os nós i e j.

semarestas=Function[n,Table[{},{n}]];
aresta=Function[{g,o,c,d},Module[{ng},
ng=g;
ng[[o]]=Append[ng[[o]],{d,c}];
If[o≠d,ng[[d]]=Append[ng[[d]],{o,c}]];
ng
]];
dim=Length;
arestaQ=Function[{g,o,d},
MemberQ[Map[First,g[[o]]],d]];
cores=Function[g,
Apply[Union,Map[Function[w,Map[Function[ar,ar[[2]]],w]],g]]];
subgrafo=Function[{g,cores},
Map[Function[w,Select[w,Function[ar,MemberQ[cores,ar[[2]]]]]],g]];
gbfQ=Function[e,ListQ[e]&&
Apply[And,Map[Function[w,ListQ[w]&&Apply[And,Map[Function[ar,ListQ[ar]&&Length[ar]==2&&IntegerQ[ar[[1]]]&&1≤ar[[1]]≤Length[e]],w]]],e]]];

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

(* Clear para limpar a implementação anterior *)
Clear[semarestas,aresta,subgrafo];
subgrafo[semarestas[n_],_]:=semarestas[n];
subgrafo[aresta[g_,o_,c_,d_],cores_]:=If[MemberQ[cores,c],aresta[subgrafo[g,cores],o,c,d],subgrafo[g,cores]];

maxmono=Function[g,
Module[{n,c,passoum,passotodos},
n=dim[g];
c=cores[g];
passoum=Function[cam,Map[Function[d,Append[cam,d]],
Select[Range[n],Function[d,!MemberQ[Rest[cam],d]&&arestaQ[subgrafo[g,Most[cam]],Last[cam],d]]]]];
passotodos=Function[w,Module[{nw},
nw=Apply[Join,Map[passoum,w]];
If[nw=={},w,nw]
]];

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

Grupo III   (2+4 valores)

a) Considere o programa imperativo binsI. 

binsI = Function[n, Module[{i, j, t, r},
    i = 0;
    r = {{}};
    While[i ≠ n,
     t = r;
     j = 1;
     r = {};
     While[j ≤ Length[t],
      r = Append[r, Append[t[[j]], 0]];
      r = Append[r, Append[t[[j]], 1]];
      j = j + 1
     ];
     i = i + 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 binsF equivalente a binsI.

binsF=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[{i,r},
i=0;
r=0;
While[i≠n,
i=i+1;
r=r+2i-1
];
r
]];

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

Fácil ... com invariante INV: r = = (i^2).