2014
2015
2016
2017
2018
2019
2020
2022
2023
2024

Sedmé setkání Pražského informatického semináře

Daniel Kráľ

Matematika a rychlé algoritmy

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

23. října 2014

16:00

Posluchárna E-107, FEL ČVUT
Karlovo nám. 13, Praha 2
Zobrazit na mapě

Anotace přednášky

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.

Přednášející

Prof. Daniel Kráľ

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.

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

Seminář se obvykle schází jednou za měsíc ve čtvrtek v 16:15 a to buď v budově FEL ČVUT nebo v budově MFF UK.

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

Pražský informatický seminář je z důvodů prevence šíření nákazy novým koronavirem do odvolání pozastaven.