Problém obchodního cestujícího, aneb když počítače nestíhají

Není pochyb o tom, že počítače hrají v dnešním světě čím dál větší roli. Rozšiřuje se množství přístrojů s přívlastkem "chytrý". Takovéto rozšíření počítačů ve všedním světě by mohlo vést k myšlence, že prakticky nemůže existovat úloha, kterou by dostatečně výkonný počítač nemohl vyřešit, ale to je omyl.

Ve třicátých letech minulého století byl formulován tzv. Problém obchodního cestujícího, který je založen na následující úvaze. Představme si že jsme obchodní cestující, který má z nějakého města postupně navštívit další tři města a potom se zase vrátit zpět.

Nechť je našim startovním bodem město Brno a během své služební cesty musíme navštívit Znojmo, Břeclav a Olomouc a poté se zase vrátit zpět. Přitom je třeba co nejvíce šetřit čas a benzin. Celkovou vzdálenost, kterou urazíme, musí být co nejkratší. Podíváme se do mapy a zjistíme nejkratší vzdálenost mezi každými dvěma městy, výsledky pak zapíšeme do tabulky:

	Brno	Znojmo	Břeclav	Olomouc
Brno	0	55,2	53,5	65,09
Znojmo	60,2	0	61,97	120,3
Břeclav	53,5	61,97	0	98,11
Olomouc	65,09	120,3	98,11	0

(Pozn.: Vzdálenost Brno-Znojmo není stejná jako Znojmo-Brno z důvodu objížďky na trati.)

Otázkou je jak uspořádat zbylá tři města tak, abychom ujeli co nejkratší vzdálenost. Na první pohled by tato úloha neměla být vůbec těžká. Stačí vzít jednotlivá uspořádání tras, z tabulky vyčíst vzdálenosti, sečíst je, a se získaných celkových vzdáleností vzít tu nejmenší.

Tedy v našem případě máme tyto kombinace tras:

Trasa	Celková délka [km]
Brno-Znojmo-Břeclav-Olomouc-Brno	55,2+61,97+98,11+65,09 = 280,37
Brno-Znojmo-Olomouc-Břeclav-Brno	55,2+120,3+98,11+53,5 = 327,11
Brno-Břeclav-Olomouc-Znojmo-Brno	53,5+98,11+120,3+60,2 = 332,11
Brno-Břeclav-Znojmo-Olomouc-Brno	53,5+61,97+120,3+65,09 = 300,86
Brno-Olomouc-Znojmo-Břeclav-Brno	65,09+120,3+61,97+53,5 = 300,86
Brno-Olomouc-Břeclav-Znojmo-Brno	65,09+98,11+61,97+60,2 = 285,37

Je evidentní, že v našem případě je optimální trasa Brno-Znojmo-Břeclav-Olomouc-Brno, jejíž délka je 280,37 km. Poznamenejme, že použité vzdálenosti jsou pouze přibližné a pro jejich získání byl použit vyhledávač WolframAlpha.

Pro malé množství tras je tato úloha triviální, ale v případě obchodního cestujícího, který musí navštívit velké množství měst, je tato úloha opravdu dost náročná.

Řekněme, že naše trasa obsahuje kromě počátečního města ještě dalších 10 měst. Mohli bychom pokračovat mnoha způsoby, od ručního počítání (to ale nelze doporučit, neboť celkový počet tras je 3 628 800) nebo provedeme výpočet na PC, třeba v nějakém tabulkovém procesoru.

Jak jsme došli k číslu 3 628 800? Jedná se o takzvaný faktoriál čísla 10 a píšeme 10!. Faktoriál čísla n je roven součinu všech kladných celých čísel menších nebo rovných n.

Faktoriál se vyskytuje v mnoha oblastech matematiky, zejména pak v kombinatorice, kde vyjadřuje počet permutací množiny n prvků, tzn. vyjadřuje počet způsobů, jak seřadit n různých objektů. V našem případě

10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3 628 800

(na začátku máme 10 možností, kde začít, pak 9, ...).

Teď si představme, že si sami pro každou z těchto tras spočítáme celkovou vzdálenost a že nám každý takový výpočet zabere přesně jednu minutu. Potom bychom strávili nepřetržitým počítáním 6,9 roku! Skoro 7 let kvůli deseti městům.

