Témata

Pozor, tato stránka není aktuální! Aktualizovaný seznam všech čísel v PDF najdete zde. Za problémy se omlouváme.

Témata jsou texty nejen z oblasti matematiky, fyziky a informatiky, které popisují nějaký problém a jsou doprovázeny návodnými úlohami. Vaším úkolem je zamyslet se nad daným problémem a sepsat vaše úvahy ve formě krátkého textu.

Jak řešit téma?

Letos jsme pro tebe připravili tato témata:

Téma 1: Paradoxní výsledky

Obsah:

1. díl

2. díl

3.díl

Pozor, tato stránka není aktuální! Aktualizovaný seznam všech čísel v PDF naleznete zde. Za problémy se omlouváme.


1. díl

V tomto spíše experimentálním témátku se budeme zabývat ověřováním a následně interpretací dat, která jste naměřili. Nebude nijak početně složité, chceme po vás, abyste se naučili přemýšlet o datech, která získáte, vyvozovat z nich hypotézy a umět si na jejich základě pokládat otázky, které vás dovedou k dalším úvahám a experimentům.

Začněme takovým malým příběhem, který nám nastíní, o co se bude v tomto témátku jednat. Bylo nebylo, kdesi daleko žil jeden malý kluk. Jmenoval se Bartoloměj a měl rád zmrzlinu. Vyráběl si ji spolu s kamarády ve škole skoro každý den. Vždy smíchali mléko a cukr, tuto směs zahřáli v hrnci, nechali vychladnout a pak dali zmrznout do mrazáku. Jelikož kluků bylo hodně a míst v mrazáku málo, ne vždy se dostalo na všechny. Platilo, že kdo dřív přijde, ten dřív mele, takže Bartoloměj jednoho dne v zápalu boje o poslední místo v mrazáku zariskoval, nepočkal, až mu směs na zmrzlinu vychladne, a zavřel ji do mrazáku horkou. Když se po chvíli vrátil, bylo mu opravdu divné, že jeho směs už ztuhla a proměnila se ve zmrzlinu, avšak zmrzliny ostatních kamarádů ještě neztuhly. Vždyť byly studenější než ta jeho! V Bartolomějovi to vzbudilo zájem, ale ať přemýšlel, jak chtěl, nemohl přijít na to, proč tomu tak bylo. Když se zeptal učitelů, tak mu nevěřili a dělali si z něj legraci, že si vymyslel své vlastní fyzikální zákony. Jenže Bartoloměj věděl, co viděl. Rozhodl se dokázat ve školní laboratoři, že měl pravdu. Připravil si dvě navlas stejné nádoby a poté do jedné nalil horkou vodu a do druhé o něco chladnější. Obě poté zavřel do školního mrazáku.


Problém:

Co si myslíte vy, jaký byl výsledek jeho pokusu? Proveďte podobný pokus a ověřte, zda měl Bartoloměj pravdu. Doporučujeme to vyzkoušet nejprve s vodou, ta má víc konzistentní strukturu než Bartolomějova zmrzlina (ale nikdo vám samozřejmě nebrání něco podobného vyzkoušet). Zkuste si graficky zaznamenat závislost doby tuhnutí na počáteční teplotě jednotlivých měření, zkoumejte i závislost teploty na čase pro jednotlivá měření. Jaké parametry určují, zda je voda zmrzlá? Stanovte si okamžik, kdy prohlásíte jednotlivá měření za ukončená.


Tip: Experimenty bývají obecně časově náročnější, proto pokud se rozhodnete pro toto témátko, nezačínejte s měřeními na poslední chvíli.


2. díl

Malý Bartoloměj provedl svůj pokus a zjistil, že teplejší voda opravdu zmrzne rychleji, ale jen pokud pokus probíhá v menším měřítku (tedy pokud Bartoloměj neumístí do jednoho mrazáku mnoho nádob najednou). Rád by však přišel na to, co za to může. Nejprve se rozhodl prozkoumat vlastnosti kapaliny. Připravil si tedy teploměr a vyzkoušel tato měření s roztokem kuchyňské soli. Svoje měření ukončil, když teplota dané kapaliny dosáhla hodnot lehce pod 0C. Napadlo ho, že kapalina má jinou teplotu v různých místech svého objemu. Co kdyby do ní něco vložil a zabránil tak jejímu míchání anebo materiálem vloženého tělesa (například lžičky) ovlivnil odvod tepla z kapaliny?


Problém 1:

Ověřte, zda i pro ostatní kapaliny platí, že na počátku teplejší kapalina mrzne rychleji. Vyzkoušejte např. mléko, vodu se solí atd. Na čem si myslíte, že bude výsledek měření záviset? Zkuste navrhnout ideální kapalinu, na které bude efekt nejsilnější. Zkuste změnit podmínky, za kterých voda a vámi zvolené kapaliny tuhnou, tím, že zamezíte pohybu molekul v objemu kapaliny či změníte odvod tepla tím, že do kapaliny něco vložíte. Diskutujte důsledky těchto vámi změněných podmínek.

Pája a Matej; pavla.trembulakova@seznam.cz
e-mailová konference: paradoxni@mam.mff.cuni.cz


3. díl

Řešení 1. série

Zadání:

Co si myslíte vy, jaký byl výsledek Bartolomějova pokusu? Zmrzne teplá voda dříve než studená? Proveďte podobný pokus a ověřte, zda měl Bartoloměj pravdu. Doporučujeme to vyzkoušet nejprve s vodou, ta má víc konzistentní strukturu než Bartolomějova zmrzlina (ale nikdo vám samozřejmě nebrání něco podobného vyzkoušet). Zkuste si graficky zaznamenat závislost doby tuhnutí na počáteční teplotě jednotlivých měření, zkoumejte i závislost teploty na čase pro jednotlivá měření. Jaké parametry určují, zda je voda zmrzlá? Stanovte si okamžik, kdy prohlásíte jednotlivá měření za ukončená.

Řešení:

Pokud se zamyslíme nad samotnou hypotézou, tak odporuje prvotnímu logickému úsudku. Při srovnání dvou stejných nádob s vodou lišících se jen teplotou vody by nádoba s teplejší vodou měla nejprve vychladnout na teplotu té studenější vody v nádobě a pak teprve zmrznout, což neodpovídá tomu, co bychom měli experimentem dokázat.

Pro provedení tohoto experimentu je nejprve třeba definovat si podmínky, které budeme dodržovat během celého experimentu. Jako prostředí, ve kterém experiment proběhne, si zvolíme mrazák. Budeme pracovat s obyčejnou kohoutkovou vodou, kterou nejprve převaříme (např. ve varné konvici či v hrnci) a poté necháme vychladnout na požadovanou teplotu. Tímto snížíme pravděpodobnost rozdílu v koncentraci rozpuštěných minerálů (rozpustnost látky se s teplotou rozpouštědla mění a při pozvolném chladnutí na počáteční teplotu nedojde k extrémním změnám ve složení). Můžeme použít i destilovanou vodu a tím minimalizovat anomálie způsobené složením vody úplně. Jako nádobu budeme používat odměrnou kádinku z laboratorního skla.

Z kvantitativního hlediska není dobré měřit objem, ale hmotnost kapaliny, protože objem je závislý na teplotě podle jejího koeficientu tepelné roztažnosti. Pokud však měříme kvantitu vody v objemových jednotkách, tak to pro tuto chvíli nemá vliv. Přeci jen nám zde jde o to mít u každého měření stejné množství vody a odchylky v objemu při teplotách na námi měřeném intervalu teplot od $21 \, \mathrm{^{\circ }C}$ až $82 \, \mathrm{^{\circ }C}$ jsou malé, přibližně v jednotkách mililitrů.

Měření není dobré provádět ve velkém množství, neboť se stane, že přetížíme mrazák a jeho výkon začne značně kolísat. V závislosti na velikosti mrazáku tedy budeme měřit 2 až 3 nádoby najednou.

Je dobré zvolit si, jaký typ teploměru budeme používat. Při měření bychom měli dbát na to, aby šla zavírat dvířka mrazáku na doraz a nepronikalo teplo dovnitř. Otevřené dveře by měnily výkon mrazáku a tak i celkové mikroklima a teplotu. Podobné riziko bude hrozit při každém zkontrolování teploty vody v mrazáku, kdy otevřeme dveře. Zároveň nádobu s kapalinou neumístíme do nějakého stojanu z kartonu apod., naruší nám to plynulost teplotní interakce kapaliny s okolím přes stěnu nádoby a může se stát, že naše měření nebudou vykazovat to, co by měla, kdyby tam tato bariéra nebyla.

Další bod je stanovit si moment, kdy ukončíme měření a podle čeho prohlásíme, že voda zmrzla. Zmrznutí můžeme definovat například jako moment, kdy se na vodě objeví první ledové krystaly. Nevýhoda této definice zmrznutí je ta, že se musíme spoléhat na vlastní zrak a přesně jím určit moment vzniku prvních ledových krystalků.

Jeden z problémů ovlivňujících naše výsledky je ten, že musíme experiment kontrolovat vizuálně a otevírat dveře mrazáku, a to zejména ke konci, kdy potřebujeme určit přesně okamžik ztuhnutí. Tomuto se můžeme vyhnout například tím, že si zmrznutí zadefinujeme jako moment, kdy teplota vzorku vody dosáhne teploty menší než $0 \, \mathrm{^{\circ }C}$ a zároveň použijeme teploměr s digitálními senzory, které nám budou vypisovat teplotu kapaliny pravidelně do počítače i při zavřených dveřích mrazáku. Pokud takové zařízení nemáme k dispozici, proveďme nejprve měření, podle kterého odhadneme dobu tuhnutí kapaliny a nebudeme muset mrazák otevírat už od začátku měření.

Sledování doby tuhnutí v závislosti na počáteční teplotě vody je na provedení snazší než sledovat i průběh mrznutí vody, protože v takovém případě musíme sledovat a zaznamenávat i průběžnou teplotu, ne jen čas, kdy voda zmrzne. Data z našeho experimentu můžeme vidět v tabulce 1 a na obrázcích 1 a 2 níže1.

$T_0$

$t_\mathrm {z}$

$\Delta m$

Úbytek ve hm. %

$82,6 \, \mathrm{^{\circ }C}$

$39,28 \, \mathrm{min}$

$7 \, \mathrm{g}$

$7 \, \mathrm{\% }$

$69,9 \, \mathrm{^{\circ }C}$

$37,00 \, \mathrm{min}$

$6 \, \mathrm{g}$

$6 \, \mathrm{\% }$

$65,3 \, \mathrm{^{\circ }C}$

$42,75 \, \mathrm{min}$

$1 \, \mathrm{g}$

$1 \, \mathrm{\% }$

$60,0 \, \mathrm{^{\circ }C}$

$40,28 \, \mathrm{min}$

$2 \, \mathrm{g}$

$2 \, \mathrm{\% }$

$41,9 \, \mathrm{^{\circ }C}$

$57,43 \, \mathrm{min}$

$3 \, \mathrm{g}$

$3 \, \mathrm{\% }$

$30,9 \, \mathrm{^{\circ }C}$

$54,50 \, \mathrm{min}$

$2 \, \mathrm{g}$

$2 \, \mathrm{\% }$

$25,0 \, \mathrm{^{\circ }C}$

$51,92 \, \mathrm{min}$

$2 \, \mathrm{g}$

