Témata

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

 

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

Stejně


Téma 2: Principy kryptografie

Obsah:

Substitučně-permutační sítě a AES

Hashovací funkce

Substitučně-permutační sítě a AES

V on-line světě každý den odešleme i přijmeme celou řadu šifrovaných zpráv. Obvykle se tak děje bez toho, abychom si to jakkoli uvědomovali. Zatímco ještě před několika lety byla i nešifrovaná komunikace na internetu celkem běžná, dnes, pokud si chceme zobrazit webovou stránku nebo někomu zavolat, obvykle šifrování využíváme. Za způsoby, jakými jsou data šifrována, přitom často nejsou schovány nijak složité úvahy. Cílem tohoto tématu bude tyto postupy přiblížit a trochu si je osahat.

V první části se budeme věnovat substitučně-permutačním sítím (substitution-permutation network, SPN), na kterých je založená mimo jiné v dnešní době nejrozšířenější bloková šifra AES.

Historické metody

Potřeba utajovat zasílané vzkazy je stará tisíce let. Například z dob antiky pochází slavná Caesarova šifra, která spočívá v posunutí každého písmena v abecedě o tři, tedy v nahrazení (neboli substituci) jednoho písmena druhým podle pevně stanovené tabulky.

Později byla vymyšlena Vigenèrova šifra, u které vznikne zašifrovaný text postupným přičtením jednotlivých písmen klíče k jednotlivým písmenům původního textu. Pokud se tedy v původním textu (budeme mu říkat otevřený) objevuje stejné písmeno vícekrát, může být v zašifrovaném textu zakódované pokaždé pomocí jiného znaku.

Dalším tradičním způsobem je proházení (permutace) pozic písmen obsažených v textu.

Substitučně-permutační sítě v podstatě nepřinášejí nic nového. Pouze všechny tyto tři dávno známé metody šikovným způsobem propojují.

Moderní blokové šifry

Aby matematici mohli šifry lépe popisovat a zkoumat, zavedli pojem „bloková šifra“. Tu si můžeme představit jako sadu dvou černých krabiček. První slouží pro šifrování – pokud do ní vložíme otevřený text a šifrovací klíč, dostaneme zašifrovaný text. Druhá krabička pak umožňuje s pomocí zašifrovaného textu a šifrovacího klíče vytvořit zpátky otevřený text.

Šifrovacím klíčem je vždy nějaká posloupnost znaků („heslo“) předepsané délky. Bloková šifra vždy očekává vstup pevně zadané délky a stejně dlouhý je i její výstup. Této délce se říká velikost bloku. Například AES používá bloky o velikosti 128 bitů neboli 16 znaků. Pokud chceme zašifrovat delší text, můžeme ho například rozdělit na části odpovídající velikosti bloku a ty zašifrovat zvlášť.

Dvojková soustava

Než budeme pokračovat, musíme udělat krátkou odbočku. Moderní kryptografie předpokládá využití počítačů, a tak jim přizpůsobuje využívané prostředky. Čísla jsou obvykle zapisována ve dvojkové soustavě. Při početních operacích se typicky počítá s bloky dat (proměnnými) omezené velikosti.

Každé číslo je možné v desítkové soustavě zapsat jako součet jednociferných násobků mocnin deseti, například $2945 = 2\cdot 10^3 + 9\cdot 10^2 + 4\cdot 10^1 + 5\cdot 10^0$. Podobně ve dvojkové soustavě je možné každé číslo zapsat jako součet mocnin dvojky.

Pokud chceme převést číslo z desítkové soustavy do dvojkové, stačí najít vhodné mocniny dvou, jejichž součet odpovídá původnímu číslu. Například:

\[ (42)_{10} = 4\cdot 10^1 + 2\cdot 10^0 = 1\cdot 2^5 + 0\cdot 2^4 + 1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 0\cdot 2^0 = (101010)_2 \]

Převod z dvojkové soustavy do desítkové probíhá podobně.

