Premium

Získejte všechny články mimořádně
jen za 49 Kč/3 měsíce

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

KVÍZ: Zapomenuté funkce domácí techniky, po kterých se už nikomu nestýská

v diskusi je 19 příspěvků

13. května 2024

Byly běžnou součástí životů vás, vašich rodičů nebo prarodičů. Většinu z nich dnes však nikdo...

Sověti neuměli zkonstruovat těžký tank. Pomohl jim až německý inženýr

v diskusi je 44 příspěvků

19. května 2024

Když je řeč o sovětských těžkých tancích, výčet zpravidla začíná pětivěžovým typem T-35. Jenže...

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

Pět věcí, které byste s Windows měli dělat, ale možná neděláte, a naopak

v diskusi je 10 příspěvků

15. května 2024

Možná prakticky ihned po instalaci, při prvním spuštění nového PC nebo později deaktivujete některé...

Umělá inteligence od OpenAI má nový pohon. A rovnou ho dává zadarmo

v diskusi je 9 příspěvků

13. května 2024  20:34

Společnost OpenAI vůbec poprvé pořádala živé představení svých pokroků. Hlavní novinkou se stala...

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

Panasonic překvapil, jeden opuštěný operační systém nahradily dva nové

v diskusi je 14 příspěvků

17. května 2024

Düsseldorf (Od zpravodaje Technet.cz) Když odhlédneme od kvality zobrazovacího panelu a obvodů zpracovávajících obraz, je operační systém...

Věci, které by ve Windows 11 měli ihned opravit

v diskusi je 1 příspěvek

20. května 2024

Windows 11 z uživatelského pohledu nastavuje zrcadlo budoucnosti. Nacházejí se v něm věci uživateli...

Beneš se Mussoliniho neštítil. Před 100 lety s ním vyjednal mezistátní smlouvu

v diskusi je 32 příspěvků

19. května 2024  10:30

V polovině května 1924 jednal československý ministr zahraničí Edvard Beneš v Římě s italským...

Sověti neuměli zkonstruovat těžký tank. Pomohl jim až německý inženýr

v diskusi je 44 příspěvků

19. května 2024

Když je řeč o sovětských těžkých tancích, výčet zpravidla začíná pětivěžovým typem T-35. Jenže...

Jak Muskova firma vyřešila problém prvního čipu v mozku člověka

v diskusi je 5 příspěvků

18. května 2024

Neuralink je jedna z firem Elona Muska, o které se mnoho mluví. V lednu totiž zavedli její...

Bohužel nám to nevyšlo, oznámili manželé Pagáčovi rozchod po šesti letech

Herečka Patricie Pagáčová (35) a dramaturg Tibor Pagáč (32) se rozešli po pěti letech manželství. Žádost o rozvod zatím...

Zemřel Vlastimil Harapes. Baletní mistr Národního divadla i českých filmů

Ve věku 77 let zemřel tanečník a herec Vlastimil Harapes. Dlouhá léta byl sólistou baletu Národního divadla. Zahrál si...

Anální sex je výzva. Nejvíc tabu je však v Česku jiná praktika, říká průzkum

Erotické hračky nepředstavují podezřelou exotiku, v ložnicích jsou jako doma. Ostatně jako masturbace. I orální sex....

Svěrák se na mě nedíval jen jako na hezkou buchtu, říká Radka Pavlovčinová

Jan Svěrák ji vidí jako robotku. Radka Pavlovčinová v nové hře filmového a teď už i divadelního režiséra hraje umělou...

Plné divadlo i bazilika. Nad rakví Postlerové mluvila dcera, Töpfer i Šťastný

S herečkou Simonou Postlerovou se v prostorách Divadla na Vinohradech rozloučili kolegové i veřejnost. Nad rakví...