Problém obchodního cestujícího patří mezi nejintenzivněji studované problémy výpočetní matematiky. Přednáška zahrne přehled historie problému a také technik a triků užívaných k jeho řešení.
Problém obchodního cestujícího patří mezi nejintenzivněji studované problémy výpočetní matematiky. Jeho formulace je jednoduchá: máte-li konečný počet měst spolu s cenou cesty mezi každou jejich dvojicí, najděte nejlevnější způsob, jak všechna ta města navštívit a vrátit se do výchozího bodu.
Obtížnost řešení je proslulá. Přednáška zahrne přehled historie problému a také technik a triků užívaných k jeho řešení.
Vašek Chvátal se narodil v Praze roku 1946, promoval na MFF UK na jaře 1968 a opustil republiku 24. srpna téhož roku. Potom učil matematiku a informatiku na universitách McGill, Stanford, Université de Montréal, Rutgers a Concordia. Jeho profesionální zájmy přecházely od hamiltonovských grafů (Chvátal-Erdősova věta) k extremální kombinatorice (Chvátalova hypotéza), matematickému programování (Gomory-Chvátalova metoda cutting planes pro řešení celočíselných programů), diskrétní geometrii (Chvátalova věta o tzv. art gallery problému), analýze algoritmů, perfektním grafům a dalším tématům. V roce 1983 vydal učebnici lineárního programování, která je dodnes široce populární. V tomto roce je jedním ze dvou laureátů ceny John von Neumann Theory Prize, kterou uděluje Institute for Operations Research and the Management Sciences. Společně s Davidem Applegatem, Robertem Bixbym a Williamem Cookem napsal počítačový program Concorde určený k řešení problému obchodního cestujícího a monografii na stejné téma. Za tuto práci obdržela jejich skupina v roce 2000 Beale-Orchard-Haysovu cenu za vynikající výsledky v oblasti výpočetního matematického programování, a v roce 2007 cenu Fredericka W. Lanchestera za nejlepší anglicky psaný příspěvek k rozvoji operačního výzkumu a věd o řízení.
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.
