Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Абстрактна алгебра, теорія груп, скінченні групи.
Протягом останніх 2-х років мої дослідження загнали мене в гроб теорію груп (область, в якій я нічорта не тямлю). В мене багато питань і вони між собою пов'язані, тому я буду всіх їх скидувати в цю тему і сподіватися, що хтось на них відповість.
Перше питання :
Є така штука, називається комутатор. Для чого він існує ? Де він використовується ?
Щойно осилив такі поняття як ізоморфізм і автоморфізм груп. Тепер ізоморфність груп для мене інтуїтивно зрозуміла.
Комутатори поки залишаються за межами мого розуміння.
Я перечитав кількадесят статтей, в яких використовувалися комутатори, і дійшов до висновку, що вони використовуються тільки для того, щоб встановити чи є група комутативною. Ні для чого більше.
Група є комутативною (тобто для будь-яких елементів групи a, b виконується умова +a+b == +b+a) тоді і тільки тоді, коли всі комутатори дорівнюють елементу ідентичності (+a+b-a-b == 0).
Це те, що було очевидним з самого початку. Нічого нового я не дізнався і мене це бісить.
В них є ще багато цікавих властивостей, але по факту, ні для чого більше комутатори нафіг не потрібні. Таке враження, що це поняття було введне для того щоб хтось захистив дисертацію.
І, так, я буду використовувати не загально прийняті позначення (g-1h-1gh = e), а свої (+a+b-a-b == 0), бо вважаю, що вони краще адаптовані для математика-програміста.
Щоб зайвий раз не ганяти форумчан по інтирнетах, ще разок пройдусь по основах.
Означення групи та властивості елементів групи :
Не порожню множину елементів 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. Але воно тягне поняття генеруючої множини.
+1 питання :
Задано множину елементів S = { a0, a1, a2, ... , an-1 } (|S| == n) і елемент x. Існує така група G, що містить всі елементи множини S і містить x, тобто для всіх цих елементів визначена групова операція + (не путати з операцією додавання чисел). Потрібно розробити алгоритм, який дозволить дізнатися : Чи можна з елементів множини S згенерувати елемент x ?
Я, звичайно, можу зробити повний перебір по всіх можливих комбінаціях елементів множини S і дещо подібне (але для групи) я вже зробив, але проблема в тому, що такий алгоритм працює надто довго. Наприклад для групи перестановок (довжиною до 8 чисел) при деяких параметрах програма крутиться більше ніж 5 хвилин (для мене це неприйнятний результат).
Чи існує якийсь елегантний алгоритм, який би давав результат за мілісекунди ?
Чи можна згенерувати елемент x ?
Спроба розробити такий алгоритм привела мене до висновку, що ця задача трохи складніша ніж згенерувати групу з множини S, тому спочатку мушу знайти оптимальне рішення для останньої.
Але тут вилізла ще одна проблема : Як зберігати групу ?
Генерувати всі елементи групи і додавати їх у список (як я роблю це на даний момент) взагалі не варіант, бо навіть множина із 2-х елементів здатна згенерувати групу як завгодно великих розмірів (йдеться про кількість елементів ~10^13, де кожен елемент займає по 8 байт).
Я пошукав, як інші розробники зберігають групи, і вони використовують генеруючі множини. Але у відкритому доступі я не знайшов як вони вирішили проблему перевірки належності заданого елемента заданій групі. Якщо ви знайдете якісь сурси по цій темі, то дайте посилання.
лишається NP-повною.
Кажете, отримувати результати за мілісекунди я не зможу ? 
koala написав:лишається NP-повною.
Кажете, отримувати результати за мілісекунди я не зможу ?
Немає нічого неможливого, не здавайтеся і у вас все вийде!
koala написав:лишається NP-повною.
Кажете, отримувати результати за мілісекунди я не зможу ?
Не переживайте так, це ненадовго, квантові комп'ютери розвиваються 
Поки квантові компютери розвиваються я вирішив не стояти на місці і розвивати проект в тих напрямках, в яких це ще можливо.
На даний момент, я можу зберігати великі скінченні групи, в яких генеруюча множина містить 1 або 2 елементи.
У випадку з одним елементом це буде циклічна група (a*N == 0).
З двома елементами трохи складніше. Першим ділом перевіряємо чи 2 елементи є комутативними (чи виконується a+b == b+a).
Якщо вони комутативні, то граф кейлі для такої групи можна зобразити як дискретну 2-вимірну поверхню тора в 3-вимірному просторі.
Якщо вони не комутативні, то граф кейлі буде як дискретна 3-вимірна поверхня аналога тора в 4-вимірному просторі.
До груп з 2ма генеруючими елементами належать :
Дигедральні (не комутативні) (r*N == 0) & (f*2 == 0) & (f+r+f+r == 0)
Дициклічні (не комутативні) (r*N == f*2) & (f*4 == 0) & (f+r-f+r == 0)
ZM x ZN (комутативні) (a+b == b+a) & (a*M == 0) & (b*N == 0)
Тетрахедральна (не комутативна)
Октахедральна (не комутативна)
і на диво багато інших.
Стосовно багатовимірних просторів, я думаю там все не так страшно, це лише топологія. Можливо вдасться звести її до якогось простого набору правил.
Знайшов список графів для груп розміром < 32 елементів.
Графи для деяких груп таки довелось створити самостійно.
3*a == 0 &
4*b == 0 &
2*(a + b) == 0 &
4*(a - b) == 0 &
3*(a + 2*b) == 0
24 елементів групи, 2 елементи генеруючої множини.
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
48 елементів групи, 3 елементи генеруючої множини.
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
48 елементів групи, 2 елементи генеруючої множини.
От відразу треба було з картинок починати, бо нецікаво читати було!
От відразу треба було з картинок починати, бо нецікаво читати було!
Абсолютно згідний. Мені і самому без картинок було не цікаво. Але створення таких картинок відберає багато часу.
Шкода що в 2019му немає зручних інструментів для створення векторної графіки і немає підтримки 3D в SVG 
здається, саме цю всю високу, і ще вищу, математику, постійно обговорюють в haskell чатах в телеграмі
я там розумію менше 20% слів
цікаво, і абсолютно незрозуміло
imho на хаскелі такі приколи виглядають природньо,
їх можна, навіть не розуміючи, довго роздивлятись, наче красиву мозаїку з незрозумілих іерогліфів
а такий код на джаві чи сішарпі мені виглядає наче кадр з фільму жахів 
відкрив, одним оком обережно кліпнув, закрив
про ілюстрації -- можна ж зробити простенький конструктор таких схем, на канвасі
(окремі "запчастини" для такого зустрічав)
якщо потрібно -- можу посидіти, все-одно маю бажання добряче над канвасом посидіти
на хаскелі такі приколи виглядають природньо
За часів заснування проекту мені довелось вибирати між кількома мовами (C++, Java, C#, Python, PHP, Haskell).
Haskell вилетів зі списку першим, через відсутність ООП, і складність підтримки проекту.
Python і PHP відкинув через відсутність строгої типізації. В останніх версіях цих мов її намагались "акуратно ввести", але це не привело їх до потрібного мені результату.
Залишились C++, Java, C#. З C# я мав найбільше досвіду, тому вибрав його. Сподіваюсь дожити до часу, коли проект буде готовий, і тоді зможу переписати його на Java.
а такий код на джаві чи сішарпі мені виглядає наче кадр з фільму жахів
Поки нема документації по коду - так, це жах.
про ілюстрації -- можна ж зробити простенький конструктор таких схем, на канвасі
(окремі "запчастини" для такого зустрічав)
якщо потрібно -- можу посидіти, все-одно маю бажання добряче над канвасом посидіти
Не робіть, не повторюйте моїх помилок. Я вже наступив на ці граблі, тільки час марно потратив.
Замість "простенького конструктора" використовую Inkscape, але він "пише не охайно", після нього доводиться повністю переписувати.
пишіть на js, для строгої типізації можна було б typescript накатити, я вам кажу, круто було б.
За часів заснування проекту мені довелось вибирати між кількома мовами (C++, Java, C#, Python, PHP, Haskell).
Haskell вилетів зі списку першим, через відсутність ООП, і складність підтримки проекту.Поки нема документації по коду - так, це жах.
Не робіть, не повторюйте моїх помилок. Я вже наступив на ці граблі, тільки час марно потратив.
Замість "простенького конструктора" використовую Inkscape, але він "пише не охайно", після нього доводиться повністю переписувати.
не розумію, в чім там складність підтримки
не розумію, про які саме корисні потрібні властивості ООП, відсутні в haskell, йде мова
(мб тому, що я ще не повністю вивчив хаскель, "не осилив" ООП, та не розумію, чому так багато людей навколо так захоплено видихає "ООП, ООП")
та ні, я скоріше про сам код, організацію коду та синтаксис
(мої особисті заморочки по темі "подобається/не подобається", не звертайте уваги)
чому граблі та час марно потратив?
пишіть на js, для строгої типізації можна було б typescript накатити, я вам кажу, круто було б.
прошу пробачення за оффтоп, а у чім перевага js над haskell чи C# (в контексті цієї теми)?
допустимо, в haskell багато де ноги з математики ростуть, C# -- приємний звичний інструмент для ТС, а js ?
