Principy kombinatorického generování
Cíle projektu
Generování kombinatorických objektů je základní algoritmickou úlohou s širokou řadou praktických aplikací. Tato úloha vede k definici tzv. flip grafů, jež mají za vrcholy generované objekty a hrany spojují objekty, jež se od sebe málo odlišují. Cílem tohoto projektu je (1) rozvinout a rozšířit teoretické základy pro kombinatorické generování se zaměřením na algoritmy a kombinatoriku, (2) zkoumat strukturální vlastnosti příslušných flip grafů, které vedou k několika dlouhodobě otevřeným problémům, (3) naimplementovat nové algoritmy pro generování a zpřístupnit je na serveru kombinatorických objektů (Combinatorial Object Server).
Klíčová slova
combinatorial generationhighly symmetric graphsHamilton cyclehypercubegeometric flip graphs
Veřejná podpora
Poskytovatel
Grantová agentura České republiky
Program
Standardní projekty
Veřejná soutěž
SGA0202200004
Hlavní účastníci
Univerzita Karlova / Matematicko-fyzikální fakulta
Druh soutěže
VS - Veřejná soutěž
Číslo smlouvy
22-15272S
Alternativní jazyk
Název projektu anglicky
Principles of combinatorial generation
Anotace anglicky
Generation of combinatorial objects is a fundamental algorithmic task with a wide range of practical applications. This task leads to the definition of flip graphs, which have as vertices the objects to be generated, and edges connect objects that differ in a small change. The aim of this project is to (1) develop and extend the theoretical foundations for combinatorial generation, with a focus on algorithms and combinatorics, (2) investigate structural properties of the underlying flip graphs, which leads to several long-standing open problems, (3) implement new generation algorithms and make them available on the Combinatorial Object Server.
Vědní obory
Kategorie VaV
ZV - Základní výzkum
OECD FORD - hlavní obor
10102 - Applied mathematics
OECD FORD - vedlejší obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - další vedlejší obor
—
CEP - odpovídající obory
(dle převodníku)AF - Dokumentace, knihovnictví, práce s informacemi
BC - Teorie a systémy řízení
BD - Teorie informace
IN - Informatika
Termíny řešení
Zahájení řešení
1. 1. 2022
Ukončení řešení
31. 12. 2024
Poslední stav řešení
—
Poslední uvolnění podpory
29. 2. 2024
Dodání dat do CEP
Důvěrnost údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Systémové označení dodávky dat
CEP25-GA0-GA-R
Datum dodání záznamu
12. 3. 2025
Finance
Celkové uznané náklady
6 795 tis. Kč
Výše podpory ze státního rozpočtu
6 552 tis. Kč
Ostatní veřejné zdroje financování
243 tis. Kč
Neveřejné tuz. a zahr. zdroje finan.
0 tis. Kč
Základní informace
Uznané náklady
6 795 tis. Kč
Statní podpora
6 552 tis. Kč
96%
Poskytovatel
Grantová agentura České republiky
OECD FORD
Applied mathematics
Doba řešení
01. 01. 2022 - 31. 12. 2024