Assoziativität einer Verknüpfung feststellen |
15.02.2022, 08:10 | durst | Auf diesen Beitrag antworten » |
Assoziativität einer Verknüpfung feststellen Es sei eine Verknüpfung auf einer endlichen (großen) n-elementigen Menge gegeben, z.B. durch Verknüpfungstafel. Gibt es einen effizienten Algorithmus, um die Assoziativität der Verknüpfung zu prüfen, ohne alle n^3 Kombinationen zu prüfen? Meine Ideen: Ich habe dazu noch keine Idee. Schön wäre eine Lösung die mit dem Aufwand n^2 auskommt, wie bei der Kommutativität. Also ein paar einfache Gedanken dazu hatte ich schon. Wenn es Elemente a (und c) gibt, mit a*x = a oder x*a = a oder a*x = c oder x*a = c für alle x, also eine Zeile oder eine Spalte in der Tabelle ist konstant oder gleich der Eingangszeile bzw. -spalte, dann kann ich mir für diese Elemente a die komplette Prüfung sparen. Das ist z.B. bei der normalen Multiplikation mit den Elementen 0 und 1 so. Das reduziert den Gesamtaufwand aber kaum, es bleibt bei O(n^3). Willkommen im Matheboard! Ich hab die beiden Beiträge zusammengefasst, damit es nicht so aussieht, als ob schon jemand antwortet. Viele Grüße Steffen |
|