Pondělí 16. prosince 2019, svátek má Albína
  • schránka
  • Přihlásit Můj účet
  • Pondělí 16. prosince 2019 Albína

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:

Přechod na DVB-T2

Od 27. 11. probíhá postupný přechod na vysílací standard DVB-T2. Proces by měl být dokončen do poloviny roku 2020. Diváci si tak musí pořídit televizi s podporou kódování H.265 (HEVC) nebo starší televizi doplnit vhodným set-top boxem.

  • Nejčtenější

V Benešově udeřil virus, který vydírá nemocnice i města po celém světě

V benešovské nemocnici pravděpodobně zaútočil typ počítačového viru, který dokáže z provozu vyřadit policii, úřady i...

Molotovův koktejl: finský lihovar přinášel zkázu sovětským tankistům

Podobně jako nouze naučila Dalibora housti, museli se finští obránci během zimní války spolehnout v boji se sovětskými...

Nevíte co? Tipy na dárky, o kterých možná nevíte, že existují

„Hele, to je dobré, to jsem neznal,“ překvapí nás občas někdo údivem nad věcí, kterou považujeme za docela běžnou....

USA testují vojáka budoucnosti. Přes brýle uvidí nebezpečí a neztratí cíl

Na vojenské základně Fort Pickett ve Virginii testují vojáci brýle s průhledovými displeji IVAS (Integrated Visual...

{NADPIS reklamního článku dlouhý přes dva řádky}

{POPISEK reklamního článku, také dlouhý přes dva a možná dokonce až tři řádky, končící na tři tečky...}

Nahaté fotky v telefonu skryje před cizími zraky šikovná aplikace

Do přehledu užitečných mobilních aplikací jsme tentokrát zařadili například aplikaci, která vyhledá a skryje lechtivé...

Premium

Neustále se mě ptají na honorář, říká „holčička“ z reklamy s prasátkem

Tak nám ta malá holčička z prasátkové reklamy na kofolu trochu povyrostla. Už jí je dvacet, jmenuje se Sandra Flemrová...

Premium

Na Gottově pohřbu jsem se bál, že spáchám atentát na Zemana, říká Strach

Každý se ho ptá na Anděla Páně 3. Jiří Strach ale trpělivě vysvětluje, že to nezáleží jen na něm. „Rozhodujeme o tom...

Premium

Zalepili matce prsa, aby nemohla kojit. Při příbězích z Osvětimi pláče i průvodce

Lukáš Lev provází v koncentračních táborech a popisuje nacistická zvěrstva. Jeho babička si však stála za tím, že za...

  • Další z rubriky
Premium

Vědci odnaučili mikroby jíst. Je to, jako by ze zvířete udělali rostlinu

Izraelským biologům se podařilo přesvědčit běžnou bakterii, aby se naučila zcela novému kousku: využívat oxid uhličitý...

Kolik je vašemu psovi lidských let? Spočítáme vám to podle nového vzorce

Při zkoumání zákonů stárnutí vědci přišli s lepším vzorcem pro přepočet psích let na lidské. Konkrétně jej ladili na...

Vědci pomocí chladiva „zastavili“ mozek člověka, aby mu zachránili život

V USA běží klinická zkouška účinnosti "podchlazení" těla vážně raněných na teploty až kolem pouhých 10° C. Krev...

Auto je zbytečné, je to fosilní zábava, řekl fyzik v Rozstřelu

Mít vlastní auto ve městě dnes není luxus, nýbrž „opruz“ - a dobrý způsob, jak snížit naší spotřebu peněz i materiálu,...

TIPY: Dárky pro malé princezny, které zaručeně potěší
TIPY: Dárky pro malé princezny, které zaručeně potěší

Nemáte ještě nakoupené všechny vánoční dárečky? Pokud zrovna vybíráte pro slečny, jistě uvítáte inspiraci.

Najdete na iDNES.cz