Přidáme-li jedenácté město, pak se celkový počet různých tras přiblíží čtyřiceti milionům:

11! = 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 39 916 800

počítání by nám trvalo skoro 76 let!

Vidíme tedy, že faktoriály rostou velice rychle, a nemůžeme se proto divit, že když přidáme k našemu seznamu měst jen pár položek navíc, tak se radikálně zvýší časová náročnost výpočtu a i nejvýkonnější počítače takovýto úkol, založený na faktoriálním růstu veličiny, nemusí zvládnout.

Problém obchodního cestujícího ilustruje zajímavý fakt, že i velmi jednoduše formulované problémy mohou být neřešitelné (nebo jsou řešitelné, ale výpočet by trval příliš dlouho).

Samozřejmě v reálném životě nelze říct, že daný problém je neřešitelný, a proto matematici vynaložili velké množství energie pro nalezení jiných postupů. Zvolené přístupy lze zhruba rozdělit do dvou skupin.

První přístup je založen na tom, že se spokojíme s přibližným výsledkem. Místo absolutně nejkratší trasy budeme hledat nějakou jinou trasu, která se bude od optimální trasy lišit maximálně o zadané procento. Tento způsob se často využívá, neboť funguje ve většině bežných situací.

Druhý způsob spočívá v tom, že sice budeme trvat na přesném výsledku, ale napřed se podíváme na celkové zeměpisné rozložení měst a budeme se snažit využít specifických vlastností jejich poloh ke snížení celkového počtu tras, které je třeba zanalyzovat.

Například můžeme vyloučit na první pohled neefektivní trasy, např. ty které nás nutí cestovat z nejjižnějšího města do toho nejsevernějšího v prvních dvou krocích. Velkou nevýhodou tohoto přístupu je, že je optimalizován pouze pro konkrétní skupinu cílů, přidáním dalších měst musíme výpočet provést znovu.

Náročnost a neefektivnost této metody dokládá i výsledek amerických matematiků z roku 1998, kterým výpočet nejkratší trasy, která spojuje všech 13509 amerických měst nad 5000 obyvatel trval 3 měsíce nepřetržitých výpočtů na na počítačové síti složené ze třech superpočítačů (12 procesorů) a 32 PC Pentium II.

Je možné, že budoucí výpočetní systémy využívající kvantové jevy či DNA budou zvládat řešit problém obchodního cestujícího dostatečně rychle, ale v současnosti se musíme smířit s tím, že kromě přibližných či částečných výsledků pro některé podmnožiny měst žádné úplné prakticky využitelné řešení prostě neexistuje.

Zdroje a další informace
Wikipedia, crpc.rice.edu, Keith Devlin - Problémy pro třetí tisíciletí, Argo.

Hyperbolické funkce a jejich využití v architektuře

Mezi největší architektonické skvosty USA patří podle mého názoru Gateway Arch v St. Louis, Missouri. Tato stavba je příkladem využití matematiky v praxi. Myšlenka na postavení památníku osídlování Amerického západu¹ vznikla v roce 1933 v myšlénkách Luthera Ely Smitha veřejného činitele ze St. Louis. Trvalo 14 let než došlo k vypsání architektonické soutěže na tento monument. Soutěž nakonec vyhrál architekt finského původu Eero Saarinen v roce 1947. Jeho vítězný návrh představoval zužující se oblouk ve tvaru křivky řetězovky. Jednalo se však o technologicky velmi složitý projekt, a tak i kvůli válce v Koreji (chybějící finanční prostředky) byl projekt dokončet až v roce 1965.

Stavba je vysoká 192 m a v nejširším místě 192 m široká. Průřez má tvar trojúhelníku, o délce stran 16,5 m u paty a 5,2 m ve vrcholu oblouku. V konstrukci stěn byla použita kombinace železobetonové skořepiny a karbonové ocelové konstrukce. Ve vnitřku konstrukce se nachází transportním systémem, který přepravuje návštěvníky na vrchol, kde se nachází vyhlídková plošina.

