1 Востаннє редагувалося leofun01 (05.08.2019 17:32:58)

Тема: Абстрактна алгебра, теорія груп, скінченні групи.

Протягом останніх 2-х років мої дослідження загнали мене в гроб теорію груп (область, в якій я нічорта не тямлю). В мене багато питань і вони між собою пов'язані, тому я буду всіх їх скидувати в цю тему і сподіватися, що хтось на них відповість.

Перше питання :
Є така штука, називається комутатор. Для чого він існує ? Де він використовується ?

Подякували: 221VOLT, ostap34PHP2

2

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Щойно осилив такі поняття як ізоморфізм і автоморфізм груп. Тепер ізоморфність груп для мене інтуїтивно зрозуміла.
Комутатори поки залишаються за межами мого розуміння.

Подякували: 221VOLT, ostap34PHP2

3

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Я перечитав кількадесят статтей, в яких використовувалися комутатори, і дійшов до висновку, що вони використовуються тільки для того, щоб встановити чи є група комутативною. Ні для чого більше.

Група є комутативною (тобто для будь-яких елементів групи a, b виконується умова +a+b == +b+a) тоді і тільки тоді, коли всі комутатори дорівнюють елементу ідентичності (+a+b-a-b == 0).

Це те, що було очевидним з самого початку. Нічого нового я не дізнався і мене це бісить.
В них є ще багато цікавих властивостей, але по факту, ні для чого більше комутатори нафіг не потрібні. Таке враження, що це поняття було введне для того щоб хтось захистив дисертацію.


І, так, я буду використовувати не загально прийняті позначення (g-1h-1gh = e), а свої (+a+b-a-b == 0), бо вважаю, що вони краще адаптовані для математика-програміста.

Подякували: 221VOLT, ostap34PHP2

4

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Щоб зайвий раз не ганяти форумчан по інтирнетах, ще разок пройдусь по основах.

Означення групи та властивості елементів групи :
Не порожню множину елементів G, для яких визначена бінарна операція +, яка є відображенням в G, називають групою відносно +, якщо виконуються умови :

  • E + : (a + b) == c, де c належить G, для всіх { a, b } з G (тобто операція + є відображенням в G)

  • E 0 : (a + 0) == a && a == (0 + a), де 0 належить G, для всіх a з G (тобто 0 - це елемент ідентичності)

  • (a + (b + c)) == ((a + b) + c), для всіх { a, b, с } з G (тобто операція + є асоціативна)

  • E -a : (a + -a) == 0 && (-a + a) == 0, для всіх a з G (тобто -a - це обернений елемент для a)

Елементи скінченних груп ще мають таку властивість яку всі називають "порядок" (не подобається мені їхнє означення, воно там не однозначне і не підлягає узагальненню), а я це називаю "довжина циклу".

Означення :
Довжина циклу елемента a - це кількість елементів циклічної групи, утвореної генеруючою множиною { a }.

Таке означення є однозначне і з нього зразу ясно, чому довжина циклу для елемента ідентичності == 1. Але воно тягне поняття генеруючої множини.

Подякували: 221VOLT, ostap34PHP2

5

Re: Абстрактна алгебра, теорія груп, скінченні групи.

+1 питання :

Задано множину елементів S = { a0, a1, a2, ... , an-1 } (|S| == n) і елемент x. Існує така група G, що містить всі елементи множини S і містить x, тобто для всіх цих елементів визначена групова операція + (не путати з операцією додавання чисел). Потрібно розробити алгоритм, який дозволить дізнатися : Чи можна з елементів множини S згенерувати елемент x ?

Я, звичайно, можу зробити повний перебір по всіх можливих комбінаціях елементів множини S і дещо подібне (але для групи) я вже зробив, але проблема в тому, що такий алгоритм працює надто довго. Наприклад для групи перестановок (довжиною до 8 чисел) при деяких параметрах програма крутиться більше ніж 5 хвилин (для мене це неприйнятний результат).

Чи існує якийсь елегантний алгоритм, який би давав результат за мілісекунди ?

Подякували: 221VOLT1

6

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Чи можна згенерувати елемент x ?

Спроба розробити такий алгоритм привела мене до висновку, що ця задача трохи складніша ніж згенерувати групу з множини S, тому спочатку мушу знайти оптимальне рішення для останньої.

Але тут вилізла ще одна проблема : Як зберігати групу ?
Генерувати всі елементи групи і додавати їх у список (як я роблю це на даний момент) взагалі не варіант, бо навіть множина із 2-х елементів здатна згенерувати групу як завгодно великих розмірів (йдеться про кількість елементів ~10^13, де кожен елемент займає по 8 байт).

