Premium

Získejte všechny články
jen za 89 Kč/měsíc

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

Zázrak! NASA po pěti měsících obdržela od sondy Voyager smysluplnou zprávu

v diskusi je 135 příspěvků

23. dubna 2024  13:37

Když se v únoru letošního roku stále nedařilo navázat smysluplnou komunikaci s jedním z...

Herečce Slávce Budínové by bylo 100 let. Zemřela opuštěná, bez zájmu veřejnosti

v diskusi je 27 příspěvků

21. dubna 2024

Před 100 lety, 21. dubna 1924, se v Ostravě narodila známá česká herečka Slávka Budínová.

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

Znovuzrození japonských letadlových lodí. Ve výzbroji budou mít F-35B

v diskusi je 51 příspěvků

19. dubna 2024

Japonsko má ve své ústavě zakázáno vlastnit ofenzivní zbraně, jako jsou letadlové lodě. Doba...

Uvidíme v budoucnu na obloze druhý Měsíc? Příčinou může být neobvyklá hvězda

v diskusi je 13 příspěvků

17. dubna 2024

Velmi neobvyklá hvězda éta Carinae v 19. století náhle zjasnila a stala se druhou nejjasnější...

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

Unikátní exkurze. Nahlédněte do francouzské jaderné ponorky před vyplutím

v diskusi je 16 příspěvků

20. dubna 2024

Není obvyklé, aby reportéři mohli nahlédnout do jaderné ponorky v aktivní službě. Agentura AP nyní...

Jiří Horák obnovil ČSSD a dovedl ji do parlamentu. Se Zemanem si nerozuměl

v diskusi nejsou příspěvky

24. dubna 2024

Před 100 lety se narodil Jiří Horák, který po sametové revoluci pomáhal znovuobnovit sociální...

Dnes už se bez nich válčit nedá. Raketový vzestup bojových dronů

v diskusi jsou 3 příspěvky

24. dubna 2024

Bezpilotní letadla (drony) jsou v posledních dvou dekádách na raketovém vzestupu. Přispěla k tomu...

Snadno s fotkami už i ve Windows. Aplikace Fotografie vyrostla na novou úroveň

v diskusi nejsou příspěvky

24. dubna 2024

Premium Aplikace Fotografie, která je pevnou součástí Windows, slouží nejen k prohlížení obrázků. Stejně...

Zázrak! NASA po pěti měsících obdržela od sondy Voyager smysluplnou zprávu

v diskusi je 135 příspěvků

23. dubna 2024  13:37

Když se v únoru letošního roku stále nedařilo navázat smysluplnou komunikaci s jedním z...

Manželé Babišovi se rozcházejí, přejí si zachovat rodinnou harmonii

Podnikatel, předseda ANO a bývalý premiér Andrej Babiš (69) s manželkou Monikou (49) v pátek oznámili, že se...

Sexy Sandra Nováková pózovala pro Playboy. Focení schválil manžel

Herečka Sandra Nováková už několikrát při natáčení dokázala, že s odhalováním nemá problém. V minulosti přitom tvrdila,...

Herečka Hunter Schaferová potvrdila románek se španělskou zpěvačkou

Americká herečka Hunter Schaferová potvrdila domněnky mnoha jejích fanoušků. A to sice, že před pěti lety opravdu...

Největší mýty o zubní hygieně, kvůli kterým si můžete zničit chrup

Možná si myslíte, že se v péči o zuby orientujete dost dobře, přesto v této oblasti stále ještě existuje spousta...

Tenistka Markéta Vondroušová se po necelých dvou letech manželství rozvádí

Sedmá hráčka světa a aktuální vítězka nejprestižnějšího turnaje světa Wimbledonu, tenistka Markéta Vondroušová (24), se...