$2 \, \mathrm{\% }$

$22,1 \, \mathrm{^{\circ }C}$

$65,05 \, \mathrm{min}$

$1 \, \mathrm{g}$

$1 \, \mathrm{\% }$

$21,5 \, \mathrm{^{\circ }C}$

$62,48 \, \mathrm{min}$

$1 \, \mathrm{g}$

$1 \, \mathrm{\% }$

 

 

 

 

 

 
 
 

 

 

 

 
 
Tabulka 1: Data z experimentů pro závislost doby tuhnutí na počáteční teplotě kapaliny, kde $T_0$ je počáteční teplota vody, $t_\mathrm {z}$ je čas překročení $0 \, \mathrm{^{\circ }C}$ a $\Delta m$ je odpar vody
 

 

Obrázek 1: Shrnutí měření průběhu teploty vzorku vody v čase; legenda grafu určuje počáteční teplotu v experimentech znázorněných danou křivkou
 

 

Obrázek 2: Výsledek závislosti doby tuhnutí na počáteční teplotě
 

Můžeme vidět, že s rostoucí počáteční teplotou nám klesá doba, za kterou voda ztuhne. Proč tomu asi tak je? Ono totiž teplá voda zmrzne rychleji je velmi zavádějící úsloví. Pojem teplota se zde vztahuje k průměrné teplotě v objemu kapaliny. Tohoto si všiml ve svém řešení Viktor Materna, který správně podotknul, že teplota v různých místech kapaliny je jiná a tento rozdíl teplot je markantnější u kapaliny s vyšší počáteční teplotou.


Zadání 3. série

V minulých číslech jsme experimentálně dokázali teorii mladého fyzika Bartoloměje, který se domníval, že teplá voda zmrzne rychleji než studená.2 Když jsme podle Bartolomějova vzoru vyzkoušeli naměřit i to, jak se tento jev projevuje na různých kapalinách, před námi vyvstal další problém: jak ovlivňuje průběh tuhnutí okolí? Poté, co Bartoloměj vyzkoušel, jak se tento jev projevuje na ostatních kapalinách, zkoumal dále, jak se na průběhu tuhnutí kapaliny projeví změny v okolí. Nejprve zkusil zaměnit nádoby a naměřit nějaké pokusy s alespoň dvěma nádobami s rozdílnými rozměry ze stejného materiálu. Poté zkusil zaměnit i materiál podloží nádoby3. Nakonec se zamyslel, jak ovlivňuje výkon mrazáku dobu tuhnutí.

Jak jste si mohli všimnout ve vzorovém řešení 1. série obsaženém v tomto čísle, průběh a doba tuhnutí závisí na způsobu odvodu tepla z kapaliny. Tento odvod tepla závisí na veličině zvané tepelný tok $Q_ v$ vyjadřující průnik množství energie válcovou nádobou se stěnou o tloušťce $l$ přes plochu kolmou na směr proudění tepla $S$ při rozdílu teplot $\Delta t$ prostředí dotýkajících se vodícího předmětu (zde nádoby) z obou stran. Materiál, který také ovlivňuje snadnost/nesnadnost průtoku tepla předmětem, je zastoupen veličinou $\lambda $ neboli součinitelem tepelné vodivosti. Vzorec pro výpočet velikosti tepelného toku pro válcovitou nádobu vypadá takto:

\begin{equation} Q_ V = \frac{\lambda S (t - t_{p1})}{l} + \pi \frac{r_2 + r_1}{r_2 - r_1} \lambda h (t - t_{p2}) \end{equation}

Doplňme, že $l = r_2- r_1$ je zároveň rozdíl vnitřního poloměru $r_1$ a vnějšího poloměru $r_2$. První sčítanec ve vzorci reprezentuje tepelný tok přes stěnu nádoby a druhý sčítanec reprezentuje tepelný tok přes dno nádoby, které je vlastně rovinná stěna. Pokud budeme opravdu důslední, tak v prvním a druhém sčítanci bude $\Delta t$ rozdílné, jednou se týká teploty vzduchu v mrazáku a podruhé teploty dna mrazáku.


Problém:

Změřte závislost teploty kapaliny na čase pro dvě různé nádoby a poté i pro dvě různá podloží z různých materiálů. Jak materiál nádoby a podloží ovlivňuje průběh tuhnutí? Jak závisí doba tuhnutí na výkonu mrazáku? Odhadněte číselně pro váš konkrétní mrazák. Diskutujte závislost parametrů vaší nádoby a parametrů jejího okolí na velikost tepelného toku. Pokud jste použili nádobu, která nemá válcovitý tvar, vzorec pro výpočet tepelného toku si najděte např. v odborné literatuře či na internetu.


1) Přehlednější grafy v barevné podobě jsou k nahlédnutí v PDF verzi čísla na našem webu.

2) Proč tomu tak je, se můžete dozvědět v řešení 1. čísla.

3) Podložím rozumíme to, na čem vaše nádoba stojí.

4) např. studijní text Fyzikální olympiády: http://fyzikalniolympiada.cz/texty/texttz.pdf

Stejně


Téma 2: Principy kryptografie

S jakýmikoli dotazy se nebojte ozvat do naší e-mailové konference krypto@mam.mff.cuni.cz. Příspěvky zaslané do této konference dostanou organizátoři i všichni účastníci, kteří k tématu poslali nějaké řešení.

5. díl: Elektronický podpis

Text vydaný v čísle (PDF)

Ve třetím problému je úkolem najít RSA klíč (veřejnou a případně i privátní část), který byl využit pro podepsání PDF dokumentu se zadáním tématu v pátém čísle, který je též odkazován výše.

Pro vyřešení čtvrtého problému budete potřebovat tento privátní klíč ve formátu PEM. Některé prohlížeče nejsou ochotné stahovat soubory s příponou PEM, nabízíme proto též ten samý soubor pouze se změněnou příponou. Použitý je asi nejrozšířenější formát souboru pro uchovávání privátního klíče definovaný ve standardu PKCS#1 a popsaný v RFC 3447.

4. díl: Asymetrické šifrování

Text vydaný v čísle (PDF)

3. díl: Módy blokových šifer

Text vydaný v čísle (PDF)

Cílem problémů 1 a 2 ve třetím čísle je ověřit, jaký má vliv mód blokové šifry na výsledek šifrování. Kvůli snadné vizualizaci výsledků jsme se rozhodli šifrovat obrázky.

Aby byla práce s obrázky co nejjednodušší, doporučujeme využít obrázky ve formátu PPM. Pro převod libovolného obrázku do tohoto formátu lze využít grafický editor Gimp (při převodu vyberte binární variantu formátu). Zobrazení obrázku je možné buďto opět Gimpem nebo celou řadou dalších programů. Pro uživatele Windows můžeme doporučit například IrFanView, na Linuxu dobře poslouží eog.

Formát PPM obsahuje krátkou hlavičku definující nezbytné vlastnosti obrázku, za kterou následují vlastní obrazová data. Aby bylo možné zašifrované obrázky opět zobrazit, budeme šifrovat pouze obrazová data. Můžete zašifrovat libovolný obrázek, který si vyberete, a nebo využít náš předpřipravený portrét Rikiho. V tomto obrázku zabírá hlavička 15 bytů. U předpřipraveného obrázku se tedy vnitřní strukturou formátu PPM nemusíte vůbec zabývat. Stačí když při šifrování přeskočíte prvních 15 bytů.

2. díl: Hashovací funkce

Text vydaný v čísle (PDF)

Pro zájemce nabízíme přímo ke stažení implementaci hashovací funkce RIKSHA v jazyku Python.

1. díl: Substitučně-permutační sítě a AES

Text vydaný v čísle (PDF)

 

Stejně


Téma 3: Neznámý měsíc

Obsah:

1. díl

2. díl

Pozor, tato stránka není aktuální! Aktualizovaný seznam všech čísel v PDF naleznete zde. Za problémy se omlouváme.

1. díl

Byli jste vysláni do jedné z hvězdných soustav objevených výzkumníky institutu M&M, specificky prozkoumat soustavu M&M-25 (podle jednoho ze standardních značení „objevitel-pořadové číslo objevené hvězdy-planeta měsíc“). Nejzajímavější se vám zdál měsíc M&M-25-d I. Tento měsíc má velikost i hustotu atmosféry přibližně stejnou jako Země a nemá vázanou rotaci. Planeta, kterou obíhá, je velikostí podobná Uranu, má ale výrazněji viditelné bouře -- podobné těm, jaké jsou na Jupiteru. Při vstupu do atmosféry měsíce se vaše loď začala rozpadat, tak jste ji opustili v únikovém modulu a následně úspěšně přistáli. Máte prostředky pro přežití, ale přišli jste o veškeré pokročilé vybavení. Než se jej vydáte hledat, bylo by dobré zjistit o planetě i měsíci vše, co půjde zjistit pomocí improvizovaného vybavení vyrobeného z vám dostupných předmětů -- např. máte jídlo, igelitové balíčky, nějaké ulomitelné části lodi… Bude také dobré zavést nějaký navigační systém -- jak definovat souřadnice, podle čeho určovat pozici. Pokud to nevymyslíte jinak, zamyslete se alespoň jak to udělat, kdybyste měli stopky a metr.


Úloha 1:

Zaveďte navigační systém a navrhněte nástroje a metody pro navigaci.


Úloha 2:

Zjistěte gravitační zrychlení, velikost, parametry rotace a oběžné dráhy měsíce a planety.


Problém:

Můžete určit ještě něco jiného pomocí obecně dostupných předmětů – např. kdybyste měli lékárničku či nějakou kosmetiku?


Kuba a Kubo; kusnir.jk@gmail.com
e-mailová konference: mesic@mam.mff.cuni.cz

2. díl

Druhá časť tématka je tu a my chceme, abyste prišli na čo najviac jednoduchých spôsobov, ako niečo zistiť o našom neznámom mesiaci. Planéty sa v dnešnej dobe hlavne skúmajú družicami s moderným vybavením. Je však zaujímavé, ako naši predkovia v novoveku a stredoveku dokázali zistiť napríklad polomer Zeme, tiažové zrýchlenie a dobu obehu okolo Slnka a to jednoduchými a nenáročnými experimentami. Jednoduchý spôsob, ako zistiť napríklad tiažové zrýchlenie, je pozrieť sa na vzorce, kde sa objavuje tiažové zrýchlenie, a z nich ho vypočítať. Stále môžete posielať riešenia úloh a problémov z prvého čísla.


Problém 1:

Vedeli by ste určiť odklon rotačnej osi mesiaca od ekliptiky mesiaca s bežne dostupnými vecami? Ak nie, čo by ste minimálne potrebovali?


Problém 2:

Potvrďte prítomnosť magnetického poľa na povrchu mesiaca. Vedeli by ste určiť, či toto magnetické pole generuje mesiac, planéta alebo aj obe zároveň?


Kuba a Kubo; kusnir.jk@gmail.com
e-mailová konference: mesic@mam.mff.cuni.cz

Stejně


Téma 4: Algoritmy od nuly (do $n$)

Obsah:

1. díl: Stavíme počítač

2. díl: Rekurze

Pozor, tato stránka není aktuální! Aktualizovaný seznam všech čísel v PDF naleznete zde. Za problémy se omlouváme.


Stavíme počítač

Slovo úvodem