Protože čísla ve dvojkové soustavě jsou dlouhá a jejich zápis pro člověka není příliš dobře čitelný, často se místo dvojkové soustavy používá soustava šestnáctková. Způsob převodu je opět úplně stejný. Abychom měli pro šestnáctkovou soustavu dostatečné množství číslic, přidávají se za číslici 9 ještě písmena A až F, například $(42)_{10} = (2\mathrm{A})_{16}$. Všimněte si, že 16 je mocninou 2, převod mezi dvojkovou a šestnáctkovou soustavou je proto velmi jednoduchý. Každá hexadecimální číslice totiž odpovídá čtveřici binárních číslic, např. $(2\mathrm{A})_{16} = (10\; 1010)_2$.

Pro čísla zapsaná ve dvojkové soustavě můžeme snadno definovat takzvané bitové operace, tedy početní operace, které provádíme na jednotlivých bitech (tj. pozicích ve dvojkové soustavě) čísla nezávisle na ostatních. Obvyklými operacemi pro dvě čísla jsou:

and $\mathbin {\& }$ z čísel vybere pouze ty bity, na kterých je v obou číslech 1 (ostatní bity nastaví na 0), tedy např.

 

$10100110$

$\mathbin {\& }\;$

$\underline{01101011}$

  $00100010$

 

or $\mathbin {\parallel }$ vybírá ze zadaných čísel všechny bity, na kterých je jednička alespoň v jednom z nich, např.

 

$10100110$

$\mathbin {\parallel }\;$

$\underline{01101011}$

 

$11101111$

 

xor $\mathbin {\oplus }$ na výstup vypíše 1 u těch bitů, kde se zadaná čísla liší, např.

 

$10100110$

$\mathbin {\oplus }\;$

$\underline{01101011}$

 

$11001101$

Kromě těchto operací se ještě využívá klasické sčítání (značíme +) na číslech omezené délky, ve kterém zanedbáváme přenos přes nejvyšší řád. Pokud tedy budeme pracovat s 8-bitovými čísly, tak $10100110 + 01101011 = 00010001$. Hodnota odpovídá běžnému sčítání v desítkové soustavě, při kterém nás ale zajímá ze součtu pouze zbytek po dělení $2^8$ (obecně $2^ n$ pro $n$-bitová čísla).

Navíc ještě definujeme operace, které provádíme vždy pouze s jedním číslem:

not $\sim $ je operace, která prohazuje, na kterých bitech jsou jedničky a na kterých nuly, např. $\sim 10100110 = 01011001$.

shift left $\ll $ posouvá všechny bity o jednu pozici vlevo a na konec přidá nulu. Bit nejvíce vlevo se ztratí. Např. $\ll 10100110 = 01001100$. Tato operace odpovídá násobení 2.

shift right $\gg $ posouvá všechny bity o jednu pozici vpravo a na první pozici přidá nulu. To odpovídá dělení 2, např. $\gg 10100110 = 01010011$.

rot left $\lll $ neboli rotace vlevo funguje obdobně jako shift vlevo, ale bit z nejlevější pozice přesune na konec čísla, např. $\lll 10100110 = 01001101$.

rot right $\ggg $ neboli rotace vpravo opět připomíná shift vpravo, ale poslední bit přesune na začátek čísla, např. $\ggg 10100110 = 01010011$, $\ggg 01101011 = 10110101$.

V tomto dílu využijeme jen některé z těchto operací, ale v průběhu tématu se nám mohou hodit i další.


Úloha 1 [1b]: Mějme libovolná čísla $a$ a $b$. Dokážete získat výsledky operací or, xor a rotace vpravo pouze pomocí opakovaného využití operací and a not?


Šifra OCTA

Vybaveni potřebným matematickým aparátem si můžeme konečně zadefinovat naši vlastní jednoduchou šifru OCTA založenou na substitučně-permutační síti a trochu ji prozkoumat.

