Středa 17. srpna 2022, svátek má Petra
  • schránka
  • Přihlásit Můj účet
  • Středa 17. srpna 2022 Petra

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:

Gamescom 2022

Letošní veletrh her Gamescom 2022 opět pořádá na výstavišti v Kolíně nad Rýnem od 24. do 28. srpna. Slavnostní zahájení proběhne večer předem na Opening Night Live 2022 show 23. srpna.

  • Nejčtenější

KOMENTÁŘ: Obrana kupuje bezpilotního dědečka. Zda umí bojovat, nikdo neví

Po několika týdnech spekulací o tom, jaké bojové drony česká armáda nakoupí, ministerstvo obrany zveřejnilo, že půjde o...

ANALÝZA: Tchaj-wan v ohrožení. Neptejme se zda, ale kdy bude válka

Premium Uprostřed obav o budoucnost míru ve světě, na pozadí války probíhající mezi dvěma největšími armádami Evropy...

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

Armáda by mohla dostat německé obrněnce Marder a svá BVP-2 poslat Ukrajině

Válka na Ukrajině rozpoutala v Evropě velké pohyby zbraní a vojenské techniky. Některé země své starší kusy posílají na...

Rusko začíná vyrábět vlastní notebook. Přirovnání k macbookům pokulhává

Po letech vývoje se má letos rozběhnout výroba zcela nového notebooku vyvinutého přímo v Rusku. Stroj s názvem Bitblaze...

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

Tatry na Technetu: letiště Poprad je vysoko. První linku mělo v roce 1943

Seriál U Popradu vzniklo nejvýše položené československé dopravní letiště, jeho nadmořská výška je 718 metrů. Když se v roce...

Porucha imunity je první známka, že je v našem životě něco špatně, říká lékařka

Premium Lidí s poruchami imunity přibývá. Příčinou je často špatný životní styl, což vede k vážným nemocem, třeba k rakovině....

Bude hůř. Považuji za férové sdělit to divákům předem, přiznal šéf ČT

Premium Inflace, energie, válka na Ukrajině a k tomu nízké koncesionářské poplatky. Současná situace postihla i Českou...

První díl rozhovoru s Shopaholicadel: Práci neseženu, každý den můžu umřít!

Premium Rozhovorům se dlouho úspěšně vyhýbala, nyní ale udělala výjimku a Expresu poskytla exkluzivní sondu do své duše....

  • Další z rubriky

Největší známý dinosaurus žil možná v Indii, říká odborná vědecká práce

O záhadném obřím sauropodním dinosaurovi pojmenovaném Bruhathkayosaurus matleyi bylo diskutováno již mnohokrát, zejména...

Expert: Do Česka se plyn z LNG terminálu přepraví těžko. Dostaneme ten, co bude

Rozstřel Česká vláda zajistila v Nizozemsku terminál na zkapalněný zemní plyn (LNG). Ten by měl v případě výpadku dodávek z...

Laboratoř zkázy dinosaurů. Našla se noha i s kůží, pro palentology zázrak

Premium Před 66 miliony lety dopadl na Zemi asteroid, který téměř zničil život na planetě. Dokonalé svědectví o síle katastrofy...

Rozšíření oparů souvisí s rozmachem líbání v době bronzové, tvrdí vědci

Příčinou šíření oparů je pravděpodobně rozmach líbání v době bronzové. Vyplývá to ze studie, o které informoval deník...

Léto venku s eMiminem: Na co se těšit v 7. soutěžním týdnu?
Léto venku s eMiminem: Na co se těšit v 7. soutěžním týdnu?

Léto venku s eMiminem je tady! Každý týden budeme soutěžit o fantastické ceny v celkové hodnotě 298.000 Kč. Sdílejte své letní zážitky, hodnoťte...

Bude hůř. Považuji za férové sdělit to divákům předem, přiznal šéf ČT

Premium Inflace, energie, válka na Ukrajině a k tomu nízké koncesionářské poplatky. Současná situace postihla i Českou...

K vulgárnímu nápisu musela tatéra přemluvit sexem. Teď ho chce pryč

Její nápad se v salónech nikomu nelíbil. Žádný tatér s ním nechtěl mít nic společného, tak moc nápis svou nositelku...

Herečka Anne Heche zemřela, nepřežila následky zranění po autonehodě

Třiapadesátiletá herečka Anne Heche zemřela. Uvedla to její přítelkyně Nancy Davisová. Herečka skončila v nemocnici v...

Stav herečky Anne Heche je téměř beznadějný. Má vážně poškozený mozek

Herečka Anne Heche (53) s největší pravděpodobností nepřežije nehodu, při níž autem narazila do dvoupodlažní budovy v...

Rýn během pátku přestane být splavný. Ekonomické dopady pocítí celá Evropa

Hladina řeky Rýn v německé oblasti Rheingau podle úřadů v pátek klesne na kritickou úroveň, na klíčovém místě naměří už...