Jak je již z názvu patrné, v našem témátku se budeme zabývat algoritmy. Co je to takový algoritmus? Žádná oficiální definice neexistuje. Dá se třeba říct, že je to přesný popis postupu, jak něco udělat. V tomto pojetí by algoritmem mohl být třeba dobře popsaný recept na smažení palačinek nebo návod na složení židle z IKEA. My se ale omezíme pouze na algoritmy, které jsou ve výsledku určeny pro zpracování počítačem. Po počítači nemůžeme chtít, aby nám usmažil palačinky (tedy, chtít to samozřejmě můžeme). Co po něm naopak chtít budeme, je například sečíst dvě čísla nebo určit, jestli se v posloupnosti čísel vyskytuje dané číslo. Náš algoritmus bude mít vždy vstup (data, se kterými má počítat) a výstup (výsledek). V případě prvního algoritmu by tedy vstupem byla dvě čísla a výstupem jejich součet, vstupem pro druhý algoritmus by byla posloupnost $n$ čísel a hledané číslo $k$ a výstupem informace, zda se číslo $k$ v posloupnosti vyskytuje, případně na které pozici.

Během řešení témátka se budeme snažit pro různé problémy vymyslet algoritmy, které vždy nejen vypíší správný výsledek, ale udělají to v co nejkratším čase. Algoritmus, který odpovídá vždy správně, ale výpočet by mu na dnešních počítačích již pro krátké vstupy trval několik miliard let, pro nás, jak jistě uznáte, není příliš užitečný (a brzy uvidíte, že omylem vymyslet takový algoritmus není vůbec složité).

Při vymýšlení algoritmů budeme, jak název napovídá, začínat úplně od nuly. Body tedy dáváme za to, že jste vymysleli řešení, a ne za sepsání algoritmu, který jste již dobře znali. Také věříme, že M&Mko řešíte hlavně proto, abyste se něco nového naučili (a ne jen kvůli bodům). Pokud tedy řešení některých zde zmíněných problémů znáte, pusťte se raději do jiného témátka nebo jiné úložky tohoto témátka, které pro vás budou větší výzvou, nebo si vhodnou úložku k řešení sami vymyslete.

Počítač

Algoritmy nebudeme spouštět na skutečném počítači – museli bychom brát ohled na spoustu technických detailů, které by nám zabraňovaly soustředit se na samotný algoritmus. Místo toho si tedy vymyslíme vlastní teoretický model počítače. Budeme od něj chtít, aby byl co nejjednodušší a aby zároveň jeho fungování co nejlépe odpovídalo skutečnému počítači (tedy aby algoritmy, které jsou na něm rychlé, byly rychlé i na skutečném počítači a naopak).

Protože zavést takový model od nuly dá trochu práci, ukážeme vám nejdříve jeho verzi, která bude obsahovat o trochu pokročilejší konstrukce, zato bude jednodušší na pochopení a používání. Nemusíte se ale bát, že bychom vás o skutečně minimalistický model ochudili – naleznete ho na konci tohoto textu.

Náš počítač má paměť, do které si můžeme ukládat proměnné. Proměnná má vždy nějaké jméno a je v ní uloženo jedno celé číslo. Počítač umí počítat (tedy provádět operace $+$, $-$, $\cdot $, $/$) s čísly uloženými v proměnných a přiřazovat je do jiných proměnných. Protože umíme do proměnných ukládat jen celá čísla, funguje dělení jako dělení se zbytkem, ale zbytek se nikam neukládá (tedy $8/3 = 2$). Na první pohled by se mohlo zdát, že je velmi omezující, že umíme pracovat pouze s celými čísly. Můžete si ale zkusit rozmyslet, že třeba text nebo racionální čísla se dají jednoduše zakódovat pomocí celých čísel.

Když chceme na našem modelu něco spočítat, rozepíšeme náš algoritmus jako jednotlivé instrukce, které má počítač provést, dáme mu je a on je postupně jednu po druhé provádí. Takovému seznamu instrukcí říkáme kód nebo program. Může vypadat například takto:

  1.     a $\gets $ 4 (do proměnné a přiřaď číslo 4)
  2.     b $\gets $ 5 (do proměnné b přiřaď 5)
  3.     soucet $\gets $ a $+$ b (do proměnné soucet přiřaď součet a $+$ b, tedy číslo 9)

Náš program sčítá čísla. Sčítá ale vždy jen čísla 4 a 5, což není moc užitečné. Potřebovali bychom, aby náš algoritmus (sečtení dvou čísel) šlo spustit pro libovolný vstup (tedy pro libovolná 2 čísla) a nemuseli jsme kvůli tomu psát pokaždé nový program. V praxi bychom museli vstup nějak načíst (třeba z klávesnice či souboru). My budeme předpokládat, že máme instrukci na načtení čísla ze vstupu a vypsání čísla nebo textu na výstup. Program tedy bude vypadat následovně:

  1.     a $\gets $ přečti číslo
  2.     b $\gets $ přečti číslo
  3.     soucet $\gets $ a $+$ b
  4.     Vypiš soucet

Vezměme si nyní další problém z úvodu tohoto textu. Chceme najít určené číslo v posloupnosti délky $n$. Abychom mohli problém vyřešit, museli bychom jako vstup dostat kromě čísla $n$ a čísla, které hledáme, ještě dalších $n$ proměnných – prvky posloupnosti. Stejně tak na výstup bychom někdy mohli potřebovat vypsat třeba $n$ proměnných. Pojmenovávání $n$ proměnných by bylo poněkud nepraktické, proto si zavedeme konstrukt, kterému budeme říkat pole. Pole je prostě pojmenovaná posloupnost celých čísel, která má předem určenou délku. V informatice je zvykem číslovat prvky pole od nuly a my budeme tento zvyk dodržovat. K prvkům pole budeme přistupovat tak, že za název pole napíšeme pozici příslušného prvku, tedy např. seznam[8] je devátý prvek v poli seznam (protože číslujeme od nuly). Jednotlivé prvky pole se pak chovají jako proměnné, a můžeme s nimi tedy dělat to, co s proměnnými – sčítat, odčítat, násobit, dělit (celočíselně), přiřazovat do nich, ale nejde třeba naráz přičíst jedničku ke všem číslům v poli. Pole navíc umí oproti proměnným to, že ho můžeme indexovat proměnnou. Tedy pokud je třeba v proměnné a hodnota 8, pak seznam[a] je to samé, co seznam[8]. Také nesmíme zapomenout, že u pole musí být určena maximální délka, nemůžeme tedy pole rovnou používat (jak to děláme u proměnných), ale musíme počítači napřed říct, aby vyrobil pole dané délky, tedy např. „vyrob pole seznam délky $n$“ a až poté „seznam[i] $\gets $ 13“.

Chybí nám ještě poslední dvě instrukce – podmínka a cyklus.

Podmínka obsahuje nějaký výraz, u kterého lze určit, zda je, či není pravdivý. Výraz má tvar „proměnná nebo číslo $<$, $>$, $\ge $, $\le $, $=$ jiná proměnná nebo číslo“ (např. a $>$ 0). Můžeme také použít negaci a spojit více výrazů pomocí OR, nebo AND1. Pod podmínku pak napíšeme část kódu, která se má provést, pokud podmínka platí, a volitelně i část kódu, která se má provést, pokud podmínka neplatí. Můžeme tedy napsat:

  1.     a $\gets $ vstup
  2.     Pokud (a$/$2)$\cdot $2 $=$ a:
  3.         Vypiš „Vstup je sudý“
  4.     Jinak:
  5.         Vypiš „Vstup je lichý“

Všimněme si, že u lichých čísel se podíl při dělení dvojkou zaokrouhlí dolů, a tedy opravdu nenastane v podmínce rovnost.

Nyní si zavedeme další konstrukt. Budeme mu říkat cyklus a vypadá následovně: Dokud platí „podmínka“, tak dělej „část kódu, která se má provádět“. Cyklus můžeme použít například k napsání programu, který násobí dvě přirozená čísla, aniž by použil operaci násobení.

  1.     a $\gets $ vstup
  2.     b $\gets $ vstup
  3.     pocetScitani $\gets $ 0
  4.     soucin $\gets $ 0
  5.     Dokud (pocetScitani $<$ b) tak:
  6.         soucin $\gets $ soucin $+$ a
  7.         pocetScitani $\gets $ pocetScitani $+$ 1
  8.     Vypiš soucin

To je zatím k našemu modelu vše. Pojďme si teď zkusit nějaký užitečný algoritmus napsat.

Algoritmus – hledání čísla v poli

Nyní si ukážeme jednoduchý algoritmus, který zjistí, zda se v posloupnosti čísel nachází číslo 42. (Zatím nás nebude zajímat, na které pozici je. Můžete si rozmyslet, jak algoritmus upravit, abychom pozici zjistili.) Budeme předpokládat, že víme, kolik čísel dostaneme. Pomocí cyklu si pak ze vstupu uložíme čísla do pole. (Tento technický detail nebudeme pokaždé zmiňovat – dále už budeme vždy předpokládat, že vstup máme na začátku uložen v paměti.)

Pomocí cyklu budeme postupně procházet celé pole. Vytvoříme si proměnné pozice a nalezeno. V proměnné pozice si budeme pamatovat pozici v poli, na které zrovna hledáme číslo 42 a kterou po každém průchodu cyklem zvýšíme o jedna. Takovou proměnnou potřebujeme, abychom věděli, jak v podmínce cyklu otestovat, zda máme pokračovat. V proměnné nalezeno bude na začátku 0 symbolizující, že jsme 42 ještě nenalezli, a když ji najdeme, nastavíme tuto proměnnou na hodnotu 1. V každém průchodu cyklem pak podmínkou zkontrolujeme, zda na pozici dané proměnnou pozice není číslo 42. Pokud je, tak proměnnou nalezeno nastavíme na 1, jinak jí necháme původní hodnotu. Po doběhnutí programu tedy můžeme díky proměnné nalezeno zjistit, zda jsme číslo 42 našli, nebo nenašli.

Celý algoritmus by tedy vypadal asi následovně:

     Vstup: posloupnost čísel v poli posloupnost a jejich počet v proměnné n

  1.     pozice $\gets $ 0
  2.     nalezeno $\gets $ 0
  3.     Dokud pozice $<$ n:
  4.         Pokud posloupnost[pozice] $=$ 42:
  5.             nalezeno $\gets $ 1
  6.     pozice $\gets $ pozice $+$ 1

     Výstup: Proměnná nalezeno, ve které je uložena 1, právě pokud je číslo 42
v posloupnosti obsaženo

Můžeme si navíc všimnout, že jsme k ničemu nepoužili to, že jsme hledané číslo znali předem, a že jsme na řádce 4 mohli kontrolovat rovnost s proměnnou, ve které by bylo uložené hledané číslo. Umíme takto tedy zjistit, zda je v poli libovolné číslo uložené v proměnné.

Časová složitost

V úvodu jsme tvrdili, že se budeme snažit vymýšlet algoritmy, které spočtou výsledek v co nejkratším čase. Co to ale na našem novém počítači vlastně znamená? Protože na teoretickém modelu jen těžko můžeme měřit čas běhu programu, budeme místo toho počítat provedené instrukce. Vztah ke skutečným počítačům je zde zřejmý – skutečné procesory opravdu mají sadu instrukcí (do kterých je každý program přeložen) a vykonat jednu instrukci trvá nějakou krátkou dobu. Počet vykonaných instrukcí tedy nějakým způsobem odpovídá době běhu programu.