OCTA využívá blok o velikosti osmi bitů a očekává klíč, jehož délka v bitech je násobkem osmi. Jak je u moderních blokových šifer obvyklé, bude dělat několikrát po sobě operace zapsané pomocí stejného předpisu. Při tvorbě šifrového textu tedy proběhne několik kol šifrování (těm říkáme rundy).

Na začátku každé rundy přixorujeme k aktuálnímu textu klíč. Abychom pořád nexorovali stejnou hodnotu, použijeme poprvé prvních osm bitů klíče (označíme $K_1$), v druhé rundě dalších osm bitů ($K_2$) a tak dále. Jakmile dojdeme až na konec klíče, začneme opět od začátku. Pokud by tedy měl klíč například 16 bitů, tak $K_1 = K_3 = K_5 = \dots $.

Druhou operací v rámci rundy bude využití takzvaných S-boxů neboli substituce podle pevně stanovené tabulky. Text (tj. osm bitů) rozdělíme na čtyři skupiny po dvou bitech a hodnotu každé z nich změníme podle tabulky:

 $x$

 00

 01

 10

 11

 $S(x)\;$

 10

 00

 01

 11

Tedy například text $01110101$ změníme na $00110000$.

Třetí operací pak bude třikrát po sobě rotace celého textu vpravo (tedy rotace vpravo o tři bity).

Takových rund proběhne pět. Na závěr ještě jednou přixorujeme klíč.

Schéma celé šifry je zachyceno na Obrázku 1.

 
Obrázek 1: schéma šifry OCTA

Abychom pomocí naší šifry mohli šifrovat reálné texty, využijeme v souladu se skutečnou praxí reprezentaci znaků pomocí ASCII tabulky1, která převádí základní tisknutelné znaky na osmibitové hodnoty. Pokud budeme chtít mít v otevřeném textu písmeno A, tak do něj tedy napíšeme $(41)_{16} = (01000001)_2$. Každou osmici bitů (tedy každé písmeno) pak budeme šifrovat zvlášť.

Zbývá otázka, jak bude vypadat funkce pro dešifrování zpráv. Můžeme si ale všimnout, že všechny kroky, které jsme v průběhu šifrování provedli, lze provést i zpětně (všimněte si, že přixorování je samo sobě inverzní operací). Dešifrovat zprávy tedy můžeme pomocí stejného algoritmu, ale pozpátku.


Úloha 2 [2b]: Dostali jste zprávu 89 19 2C 8C F9 BC FA CC 6D 6C FC BD 19 59 19 C8 29, o které víte, že je zašifrovaná šifrou OCTA pomocí klíče 4D 41 4E 44 4D (tj. MANDM). Jaká byla původní zpráva?


Využití šifry


Problém [2b+]:

Představme si reálné využití šifry. Chcete mít aktuální přehled o tom, kolik máte doma tabulek hořké čokolády. A tak si každou hodinu posíláte do školy zprávu o jejich počtu. Protože tato informace je ale důvěrná, posíláte ji zašifrovanou pomocí šifry OCTA s klíčem, který znáte jenom vy.

Je k tomuto účelu OCTA vhodná? Pokud někdo bude odposlouchávat vaše zprávy, dokáže z nich něco zjistit? Jak by bylo možné zasílání zprávy vylepšit?


Zkuste se zamyslet i nad případnými dalšími nedostatky prezentované šifry. Kde všude by mohla v praxi narazit? Za pěkný rozbor lze získat pěkné bodové ohodnocení.


Úloha 3 [2b+]:

Můžete též zkusit zauvažovat nad volbou šifrovacích klíčů. Existuje klíč, který vámi zvolený otevřený text zašifruje tak, že otevřený i šifrový text budou stejné? A existuje klíč, který zašifruje libovolný otevřený text na šifrový text, který bude s otevřeným textem shodný?

Najdete otevřený text a klíč, který tento text zašifruje na samé 1, tj. FF?


AES

Zatím jsme si hráli s jednoduchou šifrou OCTA. Jak to ale vypadá s reálnými šiframi jako třeba s AES? Od naší šifry se až tak moc neliší. AES používá 128-bitové bloky a klíče o velikosti 128, 192, nebo 256 bitů. Podle velikosti klíčů je využito 10, 12, nebo 14 rund.

