Akce ČVUT

PIS VII. přednáška - prof. Daniel Kráľ - Matematika a rychlé algoritmy

23.10.2014   16:00

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áľ

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 schází vždy 4. čtvrtek v měsíci v 16 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ě.
Formát semináře připravil přípravný výbor ve složení Michal Chytil (ÚI AVČR), Pavel Kordík (FIT ČVUT), 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), 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.

Místo konání

ČVUT FEL Karlovo nám. 13, budova E, KN:E-107 Zengerova posluchárna

Pořadatel

Přípravný výbor PIS

Kontaktní osoba

Přípravný výbor PIS, info@praguecomputerscience.cz

Podrobnější informace

http://www.praguecomputerscience.cz/

Příloha

Stáhnout