Za instrukci považujeme některou z operací $\gets $ (přiřazení), $+$, $-$, $\cdot $, $/$ nebo určení pravdivostní hodnoty jednoduchého výrazu.

Můžete se pokusit spočítat, kolik instrukcí provede výše popsaný algoritmus (nezapomeňte, že některé instrukce uvnitř cyklu bude počítač provádět $n$-krát). Už jen to, že se autoři tohoto textu nejsou schopni shodnout, zda to vyjde $4n+4$, nebo $6n+3$, napovídá, že spočítat přesný počet instrukcí není vůbec jednoduché a u složitějších algoritmů téměř nemožné. Navíc když spustíme program na skutečném počítači, závisí počet instrukcí na tom, jak přesně funguje procesor daného stroje. Počítače jsou také ve skutečnosti různě rychlé, takže stejná instrukce bude trvat na různých počítačích různě dlouho. Co s tím? Místo toho, abychom počítali přesný počet instrukcí, budeme ho počítat jen zhruba. Konkrétně nebudeme řešit konstanty, kterými $n$ násobíme a které k němu přičítáme. Důvodem, proč to není zas tak špatné řešení, je, že když bude vstup dostatečně dlouhý (a tedy $n$ dostatečně velké), budou konstanty zanedbatelně velké vůči něčemu, co závisí na $n$. Například pokud porovnáme časové složitosti $20n$ a $3n^2$, tak vidíme, že již pro poměrně malá $n$ budou konstanty zanedbatelné vzhledem k rozdílu způsobenému kvadratickou funkcí.

V našem algoritmu závisí počet instrukcí na $n$ lineárně – počet provedených instrukcí je nejvýše přímo úměrný počtu čísel na vstupu. Není těžké si uvědomit, že rychlejší algoritmus nemůže existovat – na každé z $n$ zadaných čísel se totiž musíme alespoň jednou podívat a jen na to potřebujeme alespoň $n$ instrukcí.

Abychom si tedy ulehčili práci a nemuseli jsme počet instrukcí počítat přesně, zavádíme takzvanou „óčkovou notaci“2. Óčková notace je horní odhad na počet instrukcí, které algoritmus provede, pokud zanedbáme multiplikativní konstanty a spustíme ho pro dostatečně velký vstup. 3 Pokud má tedy algoritmus časovou složitost $\mathcal{O}(n^2)$, znamená to, že pro dostatečně velká $n$ existuje konstanta $k$ taková, že algoritmus provede maximálně $k \cdot n^2$ instrukcí (například pro každé $n$ větší než 100 provede algoritmus maximálně $42 \cdot n^2$ instrukcí). Také si můžeme všimnout, že například algoritmus, který vždy provede $5 + 2n + 3n^4$ instrukcí běží v čase $\mathcal{O}(n^4)$, jelikož $5 + 2n + 3n^4 < 5n^4$ pro každé $n > 1$ (ze stejného důvodu bychom mohli tvrdit, že tentýž algoritmus běží v čase $\mathcal{O}(2^ n)$, tato informace by ale pro nás nebyla příliš cenná – vždy se snažíme o co nejtěsnější odhad.) O našem algoritmu na hledání čísla v poli tedy můžeme říct, že má časovou složitost $\mathcal{O}(n)$.

V předchozím textu jsme vám trochu zalhali. Náš algoritmus umíme drobně upravit tak, že pro něj půjde najít lepší odhad než $\mathcal{O}(n)$. Stačilo by po každém průchodu cyklem zkontrolovat, jestli už jsme číslo našli, a pokud ano, ukončit provádění smyčky. Pokud by tedy první z čísel v posloupnosti bylo 42, algoritmus by provedl jen konstantně mnoho instrukcí (počet instrukcí by byl nezávislý na $n$), běžel by tedy v čase $\mathcal{O}(1)$. Takový případ ale pro nás není příliš zajímavý, protože nikdy nevíme, jaká čísla na vstupu dostaneme, a nemůžeme se při návrhu algoritmů spoléhat na to, že budeme mít pokaždé štěstí. Pokud tedy není řečeno jinak, budeme vždy určovat časovou složitost v nejhorším případě. Budeme tedy předpokládat, že nepřítel nám zadal vstup tak, aby náš algoritmus běžel co nejdéle. Taky si to můžeme představit tak, že spustíme algoritmus pro všechny vstupy dané délky a budeme počítat ten vstup, na který jsme potřebovali nejvíce instrukcí. S touto definicí složitosti už tedy opravdu platí naše dřívější poznámka, že najít číslo v poli $n$ čísel obecně neumíme rychleji než v čase $\mathcal{O}(n)$.


Úloha 1 [2b]: Vymyslete algoritmus, který zjistí, kde se v poli nachází největší číslo a jaké číslo to je. Můžete předpokládat, že největší číslo je v poli jen jedno.


Tato úložka by měla jít vyřešit podobně jako ukázkový problém výše. Kdykoliv po vás chceme vymyslet algoritmus, rádi bychom slyšeli i jeho časovou složitost. To k algoritmu patří, protože to je v určitém slova smyslu to, co nám říká, jak je daný algoritmus dobrý.

Když už umíme najít maximum v poli, tak není těžké pole setřídit.


Úloha 2 [3b]: Vymyslete algoritmus, který setřídí pole čísel. Jinými slovy, chtěli bychom čísla seřadit podle jejich velikosti.


Tento problém se vám pravděpodobně nepodaří vyřešit v čase $\mathcal{O}(n)$. Pokud ano, určitě nám takové řešení pošlete. Jedná se totiž o slavný otevřený problém, který se informatici snaží vyřešit již po desetiletí. A pokud máte pomalejší řešení, také ho určitě pošlete, i když si myslíte, že by to mohlo jít rychleji.

Lze dokázat, že třídit nejde rychleji než v $\mathcal{O}(n \log n)$, ale tento důkaz předpokládá, že si zakážeme s čísly dělat cokoliv kromě porovnávání. Kdybyste tento důkaz viděli, tak si vzpomeňte na tento předpoklad, díky kterému si důkaz neprotiřečí s tím, že bychom chtěli umět třídit v čase $\mathcal{O}(n)$.


Bonusová verze [+2b]: Vyřešte ten samý problém, ale jen s konstantní pamětí navíc. To znamená, že máte v paměti pole, chcete ho setřídit a smíte při tom využívat libovolné konstantní (tedy nezávislé na $n$) množství proměnných. Už si ale třeba nemůžete pořídit pole, do kterého budete ukládat setříděnou posloupnost. To konkrétně znamená, že setříděná čísla budou na konci muset být v poli, ve kterém jste je dostali (na výstup nic nevypisujte).


Na závěr formálněji popíšeme a odůvodníme chování našeho modelu. Pokud následující část nechcete číst, nijak vám to nebrání v řešení témátka, vážou se k ní ale některé další problémy.

Formální popis modelu

Náš počítač bude mít paměť, která se skládá z nekonečně mnoha paměťových buněk očíslovaných celými čísly (představujte si ji jako nekonečnou posloupnost čtverečků). V každé buňce může být uloženo libovolně velké celé číslo. Číslu buňky budeme říkat adresa. Buňka může být určena dvěma způsoby: Přímou adresací – napíšeme adresu buňky do hranatých závorek (buňku s adresou 3 tedy značíme [3]), nebo nepřímou adresací – do dvojitých hranatých závorek napíšeme adresu buňky, ve které je uložena výsledná adresa buňky (buňku, jejíž adresa je uložena v buňce s adresou 3, tedy značíme [[3]]).

Každý algoritmus, který chceme na našem počítači spustit, musíme zapsat pomocí instrukcí. Počítači tedy předáme seznam instrukcí (ekvivalent kódu napsaného v programovacím jazyce pro skutečné počítače) a do určených paměťových buněk napíšeme vstup. Na reálném počítači by vstup pocházel z nějakého souboru nebo by ho zadal uživatel, ale my budeme pro jednoduchost předpokládat, že ho už máme někde uložený. Počítač poté provede všechny instrukce v takovém pořadí, v jakém jsou zapsány. Až mu instrukce dojdou, skončí. Počítač navíc může pomocí instrukce print postupně vypisovat čísla na výstup. Výstupem je pak posloupnost čísel, které vypsal za dobu svého běhu.

Nyní již přímo k instrukcím našeho počítače. Typická instrukce bere dva argumenty – každý z nich je (přímo či nepřímo adresovaná) paměťová buňka, nebo celé číslo. Pokud je argumentem buňka, instrukce si vždy přečte číslo, které je v ní uložené, a dále počítá s ním. S takto určenými celými čísly instrukce něco provede a výsledek uloží do předem určené paměťové buňky.

Samotné instrukce budou následující:

  • Instrukce přiřazení $\gets $ bere jeden argument a jeho hodnotu uloží do určené buňky. Například [1] $\gets $ [2] přečte číslo z druhé paměťové buňky a uloží ho do první paměťové buňky.

  • Instrukce $+$, $-$, $\cdot $ a $/$ berou vždy dva argumenty, spočítají jejich součet, rozdíl, součin nebo podíl (zaokrouhlený dolů na celé číslo) a výsledek uloží do dané buňky. Například [[4]] $\gets $ [1] $+$ 2 vezme číslo uložené v první buňce, přičte k němu dvojku a výsledek uloží do buňky, jejíž adresa je uložena v buňce číslo 4.

  • Instrukce skoku nebere žádný argument, ale „skočí“ v našem programu na označené místo. Někam mezi instrukce tedy napíšeme klíčové slovo (třeba „bagr“). Pokud na jiném místě napíšeme instrukci „skok na bagr“, náš počítač začne provádět instrukce, které následují za slovem „bagr“. Můžeme tím tedy způsobit, že se některé instrukce přeskočí, nebo naopak provedou víckrát.

  • Instrukce podmíněného příkazu bere dva argumenty, podmínku, kterou mají splňovat, a libovolnou jinou instrukci s jejími argumenty. Podmínka je vždy některý z matematických operátorů ($<$, $>$, $\ge $, $\le $, $=$, $\neq $). Pokud je podmínka splněna, provede se daná instrukce. Např. „Pokud [1] $>$ 1, [2] $\gets $ 3“ uloží do druhé buňky číslo 3, pokud je v první buňce uloženo číslo větší než 1.

  • Instrukce print vypíše argument na výstup.

Tím je náš model kompletní.

Model jsme se snažili zavést tak, aby byl co nejjednodušší, ale zároveň uměl spočítat vše, co umí dnešní počítače, a to se stejnou časovou složitostí. Výhodou našeho nového modelu je, že má méně instrukcí a lépe se s ním pracuje matematicky (třeba se v něm lépe dokazuje, že problém nelze algoritmicky vyřešit), zatímco v tom předchozím se zase lépe uvažuje o programech. Můžete si zkusit rozmyslet, že ve skutečnosti není o nic slabší než náš dříve zavedený uživatelsky přívětivější model…


Problém: Zkuste dokázat, že jakýkoliv program, který funguje na modelu, který jsme si pro větší pohodlnost dříve zavedli, lze přepsat tak, aby fungoval i na tomto minimalistickém modelu se stejnou časovou složitostí. Můžete to samozřejmě dokázat jen pro nějakou část – například vysvětlit, jak v minimalistickém modelu vytvořit pole, podmínku či cyklus.


