2014
2015
2016
2017

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

Vašek Chvátal

Problém obchodního cestujícího

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

26. listopad 2015

16:00

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

Anotace přednášky

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

Přednášející

Vašek Chvátal

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

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

Seminář připravuje organizační výbor ve složení Roman Barták (MFF UK), 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), 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