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ší

Nejšťastnější americká stíhačka. Pilot ji opustil, a tak přistála sama

Convair F-106A Delta Dart

Před téměř půlstoletím se stal v americké Montaně zázrak. Z nebe se snesl na pšeničné pole proudový letoun, který byl...

Nejvtipnější chyby z českého hitu Kingdom Come: Deliverance

Kingdom Come: Deliverance

Kingdom Come je obrovská a propracovaná hra, ale její autory čeká ještě spousta práce při odlaďování mnoha chyb, které...



Prohledejte půl miliardy uniklých hesel. Najdete tam i to svoje?

Ilustrační foto

Úniků dat, často velmi citlivých, stále přibývá. O spoustě z nich se ani nemusíme dozvědět. Kromě e-mailových adres...

Vyfotil jeden jediný atom. Stačil běžný foťák a složitá past

Snímek zachycující jediný atom stroncia v tzv. iontové pasti. Atom je uprostřed...

Atomy jsou pouhým okem neviditelné, to víme všichni. Ale pokud je správně nasvítíte a připravíte pro ně vhodné...

Internet levně a rychle. SpaceX načíná další „megalomanský“ projekt

Falcon 9 připravený pro misi Paz. Všimněte si nového aerodynamického krytu...

Na oběžnou dráhu dnes odstartovala další raketa firmy SpaceX. Tentokrát na palubě ponese mimo jiné i dva experimentální...

Další z rubriky

Vidíte to jinak než ostatní? Optické iluze, které nás rozdělují

Co vidíte na obrázku?

Věříte vlastním očím? Nezapomínejte, že to, co vidíte, není jen výsledkem senzorických vjemů, ale především...

Převalského koně nejsou divoký druh. Unikli z lidského zajetí

Koně Převalského čekají na transport v chovné stanici v Dolním Dobřejově na...

Koně Převalského nejsou „poslední druh divokého koně“, jak jsme se dosud domnívali. Podle nové genetické analýzy jde o...

Co říkáme ze spaní? To se rozhodně nedá tisknout

Chrápání (ilustrační foto)

Ze spánku mluví někdy zřejmě většina z nás. Ale co při tom říkáme? Podle závěru francouzské studie býváme zřejmě velmi...

Najdete na iDNES.cz