Klávesové zkratky na tomto webu - základní­
Přeskočit hlavičku portálu


Přednáška: Proč je tak těžké najít správnou odpověď?

  10:35aktualizováno  17:40
Kolik barev potřebujeme k vybarvení mapy světa? Jak si nejlépe naplánovat dovolenou, pokud chceme navštívit všechna hlavní města Evropy a přitom co nejvíce ušetřit? Tyto otázky zní sice poměrně jednoduše, ale ve skutečnosti tak triviální nejsou. Jak tyto problémy modelovat, v přednášce vysvětlí Diana Piguet.

Nezřídka se v matematice setkáváme s problémem, který vypadá na první pohled poměrně jednoduchý. S trochou snahy by to snad každý zvládl vyřešit za večer. Takový byl například problém o čtyřech barvách z roku 1852. Zní takto: „Chcete danou mapu vybarvit tak, aby sousední země dostaly různé barvy. Postačí vám k tomu vždy jen čtyři barvy?“ Vypadá to, že k řešení této hádanky nepotřebujete žádné hluboké matematické znalosti, ale jen papír, barvené tužky a trochu trpělivosti, nebo snad ne?

Mgr. Diana Piguet, Ph.D.

Pracuje v Oddělení teoretické informatiky Ústavu informatiky a zabývá se teoriemi grafů.

Matematikům to ale trvalo více než 120 let, aby problém konečně vyřešili. Navíc řešení se neobejde bez použití počítačů.

Jiný problém dodnes odolává úsilí matematiků a informatiků. Je to problém obchodního cestujícího. Představte si, že jste obchodník, který potřebuje navštívit několik měst a pak se vrátit domů. Zřejmě chcete mít co nejmenší náklady a tudíž najít co možná nejlevnější trasu. V jaké pořadí máte jednotlivá města navštívit? Jeden přístup by mohl být takový, že si navrhnete všechny trasy, spočítáte náklady každé z nich a potom si vyberete tu nejlevnější.

Pokud jste malý podnikatel a potřebujete navštívit jen tři města, je tento přístup zcela vhodný. Pokud se vám více daří a těch měst už je deset, k obchodní dovednosti potřebujete též dovednosti programátorské. Budete totiž potřebovat spočítat náklady přes tři miliony rozdílných tras. Problém ale opravdu nastane, když počet měst, které chcete navštívit, dále roste. Pak vás nezachrání ani sebelepší programátorské dovednosti.

Rozcestník

Kde sledovat další přednášky?

Pokud potřebujete navštívit 100 měst, váš osobní počítač vám sdělí odpověď zhruba za 40 milionů let a zatím neexistuje žádný algoritmus, který by výpočet podstatně zrychlil.

.

Autor:


Témata: matematika, Dovolená

Nejčtenější

Okamura má na fotce z posilovny přifouknuté svaly. Jak poznat fotomontáž

Ukázka nepovedené fotomontáže z posilovny. Mřížka v pozadí ukazuje, k jakému...

Předseda SPD se na svém oficiálním profilu na Facebooku pochlubil fotkami z posilovny. Komentátoři si všimli, že fotka...

Dvakrát přežil ohnivé peklo a vrátil se do boje. Chybu udělal po válce

František Truhlář před válkou

Letec RAF František Truhlář přežil dvě těžké havárie při návratech z bojových letů. Při obou utrpěl těžké popáleniny,...



Proč chtěl Hitler Svatý grál a archeologie za ČSSR nebyla marxistická

Svastika na archaické řecké keramice (8. století před Kr., Archeologické muzeum...

Jedním z oblíbených triků propagandy a propagandistů je návrat k mýtům a ohýbání historie do podoby, která politickému...

Tohle astronomové ještě neviděli. Přiletěla první mezihvězdná planetka

Rekonstrukce možné podoby planetky 1I/2017 U1 (‘Oumuamua) na základě údajů...

V naší soustavě už více či méně dobře známe 750 tisíc různých planetek a dalších menších těles. Ale žádný z nich se...

Legendární pragovka pokořila Balkán a Jugoslávci ji pojmenovali Pionir

Praga RND

Legendární nákladní automobil Praga RN, včetně dieselové mutace RND, vznikl v první polovině třicátých let, ale ve...



Další z rubriky

Sci-Hub by měl znovu platit a možná bude opětovně nedostupný

Zakladatelka serveru Sci-Hu, Alexandra Elbajkanová. na konferenci na Harvardově...

Služba Sci-hub, která nabízí „upirátěné“ vědecké studie zdarma ke stažení, čelí dalším žalobám.

Byl Tyranosaurus rex největším dravým dinosaurem? Záleží i na hmotnosti

Velikostní srovnání čtyř největších známých teropodů. Z hlediska délky je T....

Existuje řada dravých dinosaurů, kteří jsou o něco větší než asi nejznámější Tyranosaurus rex. Ale co se týká...

Nejslavnější tyranosauří teenager je „půvabná Janička“

Jane je zatím tou nejlepší ukázkou vzezření mladých tyranosaurů. Tento téměř...

V létě roku 2001 objevili výzkumníci doposud nejkompletnější fosilní exemplář dospívající jedince druhu Tyrannosaurus...

Vozový park, který obstojí i v podzimním počasí
Vozový park, který obstojí i v podzimním počasí

Přečtěte si recenze kočárků na eMimino.cz a vyberte ten nejlepší.



Najdete na iDNES.cz