Tutorial: Problems with Macros pdf
Makroproblem 9:
Subdirekte Zerlegung von Verbänden
Die ursprüngliche Idee
Nach dem Satz von Birkhoff (Satz B.50) ist bekannt, dass sich jede Algebra subdirekt in subdirekt irreduzible Faktoren zerlegen lässt; (siehe Definition B.37 (Subdirektes Produkt) und die Sätze B.36 und B.37 (Irreduzibles subdirektes Produkt 1 und 2)). Das verspricht uns leider nicht, diese Zerlegung auch zu kennen!
Jiri Demel hat in seinem Artikel "Fast Algorithms for Finding a Subdirekt Decomposition and Interesting Congruences of Finite Algebras" [Dem82] einen Algorithmus veröffentlicht, welcher zu einer beliebigen Algebra eine subdirekte Zerlegung in subdirekt irreduzible Faktoren berechnet. In einer Subroutine werden unter anderem Kongruenzklassen vereinigt und dann zur nächst grösseren Kongruenzklasse aufgeblasen, was je nach Algebra ziemlich viel Zeit beanspruchen kann (für jedes Element muss berechnet werden, ob es auch zur neuen aufgeblasenen Kongruenz gehört oder nicht).
In Sabine Goels Diplomarbeit Algorithmen zur subdirekten Zerlegung von Verbänden [Goe02] wird der Algorithmus von Demel für Verbände (als Algebren mit zusätzlichen Eigenschaften zu verstehen) optimiert. Jede Kongruenzklasse eines Verbandes ist ein Intervall (siehe auch Satz B.34). Die Vereinigung von zwei Intervallen ist viel weniger aufwändig zu berechnen als die Vereinigung von zwei Kongruenzen einer beliebigen Algebra.
Es stellt sich die Frage, ob diese Optimierung sich tatsächlich auf die Rechenzeit für Zerlegungen auswirkt.
Mit Hilfe von theoretischen Überlegungen konnte nicht nachgewiesen werden, dass der abgeänderte Algorithmus wirklich eine kleinere Zeitkomplexität aufweist - was noch keine praktische Schlüsse ziehen lässt, da die Zeitkomplexitätsangaben nur obere Schranken darstellen. Um den "frisierten" Algorithmus aus [Goe02] mit dem ursprünglichen aus [Dem82] zu vergleichen, könnten beide Algorithmen in der AWB-Macrosprache implementiert werden, um für ausgewählte Verbände die Berechnungszeiten zu vergleichen.
In diesem letzten Makroproblem wird ein Teil des "frisierten" Algorithmus von Pseudocode in die Macrosprache übersetzt, was einen Anfang für den oben erwähnten Vergleich liefert.
Lösung: Download MakroWorkspace 9
Vom Pseudocode zur Macrosprache
Der Pseudocode der beiden Hilfsfunktionen von SafeCongInt(v,w) sieht wie folgt aus ([Goe02] entnommen).
Zur Notation: I ist eine Menge von Intervallen, I_i ein Intervall aus I mit den Grenzen a_I_i und b_I_i, I_x ein Intervall welches x enthält.
Zur Funktion unionInt(I_j, I_k, II, I_neu): Gegeben ein Verband L. Sei I eine Menge von Intervallen auf L, die L überdecken, Ij, Ik ∈ I. Dann liefert der Algorithmus unionInt(Ij, Ik, I, Ineu) die kleinste Intervallmenge I' auf L mit I' ⊇ I, die L überdeckt und ein Intervall Ineu enthält, das Ij und Ik enthält. Ineu ist leer, falls für die zwei Elemente v und w die Vereinigung impliziert, dass v und w in demselben Intervall liegen. In diesem Fall ist I' = I.
Zur Funktion findInt(v, II): Sei v ∈ L, I Intervallpartition auf L (I kann eine Kongruenz sein - muss aber nicht). Dann liefert findInt(v,I) das Intervall Ii ∈ I mit v ∈ Ii.
unionInt(I_j, I_k, II, I_neu)
JJ := II
a_I_j := a_I_j meet a_I_k
b_I_j := b_I_j join b_I_k
if (w in I_j and v in I_j) then
I_neu := leeres Intervall
RETURN (JJ, I_neu)
else
I_neu := I_j
i := 1
// Kontrolle, ob I_j mit allen Intervallen aus II disjunkt ist
while (I in der Liste II) do
// I_i ist das neue Intervall
if (I_i = I_j) then
i := i + 1
if (I_i Schnitt I_j) = (leere Menge) then
i := i + 1
// (I_i = I_j) ausgeschlossen, I_i aus II entfernen
if (I_i in I_j enthalten) then
p := Anzahl Intervalle von II
II := II ohne I_i
// stelle alle Intervalle, die hinter
// dem Intervall I_i sind zurück
from k := i + 1 to k = p
I_(k-1) := I_k
end // from
i := i + 1
else
I_neu := leeres Intervall
unionInt(I_i, I_j, II, I_neu)
end // while
RETURN (II, I_neu)
findInt(v, II)
p := Anzahl Intervalle von II
i := 1
// prüfe, ob v im Intervall I_i = [a_I_i, b_I_i] ist
while (i <= p) do
x := (v meet a_I_i)
y := (v join b_I_i)
if (x = a_I_i and y = b_I_i) then
RETURN [a_I_i, b_I_i]
else
i := i + 1
end // while
Nun besteht die Aufgabe darin, diesen Pseudocode in die Macrosprache der AWB zu übersetzen, damit er dort ausführbar wird. Pseudocode kann meistens nicht eins zu eins übernommen werden, da nicht alle Funktionen, die im Pseudocode klar erscheinen, auch als AWB-Makrobefehle vorhanden sind. Hier ist zum Beispiel einleuchtend, dass die Kongruenzen eines Verbandes als Intervalle dargestellt werden können. Die AWB unterstützt dies aber nicht a priori. Zudem sind Tests wie if (I_i in I_j enthalten) then für die Macrosprache nicht selbstverständlich. Im Folgenden ist eine mögliche Umsetzung in die AWB-Sprache gegeben.
% Einige Hilfsfunktionen werden definiert. %
% eq definieren %
eq := lambda(a,b) and(leq(a,b),geq(a,b)); endlambda;
% setmax berechnet Maximum für die übergebene Menge. %
setmax := lambda(set)
if not(>(card(set), 0)) then
max := emptyset;
else
max := item(set,0);
for n in card(set) do
if >(item(set,n), max) then
max := item(set,n);
else noop; endif;
endfor;
endif;
max;
endlambda;
% setmin berechnet Minimum für die übergebene Menge. %
setmin := lambda(set)
if not(>(card(set), 0)) then
min := emptyset;
else
min := item(set,0);
for n in card(set) do
if <(item(set,n), min) then
min := item(set,n);
else noop; endif;
endfor;
endif;
min;
endlambda;
% Schnitt zweier Intervalle I_1 und I_2. %
intMeet := lambda(I_1, I_2)
a_I_1 := item(I_1, 0);
b_I_1 := item(I_1, 1);
a_I_2 := item(I_2, 0);
b_I_2 := item(I_2, 1);
b1 := and(leq(a_I_1, a_I_2), leq(a_I_2, b_I_1));
b2 := and(leq(a_I_2, a_I_1), leq(a_I_1, b_I_2));
% wenn sich die Intervalle schneiden %
if or(b1, b2) then
a_I_Meet := sup(a_I_1, a_I_2);
b_I_Meet := inf(b_I_1, b_I_2);
I_Meet := {a_I_Meet, b_I_Meet};
else
I_Meet := emptyset;
endif;
endlambda;
% true, falls v im Intervall I liegt. %
isIn := lambda(v, I)
a_I := item(I, 0);
b_I := item(I, 1);
and(leq(a_I, v), leq(v, b_I));
endlambda;
% true, falls das Intervall I im Intervall J enthalten ist. %
intInInt := lambda(I, J)
a_I := item(I,0);
b_I := item(I,1);
a_J := item(J,0);
b_J := item(J,1);
and(leq(a_J, a_I), leq(b_I, b_J));
endlambda;
% Kongruenzen in spezielles Format bringen. %
% Benutzer wählt den Verband aus. %
L := prepare(listprompt("Wähle einen Verband"', structures));
% Benutzer wählt die zwei Elemente v und w aus. %
el_v := listprompt("Erstes Element"', L);
el_w := listprompt("Zweites Element"', L);
% Kongruenzen von L in gewünschtes Intervall-Format bringen. %
SetConL := congruenceset(L, [presmeet,presjoin]);
ConL := emptyset;
% Durch die Kongruenzen rattern. %
for j in card(SetConL) do
% elementList := asaset(L); %
% Intervall-Liste erstellen. %
IntList := emptyset;
% Durch die Kongruenzklassen der j-ten Kongruenz rattern. %
% In jedem Durchlauf entsteht ein Intervall. %
for k in card(item(SetConL,j)) do
% tempKong speichert die aktuelle Kongruenzklasse. %
tempKong := item(SetConL,j);
tempInt := emptyset;
tempInt := setunion({tempInt, {item(elementList,0)}});
elementList := removefromlist(elementList,0);
e0 := item(tempInt,0);
% Die merkenListe speichert Positionen der elementList, %
% damit diese später gelöscht werden können. %
merkenListe := emptyset;
% Welche Elemente sind unter tempKong zu e0 kongruent? %
for m in card(elementList) do
e1 := item(elementList,m);
if tempKong(e0,e1) then
% Füge das Element e1 dem Intervall hinzu. %
tempInt := setunion({tempInt, {e1}});
% Elemente, die nachher gelöscht werden müssen... %
merkenListe := setunion({merkenListe, {m}});
else noop; endif;
endfor;
% Elemente in der merkenListe aus der elementList löschen. %
for n in card(merkenListe) do
index := -(item(merkenListe,n), n);
elementList := removeitem(elementList, index);
endfor;
% tempInt in die Liste der berechneten Intervalle stecken. %
IntList := setunion({IntList, {tempInt}});
endfor;
% Intervalle haben jetzt die gewünschte Form: %
% ConL = {C0,C1,...,Cn} %
% C0 = {I_1,I_2,...,I_m}, C1 = {I_1,I_2,...,I_s}, ... %
% I_1 = [a_I_1, b_I_1], I_2 = [a_I_2, b_I_2], ... %
konklassen := emptyset;
for s in card(IntList) do
intervall := emptyset;
% Intervallanfang und -ende speichern. %
additem(intervall, setmin(item(IntList,s)));
additem(intervall, setmax(item(IntList,s)));
% Definiertes Intervall zur Kongruenz hinzufügen. %
konklassen := setunion({konklassen, {intervall}});
endfor;
% Eben konstruierte Kongruenzklasse zu ConL hinzufügen. %
ConL := setunion({ConL, {konklassen}});
endfor;
% ConL ausgeben. %
writeln("- ConL (eine Menge von Mengen von Intervallen):"');
writeln(ConL); writeln(" "');
% Die Funktion findInt wird definitert. %
findInt := lambda(v, I)
% Sei p die Anzahl Intervalle in I: %
p := card(I);
ii := 0;
stop := false;
while and(leq(ii,p),not(stop)) do
% pr¸fe, ob v im Intervall I_i = [a_I_i, b_I_i] ist %
% Intervallgrenzen bestimmen. %
I_i := item(I,ii);
a_I_i := item(I_i,0);
b_I_i := item(I_i,1);
x := setmin({v, a_I_i});
y := setmax({v, b_I_i});
if and(eq(x, a_I_i), eq(y, b_I_i)) then
stop := true;
else
ii := +(ii, 1);
endif;
endwhile;mbox{}
[a_I_i, b_I_i];
endlambda;
% Testen von findInt. %
ko := listprompt("Wähle eine Kongruenz"',ConL);
resultat := findInt(el_v, ko);
write("- findInt hat die Kongruenzklasse gefunden, "');
write("welche unter der gewählten Kongruenz "');
write("("'); write(ko); write(") das erstgewählte Element ("');
write(el_v); write(") enthält: "'); writeln(resultat);
% Die Funktion unionInt wird definiert. %
unionInt := lambda(I_j, I_k, II)
a_I_j := item(I_j, 0);
b_I_j := item(I_j, 1);
a_I_k := item(I_k, 0);
b_I_k := item(I_k, 1);
a_I_j := inf(a_I_j, a_I_k);
b_I_j := sup(b_I_j, b_I_k);
I_j := {a_I_j, b_I_j};
if (and(isIn(el_w, I_j), isIn(el_v, I_j))) then
I_neu := emptyset;
else
I_neu := I_j;
% Kontrolle, ob I_j mit allen I_i aus II disjunkt ist. %
i := 0;
while leq(+(i,1),card(II)) do
I_i := item(II,i);
% Wenn I_i und I_j gleich oder disjunkt sind: nichts tun %
if or(equal(I_i, I_j), eq(card(intMeet(I_i,I_j)),0)) then
i := +(i,1);
else
% (I_i = I_j) ausgeschlossen, I_i aus II entfernen %
if intInInt(I_i, I_j) then
removeitem(II, indexof(II,I_i));
i := +(i,1);
else
resui := unionInt(I_i, I_j, II);
I_neu := item(resui,0);
II := item(resui,1);
endif;
endif;
endwhile;
endif;
{I_neu, II};
endlambda;
% Testen von unionInt. %
writeln(" "'); writeln("- unionInt wurde definiert."');
I55 := item(item(ConL,7),4);
I23 := item(item(ConL,5),1);
I35 := item(item(ConL,2),1);
I11 := item(item(ConL,7),0);
I25 := item(item(ConL,4),1);
II := {I35, I11, I25};
write("Die Intervallmenge II: "'); writeln(II);
write("Das Intervall I_j: "'); writeln(I55);
write("Das Intervall I_k: "'); writeln(I23);
res := unionInt(I55,I23,II);
writeln("unionInt liefert das Intervall "'); write(item(res,0));
write(" und die neue Intervallmenge "'); writeln(item(res,1));
Wir testen den Makrocode mit dem fünfelementigen Verband L, der in Abbildung 4.9.1 zu sehen ist. Wenn wir das Makro ausführen, werden wir zweimal aufgefordert, ein Element zu wählen. Wir entscheiden uns für X1 und X4. Ferner wählen wir die Kongruenz {{X1, X4}, {X3, X5}}, wenn wir uns für eine von acht Kongruenzen von L entscheiden müssen.
Abbildung 4.9.1: Der Verband L
Mit obigen Voraussetzungen erhalten wir vom Makro folgende Ausgabe:
- ConL (eine Menge von Mengen von Intervallen):
{{{X1,X5}},{{X1,X3},{X4,X5}},{{X1,X4},{X3,X5}},{{X1,X2},
{X3,X3},{X4,X4},{X5,X5}},{{X1,X1},{X2,X5}},{{X1,X1},
{X2,X3},{X4,X5}},{{X1,X1},{X2,X4},{X3,X5}},{{X1,X1},
{X2,X2},{X3,X3},{X4,X4},{X5,X5}}}
- findInt hat die Kongruenzklasse (ein Intervall) gefunden,
welche unter der gewählten Kongruenz ({{X1,X4},{X3,X5}})
das erstgewählte Element (X1) enthält: {X1,X4}
- unionInt wurde definiert.
Die Intervallmenge II: {{X3,X5},{X1,X1},{X2,X5}}
Das Intervall I_j: {X5,X5}
Das Intervall I_k: {X2,X3}
unionInt liefert das Intervall {X2,X5}
und die neue Intervallmenge {{X1,X1},{X2,X5}}