Akce ČVUT

 Dnes
«  červen  2019  »
Po Út St Čt So Ne
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

Zpět na kalendář

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