109
edits
Changes
Jump to navigation
Jump to search
no edit summary
AllRelations(1,2);
</pre>
2- Determine quantas relações transitivo existem em um conjunto com ''n'' elementos para todos os inteiros positivos ''n'' com ''n'' ≤ 7.
'''Solução:'''
Vamos construir cada possíveis <math>N x N</math> da matriz zero-um, usando um algoritmo semelhante ao de contagem binária. O pseudocódigo é:
1- Para cada valor de 1 até <math>2^{(n ^{2})}</math>, criamos uma lista que é a representação de base 2 desse inteiro.
2- Nós criamos uma matriz M com elementos sendo a lista de valores. Estes são todos os possíveis <math>n^{2}</math> de matriz zero-um (o leitor pode provar esta afirmação).
3- Avaliar o fechamento transitivo de cada uma das matrizes que criamos, e retornar o conjunto de fechos transitivos dessas matrizes.
A implementação é como se segue:
<pre>
FindTransitive := proc(S::set)
local i, j, T, P;
P := {};
for i from 0 to 2^(nops(S)^2)-1 do
T := convert(i, base, 2);
while nops(T) < nops(S)^2 do
T := [op(T), 0];
od;
P := P union matrix(nops(S), nops(S), T);
od;
P;
end:
</pre>
Mais uma vez, utilizamos o nosso processo em valores relativamente pequenos (devido ao comprimento da saída), e deixamos a exploração adicional para o leitor.
<pre>
P := FindTransitive(1,2):
Q := {}:
for i from 1 to nops(P) do
Q := Q union Warshall(P[i]):
od:
Q;
</pre>
3- Encontre o fecho transitivo de uma relação em um conjunto com pelo menos 200 elementos.
'''Solução:'''
Vamos gerar aleatoriamente uma matriz zero-um com dimensão 10x10, e em seguida, aplicar o algoritmo de \textbf{Warshall} para deduzir o fecho transitivo matriz.
Para gerar uma matriz zero-um aleatória, usamos a função '''randmatrix''' do pacote '''linalg''', e fornecer seu terceiro argumento, opcional com um procedimento que gera uma sequência aleatória 0's (zero) e 1's (uns). Em seguida, aplicamos o algoritmo de '''Warshall''' a esta matriz aleatória, obtendo o resultado. Aqui, para economizar espaço, podemos aplicar este procedimento para uma matriz de 10x10 como um exemplo.
<pre>
Q := randmatrix(10, 10, entries=rand(2));
Warshall(Q);
</pre>
== Referências ==
[http://www.mhhe.com/math/advmath/rosen/r5/student/ch07/maple.html Maple: Chapter 7. Relations]
