proběhne 23. května 2019
v posluchárně S5, MFF UK
Malostranské nám. 25, Praha 1
Na programu je Radomír Černoch: Systém generálního klíče: Od NP-úplnosti po start-up
Návrh systémů generálního klíče, známý též jako problém lock-chartu, je kombinatorickou úlohou z 19. století, která zůstala až do 21. století teoretickým výzkumem v podstatě neobjevena. Úloha má za cíl navrhnout mechanické klíče a cylindrické vložky podle zadaných přístupových práv. Kromě své historie je zajímavá jednoduchou formulací, složitostí na hranici možností efektivních algoritmů, a šíří algoritmů existujících pro její řešení. Stojí za pozornost už proto, že je výborným zadáním studentských úloh v programování a optimalizaci.
V přednášce představím problém a řešení lock-chartu, dosavadní teoretické výsledky, i nástin praktických algoritmů. U redukce na úlohu splnitelnosti výrokových formulí, jako jednoho z nejúspěšnějších přístupů, vyzdvihnu přednosti moderních SAT solverů.
Bližší informace najdete na webové stránce PIS.
Žádné komentáře:
Okomentovat