Metody z kombinatoriky, logiky a dalších oborů matematiky nacházejí stále více aplikací v různých oblastech informatiky. Jednou z oblastí, kde se matematické metody často využívají, je návrh efektivních algoritmů a datových struktur...
Metody z kombinatoriky, logiky a dalších oborů matematiky nacházejí stále více aplikací v různých oblastech informatiky. Jednou z oblastí, kde se matematické metody často využívají, je návrh efektivních algoritmů a datových struktur. Nicméně řada důležitých algoritmických problémů je těžká z hlediska výpočetní složitosti a proto je nepravděpodobné, že by je bylo možné efektivně vyřešit v plné obecnosti. Jeden z přístupů k řešení takových problémů je založen na omezení jejich těžkosti vhodnou parametrizací, např. omezením struktury vstupních dat nebo logickou složitostí uvažovaných typů problémů.
V úvodu přednášky předvedeme využití matematických metod v návrhu algoritmu pro vybraný konkrétní problém. Tohoto příkladu využijeme k zavedení pojmů, které se vyskytují v oblasti parametrizované složitosti, a představíme základní výsledky z této oblasti. Na závěr zmíníme několik obecných výsledků založených na poznatcích z kombinatoriky a logiky, které zaručují existenci efektivních algoritmů a které se souhrnně označují jako algoritmické metavěty.
Prof. Daniel Kráľ je mezinárodně uznávanou vědeckou osobností v oblasti kombinatoriky a teorie grafů. Kromě algoritmických otázek, jimž je věnována přednáška, se věnuje strukturální teorii grafů, zejména otázkám barevnosti, extremální kombinatorice a teorii kombinatorickych limit. Je autorem více než 100 článků publikovaných v časopisech včetně velmi prestižních jako Advances in Mathematics, Geometric and Functional Analysis a Journal of the ACM. Má řadu publikací i na nejvýznamnějších informatických konferencích jako FOCS, SODA, ICALP. Jako první v české informatické komunitě získal ERC grant (starting grant). Z dalších ocenění jmenujeme Evropskou cenu za kombinatoriku, Bolzanovu cenu a absolutní vítězství v Mezinárodní olympiádě v informatice (jako jeden ze dvou českých soutěžících v historii). Kromě Univerzity Karlovy v Praze působil na Georgia Inst. of Technology a TU Berlin, v současné době je profesorem na Univ. of Warwick.
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.
© 2013-2022, Prague Computer Science Seminar 
Toto dílo podléhá licenciCreative Commons Attribution 4.0 International License.