Do roku 1968 se bylo možno dopravit na vrchol jedině pomocí více než tisíce schodů. Od roku 1968 je instalován unikátní kabinkový transportní systém. Jednotlivé kabinky jsou pro pět lidí. Jsou pospojované do vláčků po osmi kabinkách. Cesta vzhůru trvá 4 minuty, zpět o minutu méně. Vyhlídka ve vrcholu oblouku má malá okna, která jsou ze země téměř neviditelná.

Gateway Arch má tvar křivky o rovnici

kde x ∈ [-315,315] (základna je tedy široká 630 stop = cca 192 m). Ve výše uvedeném vzorci se nachází matematická funkce cosh, která se nazývá hyperbolický cosinus.

Podobně jako existují funkce sinus, cosinus, tangens a kotangens. Existují i jejich hyperbolické protějšky - hyperbolický cosinus (cosh), sinus (sinh), tangens (tgh) a cotangens (cotgh). Mají spoustu analogických vlastností, z nichž některé ukáži v následujícím textu.

V minulém článku jsem poukázal na to, jak lze z exponenciální funkce v oboru komplexních čísel získat funkce sinus a kosinus. Podobné úvahy lze provést i v oboru reálných čísel. Rozdělme nekonečnou řadu, pomocí které se definuje exponenciální funkce, na řadu se sudými a lichými členy:

Tento vztah definuje funkce, které se nazývají hyperbolický cosinus (cosh) a sinus (sinh). Bezprostředně hned si lze všimnout, že se jejich definice pomocí nekonečných sum liší akorát v absenci mocniny mínus jedničky:

V učebnicích matematiky se ale většinou používá definice, která má poněkud jiný tvar - je vyjádřena pomocí exponenciální funkce. Abychom došli k tomuto tvaru je nutné si uvědomit, že každou funkci, která je definována na nějakém intervalu symetrickém podle počátku, lze jednoznačne rozložit na součet sudé² a liché³ funkce.

To znamená, že libovolnou funkci f lze psát jako

Aplikujeme-li tento vztah na exponenciální funkci, získáme tím součet dvou funkcí, pomocí kterých se funkce hyperbolický cosinus

a sinus obvykle definují⁴ . Grafy funkcí

Z grafů lze vidět, že hyperbolický sinus je lichá funkce, kdežto hyperbolický cosinus je funkce sudá; přesně takhle to platí i pro známé funkce sinus a cosinus. Hyperbolické funkce rovněž splňují spoustu identit, které jsou podobné identitám pro goniometrická funkce, např. známé vzorce pro dvojnásobný argument:

Jak je vidět, první vzorec platí úplně stejně jako u goniometrických funkcí, v druhém vzorci je pouze jediná odlišnost, a to, že u goniometrických funkcí je u funkce sinus znaménko mínus. A podobně to platí i u většiny všech ostatních vzorečků.

Zdroje a další informace
archiweb.cz, en.wikipedia.org, cs.wikipedia.org,

---