Možná vám přijde zvláštní, že jsme schopni na našem modelu počítat s libovolně velkými čísly v konstantním čase. Říkáte si, že to asi neodpovídá realitě, protože určitě bude existovat vážně velké číslo, které na opravdový počítač ani nepůjde uložit, natož aby s ním počítače uměly pracovat v konstantním čase (ať už to u reálných počítačů znamená cokoliv). Nám to také přijde zvláštní. Je na vás, abyste tento problém vyřešili. Zkuste náš model nebo způsob počítání složitosti nějak upravit, nebo si vymyslet vlastní výpočetní model a počítat časovou složitost na něm. Můžete samozřejmě popsat více různých možností.


Problém: Navrhněte výpočetní model nebo způsob počítání časové složitosti, který bude odpovídat realitě v tom, že operace s dlouhými čísly trvají déle než s krátkými.


Ptáte se, zda je to opravdu třeba? Zatím jsme si neukázali žádný způsob, jak by šlo konstantní operace s dlouhými čísly zneužít. Jedním z problémů, při jehož řešení to jde, je například již zmíněné třídění čísel, které lze v našem modelu provést v $\mathcal{O}(n)$, a tedy není tak úplně pravda, že by to byl slavný otevřený problém, jak jsme psali. Ale v libovolném rozumném modelu tomu tak je. Další takový problém je násobení matic, které lze zrychlit tím, že zakódujeme $n$ čísel do jednoho a poté umíme provést aritmetickou operaci na $n$ číslech v čase $\mathcal{O}(1)$. Tyto konstrukce však nejsou úplně jednoduché, a nebudeme je zde tedy ukazovat. Pilný řešitel si je může vymyslet sám a pak o tom napsat pro ostatní.


Těžký problém: Vymyslete nějaký algoritmus, který zneužívá operace s dlouhými čísly v konstantním čase. (Řešení tohoto problému nebudeme zveřejňovat, bude tedy možnost posílat k němu řešení po celý školní rok.)


Kuba a Tom; domestomas+mam@gmail.com
e-mailová konference: algoritmy@mam.mff.cuni.cz


1) AND a OR jsou logické spojky, které jste pravděpodobně brali ve škole v rámci výrokové logiky pod názvy konjunkce a disjunkce. Složený výrok se spojkou AND je pravdivý právě tehdy, když jsou pravdivé oba výroky, a se spojkou OR právě tehdy, když je pravdivý alespoň jeden z nich.

2) Přestože pojem „óčková notace“ nezní úplně odborně, anglicky se toto značení skutečně nazývá „Big O notation“.

3) Formální definici si můžete přečíst třeba na Wikipedii: https://en.wikipedia.org/wiki/Big_O_Notation


 

 

 

Rekurze

Slovo úvodem

Vítáme vás u dalšího dílu našeho témátka pro začínající informatiky (a také pro zvídavé fyziky a matematiky). Pokud jste zatím nečetli první díl, snažně vám doporučujeme s ním začít – budeme na něj navazovat. Znovu pro jistotu připomínáme, že cílem témátka je vymyslet si postupně základy teoretické informatiky. Body tedy dáváme za to, že jste vymysleli řešení, a ne za sepsání algoritmu, který jste již dobře znali. Také věříme, že M&Mko řešíte hlavně proto, abyste se něco nového naučili (a ne jen kvůli bodům). Pokud tedy řešení některých zde zmíněných problémů znáte, pusťte se raději do jiného témátka nebo jiného problému tohoto témátka, které pro vás budou větší výzvou, nebo si vhodný problém k řešení sami vymyslete. Také bychom chtěli doplnit, že u většiny problémů očekáváme především slovní popis algoritmu a ideálně i časovou složitost. Když přidáte i kód, může nám to pomoct lépe pochopit vaši myšlenku a rozhodně vám za něj body neubereme, neměl by ale nahrazovat slovní popis.

Dnes si ukážeme, jak funguje takzvaná rekurze, důležitá technika designu algoritmů. Ač, striktně vzato, není potřeba, protože libovolný algoritmus používající rekurzi můžeme přepsat v modelu, jenž jsme si ukázali minule, často výrazně zjednodušuje vymýšlení i následné programování algoritmu. Předtím si ale ještě řekneme, co jsou to funkce.

Funkce

Při programování často potřebujeme dělat nějakou věc opakovaně na různých místech v programu. Například, kdybychom programovali program na kreslení geometrických útvarů, budeme pravděpodobně často potřebovat počítat délku přepony trojúhelníku pomocí Pythagorovy věty. Proto jsou v programovacích jazycích takzvané funkce, které nám dovolují si „pojmenovat kus kódu“, a kdykoliv potřebujeme spočítat délku přepony, zavoláme funkci, která to za nás udělá. Taková funkce a její volání může vypadat třeba takto:

  1.    Funkce délka_přepony($x$, $y$):
  2.        Vrať $\sqrt {x^2 + y^2}$
  3.    
  4.    Z $\gets $ délka_přepony(2, 3)

Zamysleme se, jak přesně funkce fungují. Funkce se zavolá s nějakými argumenty (v našem příkladu proměnné $x$ a $y$), čímž nastavíme pro funkci hodnoty proměnných, které jsme definovali jako argumenty. Tyto a všechny ostatní proměnné definované ve funkci jsou lokální pro jedno zavolání (spuštění) dané funkce a když se funkce dokončí, zaniknou. Naopak k proměnným mimo funkci, které jsme nepředali jako argument, se nedostaneme. Může se tedy stát, že bude jinde v programu existovat proměnná $x$, která bude mít jinou hodnotu, než proměnná $x$ lokální pro konkrétní volání funkce délka_přepony.

Postupně se budou vykonávat instrukce funkce řádek po řádku, jako kdekoliv jinde v programu. Co se stane, když dojdeme na konec funkce, nebo k příkazu vrať? Chtěli bychom se vrátit přesně na místo, ze kterého jsme funkci zavolali. Přesně to se stane, protože programovací jazyk si za nás zapamatoval místo, ze kterého jsme funkci zavolali, a díky tomu na něj dokáže skočit, když funkce skončí. Pokud byla funkce ukončena příkazem vrať, vrátí se daná hodnota, jak můžete vidět v příkladu, kde nám funkce vrátí hodnotu $\sqrt {13}$.


Problém 1 (4b): Zkuste na našem formálním modelu, který jsme si vytvořili na konci minulého dílu, vytvořit funkce. Nezapomeňte, že po svém ukončení se funkce musí vrátit hned za místo, ze kterého byla zavolána.


Rekurze

Co se přesně bude dít při zavolání funkce délka_přepony by mělo být celkem intuitivní – funkce se spustí, spočte se výsledek, ten se vrátí a budeme pokračovat ve vykonávání instrukcí na místě, ze kterého jsme funkci volali. Co ale třeba následující funkce na výpočet Fibonacciho čísel?

1. Funkce fibonacciho_číslo($n$):
2.   Pokud $n$ = 0:
3.      Vrať 0
4.   Pokud $n$ = 1:
5.      Vrať 1
6. Vrať fibonacciho_číslo($n-1$) + fibonacciho_číslo($n-2$)

Už by nám mělo být jasné, co se stane, když $n$ bude 1, nebo 2. Když ale bude $n$ rovno 3 nebo víc, ani jedna z prvních dvou podmínek nebude splněna a tedy se při vyhodnocování funkce dostaneme až na řádek 6. Tady by se mohlo zdát, že funkce není dobře definovaná, protože její definice závisí na sobě samé. Není tomu ale tak. Abychom pochopili, co přesně se bude dít, uvědomme si, jak funkce fungují. Když funkci zavoláme, začne se vyhodnocovat řádek po řádku a když vyhodnocování skončí, pokračuje se ve vykonávání instrukcí na místě, odkud se funkce volala. Pokud tedy funkce zavolá sebe samou, začne se se vyhodnocovat ještě jednou od začátku a když přijde k příkazu vrať, skočí na místo odkud jsme ji zavolali, totiž do sebe samé. Hodnoty proměnných jsou lokální pro každé volání funkce, a tedy se jednotlivá volání nebudou navzájem ovlivňovat tím, že by si jednotlivá volání funkce „navzájem sahala na proměnné“.

Pokud tedy budeme chtít spočítat čtvrté Fibonacciho číslo, bude funkce
fibonacciho_číslo zavolána celkem pětkrát. Následující diagram ukazuje, jak by výpočet probíhal. Každý bod diagramu odpovídá jednomu zavolání funkce fibonacciho_číslo a z každého volání vedou šipky do bodů odpovídajících vykonání funkce z něj zavolané.

Fibbonacciho čísla
Obrázek 1: Výpočet Fibonacciho čísel

 


Problém 2 (1b): Spočítejte faktoriál pomocí rekurze bez použití cyklu. Otázka, kterou je dobré si položit při řešení tohoto problému, je: „Kdybych měl spočítané $(n-1)!$, jak z toho spočítám $n!$?“. Toto je ostatně otázka, kterou je dobré si položit, kdykoliv řešíte nějaký algoritmický problém a která vede na rekurzivní algoritmus (rozmyslete si proč).


Logaritmus

Ze školy možná znáte definici funkce zvané logaritmus. Logaritmus kladného reálného čísla $x$ o základu $a$ je takové reálné číslo $y$, pro které platí $a^ y = x$. Zapisujeme $y = \log _ a x$. Intuitivnější definice je, že logaritmus nám říká, kolikrát musíme základ vynásobit sebou samým, abychom dostali $x$. Platí tedy, že $\log _2 8 = 3$, protože $2^3 = 8$. Pokud se v informatice mluví o logaritmu, myslí se tím v drtivé většině případů logaritmus o základu 2. Stejně to bude i v našem témátku. Pokud tedy píšeme $\log n$, myslíme tím vždy $\log _2 n$.

\includegraphics[height=200pt]{obrazky/tema4-graf_30.pdf}
Obrázek 2: Porovnání lineání funkce s logaritmem

 

\includegraphics[height=200pt]{obrazky/tema4-graf_1000.pdf}
Obrázek 3: Porovnání lineání funkce s logaritmem – pohled z dálky

 

Na obrázku 4 můžete vidět úplný binární strom. Strom se skládá z vrcholů spojených hranami a neobsahuje cykly („větve“ se nikde nespojují). Jednotlivým „vrstvám“ vrcholů říkáme hladiny a číslujeme je od shora a od nuly. Na nulté hladině tedy leží jeden vrchol. Vrcholům, které jsou připojené pod některým vrcholem, říkáme jeho synové (podle rodokmenu, který má podobný tvar) a vrchol, který nemá ani jednoho syna, je list, zatímco vrchol bez otce se nazývá kořen (je vždy právě jeden). Strom na obrázku je navíc binární, protože každý vrchol má maximálně dva syny, a je úplný, protože každý vrchol kromě listů má dva syny a všechny listy leží na stejné hladině. Více se o stromech dozvíte v některém z dalších dílů témátka.

Můžeme si povšimnout, že na každé z hladin je dvakrát více vrcholů než na té předchozí. Na $k$-té hladině (počítáno shora) se tedy nachází $2^ k$ vrcholů (na nulté hladině jich je $1 = 2^0$). Podle zmíněné definice logaritmu tedy platí, že logaritmus počtu vrcholů na dané hladině je číslo hladiny (jinak řečeno hloubka).

