2014
2015
2016
2017
2018
2019

Čtyřicátétřetí setkání Pražského informatického semináře

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.

23. května 2019

16:15

Posluchárna S5, MFF UK
Malostranské nám. 25, Praha 1
Zobrazit na mapě

Anotace přednášky

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

Přednášející

Radomír Černoch

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.

O PRAŽSKÉM INFORMATICKÉM SEMINÁŘI

Seminář se schází zpravidla 4. čtvrtek v měsíci v 16:15 hod. (s výjimkou letních měsíců a prosince), a to buď v budově FEL ČVUT na Karlově náměstí, nebo v budově MFF UK na Malostranském náměstí.

Jeho program je tvořen hodinovou přednáškou, po níž následuje časově neomezená diskuse. Základem přednášky je něco (v mezinárodním měřítku) mimořádného nebo aspoň pozoruhodného, na co přednášející přišel a co vysvětlí způsobem srozumitelným a zajímavým i pro širší informatickou obec. Přednášky jsou standardně v angličtině.

Seminář připravuje organizační výbor ve složení Roman Barták (MFF UK), Jaroslav Hlinka (ÚI AV ČR), Michal Chytil, Pavel Kordík (FIT ČVUT), Michal Koucký (MFF UK), Jan Kybic (FEL ČVUT), Michal Pěchouček (FEL ČVUT), Jiří Sgall (MFF UK), Vojtěch Svátek (FIS VŠE), Michal Šorel (ÚTIA AV ČR), Tomáš Werner (FEL ČVUT), Filip Železný (FEL ČVUT)

Idea Pražského informatického semináře vznikla z rozhovorů představitelů několika vědeckých institucí na téma, jak odstranit zbytečnou fragmentaci informatické komunity v ČR.

Podporovatelé

Kontakt