Balanced and almost balanced group presentations from algorithmic viewpoint
| Název práce v češtině: | Balancované a téměř balancované prezentace grup z algoritmického pohledu |
|---|---|
| Název v anglickém jazyce: | Balanced and almost balanced group presentations from algorithmic viewpoint |
| Klíčová slova: | Prezentace grup, algoritmus, problém triviality, Andrews-Curtisova domněnka |
| Klíčová slova anglicky: | Group presentation, algorithm, triviality problem, Andrews-Curtis conjecture |
| Akademický rok vypsání: | 2017/2018 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | doc. RNDr. Martin Tancer, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 12.10.2017 |
| Datum zadání: | 16.10.2017 |
| Datum potvrzení stud. oddělením: | 23.10.2017 |
| Datum a čas obhajoby: | 18.09.2018 09:00 |
| Datum odevzdání elektronické podoby: | 19.07.2018 |
| Datum odevzdání tištěné podoby: | 20.07.2018 |
| Datum proběhlé obhajoby: | 18.09.2018 |
| Oponenti: | RNDr. Pavel Paták, Ph.D. |
| Zásady pro vypracování |
| V této práci se její řešitel zaměří na studium prezentací grup z algoritmického úhlu pohledu. Především půjde o balancované prezentace (stejný počet symbolů a relací) nebo skoro balancované prezentace (počet relací omezený nějakou funkcí počtu symbolů). Konkrétní dílčí úkoly jsou:
- Nastudovat literaturu a sepsat pojednání o tématu. - Zaměřit se na "výpočetní sílu" problému triviality grupy zadané pomocí balancované či skoro balancované prezentace. Zejména s ohledem na to, jaké výpočetní problémy lze pomocí problému triviality simulovat. Dálší možné rozšiřující úkoly například jsou: - Zaměřit se na souvislost s Andrews-Curtisovou domněnkou, např. na studium konkrétních známych potenciálních protipříkladů. - Zaměřit se na topologické aspekty balancovaných či skoro balancovaných prezentací, tj. popsat topologické souvislosti a studovat, jaké topologické vlastnosti mohou mít vliv na výpočetní sílu. - Naprogramovat heuristické nástroje pro potvrzení triviality/netriviality. |
| Seznam odborné literatury |
| M. R. Bridson. The complexity of balanced presentations and the Andrews-Curtis conjecture, preprint 2015. https://arxiv.org/abs/1504.04187
Miasnikov, Alexei D., and Alexei G. Myasnikov. Balanced presentations of the trivial group on two generators and the Andrews-Curtis conjecture. Groups and Computation III (W. Kantor and A. Seress, eds.), de Gruyter, Berlin (2001): 257-263. Další literatura bude doplněna dle postupu práce. |