Akce ČVUT

 Dnes
«  březen  2017  »
Po Út St Čt So Ne
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

Zpět na kalendář

27. PIS prof. Monika Henzinger: Hledání globálně minimálních řezů: Toky v sítích vs. PageRank

23.03.2017   16:00

ANOTACE:

V přednášce podáme přehled historie a současného poznání algoritmů pro hledání minimálních řezů v grafech, včetně některých nových výsledků. Zaměříme se na globálně minimální řezy, což je minimum z s-t řezů přes všechny dvojice vrcholů s a t. Je dobře známo, že cena minimálního s-t řezu v grafu je rovna velikosti maximálního toku z s do t, a standardní algoritmus pro počítání minimálního s-t řezu je skutečně založen na výpočtu maximálního toku. Pro globálně minimální řezy však stejný přístup vede k neefektivnímu algoritmu, který vyžaduje výpočet n maximálních toků, kde n je počet vrcholů grafu.

Do nedávné doby nejrychlejší algoritmus pro globálně minimální řezy v nevážených grafech proto nepoužíval výpočty toků, ale namísto toho spoléhal na opakované výpočty míry PageRank v kombinaci s různými grafově-teoretickými úvahami. Vysvětlíme, jak nahradit výpočty PageRank výpočty toků s více zdroji a více s toky, což vede k nejrychlejšímu současnému algoritmu pro výpočet globálně minimálních řezů v nevážených grafech. Spoluautory výsledků jsou Satish Rao a Di Wang.

PŘEDNÁŠEJÍCÍ:

Monika Henzinger je profesorkou Vídeňské univerzity, kde vede výzkumnou skupinu teorie a aplikací algoritmů. Doktorát (PhD) získala v roce 1993 na Princetonské univerzitě pod vedením Roberta Tarjana a poté pracovala na Cornellově univerzitě. Později pracovala ve výzkumném centru DEC, jako ředitelka výzkumu v Google, a na EPFL Lausanne, kde vedla laboratoř teorie a aplikací algoritmů. V roce 2013 jí byl udělen čestný doktorát na technické univerzitě v Dortmundu. Monika Henzinger je členem (fellow) ACM a EATCS, získala ERC Advanced Grant a byla jí udělena řada ocenění, např. European Young Investigator Award, NSF CAREER Award a Top 25 Women on the Web Award. Publikovala přes 100 vědeckých článků a je spoluautorkou více než 80 patentů.

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í
S5, MFF UK, Malostranské nám. 25, Praha 1
Pořadatel
Přípravný výbor PIS
Kontaktní osoba
Veronika Šínová, info@praguecomputerscience.cz, 224357667
Podrobnější informace
http://praguecomputerscience.cz/index.php?l=cz&p=27