Neděle 24. října 2021, svátek má Nina
  • schránka
  • Přihlásit Můj účet
  • Neděle 24. října 2021 Nina

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:
  • Nejčtenější

Test sluchátek: Z šesti novinek nás nejvíce nadchly ty nejlevnější

Premium Test zcela bezdrátových sluchátek přinesl docela neobvyklé překvapení: úplně nejlevnější model v celkovém hodnocení...

Hledá se náhrada za gripeny. Zkusili jsme udělat tendr „nanečisto“

Páteří českého vojenského letectva je v současné době čtrnáct kusů bojového letounu Saab JAS-39 Gripen, pronajatých od...

Weby vás tajně sledují prostřednictvím otisku zařízení

Na světě je téměř 1,9 miliardy internetových stránek. Mnohdy slouží k pokoutným účelům a dost často z nich obchodníci...

Apple vylepšil svá oblíbená sluchátka a absurdně zlevnil hudební službu

Pondělní záplava novinek se v nemalé míře soustředila na zvukové a hudební produkty. Podrobně vás jimi provedeme.

{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...}

Legendy ČSD obrazem. Nejvýkonnější evropská tendrovka se vyráběla v ČKD

Lokomotiva řady 477.0, zvaná Papoušek, patří k vrcholným dílům československých konstruktérů parních lokomotiv....

Syndrom Petra Pana. Proč někteří muži nikdy nedospějí a žijí jako paraziti

Premium V každém chlapovi zůstává kousek kluka, ale musí to být právě jen ten kousek. Pokud muž nechce vyrůst a převzít...

Čína má Evropu v hrsti, za pár týdnů dojde hořčík. Auto bez něj nevyrobíte

Premium Vše nasvědčuje, že současná čipová krize v automobilovém průmyslu je jen zahřívacím kolem před tím, co se na Evropu...

Váš syn bude žít jen pár týdnů. Zpověď matky zesnulého hokejisty Buchtely

Premium Přežít své dítě. Pro každého rodiče ta nejhorší představa. Teprve dvacetiletý hokejista Ondřej Buchtela zemřel loni v...

  • Další z rubriky

STO OBJEVŮ: Splachovací záchod vymyslel poeta ze dvora královny Alžběty

Seriál Spojení „básník a splachovací záchod“ zní natolik absurdně, že to musí být pravda. První známý autor užitečného...

Nobelovu cenu za chemii získali dva vědci za nástroje pro stavbu molekul

Nobelovu cenu za chemii letos získali vědci Benjamin List z německého Max-Planck-Institutu a David MacMillan z...

STO OBJEVŮ: Už žádné destičky. Na nápad čínského eunucha píšeme dodnes

Seriál Papír používáme díky starověkému čínskému ministrovi, kterého přestalo bavit nekonečné namáhavé přehrabování v těžkých...

STO OBJEVŮ: Kostka pana Rubika se stala nejproslulejším hlavolamem

Seriál Hlavolam z barevných krychliček zasáhl koncem sedmdesátých let minulého století jako smršť všechny generace. Získal...

Najděte svou vnitřní krásu: Otestujte nutrikosmetiku od Manufaktury
Najděte svou vnitřní krásu: Otestujte nutrikosmetiku od Manufaktury

Podpořte krásný vzhled své pleti a pokožky nejen zvenku, ale také zevnitř. Objevte nutrikosmetiku značky Manufaktura. Hledáme 30 uživatelů, kteří s...

Čína má Evropu v hrsti, za pár týdnů dojde hořčík. Auto bez něj nevyrobíte

Premium Vše nasvědčuje, že současná čipová krize v automobilovém průmyslu je jen zahřívacím kolem před tím, co se na Evropu...

ČEZ od ledna zdraží: elektřinu asi o třetinu, plyn o víc než polovinu

ČEZ od nového roku zdraží elektřinu i plyn. Podle šéfa energetické společnosti Daniela Beneše to může být asi třetina u...

Jestli bude inflace stoupat dál, lidé ztratí polovinu úspor, varuje ekonom

Současná míra inflace bude trvat ještě několik let, důvodem jsou zejména vysoké objemy pumpování peněz do ekonomiky,...

Střelba proti kameře je běžná, ale herec za nehodu nemůže, tvrdí Dvořák

Zpráva, že americký herec Alec Baldwin při natáčení westernu zastřelil kameramanku a postřelil režiséra, vyvolala...

RECENZE: Je to vůbec ještě legální? Úchylná Succubus šokuje za každou cenu

Novinka od autorů nechvalně proslulého Agony sice po herní stránce trochu vyspěla, stále se však opírá především o co...