\includegraphics[height=5.3cm]{obrazky/tema4-strom_final.pdf}
Obrázek 4: Úplný binární strom

K čemu je nám to dobré? Na stromu je hezky vidět, že logaritmus roste výrazně pomaleji než lineární funkce (když říkáme lineární funkce, budeme vždy předpokládat kladný koeficient u $x$). Graf těchto dvou funkcí můžete vidět na obrázcích 2 a 3. Hlavně se nám ale často stane, že něco – třeba strom všech možných průběhů algoritmu – má tvar úplného binárního stromu. Vizte následující úlohu.

Mějme panelák o $n$ patrech (pro jednoduchost nechť $n$ je mocnina dvojky – pokud není, tak přistavíme imaginární patra navíc aby bylo, a všimneme si, že jsme počet pater nanejvýš zdvojnásobili). Patra jsou standardně očíslována od 0 do $n-1$. Dále mějme dostatek ideálních vajec – tedy vajec, která jsou ve všech možných fyzikálních vlastnostech shodná. Naším cílem je zjistit, z jakého nejvyššího patra můžeme ideální vejce shodit, aby se nerozbilo. Vejce se ale po každém shození rozbije nebo zakutálí, chceme proto výsledek zjistit na co nejméně pokusů. Jak budeme postupovat a kolik pokusů budeme potřebovat v nejhorším případě? Než si přečtete řešení, zkuste se nejdříve zamyslet, jak byste úlohu řešili vy.

Nabízíme následující řešení: Pokud má panelák jen jedno patro, řešení je triviální. V opačném případě vyjdeme do patra číslo $n/2$ a shodíme z něj vajíčko. Pokud se rozbije, musí se nutně rozbít i při pádu ze všech vyšších pater, tudíž nás žádné z těchto pater nezajímá. Můžeme tedy úlohu rekurzivně vyřešit pro prvních $n/2$ pater. Pokud se naopak vajíčko nerozbije, nezajímají nás žádná nižší patra – řešením je buď naše patro, nebo některé z vyšších pater. Vyřešíme tedy úlohu rekurzivně pro horní polovinu paneláku (představte si, že první polovinu paneláku odseknete, zahodíte a druhou polovinu paneláku položíte na zem – z toho by mělo být vidět, že se opravdu jedná o stejný problém poloviční velikosti). Pokud řešení nenajdeme, je řešením naše patro. Na závěr jen vrátíme číslo patra, případně informaci, že takové patro neexistuje (reprezentovanou hodnotou $-1$). Rozmyslete si, jak bude tato vrácená informace „vybublávat“ všemi voláními. Následuje pseudokód:

   Vstup: počet pater $n$, funkce shod_vajicko která vrací 1 pro rozbité a 0 pro
nerozbité vajíčko
1. Funkce hledani_patra($n$, $prizemi$):
2.   Pokud $n = 1$:
3.      Pokud shod_vajicko($prizemi$) $= 0$:
4.         Vrať $prizemi$
5.      Jinak:
6.         Vrať $-1$
7.   Pokud $n > 1$:
8.      Pokud shod_vajicko($prizemi + n/2$) $= 1$:
9.         Vrať hledani_patra($n/2$, $prizemi$)
10.      Jinak:
11.         Vrať hledani_patra($n/2$, $prizemi + n/2$)
Výstup: hledani_patra($n$, 0)

Nyní nám zbývá určit časovou složitost algoritmu. Podobně jako u funkce fibonacciho_cislo si nakreslíme strom rekurzivních volání funkce. Je tady ale jeden zásadní rozdíl. Zatímco u Fibonacciho čísel volala funkce sama sebe vždy dvakrát, nyní se volá vždy pouze jednou. Pokud bychom tedy nakreslili, jak byla funkce skutečně volána, dostali bychom něco, čemu se v teorii grafů říká cesta – byla by to rovná řada vrcholů spojená čarami bez jakéhokoliv větvení.

My si ale pořídíme trochu jiný strom. Nebude znázorňovat průběh jednoho spuštění algoritmu, ale všechny možné způsoby, jak může tento průběh vypadat v závislosti na vstupu. Jinými slovy, bude znázorňovat všechna rozhodnutí, která algoritmus udělal, a proto mu budeme říkat rozhodovací strom. Při každém volání se funkce v závislosti na vstupních parametrech rozhodne, zda pokračovat v hledání správného patra v dolní, nebo horní polovině paneláku. Každý z vrcholů našeho stromu značí jedno zavolání funkce a jeho dva synové tyto dvě možnosti. Pokud je funkce zavolána na vstup velikosti 1, již se dál rekurzivně nevolá a její zavolání je tak reprezentováno některým listem stromu. Tvrdíme, že tento rozhodovací strom bude mít tvar úplného binárního stromu. Proč by to tak mělo být? Když si zkusíte strom nakreslit pro nějaké malé vstupy, které jsou mocniny dvojky, zjistíte, že strom pro vstup velikosti $n$ můžete vytvořit tak, že nakreslíte vedle sebe dvakrát rozhodovací strom pro vstup velikosti $n/2$ a přidáte nový společný kořen a z něj dvě hrany do dvou původních kořenů. Nový kořen totiž značí první volání funkce hledani_patra, ve kterém se rozhodneme, na kterou z polovin paneláku se rekurzivně zavolat. Další průběh algoritmu pro danou polovinu paneláku už je stejný jako pro vstup velikosti $n/2$, a proto má i stejný rozhodovací strom. Stejným způsobem si můžeme uvědomit, že počet listů stromu je vždy roven $n$ – při zdvojnásobení vstupu se totiž zdvojnásobí i počet listů. Pokud bychom chtěli tyto vlastnosti formálně dokázat, použili bychom matematickou indukci (to je taková rekurze pro matematiky). Doufáme ale, že spojitost mezi stromem a algoritmem je vidět, a přesný důkaz zde uvádět nebudeme (pilný řešitel nám ho samozřejmě může do časopisu poslat).

Skutečný průběh algoritmu je tedy cesta z kořene do jednoho z listů. Počet zavolání funkce je tedy roven počtu hladin ve stromu, což je logaritmus počtu listů. Počet listů je ale $n$, čímž dostáváme, že počet volání funkce hledani_patra je $\log n$. Jedno volání funkce trvá konstantně dlouho, celý algoritmus tedy běží v čase $\mathcal{O}(\log n)$ a shodí $\mathcal{O}(\log n)$ vajíček.

Časovou složitost můžeme nahlédnout i bez stromu rekurze. Jak už jsme zmínili minule, každým zavoláním funkce hledani_patra se délka vstupu zmenší na polovinu. Když nás tedy zajímá počet volání, stačí říct, kolikrát musíme $n$ vydělit dvěma, abychom dostali číslo 1. To je samozřejmě tolik, kolikrát musíme dvojku vynásobit samu sebou, abychom dostali $n$, a to je rovno $\log n$. Opět tedy dostáváme časovou složitost algoritmu $\mathcal{O}(\log n)$. Můžete si zkusit rozmyslet, že algoritmus po drobné úpravě (bude třeba $n/2$ zaokrouhlit) funguje se stejnou časovou složitostí i pro vstupy, které nejsou mocniny dvojky.


Problém 3: Náš algoritmus na házení vajíček lze pro některé velikosti vstupů ještě o trochu zlepšit (jen o konstantu). Zkuste si rozmyslet jak a napište nám to.


V minulém díle jsme měli algoritmus na hledání čísla v poli. To obecně nemůžeme umět rychleji než lineárně – na každé číslo se musíme alespoň jednou podívat. Co kdybychom ale měli zaručeno, že je pole setříděné (tedy čísla jsou seřazena vzestupně)? Zkuste se inspirovat naším vajíčkovým algoritmem a vymyslete algoritmus, který v čase $\mathcal{O}(\log n)$ najde dané číslo v setříděném poli (nebo zjistí, že se v poli nenachází).


Problém 4 (2b): Vymyslete algoritmus, který najde v setříděném poli délky $n$ dané číslo v čase $\mathcal{O}(\log n)$. Nezapomeňte na slovní popis algoritmu a zdůvodnění časové složitosti.


Třídění podruhé

Nyní se zamyslíme nad tím, zda by se pomocí rekurze nedal udělat rychlejší třídící algoritmus. V minulém díle jsme vymysleli algoritmus běžící v čase $\mathcal{O}(n^2)$. Teď bychom chtěli něco rychlejšího.

Začneme s otázkou podobnou té u výpočtu faktoriálu: chceme setřídit $n$ čísel. Předpokládejme, že už umíme setřídit $n-1$ nebo méně čísel, a zkusme pomocí toho setřídit všech $n$ čísel. Jedním řešením by bylo setřídit prvních $n-1$ čísel a poslední číslo poté vložit do setříděné posloupnosti (zkuste si rozmyslet detaily). Prozradíme, že tak získáme algoritmus běžící v čase $\mathcal{O}(n^2)$. Je tedy třeba vymyslet jiný přístup. V následujících dvou problémech si vymyslíte, jak dosáhnout časové složitosti lepší než $\mathcal{O}(n^2)$.


Problém 5 (3b): Předpokládejme, že máme dvě setříděné posloupnosti čísel (mohou být různě dlouhé). Vymyslete, jak s co nejlepší časovou složitostí z těchto dvou posloupností udělat jednu setříděnou posloupnost obsahující čísla z obou. Při vyjadřování časové složitosti použijte $n$ jakožto celkový počet čísel. Nezapomeňte určit časovou složitost vašeho algoritmu.


Při řešení tohoto problému si doporučujeme zkusit napsat dvě setříděné posloupnosti a napsat ručně výstupní posloupnost. Při vymýšlení algoritmů je často dobré si zkusit výsledek na malých vstupech spočítat ručně – třeba si při tom všimnete, jak to udělat efektivně.: Při řešení následujícího problému se vám bude pravděpodobně hodit využít řešení problému 4 výše. Pokud jste ho nevyřešili, můžete nyní předpokládat, že jde řešit v čase $\mathcal{O}(n)$.


Problém 6 (4b): Vymyslete třídící algoritmus běžící v čase lepším než kvadratickém (jinými slovy lepším než $\mathcal{O}(n^2)$). Nezapomeňte udat s odůvodněním jeho časovou složitost. Prozradíme vám, že se vám bude hodit nejen rekurze, ale i kapitola o logaritmech.:


Kuba a Tom; domestomas+mam@gmail.com
e-mailová konference: algoritmy@mam.mff.cuni.cz

Stejně


Téma 5: Přeplněná tramvaj

Pozor, tato stránka není aktuální! Aktualizovaný seznam všech čísel v PDF naleznete zde. Za problémy se omlouváme.

