Light's associativity test
http://dbpedia.org/resource/Light's_associativity_test an entity of type: WikicatBinaryOperations
Lightův test asociativity je algoritmus z abstraktní algebry. Umožňuje určit, zda je binární operace nad konečnou množinou, jež byla zadána pomocí Cayleyho multiplikativní tabulky, asociativní. Tím lze rozlišit pologrupy, kde operace asociativní je, od grupoidů, jejichž operace asociativní nejsou. Test je pojmenován po , jenž jej autorům publikace The Algebraic Theory of Semigroups (Algebraická teorie pologrup) představil v roce 1949.
rdf:langString
In mathematics, Light's associativity test is a procedure invented by F. W. Light for testing whether a binary operation defined in a finite set by a Cayley multiplication table is associative. The naive procedure for verification of the associativity of a binary operation specified by a Cayley table, which compares the two products that can be formed from each triple of elements, is cumbersome. Light's associativity test simplifies the task in some instances (although it does not improve the worst-case runtime of the naive algorithm, namely for sets of size ).
rdf:langString
Test łączności Lighta – procedura odkryta przez F.W. Lighta dla testowania, czy działanie binarne określone na zbiorze skończonym przez tablicę Cayleya jest łączne. Bezpośrednie sprawdzenie łączności działania binarnego za pomocą tablicy Cayleya jest żmudne i nieporęczne. Test Lighta bardzo upraszcza zadanie.
rdf:langString
Тест ассоциативности — проверка бинарной операции на ассоциативность. Наивная процедура проверки, заключающаяся в переборе всех возможных троек аргументов операции, требует времени, где — размер множества, над которым определена операция. Ранние тесты ассоциативности не давали асимптотических улучшений по сравнению с наивным алгоритмом, однако позволяли улучшить время работы в некоторых частных случаях. Например, Роберт Тарьян в 1972 году обнаружил, что предложенный в 1949 году тест Лайта позволяет выполнить проверку за , если исследуемая бинарная операция обратима (задаёт квазигруппу). Первый вероятностный тест, улучшающий время работы с до , был предложен в 1996 году Шридхаром Раджагопаланом и . В 2015 году был предложен квантовый алгоритм, проверяющий операцию на ассоциативность за в
rdf:langString
rdf:langString
Lightův test asociativity
rdf:langString
Light's associativity test
rdf:langString
Test łączności Lighta
rdf:langString
Тест ассоциативности
xsd:integer
22783408
xsd:integer
1092919135
rdf:langString
Lightův test asociativity je algoritmus z abstraktní algebry. Umožňuje určit, zda je binární operace nad konečnou množinou, jež byla zadána pomocí Cayleyho multiplikativní tabulky, asociativní. Tím lze rozlišit pologrupy, kde operace asociativní je, od grupoidů, jejichž operace asociativní nejsou. Test je pojmenován po , jenž jej autorům publikace The Algebraic Theory of Semigroups (Algebraická teorie pologrup) představil v roce 1949.
rdf:langString
In mathematics, Light's associativity test is a procedure invented by F. W. Light for testing whether a binary operation defined in a finite set by a Cayley multiplication table is associative. The naive procedure for verification of the associativity of a binary operation specified by a Cayley table, which compares the two products that can be formed from each triple of elements, is cumbersome. Light's associativity test simplifies the task in some instances (although it does not improve the worst-case runtime of the naive algorithm, namely for sets of size ).
rdf:langString
Test łączności Lighta – procedura odkryta przez F.W. Lighta dla testowania, czy działanie binarne określone na zbiorze skończonym przez tablicę Cayleya jest łączne. Bezpośrednie sprawdzenie łączności działania binarnego za pomocą tablicy Cayleya jest żmudne i nieporęczne. Test Lighta bardzo upraszcza zadanie.
rdf:langString
Тест ассоциативности — проверка бинарной операции на ассоциативность. Наивная процедура проверки, заключающаяся в переборе всех возможных троек аргументов операции, требует времени, где — размер множества, над которым определена операция. Ранние тесты ассоциативности не давали асимптотических улучшений по сравнению с наивным алгоритмом, однако позволяли улучшить время работы в некоторых частных случаях. Например, Роберт Тарьян в 1972 году обнаружил, что предложенный в 1949 году тест Лайта позволяет выполнить проверку за , если исследуемая бинарная операция обратима (задаёт квазигруппу). Первый вероятностный тест, улучшающий время работы с до , был предложен в 1996 году Шридхаром Раджагопаланом и . В 2015 году был предложен квантовый алгоритм, проверяющий операцию на ассоциативность за время , что является улучшением по сравнению с поиском Гровера, работающим за .
xsd:nonNegativeInteger
19783