Akce ČVUT

PIS XVII. přednáška - prof. Vašek Chvátal - Problém obchodního cestujícího

26.11.2015   16:00

ANOTACE:

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

KN:E-107 (Karlovo nám. 13, budova E, 1. patro - Zengerova posluchárna)

Pořadatel

Přípravný výbor PIS

Kontaktní osoba

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

Podrobnější informace

http://www.praguecomputerscience.cz/

Příloha

Stáhnout