Určitě jste už někdy jeli vlakem nebo MHD. Možná dokonce obojím. Pravděpodobně jste si pak také všimli, že po výjezdu z výchozí stanice bývá takový vůz téměř prázdný a stejně tak bývá téměř prázdný při příjezdu do cílové stanice. Každý si asi domyslí proč. Mezi těmito dvěma body se však nachází $n-2$ dalších stanic, ve kterých se počet lidí uvnitř vozu jistým způsobem vyvíjí, pravděpodobně někde nabývá svého maxima, a tak může i vlak, který se na začátku i na konci své cesty zdá být poloprázdný, někde v polovině zcela selhat z kapacitních důvodů. Cílem každé dopravní společnosti je samozřejmě se takové věci vyvarovat a optimalizovat dopravní síť, což ovšem není možné bez předchozí analýzy vytíženosti vlaku v jednotlivých fázích cesty. Naším cílem v tomto témátku tudíž bude studium křivky popisující vývoj počtu lidí uvnitř dopravního prostředku v průběhu jeho cesty stanicemi. Budeme tedy hledat křivku, která bude mít na ose $x$ číslování\footnote{Pozor, číslování se ve skutečnosti nevztahuje k samotným stanicím, nýbrž k úsekům mezi nimi (podrobnosti v příloze). } stanic na lince (pro sjednocení značení nechť je to $N$) a na ose $y$ okamžitý počet lidí sedících v dopravním prostředku (nechť je to $S$).

Tuto úlohu budeme řešit dvěma hlavními metodami. První, jednodušší metoda, je vcelku předvídatelná: jde o experimentální stanovení naší křivky $S(N)$. V zájmu maximalizace přesnosti výsledku experimentu je pochopitelně nezbytné provést co nejvíce měření. Mnou doporučovaný postup provedení uznatelného měření spočívá v absolvování jízdy po dané lince z výchozí stanice do konečné a zaznamenávání okamžitého počtu přítomných spolucestujících mezi každými dvěma stanicemi. Kreativitě při vymýšlení jiných postupů se meze nekladou, ovšem uznány budou pochopitelně pouze ty funkční a dobře popsané.

Úloha zkoumání experimentální metodou zůstává otevřená až do odvolání nebo do uzavření témátka. Hodnocena bude podle počtu a přínosnosti provedených měření (např. z měření na lince s padesáti stanicemi lze získat o křivce $S(N)$ lepší představu než na lince s pěti stanicemi.).

Druhá metoda řešení bude metodou analytickou. Dostanete za úkol čistě matematickými metodami odvodit analytický předpis pro funkci $S(N)$. To je samozřejmě samo o sobě velmi náročným cílem, nebudeme o to tedy usilovat hned. Běžně se ve vědě totiž při hledání matematického popisu čehokoli vychází z předem známých rovnic ověřených v obecnějších případech a odvozených z nějaké prvotní úvahy. Pro situaci proměnného počtu lidí v dopravním prostředku nám žádné rovnice známy nejsou. To znamená pro vás, řešitele, příležitost si vyzkoušet pozici vědce stojícího ještě před objevením dnešních vědeckých metod a odkázaného pouze na své úvahy a svou nepodloženou představu o fungování světa. Bude zapotřebí, abyste na základě toho, jak víte, že vlaky, autobusy, tramvaje apod. fungují, vymysleli jistý zjednodušující model toho, jak se cestující dopravních prostředků chovají, aby tento model nám, teoretikům, umožňoval popsat, jakým způsobem se ve které stanici bude měnit počet lidí uvnitř prostředku. Vyvození tvaru $S(N)$ z vašeho modelu ponechávám na vás zatím čistě jako dobrovolné, samozřejmě za bonusové bodové ohodnocení.

Pozor, u hledání vhodného zjednodušujícího modelu se neočekává jednoznačné řešení! Nežádám, abyste nalezli stejný model jako já! Pokud váš model není špatný na první pohled, klidně může i on být tím správným, alespoň v jisté aproximaci. Pro rozeznání správného modelu k popisu $S(N)$ nám úvahy stačit nebudou, pro ně budeme muset využít srovnání s experimentem. Proto jestli máte nápad, nebojte se o něj podělit, třeba se právě on v některé z posledních sérií ukáže být tím pro popis nejvhodnějším. Všichni autoři nejvhodnějšího popisu pak budou odměněni body navíc.

Toto jsou vaše první úkoly k tomuto témátku:


Problém 1:

Proveďte co nejvíce měření křivky $S(N)$ dle výše uvedeného návodu na jakékoli dopravní lince autobusu, tramvaje, nebo podobného dopravního prostředku. Nezapomeňte u provedených měření zhodnotit jejich věrohodnost a diskutovat, kde mohla případná nepřesnost vzniknout. Pro přehlednost také uveďte, které linky a kdy jste zkoumali. Tento problém není časově omezený.


Problém 2:

Vymyslete jeden nebo více zjednodušujících modelů, z nichž každý nějakým způsobem popíše, dle jakých pravidel reální lidé v dopravním prostředku nastupují a vystupují, aby se na tato pravidla dalo dále navázat.


Příloha

Teorie pravděpodobnosti

Pro snazší porozumění výše uvedené úloze je dobré zmínit zde ve stručnosti úplné základy teorie pravděpodobnosti a fyzikální statistiky.

Teorie pravděpodobnosti je odvětví matematiky založené v 17. století Blaisem Pascalem a Pierrem Fermatem za účelem popisu nedeterministických jevů, to jest takových, které při námi nerozlišitelných vstupních parametrech dávají různé výsledky. Jakým způsobem tento popis funguje, budu prezentovat na příkladu klasické šestistěnné kostky.