Я пошукав, як інші розробники зберігають групи, і вони використовують генеруючі множини. Але у відкритому доступі я не знайшов як вони вирішили проблему перевірки належності заданого елемента заданій групі. Якщо ви знайдете якісь сурси по цій темі, то дайте посилання.

Подякували: 221VOLT1

7

Re: Абстрактна алгебра, теорія груп, скінченні групи.

А що якщо мої дослудження нікому не потрібні

Читаю про способи задання групи.

Моя реакція на все це ...

Нічого не зрозумів, але дуже цікаво.

Нічого не зрозумів але дуже цікаво

Подякували: 221VOLT, 0xDADA11C7, ostap34PHP3

8

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Задача факторизації довільного числа на множники все ще лишається NP-повною.

Подякували: leofun01, 221VOLT2

9

Re: Абстрактна алгебра, теорія груп, скінченні групи.

koala написав:

лишається NP-повною.

Кажете, отримувати результати за мілісекунди я не зможу ? :'(

Подякували: 221VOLT1

10

Re: Абстрактна алгебра, теорія груп, скінченні групи.

leofun01 написав:
koala написав:

лишається NP-повною.

Кажете, отримувати результати за мілісекунди я не зможу ? :'(

Немає нічого неможливого, не здавайтеся і у вас все вийде!

Подякували: leofun01, 221VOLT, ostap34PHP3

11

Re: Абстрактна алгебра, теорія груп, скінченні групи.

leofun01 написав:
koala написав:

лишається NP-повною.

Кажете, отримувати результати за мілісекунди я не зможу ? :'(

Не переживайте так, це ненадовго, квантові комп'ютери розвиваються :)

Подякували: leofun01, koala, 221VOLT, ostap34PHP4

12

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Поки квантові компютери розвиваються я вирішив не стояти на місці і розвивати проект в тих напрямках, в яких це ще можливо.
На даний момент, я можу зберігати великі скінченні групи, в яких генеруюча множина містить 1 або 2 елементи.

У випадку з одним елементом це буде циклічна група (a*N == 0).

З двома елементами трохи складніше. Першим ділом перевіряємо чи 2 елементи є комутативними (чи виконується a+b == b+a).
Якщо вони комутативні, то граф кейлі для такої групи можна зобразити як дискретну 2-вимірну поверхню тора в 3-вимірному просторі.
Якщо вони не комутативні, то граф кейлі буде як дискретна 3-вимірна поверхня аналога тора в 4-вимірному просторі.
До груп з 2ма генеруючими елементами належать :

і на диво багато інших.

Стосовно багатовимірних просторів, я думаю там все не так страшно, це лише топологія. Можливо вдасться звести її до якогось простого набору правил.

Подякували: Chemist-i, 221VOLT2

13

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Знайшов список графів для груп розміром < 32 елементів.
Графи для деяких груп таки довелось створити самостійно.


Повна тетрагедральна (2 => 24)

3*a == 0 &
4*b == 0 &
2*(a + b) == 0 &
4*(a - b) == 0 &
3*(a + 2*b) == 0

CayleyGraph_2e_3a_4b_440x440.svg
24 елементів групи, 2 елементи генеруючої множини.


Повна октагедральна (3 => 48)

2*f == 0 &
3*a == 0 &
4*b == 0 &
6*(f + a) == 0 &
f + a + f - a == 0 &
f + b + f - b == 0 &
2*(a + b) == 0 &
4*(a - b) == 0 &
4*(f + b) == 0 &
2*(f + a + b) == 0

CayleyGraph_3e_2f_3a_4b_440x440.svg
48 елементів групи, 3 елементи генеруючої множини.


Повна октагедральна (2 => 48)

6*a == 0 &
4*b == 0 &
4*(a + b) == 0 &
2*(a - b) == 0 &
2*(2*a + b) == 0 &
3*(2*a + 2*b) == 0

CayleyGraph_2e_6af_4b_440x440.svg
48 елементів групи, 2 елементи генеруючої множини.

14

Re: Абстрактна алгебра, теорія груп, скінченні групи.

От відразу треба було з картинок починати, бо нецікаво читати було!

Подякували: leofun01, dot, 221VOLT, ostap34PHP4

15

Re: Абстрактна алгебра, теорія груп, скінченні групи.

FakiNyan написав:

От відразу треба було з картинок починати, бо нецікаво читати було!

