CTU Events

The forty-third meeting of the Prague computer science seminar

23 May 2019   16:15-18:15

Radomír Černoch
Master-key system design: From NP-completeness to a 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 works in the start-up company Locksley.cz and also at the Faculty of Electrical Engineering of the CTU, where he received his Ph.D. under the supervision of Filip Železný. Previously, he studied at the University of Edinburgh and RWTH Aachen. Lately, he has been researching the combinatorics of mechanical locks, which led to the 2015 Werner von Siemens award for the innovation of the year.

Place

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

Organizer

Katedra kybernetiky FEL ČVUT

Contact person

Mgr. Helena Houšková

More information

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