Dovolujeme vás pozvat na přednášku Mgr. Josefa Cibulky z Matematicko-fyzikální fakulty UK která 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.
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).
Nejčtenější články
Česká škola - portál pro ZŠ a SŠ
Česká škola poskytuje svým čtenářům diskusní prostor k vyjádření názorů na školskou problematiku. Tyto příspěvky se nemusí shodovat se stanoviskem redakce České školy a jsou uveřejňovány jako podnět k dalším diskusím.
Obsah článků nemusí vyjadřovat stanovisko redakce nebo vydavatele Albatros Media, a.s.
Tento server dodržuje právní předpisy
ISSN 1213-6018
Tyto webové stránky používají k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Informace o tom, jak tyto webové stránky používáte, jsou sdíleny se společností Google. Používáním těchto webových stránek souhlasíte s použitím souborů cookie.
Tento server dodržuje právní předpisy
o ochraně osobních údajů.
ISSN 1213-6018
Obsah podléhá licenci Creative Commons Uveďte autora-Neužívejte dílo komerčně-Nezasahujte do díla 3.0 Česká republika, pokud není uvedeno jinak nebo nejde-li o tiskové zprávy.
Tyto webové stránky používají k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Informace o tom, jak tyto webové stránky používáte, jsou sdíleny se společností Google. Používáním těchto webových stránek souhlasíte s použitím souborů cookie.
0 komentářů:
Okomentovat