Na začátku dojde k přixorování rundovního klíče. Samotná runda pak obsahuje využití S-boxů v kroku nazvaném SubBytes a potom dvě permutace ShiftRows a MixColumns. Runda je zakončena opět přixorováním rundovního klíče.

Detailní popis šifry můžete nalézt třeba na Wikipedii2.


Úloha 4 [2b]:

V detailním popisu AES si můžete všimnout, že v poslední rundě je vynechaná permutace MixColumns. Proč tomu tak je? A proč není vynechaná i ShiftRows?

Pokud bychom i v naší šifře OCTA vynechali v poslední rundě permutaci, změnili bychom tím obtížnost jejího prolomení?


Poznámka na závěr

Protože se toto téma zabývá v praxi využívanými postupy, na část otázek a úloh může být jednoduché najít odpovědi na internetu. Takový postup je zcela regulérní a nebojte se jej využívat. Kdykoli budete něco tvrdit, tak ale nezapomínejte svá tvrzení zdůvodňovat. Argument „je to pravda, protože to psali na Wikipedii“ uznávat nebudeme. Ale pokud si na Wikipedii přečtete zdůvodnění a to potom využijete ve svém řešení včetně citace zdroje, je to naprosto v pořádku.

Kuba, Káťa a Lenka; jakub.topfer@matfyz.cz
e-mailová konference: krypto@mam.mff.cuni.cz


1) viz https://www.asciitable.com/

2) https://en.wikipedia.org/wiki/Advanced_Encryption_Standard

 

Hashovací funkce

V prvním čísle jsme se zabývali blokovými šiframi. V tomto se podíváme na další podstatný koncept, bez kterého by se kryptografie neobešla, a tím jsou hashovací neboli jednosměrné funkce. Již nyní se můžete těšit na třetí číslo, ve kterém blokové šifry a hashovací funkce využijeme dohromady. Najdete v něm také řešení úloh z prvního i druhého čísla. Pokud jste nám zatím nezaslali řešení úloh z prvního čísla, můžete je tedy posílat i nadále.

Koncept

V kryptografii nazýváme hashovací funkcí H takovou funkci, která pro libovolný vstup vrátí výstup pevně stanovené délky a splňuje následující podmínky:

1. Pro daný hash c je obtížné najít x takové, že H(x) = c. Tedy pro zadaný hash je obtížné najít vzor, který je pomocí hashovací funkce na tento hash převeden.

2. Pro daný vstup x je obtížné najít y tak, aby H(x) = H(y). Neboli je obtížné najít druhou vstupní hodnotu se stejným hashem.

3. Je obtížné najít vstupy x a y, aby H(x) = H(y). Neboli je obtížné najít libovolné dvě vstupní hodnoty se stejným hashem.

Označením, že je něco obtížné, v tomto případě chceme vyjádřit, že toho nelze dosáhnout výrazně snáze než pomocí zkoušení variant hrubou silou. Pokud budeme mít hashovací funkci s výstupem o velikosti 64 bitů a zkusíme zahashovat 264 + 1 hodnot, určitě najdeme dvě se stejným hashem. Dokonce s velkou pravděpodobností najdeme dvě hodnoty se stejným hashem mnohem dříve. Neměla by ale existovat žádná metoda, která je statisticky úspěšnější než zkoušet hrubou silou hashovat náhodné hodnoty.


Úloha 1 [1b]:

V kryptografii je obecně za úspěšný považován libovolný útok, který má alespoň 50% šanci na úspěch. Představme si ideální hashovací funkci, která má výstup o velikosti 64 bitů. Kolik výpočtů hashovací funkce budeme muset provést, abychom s pravděpodobností alespoň 50 % našli dvě hodnoty se stejným hashem?


Zároveň ještě od hashovací funkce z praktických důvodů typicky chceme, aby drobná změna vstupního textu vedla k velké změně výsledného hashe a abychom z hashe nedokázali získat ani část informace o vstupu.

