J013 AlgoMaNet

Fakulta informatiky
jaro 2023
Rozsah
0/0/1. 1 kr. Ukončení: z.
Vyučováno kontaktně
Vyučující
Prof. Dr. Pascal Schweitzer (přednášející), prof. RNDr. Daniel Kráľ, Ph.D., DSc. (zástupce)
Dr. Sophia Brenner (cvičící), prof. RNDr. Daniel Kráľ, Ph.D., DSc. (zástupce)
prof. RNDr. Daniel Kráľ, Ph.D., DSc. (pomocník)
Garance
prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
SOUHLAS
The student should be familiar with notions from abstract algebra, algorithm design, computational complexity and discrete mathematics at the level of an advanced undergraduate student.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
předmět má 12 mateřských oborů, zobrazit
Cíle předmětu
The aim of the course is to present the state of the art related to isomorphism testing algorithm in the setting of groups. When it comes to questions of polynomial-time solvability in computational group theory, the way we encode the groups in the computer is crucial. Groups can for example be represented explicitly by their multiplication tables, more compactly as permutation groups, or by so-called presentations. The course briefly discusses these differences but then focuses on permutation group algorithms, which often arise naturally when dealing with finite graphs.
Výstupy z učení
The student will get an understanding of the state of the art methods concerning group isomorphism. The student will be able to explain different ways of representing groups, their impact on algorithmic questions, and present efficient isomorphism algorithms for particular types of permutation groups.
Osnova
  • Groups are the mathematical objects that capture the symmetry of combinatorial objects. Algorithmic group theory investigates which computational tasks involving groups have efficient solutions. The goal is to develop theoretically and practically efficient algorithms. In contrast to graph theory, when it comes to questions of polynomial-time solvability in computational group theory, the way we encode the groups in the computer is crucial. Groups can for example be represented explicitly by their multiplication tables, more compactly as permutation groups, or by so-called presentations. The course briefly discusses these differences but then focuses on permutation group algorithms, which often arise naturally when dealing with finite graphs. For permutation groups, many non-trivial polynomial-time algorithms have been developed. We will discuss efficient algorithms for various tasks. Some are seemingly easy at first sight but need clever techniques. An example is the membership problem, which asks us to decide whether a given permutation is contained in a permutation group given by generators. The course will also hint at how algorithms for permutation groups are used to develop fast algorithms for the graph isomorphism problem. This is for example done in Luks's polynomial-time algorithm for isomorphism of bounded degree graphs and Babai's quasipolynomial-time algorithm.
Výukové metody
The course will be delivered as an intensive one week course in the period June 26-30 with lectures complemented by tutorial sessions.
Metody hodnocení
To pass the course, the student will have to prepare a short summary demonstrating their knowledge of the presented material acquired during the course.
Vyučovací jazyk
Angličtina
Informace učitele
https://www.fi.muni.cz/research/dimea/algomanet2023local.html.en
Další komentáře
Předmět je vyučován jednorázově.
Výuka probíhá blokově.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2023/J013