1. V dobách minulých bylo právě St. Louis posledním místem osídlenecké civilizace před vstupem na Divoký Západ. Nahoru
2. Funkce se nazývá sudá, jestliže pro všechna x ležící v nějakém intervalu platí f(x)=f(-x). Graf takovéto funkce je souměrný podle osy y. Nahoru
3. Funkce se nazývá lichá, jestliže pro všechna x ležící v nějakém intervalu platí f(-x)=-f(x). Graf takovéto funkce je souměrný podle počátku souřadnic (bod 0). Nahoru
4. Funkce hyperbolický tangens a kotangens se definují podobně jako u goniometrických funkcí :
   tgh x = (sinh x)/(cosh x), cotgh x = (cosh x)/(sinh x. Nahoru

O důležitosti exponenciální funkce

V minulém článku jsme viděli, jak lze vyjádřit Eulerovo číslo pomocí limity a nekonečné řady. Zobecněním tohoto vztahu získáme definiční vztah pro (přirozenou) exponenciální funkci:

(Vykřičník za číslem označuje faktoriál z tohoto čísla, platí : N!= N·(N-1)·(N-2)···3·2·1, 0!=1.) Tento definiční vztah exponenciální funkce je možná poněkud složitý, ale jeho vyšší obecnost nám dovoluje z tohoto vztahu získat vztahy pro další základní matematické funkce, jejichž spojitost s exponenciální funkcí není na první pohled zřejmá: Jedná se především o funkce sinus a cosinus.

Než se do toho pustíme, je nutné vysvětlit, alespoň pár základních pojmů z teorie komplexních čísel. Reálná čísla, se kterými se setkáváme v běžném životě, dokáží přesně vyjádřit jakékoliv množství či délku. Existují ovšem případy, kdy tato čísla přestávají stačit - existují rovnice s reálnými koeficienty, které nemají v oboru reálných čísel řešení. Příkladem je rovnice

Proto byly zavedeny tzv. komplexní čísla, aby byl problém chybějících kořenů algebraických rovnic vyřešen. Základem je myšlenka vhodně zadefinovat odmocninu z -1 a korektně zadefinovat principy početních operací.

Definujme tzv. imaginární jednotku i takto:

Poznamenejme pak, že obecný tvar komplexního čísla je a+bi, kde i je imaginární jednotka; další info třeba na wikipedii. Nyní se již můžeme pustit do prvního rázného kroku. Zkusme do definičního vzorce pro exponenciální funkci dosadit za x výraz ix:

Tedy získali jsme vyjádření v podobě součtu dvou sum. Otázkou je, co se skrývá za těmito sumacemi? Lze dokázat, že se jedná o velmi známé funkce cosinus a sinus; můžeme si to ověřit konstrukcí grafů funkcí

na intervalu [-2π;2π]:

Je tedy vidět, že platí následující vztahy

Oprava posledního vzorce:

První dva vzorce se často používají pro definici funkcí sinus a cosinus. Pomocí těchto vzorců počítají tyto funkce i kalkulačky. Poslední vztah se nazývá Eulerův vzorec. Podle mnohých vědců se jedná o nejpozoruhodnější matematický vzorec, neboť vyjadřuje těsnou vazbu mezi exponenciálními a goniometrickými funkcemi a ilustruje tak důvod, proč bývá exponenciální funkce považována za nejdůležitější matematickou funkci vůbec. O hlubších důsledcích Eulerova vzorce někdy příště.

Zdroje a další informace:
Exponential_function, Euler_formula.

Greased Lightbox - Je dostupná aktualizace (v0.18)

→←+-↻

Nahrávám obrázek

Klikněte kamkoliv pro zrušení

Obrázek není dostupný

Krása Eulerova čísla 2

V minulém příspěvku jsem poukázal na krásné vyjádření Eulerova čísla pomocí limity či nekonečného součtu. Eulerovo číslo  se vyskytuje poměrně často v mnoha oborech. V tomto článku poukáži na podle mého názoru dva nejzajímavější příklady.

Troufám si tvrdit, že řada lidí by nehledala Eulerovo číslo ve finančnictví, ale ono tam je - ve složeném úročení.

Řekněme, že si někdo dá 10 000 Kč na nějaký termínovaný vklad s roční úrokovou mírou 10% a ročním připisováním úroků na dobu 5 let. Pak na konci pětiletého období bude mít na účtu (pomineme-li pro zjednodušení zdanění úroků) 10 000× 1,1⁵ =16105,1 Kč. Matematicky lze složené úročení popsat jednoduchou rovnicí

kde FV je budoucí hodnota investovaných peněz, PV současná hodnota a i úroková míra. Vraťme se k našemu příkladu a uvažujme situace, kdy dochází k připisování úroků

1. čtvrtletně,
2. měsíčně,
3. denně,
4. nepřetržitě.

Použitím posledně uvedeného vzorce získáme následující výsledky

Poslední případ, kdy dochází k nepřetržitému přidávání úroku k jistině, se nazývá spojité úročení:

kde e je Eulerovo číslo, t počet let a i  úroková míra spjatá s každým přípisem úroku (tedy i je např. čtvrtina roční nominální úrokové míry). Všimněme si, že denní úročení se dosti podobá svým výsledkem spojitému úročení. Z příkladu plyne, že bychom si u různých finančních produktů, jako jsou např. spořící účty měli všímat četnosti připisování úroků, neboť s vyšší četností dosáhneme většího výdělku.

Číslo e se vyskytuje i v teorii pravděpodobnosti. Příklad: Uvažujme hráče u herního automatu, u kterého nastává výhra jednou za n her. A nechť tento hráč bude hrát právě n her. Potom pro velká n platí, že pravděpodobnost, že hráč nevyhraje ani jednu hru ze všech n her je rovna 1/e.

Tato úloha z teorie pravděpodobnosti je klasickým příkladem tzv. Bernoulliho procesu, kdy se mnohokrát (n-krát) opakuje situace, u které může nastat pouze jedna ze dvou možností, z nichž jednu chápeme jako výhru a druhou jako prohru. Uvažme například situaci, kdy n-krát házíme jednou mincí. Jako výhru v každém hodu chápejme situaci, kdy padne líc. A nechť pravděpodobnost výhry (padl líc) je rovna p. Potom pravděpodobnost, že vyhrajeme k-krát ze všech n-pokusů je rovna

Vraťme se k našemu příkladu; ze zadání plyne  n → ∞, k → 0. Nyní můžeme využít předcházejícího vzorce. Pravděpodobnost výhry v jednom hodu je p=1/n. Proto pravděpodobnost, že hráč nevyhraje ani jednu hru ze všech n her je rovna

Eulerovo číslo se vyskytuje i mnoha dalších mnohem složitějších matematických problémech, ale tyto dva pěkné příklady názorně ukazují, že matematické konstanty se mohou vyskytovat i v mnoha problémech běžného života.

Krása Eulerova čísla 1

Mezi nejdůležitější matematické konstanty patří e, která se někdy nazývá Eulerova či Napierova konstanta. Matematika sice neobsahuje tolik význačných konstant jako fyzika, ale její konstanty jsou často pilířem určité ucelené teorie - např. imaginární jednotka i pro terorii komplexních čísel, 0 a 1 pro aritmetiku, či Ludolfovo číslo π pro geometrii.

Konstanta e, jejíž přibližná hodnota je 2,718281828459045235360287471352, se často definuje jako takové jediné reálné číslo a s vlastností, že funkce a^x má hodnotu směrnice tečny v bodě 0 rovnu 1. První odkazy na tuto konstantu se objevují v roce 1618 v práci o logaritmických funkcích Johna Napiera. V této práci byla příloha, která obsahovala tabulku různých konstant a   funkčních hodnot přirozených logaritmů. Ale samotný "objev" této konstanty se přisuzuje Jacobu Bernoullimu, který se zabýval výpočtem limity

neboť jak se ukázalo, tato limita se rovná právě Napierově konstantě. Éčko se pro tuto konstantu používá od roku 1736, kdy Leonhard Euler publikoval svoji práci Mechanica.

Podívejme se nyní na důkaz, že výše uvedená limita existuje a  je rovna e. V důkazu využijeme známé nerovnosti mezi geometrickým a aritmetickým průměrem:

Dokažme nejprve, že posloupnost {1+1/n}ⁿ (n=1,...,∞) je rostoucí¹:

Dále dokážeme, že posloupnost {1+1/n}ⁿ je shora omezená.

Ještě lze dokázat, že poslední suma je menší nebo rovna 3. Nyní již víme, že naše zkoumaná posloupnost má limitu e a pro tuto limitu platí, že je menší nebo rovna výše uvedené sumě. Pokud dokážeme, že platí i obrácená nerovnost, pak získáme vztah pro numerický výpočet Eulerovy konstanty.

Zvolme m,n ∈ N, m ≤ n a rozepišme podobně jako výše výraz

a nyní limitním přechodem pro n → ∞ dostaneme pro každé m ∈ N

Provedeme-li další limitní přechod m → ∞ dostaneme

Celkem tedy platí

a snadno si můžeme pomocí součtu několika prvních členů výše uvedené nekonečné řady ověřit, že e=2,718281.....

Eulerova konstanta má spoustu zajímavých vlastností a aplikací, o tom ale příště.

Poznámky

1. to platí tehdy, když pro všechny členy posloupnosti platí, že následující člen je větší než předcházející člen.