Využití

Hashovací funkce mají celou řadu uplatnění. Jedním z nejpodstatnějších je ověření, že nějaká data nebyla změněna. Stačí si z dat spočítat hash a ten nějakým důvěryhodným způsobem uložit. Mohu si ho třeba i elektronicky podepsat (i k tomu se v rámci tohoto tématu ještě dostaneme). Pokud chceme později ověřit, že v datech nedošlo k žádné úpravě, stačí z nich znovu spočítat hash a hashe porovnat.

Zcela jiné využití hashovacích funkcí najdeme například při ukládání hesel. Představme si webovou stránku, kam se uživatelé přihlašují pomocí jména a hesla. Aby hesla nemusela být na serveru uložena jako prostý text, který si může kdokoli přečíst, bývá zvykem na serveru ukládat pouze hashe hesel. Ve chvíli, kdy se uživatel chce přihlásit, pošle na server heslo. Na serveru je z tohoto hesla spočítán hash a porovnán s uloženým záznamem. Pokud jsou stejné, uživatel zadal nejspíš správné heslo a je přihlášen.


Problém 2 [2b+]:

Hashování hesel je určitě vhodným postupem. Pokud ale jednoduše spočítáme hash z hesla, stále můžeme při odcizení hashů čelit určitým rizikům. Napadá vás, kde jsou nedostatky takového postupu? Dokážete najít a popsat, jak ukládat hesla lépe? Napovíme, že možností na vylepšení existuje celá řada.


Praktická realizace

Už víme, jaké vlastnosti by hashovací funkce měla mít. Zbývá vyřešit otázku, jak takovou funkci sestrojit. V současné době můžeme za nejrozšířenější hashovací funkce považovat MD5, SHA1 nebo rodinu funkcí SHA2 (SHA256, SHA512). Ty všechny využívají pouze klasické binární operace and, or, xor, modulární sčítání a rotace, případně shifty. Více informací o těchto operacích najdete v prvním čísle. Zmíněno tam není akorát modulární sčítání. Na této operaci ale není nic složitého – jedná se o klasické sčítání s čísly pevné maximální délky, kde u nejvyššího řádu nezohledňujeme přenos výš. Vedle uživatelského vstupu (libovolné délky) funkce vždy využívají i řadu pevných konstant.

Funkce RIKSHA

Abychom si mohli s konstrukcí hashovacích funkcí trochu pohrát, tak pro vás máme naši vlastní funkci jménem RIKSHA [čti rikša]. Princip, jak funkce pracuje, je podobný jako u běžných hashovacích funkcí. Nabízíme vám ji ve formě funkčního zdrojového kódu pro Python, o kterém doufáme, že je dostatečně názorný. Pokud by vám nebylo jasné, co některá část kódu dělá, nebojte se poslat dotaz do témátkové e-mailové konference.

#!/usr/bin/env python3
import sys

# konstanty
c0 = 0x56
c1 = 0x37
c2 = 0xa5
c3 = 0x9d
c4 = 0xbf

# inicializace casti vysledneho hashe
h0, h1, h2, h3, h4, h5, h6, h7 = c0, c1, c0, c1, c0, c1, c0, c1

# rotace vlevo o b bitu 8-bitoveho cisla n
def rotl(n, b):
      return ((n << b) | (n >> (8 - b))) & 0xff

# pridej "binarni 1", dopln 0x00 na nasobek 8 bytu
def pad(text):
      text += ’80’
      text += ’0’ * (16 - len(text) % 16)
      return text

# uprav hash podle casti vstupu
def update(chunk):
      global h0, h1, h2, h3, h4, h5, h6, h7
      # rozdel vstup na (decimalni) cisla
      d = []
      for i in range(8):
            d.append(int(chunk[2*i:2*i+2], 16))
      # spocitej mezihodnoty
      a0 = ((d[2] << 3) ^ (d[4] << 3) ^ (d[6] << 3) ^ (c2 << 5)) & 0xff
