Akce ČVUT
Dnes | ||||||
---|---|---|---|---|---|---|
« | květen 2019 | » | ||||
Po | Út | St | Čt | Pá | 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 | 31 |
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