Абсолютно згідний. Мені і самому без картинок було не цікаво. Але створення таких картинок відберає багато часу.
Шкода що в 2019му немає зручних інструментів для створення векторної графіки і немає підтримки 3D в SVG :(

Подякували: 221VOLT, ostap34PHP2

16 Востаннє редагувалося 221VOLT (07.09.2019 12:06:31)

Re: Абстрактна алгебра, теорія груп, скінченні групи.

здається, саме цю всю високу, і ще вищу, математику, постійно обговорюють в haskell чатах в телеграмі :)
я там розумію менше 20% слів  :)
цікаво, і абсолютно незрозуміло

https://t.me/haskell_learn
https://t.me/haskellru

імхо на хаскелі такі приколи виглядають природньо,
їх можна, навіть не розуміючи, довго роздивлятись, наче красиву мозаїку з незрозумілих іерогліфів
а такий код на джаві чи сішарпі мені виглядає наче кадр з фільму жахів  *CRAZY* відкрив, одним оком обережно кліпнув, закрив

про ілюстрації -- можна ж зробити простенький конструктор таких схем, на канвасі
(окремі "запчастини" для такого зустрічав)
якщо потрібно -- можу посидіти, все-одно маю бажання добряче над канвасом посидіти

Подякували: leofun011

17

Re: Абстрактна алгебра, теорія груп, скінченні групи.

221VOLT написав:

на хаскелі такі приколи виглядають природньо

За часів заснування проекту мені довелось вибирати між кількома мовами (C++, Java, C#, Python, PHP, Haskell).
Haskell вилетів зі списку першим, через відсутність ООП, і складність підтримки проекту.
Python і PHP відкинув через відсутність строгої типізації. В останніх версіях цих мов її намагались "акуратно ввести", але це не привело їх до потрібного мені результату.
Залишились C++, Java, C#. З C# я мав найбільше досвіду, тому вибрав його. Сподіваюсь дожити до часу, коли проект буде готовий, і тоді зможу переписати його на Java.

221VOLT написав:

а такий код на джаві чи сішарпі мені виглядає наче кадр з фільму жахів  *CRAZY*

Поки нема документації по коду - так, це жах.

221VOLT написав:

про ілюстрації -- можна ж зробити простенький конструктор таких схем, на канвасі
(окремі "запчастини" для такого зустрічав)
якщо потрібно -- можу посидіти, все-одно маю бажання добряче над канвасом посидіти

Не робіть, не повторюйте моїх помилок. Я вже наступив на ці граблі, тільки час марно потратив.

Замість "простенького конструктора" використовую Inkscape, але він "пише не охайно", після нього доводиться повністю переписувати.

18

Re: Абстрактна алгебра, теорія груп, скінченні групи.

пишіть на js, для строгої типізації можна було б typescript накатити, я вам кажу, круто було б.

Подякували: leofun011

19 Востаннє редагувалося 221VOLT (07.09.2019 12:32:28)

Re: Абстрактна алгебра, теорія груп, скінченні групи.

leofun01 написав:

За часів заснування проекту мені довелось вибирати між кількома мовами (C++, Java, C#, Python, PHP, Haskell).
Haskell вилетів зі списку першим, через відсутність ООП, і складність підтримки проекту.



Поки нема документації по коду - так, це жах.



Не робіть, не повторюйте моїх помилок. Я вже наступив на ці граблі, тільки час марно потратив.

Замість "простенького конструктора" використовую Inkscape, але він "пише не охайно", після нього доводиться повністю переписувати.

не розумію, в чім там складність підтримки
не розумію, про які саме корисні потрібні властивості ООП, відсутні в haskell, йде мова
(мб тому, що я ще не повністю вивчив хаскель, "не осилив" ООП, та не розумію, чому так багато людей навколо так захоплено видихає "ООП, ООП")


та ні, я скоріше про сам код, організацію коду та синтаксис
(мої особисті заморочки по темі "подобається/не подобається", не звертайте уваги)


чому граблі та час марно потратив?

FakiNyan написав:

пишіть на js, для строгої типізації можна було б typescript накатити, я вам кажу, круто було б.

прошу пробачення за оффтоп, а у чім перевага js над haskell чи C# (в контексті цієї теми)?
допустимо, в haskell багато де ноги з математики ростуть, C# -- приємний звичний інструмент для ТС, а js ?

Подякували: FakiNyan, leofun012

20

Re: Абстрактна алгебра, теорія груп, скінченні групи.

ООП = АТД + успадкування + поліморфізм. АТД в Haskell ніби є (ага, робіть монади без них).
Що саме вам треба успадковувати і поліморфувати?

Подякували: leofun01, 221VOLT2