Příklad: Při házení férovou kostkou obyčejně výsledek hodu neumíme předem nijak odhadnout. Kostka tedy představuje náhodný generátor a každý hod kostkou nazýváme pokusem, jehož výsledkem je pak náhodná veličina $X$, což zde bude jednoduše číslo, které padne. Z formálního hlediska je to funkce $X{:}\, M\to\Omega$ zobrazující z nějaké množiny vstupních parametrů $M$ (u kostky to může být například číslo, které bylo na horní stěně, když jsme kostku brali do ruky) do prostoru možných výstupů $\Omega$.Výstupem kostky může být kterýkoli prvek $x_i\in\Omega$, zde tedy kterékoli číslo z množiny\footnote{matematický zápis množiny, viz \url{https://matematika.cz/mnozinove-operace}} $\Omega=\{1, 2, 3, 4, 5, 6\}$. Množinu $A\subseteq\Omega$ takových možných výstupů označujeme jako jev, který mohl nebo nemusel nastat. U kostky můžeme zadefinovat jako jevy například $A=\{ x_i;x_i$ je liché$\}=\{1, 3, 5\}$ nebo $B=\{ x_i; x_i>3\}=\{ 4, 5, 6\}$.

Náhodnou veličinu charakterizuje její tzv. pravděpodobnostní rozdělení -- funkce\footnote{Zápis $2^\Omega$ se používá k označení tzv.~potenční množiny, což je množina všech podmnožin $\Omega$, viz \url{https://matematika.cz/mnoziny\#potencni-mnozina}.} $P{:}\, 2^{\Omega}\to[0, 1]$, která každému jevu $A\subseteq\Omega$ přiřadí číslo $P\in[0, 1]$ tak, aby: % Zas tak sofistikované to nakonec není...

  1. $P(\Omega)=1$
  2. $P(A\cup B)=P(A)+P(B)-P(A\cap B)$

Přiřazené číslo nazýváme pravděpodobností daného jevu.

Můžeme si to znovu představit na příkladu kostky: Pravděpodobnostní rozdělení je zde definováno jako $P({x_i})=1/6$ pro $i=1\ldots6$ (obecně je-li funkce $P({x_i})$ konstantní jako zde, příslušné rozdělení se nazývá uniformní).

Axiom (i) pravděpodobnostního rozdělení říká, že zcela jistě padne některý výsledek z $\Omega$, což u kostky očividně platí, neboť $P\left(\{1, 2, 3, 4, 5, 6\}\right) =P(\{1\})+\cdots+P(\{6\})=1$. Axiom (ii) pak udává vztahy mezi pravděpodobnostmi jednotlivých jevů. U dvou nezávislých jevů poslední člen vypadne, pravděpodobnosti nezávislých jevů se tedy jednoduše sčítají. Platnost tohoto axiomu si můžeme znovu ověřit u kostky na dvou výše definovaných jevech $A$ a $B$. Do levé strany dosadíme $P(A\cup B)=P(\{1, 3, 4, 5, 6\}) = 5/6$ a stejně tak do pravé $P(A)+P(B)-P(A\cap B)=P(\{1, 3, 5\})+P(\{4, 5, 6\})-P(\{5\})=1/2+1/2-1/6=5/6$. \medskip

Náhodným veličinám s číselnými výstupy bývají přiřazovány další vlastnosti, z nichž nejvýznamnější pro nás představují střední hodnota a variance. Střední hodnota $\mu(X)$ je definována jako suma součinů: $\mu(X)=\sum_{x_i\in\Omega} x_iP(x_i)$ (v případě uniformního rozdělení se tento vztah redukuje na aritmetický průměr) a má význam očekávaného\footnote{Pozor, očekávaný výsledek nemusí být vždy ten nejpravděpodobnější. Je to výsledek, kterému se při delším opakování bude blížit průměr z jednotlivých dílčích výsledků. Například když si na strany férové mince napíšeme číslice 0 a 1, po chvíli házení se bude průměr našich výsledků blížit číslu 1/2, ačkoli pravděpodobnost, že by nám v kterémkoli hodu padla strana s takovou číslicí, je nulová.} výsledku každého pokusu. Variance (rovněž rozptyl) $\sigma^2$ je potom definována velmi podobně jako $\sigma^2(X)=\sum_{x_i\in\Omega} {(\mu(X)-x_i)}^2P(x_i)$. Odmocnina z variance se nazývá směrodatná odchylka $\sigma$ a zjednodušeně řečeno má význam vzdálenosti od střední hodnoty, v níž se výsledky pokusů převážně drží.

Skutečný význam pravděpodobnosti objasňuje teprve zákon velkých čísel, což je teorém, dle kterého se při mnohonásobném opakování pokusu relativní četnosti jednotlivých výsledků rozdělují v poměru daném pravděpodobnostmi těchto výsledků. Označíme-li tedy $N$ počet provedených pokusů a $N_i$ počet pokusů, které skončily výsledkem $x_i$, tento zákon říká, že $P(x_i)=\lim_{N \to \infty}\frac{N_i}{N}$. To jest, že i systém v principu chaotický se z dlouhodobého hlediska chová deterministicky.

Poslední zajímavou odbočku k teorii pravděpodobnosti bude v tomto stručném shrnutí představovat Centrální limitní teorém. Mějme náhodnou proměnnou $X$ s libovolným pravděpodobnostním rozdělením. Nechť tato veličina vygeneruje $n$ náhodných výsledků. Jejich součet je pak rovněž náhodnou veličinou. Označme ho $S_n(X)$. Centrální limitní teorém potom říká, že čím vyšší $n$ zvolíme, tím více se pravděpodobnostní rozdělení $S_n$ blíží tzv. Gaussovu rozdělení.

Gaussovo (tzv. normální) rozdělení je známé rozdělení zvonovitého tvaru. Právě díky Centrálnímu limitnímu teorému a jeho nezávislosti na původním rozdělení se Gaussovo rozdělení vyskytuje na mnoha místech v přírodě, a je proto dobré ho znát. Ve své nejjednodušší podobě je popsané vztahem $P(x)=\frac{1}{\sqrt{\pi}}e^{-x^2}$. Vhodně doplněnými konstantami se dá modifikovat jeho střední hodnota a variance, podoba zde uvedená se nazývá standardní normální rozdělení.


Problém 3 (bonusový) [3b]:

Abyste si sami prověřili, že jste tomuto článku dobře porozuměli, podívejme se nyní na případ, kdy náhodná veličina $X$ odpovídá součtu tří nezávislých hodů šestistěnnou kostkou. Zamyslete se, co zde představuje množinu $\Omega$, zakreslete do grafu pravděpodobnostní rozdělení a spočítejte jeho střední hodnotu a varianci.


Fyzikální statistika 

Teorie pravděpodobnosti nachází dobré uplatnění mimo jiné ve fyzikální statistice, ve které samotné veličiny zkoumané sebepřesnějším experimentem představují náhodné proměnné a jejich výsledky slouží k tomu, aby za jejich pomoci byla odhadnuta střední hodnota měřené veličiny, která je teprve prohlášena za hodnotu skutečnou. Jednotlivá fyzikální měření pak z různých důvodů nevycházejí přesně a jsou od této \uv{skutečné} hodnoty více nebo méně odchýlena. Jejich předpokládané odchýlení je nezbytné uvést ve výsledku jako tzv. odchylku nebo chybu.

Tyto chyby se dělí na několik nejčastějších typů. Prvním druhem jsou chyby hrubé, které vznikají nesprávným provedením experimentu, popř. hrubým zásahem do něho. Ty je potřeba mezi výsledky rozpoznat a odstranit.

Druhou skupinu představují chyby systematické, vzniklé špatnou kalibrací nebo interpretací. Jejich vliv zatíží všechny výsledky stejným způsobem, je možno měření tedy dále využít, přijde-li se na to, kde a jaká chyba vznikla, a podaří-li se ji opravit.

Poslední, pro nás nejzajímavější, druh odchylek představují odchylky statistické, vzniklé čistě vlivy náhodnými. Statistická odchylka se po opakovaném měření projeví rozptylem hodnot, neovlivní však nijak střední hodnotu. Tyto odchylky uvádíme ve výsledku ve tvaru $x\pm\sigma_x$, kde $x$ představuje námi odhadnutou střední hodnotu a $\sigma_x$ absolutní odchylku, tedy informaci, o kolik se může naše hodnota lišit od hodnoty skutečné. Jak ze značení, tak z významu je zjevná její souvislost se střední kvadratickou odchylkou. Konkrétně v situaci vcelku častého standardního normálního rozdělení platí, že ve vzdálenosti nejvýš $\sigma$ od střední hodnoty leží výsledek s pravděpodobností 68 \%, ve vzdálenosti $2\sigma$ s pravděpodobností 95 \% a ve vzdálenosti $3\sigma$ s pravděpodobností 99,7 \%.

Alternativně k absolutní odchylce se využívá odchylka relativní, definovaná jako $\eta_x=\frac{\sigma_x}{x}$. Z ní se dá vyčíst, jak velkou nepřesnost pro nás ve skutečnosti absolutní odchylka znamená.

Ze zákona velkých čísel vyplývá, že čím více měření bude provedeno, tím blíže by střední hodnota našich výsledků měla být střední hodnotě skutečného rozdělení pravděpodobnosti. Z toho vyplývá jednak, že ve skutečně věrohodných fyzikálních experimentech je potřeba provést měření velice mnoho, a jednak, že při rostoucím počtu provedených měření by měla odchylka našeho odhadu střední hodnoty klesat. Pro naše účely stačí vědět, že tento pokles se dá odhadnout jako $\sigma_{\tilde{x}}=\frac{\sigma_x}{\sqrt{n}}$, kde $n$ je počet měření a $\tilde{x}$ střední hodnota veličiny $x$ (podrobnosti a odvození možno dohledat v~\cite{prakt}).

Stává se rovněž běžně, že se u výsledné hodnoty nastřádá statistických odchylek víc, buďto z nepřímého měření, nebo odlišných původů. Jedná-li se o měření nepřímé, tedy že hodnota vznikla matematickými operacemi s přímo naměřenými hodnotami, uplatníme metodu přenosu chyb, tedy vztah: $$ \sigma_{f(x_1, \ldots, x_n)^2}=\sum_{k=1}^n \left(\frac{df}{dx_k}\sigma_{x_k}\right)^2 $$ tedy např.: $$ {\sigma_{xy}}^2=x^2{\sigma_y}^2+y^2{\sigma_x}^2 $$

Dvě odchylky nezávislých původů se pak skládají na kombinovanou standardní nejistotu: $\sigma^2=\sigma_x^2+\sigma_y^2$.

Odvození všech těchto vztahů lze znovu dohledat v~\cite{prakt}.

Nápověda k řešení

Zde si na závěr dovolím několik poznámek k úloze, které nepatří do zadání, přesto je však dobré si je před zahájením řešení přečíst.

Především bychom si měli sjednotit číslování stanic, které není zcela přímočaré. Už bylo ostatně nastíněno v poznámce k zadání, že se $N$ vztahuje nikoli ke stanicím, nýbrž k úsekům mezi nimi (hodnoty však budeme stále vynášet na celých číslech). Doporučuji úseky číslovat vždy podle stanice, z níž vůz právě vyjíždí. Dále doporučuji výchozí depo, resp. konečné depo považovat za nultou, resp. $(n+1)$-ní stanici ($n$ nechť značí celkový počet stanic na lince). S tímto číslováním je jisté, že v $N=0$ bude vynesena hodnota $S$ příslušející úseku mezi depem a první stanicí, kde je samozřejmě $S=0$, stejně tak jako v $N=n$. Křivka $S(N)$ pak bude vycházet z bodu $[0, 0]$ a časem se do nuly zase vrátí, což bude jednak estetičtější, jednak přehlednější.

Tato úloha sice není fyzikální, některé rysy fyziky však přesto vykazuje. Okamžitý počet lidí v dopravním prostředku je jistá náhodná veličina, jejíž množinou možných výsledků je $\Omega=\mathbb{N}_0$ a jejíž rozdělení pravděpodobnosti stejně jako námi hledaná střední hodnota závisí jednak na fázi trasy, v níž se prostředek právě nachází (což je jediná závislost, kterou my chceme zkoumat), mimoto ale také na denní době, vytíženosti linky, typu prostředku apod. Abychom všechny tyto vedlejší závislosti z našeho měření odfiltrovali, musíme se nad úlohou nejdřív trochu zamyslet.

Na začátku úlohy, když bylo zadáno hledání obecného tvaru křivky $S(N)$, byl tímto zadáním zároveň vysloven předpoklad, že takový obecný tvar existuje, tj. že křivka $S(N)$ si ponechává ve všech situacích tvar stejný, který se pouze jistým způsobem roztahuje a smršťuje právě v souvislosti s vytížeností linky a s počtem stanic na lince (v prvním případě se to projeví modifikací ve svislém směru, ve druhém případě ve vodorovném). Tento předpoklad není podložen ničím kromě intuice a pravděpodobně se dokonce časem ukáže, že v jistých speciálních případech neplatí.

Přesto můžeme zatím předpokládat jeho platnost alespoň v situacích vzájemně si podobných. Není tedy například nesmyslné srovnávat tvar $S(N)$ u linky s deseti a u linky s jedenácti stanicemi. Srovnání takových linek ovšem nelze provést v grafu, jehož osa $x$ bude odpovídat přímému číslování stanic $N$ (přinejmenším proto, že jedna z křivek bude končit o stanici dál). Proto pro hledání obecného tvaru naší křivky doporučuji přejít k redukovanému číslování stanic $\tilde{N}=\frac{N}{n+1}$ ($n+1$ je skutečná délka trasy vynášené na grafu).

Sami si rozmyslete, jak podobným způsobem co nejlépe redukovat okamžitý počet cestujících $S$ na $\tilde{S}$.

Nyní jsme od křivky $S(N)$ přešli ke křivce $\tilde{S}(\tilde{N})$. Ta by dle našeho předpokladu měla mít stejný tvar jako $S(N)$ (šlo jen o přenásobení konstantami) pouze s rozdílem, že jejím definičním oborem i oborem hodnot bude interval $[0, 1]$. To je pro nás úžasný výsledek, protože nyní jsme upravili naši křivku do takové podoby, která zachovává její tvar a přitom není závislá ani na počtu stanic na lince, ani na tom, kolik lidí linkou právě jede (jde jen o to, jak se tento počet relativně mění).

Tím pádem jsme se zbavili závislosti zkoumané střední hodnoty na všech výše uvedených nepodstatných parametrech a zbyla nám pouze kýžená závislost na fázi cesty. Ani ta však není zcela nezávadná. Asi každý si dovede představit, že na pevně dané lince jsou některé stanice více frekventované než jiné. Proto kdybychom měření prováděli neustále na stejné lince, vyšla by nám i po redukci odlišná křivka, než kdybychom stejné měření prováděli na lince jiné. Proto vyjdeme-li z předpokladu, že rozložení frekventovaných stanic na Nespecifikované lince je náhodné, mé další doporučení ke hledání obecného tvaru bude nabádat ke zkoumání přednostně většího počtu linek jednou nežli jedné linky mnohokrát. Dodržování tohoto doporučení už bude hodnoceno skrze přínosnost provedeného měření (viz zadání).

Tímto doporučením dnešní odbočku k nápovědám k řešení zakončuji, přeji hodně štěstí při řešení jak experimentální části, tak i teoretické.

Reference

[1] Ch. M. Grinstead, J. L. Snell: Introduction to Probability, American Mathematical Society, Copyright (C) 2003

[2] J. Englich: Úvod do praktické fyziky I: Zpracování výsledků měření, MATFYZPRESS, Praha 2006

Evžen; JanSkvara@email.cz
e-mailová konference: tramvaj@mam.mff.cuni.cz

Stejně


Téma 6: Vrcholové pokrytí

V tomto témátku se budeme věnovat hledání minimálního vrcholového pokrytí. Máme-li graf definovaný jako množinu vrcholů a množinu hran mezi nimi, tak jeho vrcholové pokrytí je taková podmnožina vrcholů, že každá hrana má alespoň jeden svůj konec v té podmnožině. Minimální vrcholové pokrytí je potom takové vrcholové pokrytí, které obsahuje minimální možný počet vrcholů.

Pro minimální vrcholové pokrytí se umí spousta zajimavých triků, viz https://en.wikipedia.org/wiki/Vertex_cover.

Vzhledem k tomu, že v tomto témátku budeme občas pracovat s relativně velkými grafy, tak místo jejich kreslení se raději domluvíme na datovém formátu. Každý graf bude popsán samostatným textovým souborem. Na prvním řádku bude uveden počet vrcholů grafu N a počet hran M. Budeme předpokládat, že vrcholy jsou číslovány od 0 do N-1. Na následujících M řádcích budou uvedeny hrany - každý řádek bude odpovídat jedné hraně a bude obsahovat dvojici čísel vrcholů, které tato hrana spojuje. Na pořadí těchto čísel v rámci řádku ani na pořadí hran nezáleží.

Řešení pro jednotlivé grafy posílejte jako seznam čisel vrcholů, které tvoří vrcholové pokrytí. Také posílejte vaše pozorování o vlastnostech grafů, nápady na zlepšení algoritmů a obecně cokoliv, co může vám a vašim spoluřešitelům pomoct v hledání minimálních vrcholových pokrytí velkých grafů.

Poznámka: První graf by měl odpovídat obrázku z čísla. Kliknutím na graf získáte jeho datovou reprezentaci (viz výše).

Další grafy (minimálně prozatím) bez obrázků:

Graf 4

Graf 5

Graf 6

Graf 7

Graf 8

Graf 9

Graf 10

Stejně