Hardprob/Minimum Permutation Group Base — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w)_(\w)</m> на <em>\1<sub>\2</sub></em>) |
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE <m>(\w)_(\w),\s*…\s*,\s*(\w)_(\w)<\/m> на <em>\1<sub>\2</sub>, …, \3<sub>\4</sub></em>) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
* Группа <em>G</em> перестановок из <em>n</em> символов. | * Группа <em>G</em> перестановок из <em>n</em> символов. | ||
| − | * Найти базу для <em>G</em>, т.е. последовательность точек < | + | * Найти базу для <em>G</em>, т.е. последовательность точек <em>b<sub>1</sub>, …, b<sub>k</sub></em>, такой, что единственный элемент в <em>G</em> фиксирующий все эти <em>b<sub>i</sub></em> это идентичное преобразование. |
* Минимизировать размер базы, т.е. <em>k</em>. | * Минимизировать размер базы, т.е. <em>k</em>. | ||
Текущая версия на 22:54, 17 апреля 2023
- Группа G перестановок из n символов.
- Найти базу для G, т.е. последовательность точек b1, …, bk, такой, что единственный элемент в G фиксирующий все эти bi это идентичное преобразование.
- Минимизировать размер базы, т.е. k.
Задача в лаб22 (рид-онли просмотр)