Akce ČVUT

43. Pražský informatický seminář

23.05.2019   16:15-18:15

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ů.

Radomír Černoch pracuje ve start-upu Locksley.cz a na Fakultě elektrotechnické ČVUT, kde získal titul Ph.D. pod vedením Filipa Železného. Předtím studoval na Edinburské univerzitě a na RWTH v Cáchách. Poslední roky se věnuje výzkumu kombinatorických vlastností mechanických zámků. Tento výzkum v roce 2015 získal cenu Wernera von Siemense za nejvýznamnější výsledek vývoje/inovace.

Místo konání

Posluchárna S5, MFF UK Malostranské nám. 25, Praha 1

Pořadatel

Katedra kybernetiky FEL ČVUT

Kontaktní osoba

Mgr. Helena Houšková

Podrobnější informace

http://www.praguecomputerscience.cz/?l=cz&p=43