Makroproblem 9: Link zur Lösung pdf MakroWorkspace 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 Goel's 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-Makrosprache 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 Makrosprache übersetzt, was einen Anfang für den oben erwähnten Vergleich liefert.