Vizualizace grafových algoritmů je PEKLO - akce 29/11 - Praha

přidáno: 19. 11. 2010 13:39, autor: Petr Naske
Dovolujeme si Vás a Vaše studenty pozvat za projekt ROBOTOMIE.CZ  na přednášku Mgr. Josefa Cibulky (Matematicko-fyzikální fakulta UK) konanou 29.11. s názvem " Vizualizace grafových algoritmů je PEKLO". Přednáška je určena učitelům matematiky a informatiky na SŠ a jejich nadaným studentům a koná se v rámci pravidelních Exaktních pondělků na MFF UK.

29.11. 18:00 Vizualizace grafových algoritmů je PEKLO (Mgr. Josef Cibulka)

S grafovými úlohami se setkáváme takřka každý den, aniž si to uvědomujeme. Typickým příkladem může být hledání nejrychlejší cesty z místa A do místa B. Pro úspěšné vyřešení je třeba samozřejmě předem vědět, jak dlouho bude ten který úsek cesty trvat. V reálném světě nám situaci komplikují neurčitosti typu zpoždění autobusu či dopravní zácpa, ve světě matematiky se naštěstí se špatnými řidiči nesetkáme. Oblast, ve které se můžeme pohybovat, si reprezentujeme jako graf, kde máme křižovatky (tzv. vrcholy grafu) a ulice mezi dvojicemi křižovatek (tzv. hrany) spolu s časem, který potřebujeme na projetí jednotlivých ulic.
Ukážeme si algoritmy na řešení této a dalších grafových úloh a to jednak teoreticky, ale hlavně na konkrétních příkladech. K tomuto účelu budeme používat program Peklo, ve kterém jsou tyto algoritmy naimplementovány včetně popisu toho, co právě dělají.
Program lze stáhnout na adrese peklo.sf.net Předvedeme si například Dijkstrův algoritmus na hledání nejkratší cesty, Kruskalův a Borůvkův algoritmus na minimální kostru (chceme zachovat celkově co nejkratší podmnožinu úseků ulic, které dovolí spojení mezi každou dvojicí křižovatek) a Ford-Fulkersonův na maximální tok (kolik aut může za hodinu přejet z místa A do místa B, pokud kromě nich žádná jiná nejezdí). Z komplikovanějších algoritmů pak např. Edmondsův na maximální párování.

Přednáška se koná na Matematicko-fyzikální fakultě UK, Malostranské náměstí 25, Praha 1, místnost S5, čas 18:00 - 20:00 (cca).
Comments