​​​​​​​      a1 = ((d[1] << 4) ^ (d[3] << 4) ^ (d[5] << 4) ^ c3) & 0xff
​​​​​​​      a2 = rotl(d[0], 3) ^ rotl(d[7], 5) ^ c2
​​​​​​​      a3 = ((d[0] << 7) & (d[3] >> 2) ^ (c3 << 2)) & 0xff
​​​​​​​      a4 = (rotl(d[0], 3) ^ rotl(d[7], 5) ^ (d[4] << 7) ^ c4) & 0xff
​​​​​​​      # uprav hodnotu hashe
​​​​​​​      h0_puvodni = h0
​​​​​​​      h0 = (h0 + h1 + (a0 << 5)) & 0xff
​​​​​​​      h1 = (h1 + h2 + (a1 << 3)) & 0xff
​​​​​​​      h2 = (h2 + h3 + (a2 << 2)) & 0xff
​​​​​​​      h3 = (h3 + h4 + a3) & 0xff
​​​​​​​      h4 = (h4 + h5 + a2 + a4) & 0xff
​​​​​​​      h5 = (h5 + h6 + a3) & 0xff
​​​​​​​      h6 = (h6 + h7 + a2 + a4) & 0xff
​​​​​​​      h7 = (h7 + h0_puvodni + (a1 << 4)) & 0xff

# spocitej RIKSHA (vstup v hex ASCII bez mezer)
text = pad(sys.argv[1])
while len(text) > 0:
​​​​​​​      update(text[0:16])
​​​​​​​      text = text[16:]
print(’%.2X’*8 % (h0, h1, h2, h3, h4, h5, h6, h7))

Zdrojový kód v elektronické podobě si můžete stáhnout z našeho webu. Na vás je prozkoumat, jestli je RIKSHA dobrou hashovací funkcí.


Úloha 3 [1b]:

Všimněte si funkce pad, která připojuje za zprávu před doplnění nulami vždy stejnou konstantu. Tento postup jsme si vypůjčili od běžně používaných hashovacích funkcí. Napadá vás, k čemu je tato konstrukce dobrá?


Úloha 4 [2b]:

Dokážete najít dvě vstupní hodnoty, pro které je výsledný hash stejný?


Úloha 5 [3b]:

Víte, že pomocí funkce RIKSHA byl zahashován text, který není delší než 8 bytů. Výsledný hash je 02365E1E061E62BA. Dokážete najít nějaký (ne nutně stejný) vstup, který má stejný hash?


Úloha 6 [5b]:

Existuje nějaká hodnota hashe, kterou funkce RIKSHA nevrátí pro žádný vstup? Nezapomeňte své tvrzení důkladně zdůvodnit.


Kuba, Káťa a Lenka; jakub.topfer@matfyz.cz
e-mailová konference: krypto@mam.mff.cuni.cz

Stejně


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

Obsah:

1. díl

2. díl

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:

Stavíme počítač

Rekurze

 


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

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 \textit{náhodný generátor} a každý hod kostkou nazýváme \textit{pokusem}, jehož výsledkem je pak \textit{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 \textit{prostoru možných výstupů} $\Omega$. \textit{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 \textit{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. \textit{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í... \begin{itemize} \item[(i)] $P(\Omega)=1$ \item[(ii)] $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ \end{itemize}

Přiřazené číslo nazýváme \textit{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á \textit{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í \textit{střední hodnota} a \textit{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ěž \textit{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á \textit{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 \textit{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 \textit{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. \textit{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á \textit{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. \textit{odchylku} nebo \textit{chybu}.

Tyto chyby se dělí na několik nejčastějších typů. Prvním druhem jsou \textit{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í \textit{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í \textit{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$ \textit{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á \textit{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 \textit{měření nepřímé}, tedy že hodnota vznikla matematickými operacemi s přímo naměřenými hodnotami, uplatníme \textit{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}. \begin{center}\includegraphics[height=5cm]{obrazky/skladani-sil.eps}\end{center}

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

Stejně