109
edits
Changes
Jump to navigation
Jump to search
no edit summary
=== Fecho transitivo ===
Tendo criado os fechos mais simples, das propriedades reflexivas e simétricos, nós agora nos concentraremos na implementação do fecho transitivo em Maple, que é um problema mais difícil do que os casos anteriores em termos de complexidade computacional. No texto, há dois algoritmos descritos, ou seja, um fecho transitivo genérico e um algoritmo de Warshall, e ambos serão abordados nesta seção.
Para implementar o fecho transitivo, precisamos implementar tanto o juntar booleano quanto as operações de produto booleanas, previamente introduzido no Capítulo 2. Para começar, vamos criar as funções auxiliares booleana que nos permitem converter entre zero e um e valores verdadeiro-falso.
<pre>
with(linalg):
int_to_bool(0) := false:
int_to_bool(1) := true:
bool_to_int(true) := 1:
bool_to_int(false) := 0:
</pre>
Em seguida, vamos construir o booleano se juntar a função, novamente com base no trabalho anterior do capítulo 3.
<pre>
BoolJoin := proc(A::matrix, B::matrix)
local i, j, C;
C := matrix(rowdim(A), coldim(A), zeroes);
for i from 1 to rowdim(A) do
for j from 1 to coldim(A) do
C[i,j] := int_to_bool(A[i,j]) or int_to_bool(B[i,j]);
od;
od;
map(bool_to_int,C);
end:
</pre>
Após isso, nós construímos o produto booleano.
<pre>
BoolProd := proc(A::matrix, B::matrix)
local i, j, k, C;
C := matrix(rowdim(A), coldim(B), zeroes);
for i from 1 to rowdim(A) do
for j from 1 to coldim(B) do
C[i,j] := false;
for k from 1 to coldim(A) do
C[i,j] := C[i,j]
or (int_to_bool(A[i,k])
and int_to_bool(B[k,j]));
od;
od;
od;
map(bool_to_int, C);
end:
</pre>
Agora estamos prontos para começar a aplicar o procedimento para o cálculo do fecho transitivo, tal como definido na página 3877 do texto.
<pre>
TransClosure := proc(M::matrix)
local i, A, B;
A := M;
B := A;
for i from 2 to coldim(M) do
A := BoolProd(A, M);
B := BoolJoin(B, A);
evalm(A);
evalm(B);
od;
evalm(B);
end:
</pre>
Nós testamos nosso procedimento de fecho transitivo em um exemplo.
<pre>
T1 := matrix(3,3,[1,0,1,0,1,0,1,1,0]):
TransClosure(T1);
</pre>
Em seguida, vamos examinar como o algoritmo de Warshall compara (em termos de tempo de execução de um exemplo simples) para este algoritmo geral que acabamos de implementar. Em primeiro lugar, temos de implementar o algoritmo de Warshall em Maple.
<pre>
Warshall := proc(M::matrix)
local i, j, k, W, n;
W := map(int_to_bool,M);
n := coldim(M);
for k from 1 to n do
for i from 1 to n do
for j from 1 to n do
W[i,j] := W[i,j] or (W[i,k] and W[k,j]);
od;
od;
od;
evalm(map(bool_to_int, W));
end:
Warshall(T1);
</pre>
Podemos comparar estes dois procedimentos em termos de tempo de execução usando o comando do tempo no Maple. Mas, devemos notar que esta comparação em um único exemplo não prova nada; ao contrário, ela é útil para ilustrar geralmente os tempos de execução para os dois algoritmos que foram implementados. Para fazer essa ilustração, vamos criar uma matriz zero-um que opera sobre o conjunto A = {1,2,3,4}.
<pre>
T2:=matrix(4, 4, [0,0,0,1,1,0,1,0,1,0,0,1,0,0,1,0]);
st:=time():Warshall(T2):time()-st;
st:=time():TransClosure(T2):time()-st;
</pre>
A partir deste exemplo, podemos ver que no algoritmo do Warshall pode ser uma melhoria substancial sobre o método que utiliza junção e produtos booleanos, neste exemplo específico. O leitor é encorajado a explorar mais que este.
== Relações de equivalência ==
Examinaremos, nesta seção, como podemos usar o Maple para calcular com relações de equivalência. Há três problemas específicos que vamos abordar aqui: como calcular a classe de equivalência de um elemento, dada uma relação de equivalência em um conjunto; como determinar o número de relações de equivalência em um conjunto finito; e, como calcular a relação de equivalência menor que contém uma dada relação em algum conjunto finito.
Para começar, vamos primeiro fornecer um teste para uma relação estar em uma relação de equivalência. Usando o trabalho que já fizemos, e recordando que uma relação de equivalência é simplesmente aquele que é reflexiva, simétrica e transitiva, o nosso trabalho é simples.
<pre>
IsEqRel := IsTransitive @ IsSymmetric @ IsReflexive;
</pre>
Recorde-se que, tendo uma relação de equivalência de R, e um membro a do domínio de R, a classe de equivalência de um é o conjunto de todos os membros b do domínio de R para o qual o par (a,b) pertence a R. Em outras palavras, é o conjunto de todos os elementos no domínio de R que são R-equivalentes para a. Assim, o algoritmo usado para construir a classe de equivalência de um é muito simples: nós apenas iremos pesquisar R procurando todos os pares da forma (a,b), acrescentando cada um desses segundo elemento b para a classe. Não precisamos procurar por pares da forma (b,a), porque as relações de equivalência são simétricas. Dada uma relação de equivalência, e um ponto no seu domínio, esse procedimento retorna a classe de equivalência do ponto.
<pre>
EqClass := proc(R::set, a::anything)
local i, S;
S := {};
for i from 1 to nops(R) do
if R[i][1] = a then
S := S union R[i][2];
fi;
od;
RETURN(S);
end:
EqClass([0,0],[0,2],[1,0],[1,1], [2,1],[1,2],[0,1], 0);
</pre>
Agora apresentamos um procedimento que constrói todas as relações de equivalência em um determinado conjunto.
<pre>
DetermineEqClass := proc(A::set)
local P, Q, S, E, i, j, p;
S := {};
E := {};
for i from 1 to nops(A) do
for j from 1 to nops(A) do
S := S union [A[i], A[j] ] ;
od;
od;
P := combinat[powerset](S);
for p in P do
if IsSymmetric(p) and IsReflexive(p) and IsTransitive(p) then
E := E union p;
fi;
od;
RETURN(E);
end:
DetermineEqClass(1,2);
DetermineEqClass(1,2,3);
</pre>
Como última questão a ser analisada nesta seção, vamos determinar a relação de equivalência menor que contém uma determinada relação. O elemento motivador no algoritmo é o fato de que precisamos para gerar uma relação P contendo a relação determinada R tal que P é simétrica, reflexiva e transitiva. Recordando a seção sobre fechos, deduzimos a seguinte algoritmo em pseudocódigo para determinar a relação de equivalência P contendo a relação R:
1- Criar o fecho reflexivo da relação R; chamam isso de P.
2- Criar o fecho simétrico da relação P e chamar este Q. Observe que Q ainda é reflexiva já que não há elementos foram removidos, assim que todos os pares diagonais (a,a) ainda pertencem ao Q.
3- Criar o fecho transitivo da relação Q e devolver o presente como saída. Este é reflexivo, pela mesma razão, conforme descrito na etapa anterior. Esta relação também é simétrica, já que, se (a,b) e (b,c) implica a inclusão de um elemento (a,c), em seguida, uma vez que executou o fecho simétrico, sabemos que existem elementos (c,b) e (b,a) de modo a que também temos o elemento (c,a). Daí a relação final será transitiva, reflexiva e simétrica.
Nós implementamos isso em Maple como a composição dos quatro funções: '''Warshall''', '''SymmClose''', '''RefClose''', e '''MakeMatrix'''.
<pre>
EqContainment := Warshall @ SymmClose @ RefClose @ MakeMatrix;
R2;
EqContainment(R2, 1,2,3,4);
</pre>
== Ordenamento parcial e elementos mínimos ==
Nesta seção, analisamos ''posets'', ''máximos'' e ''mínimos'', assim como as ideias de supremo, ínfimo e ordenação topológica. Vamos explorar esses tópicos em Maple, e vamos deixar a exploração dos outros tópicos desta secção para o leitor.
Primeiro, vamos definir um novo tipo em ''Maple'' para ordens parciais. Para esta parte, vamos considerar uma ordem parcial a ser um conjunto de pares ordenados (um objeto do tipo '''rel''') que satisfaz as três condições necessárias para uma relação a ser uma ordem parcial: reflexividade (''reflexivity''), antissimetria (''antisymmetry'') e transitividade (''transitivity'').
<pre>
`type/po` := proc(obj)
type(obj, rel) and IsReflexive(obj)
and IsAntiSymmetric(obj)
and IsTransitive(obj);
end:
</pre>
Isto ilustra uma outra maneira em que você pode definir novos tipos em Maple, deverá a álgebra de tipos estruturados revelar-se insuficiente.
Em seguida, vamos construir um procedimento que determina o conjunto de elementos mínimos de um conjunto parcialmente ordenado. O procedimento a seguir usa dois argumentos: uma ordem de '''R''' parcial, e um subconjunto '''S''' do domínio de '''R'''. Ele retorna o conjunto de elementos mínimos de '''S''' com respeito à ordenamento '''R'''.
<pre>
MinimalElements := proc(R::po, S::set)
local M, # set of minimal elements of S; returned
s,t; # indices into S
if S minus DomainRelation(R) <> {} then
ERROR(`set must be contained in the domain of the relation`);
fi;
M := S;
for s in S do
for t in S minus s do
if member([t,s], R) then
M := M minus s;
fi;
od;
od;
RETURN(M);
end:
R := DividesRelation(1,2,3,6);
MinimalElements(R, 1,2,3,6);
MinimalElements(R, 2,3,6);
</pre>
Note-se que, pela dualidade, obtemos - quase de graça - uma forma muito simples implementação de elementos máximos (''MaximalElements'').
<pre>
MaximalElements := proc(R::po, S::set)
MinimalElements(DualRelation(R), S);
end:
MaximalElements(R, 1,2,3,6);
MaximalElements(R, 1,2,3);
</pre>
Em seguida, vamos construir um procedimento para calcular os elementos mínimos de um conjunto no que diz respeito a uma determinada ordem parcial, se ele existir. Nosso procedimento irá retornar o valor NULL no caso de o conjunto que tenha nenhum limite mínimo superior. Vamos realizar em várias etapas. Para fazer isso, primeiro escrevemos um procedimento que irá calcular o conjunto de todos os limites superiores de um subconjunto de um conjunto parcialmente ordenado. Este procedimento, por sua vez, se baseia na sequência de utilidade para determinar se um determinado elemento é um limite superior para um conjunto.
<pre>
IsUpperBound := proc(R::po, S::set, u::anything)
local s; # index into S
</pre>
verificação de sanidade:
<pre>
if not member(u, DomainRelation(R)) then
ERROR(`bad arguments`);
fi;
for s in S do
if not member([s, u], R) then
RETURN(false);
fi;
od;
RETURN(true);
end:
UpperBounds := proc(R::po, S::set)
local U, # set of upper bounds of S; returned
DomR, # domain of R
d; # index into DomR
DomR := DomainRelation(R);
</pre>
verificação de erros:
<pre>
if S minus DomR <> {} then
ERROR(`set must be contained in the domain of the relation`);
fi;
U := {};
for d in DomR do
if IsUpperBound(R, S, d) then
U := U union d;
fi;
od;
RETURN(U);
end:
</pre>
