Seriál 31. ročníku

1. Upravte výraz $\sqrt {x+1}-\sqrt {x}$ tak, aby nebyl náchylný k problémům cancellation, ordering a smearing. Ke kterým z těchto problémů byl původně náchylný a proč? Jaký je rozdíl ve výsledku původního a opraveného výrazu, pokud jej vyčíslíme v double precision pro $x=1{,}0 \cdot 10^{10}$?
2. Popište funkci následujícího kódu. Jaký je rozdíl mezi funkcemi a() a b()? Pro jaké hodnoty x je lze použít? Nebojte se kód spustit a hrát si s hodnotou proměnné x. Určete také asymptotickou časovou složitost programu v závislosti na proměnné x.

   def a(n):
     if n == 0:
       return 1
     else:
       return n*a(n-1)
   def b(n):
     if n == 0:
       return 1.0
     else:
       return n*b(n-1)
   x=10
   print("{} {} {}".format(x, a(x), b(x)))

3. Označme $o_k$ a $O_k$ obvod vepsaného a opsaného pravidelného $k$-úhelníku ke kružnici. Pak pro ně platí rekurentní vztahy \[\begin{equation*} O_{2k}=\frac {2o_k O_k}{o_k + O_k} ,\; o_{2k}=\sqrt {o_k O_{2k}} . \end {equation*}\] Napište program, který pomocí těchto vztahů vypočítá hodnotu $\pi $, začněte přitom s opsaným a vepsaným čtvercem. S jakou přesností dokážete $\pi $ takto aproximovat? Obdobu tohoto postupu původně navrhl a použil Archimedes.
4. Lukáš a Mirek hrají hru. Házejí férovou mincí a když padne orel, dá Mirek Lukášovi jedno Fykosí tričko, když padne panna, dá jedno tričko Lukáš Mirkovi. Oba dohromady mají $t$ triček, z toho $l$ patří Lukášovi a $m$ Mirkovi. Pokud jednomu z hráčů dojdou trička, hra končí.
   1. Nechť $m = 3$ a Lukášova zásoba triček je nekonečná. Určete nejpravděpodobnější dobu trvání hry, tedy počet hodů mincí, po nichž hra skončí (protože Mirkovi dojdou trička).
   2. Nechť $m = 10$, $l = 20$. Proveďte simulaci pomocí generátoru pseudonáhodných čísel a nalezněte pravděpodobnost, že Mirek vyhraje všechna Lukášova trička. Celou hru nechejte proběhnout alespoň 100krát (čím více opakování, tím lépe).
   3. Jak se změní výsledek předchozí úlohy, jestliže Mirek minci „vylepší“ a panna nyní padá s pravděpodobností $5/9$?
      Bonus: Vypočtěte pravděpodobnosti analyticky a porovnejte výsledek se simulací.
5. Mějme lineární kongruenční generátor s parametry $a = 65539$, $m = 2^{31}$, $c = 0$.
   1. Vygenerujte alespoň $1 000$ čísel a spočtěte jejich střední hodnotu a rozptyl. Porovnejte se střední hodnotou a rozptylem rovnoměrného rozdělení na stejném intervalu.
   2. Nalezněte vztah, který vyjádří číslo v generované sekvenci jako lineární kombinaci čísel na dvou předchozích pozicích, tj. nalezněte koeficienty $A$, $B$ v rekurentním vztahu $x_{k+2} = Ax_{k+1} + Bx_k$. Pokud budeme považovat každá tři po sobě následující čísla za souřadnice bodu ve trojrozměrném prostoru, jak rekurentní vztah ovlivní prostorové rozložení těchto bodů?
      Bonus: Vygenerujte sekvenci alespoň $10 000$ čísel a vykreslete 3D bodový graf, který ilustruje význam uvedeného rekurentního vztahu.

1. Vykreslete závislost chyby na velikosti kroku pro metodu odvozenou pomocí Richardsonovy extrapolace v textu seriálu. Jaký je optimální krok a minimální chyba? Porovnejte s centrovanou a dopřednou diferencí. Jako derivovanou funkci použijte $\exp(\sin(x))$ v bodě $x=1$.
   Bonus: Vypočtěte pro tuto metodu teoretickou velikost optimálního kroku pomocí odhadu chyb.
2. Na webu se nachází soubor s experimentálně zjištěnými $t$, $x$ a $y$ souřadnicemi poloh hmotného bodu. Pomocí numerické derivace nalezněte časovou závislost složek rychlosti a zrychlení a vyneste obě závislosti do grafu. Jaký fyzikální děj bod nejspíše konal? Numerickou metodu si zvolte sami, svoji volbu ale odůvodněte.
   Bonus: Existuje v tomto případě přesnější varianta získání rychlosti a zrychlení, než přímočará aplikace numerické derivace?
3. Máme zadán integrál $\int _0^{\pi } \sin ^2 x\,\d x$.
   1. Nalezněte hodnotu integrálu z geometrické úvahy za pomoci Pythagorovy věty.
   2. Nalezněte hodnotu integrálu pomocí Monte Carlo simulace. Určete směrodatnou odchylku výsledku.
      Bonus: Vyřešte Buffonovu úlohu ze seriálu (odhad hodnoty čísla $\pi$) pomocí MC simulace.
4. Nalezněte vztah pro výpočet objemu šestidimenzinální koule pomocí metody Monte Carlo.
   Nápověda: Pythagorovu větu lze využít k měření vzdáleností i ve vyšších dimenzích.

1. Vymyslete tři odlišné příklady markovovského procesu, z toho alespoň jeden fyzikální. Je procházka bez návratu markovovská? A co procházka bez křížení?
2. Mějme 2D náhodnou procházku bez návratu na čtvercové síti s počátkem v bodě $(x,y) = (0,0)$, která je omezena absorpčními bariérami $b_1: y = -5$, $b_2: y = 10$. Nalezněte pravděpodobnost, že v bariéře $b_1$ skončíme dříve než v $b_2$.
3. Proveďte simulaci pohybu brownovské částice ve 2D a vykreslete graf závislosti střední vzdálenosti od počátku na čase. Uvažujeme diskrétní čas a konstantní délku kroku (jeden krok simulace trvá $\Delta t = \textrm{konst.} $, délka kroku je $\Delta l = \textrm{konst.} $) a umožňujeme pohyb do libovolného směru, tj. každý krok je specifikován délkou a úhlem $\theta \in [0,2\pi )$, přičemž všechny směry jsou stejně pravděpodobné. Zajímá nás především asymptotické chování, tedy vývoj střední vzdálenosti pro $t \gg \Delta t$.
4. Chybová funkce je definována vztahem \[ \mathrm{erf}(x)=\frac{2}{\sqrt{\pi}}\int_0^x \eu^{-t^2}\,\d t\,.\] Tabelujte tuto funkci, tedy vypočtěte integrál pro mnoho různých $x$. Do řešení nevkládejte tabulku hodnot, ale graf funkce. Zkuste tuto funkci opět numericky zderivovat. Co dostanete?
5. Najděte si definici hustoty pravděpodobnosti Maxwellova-Boltzmannova rozdělení $f(v)$, tedy rozdělení rychlostí molekul ideálního plynu. Spočítejte pak pomocí MC integrace střední hodnotu rychlosti definovanou \[ \langle v\rangle = \int_0^{\infty} v f(v)\,\d v\,, \] přičemž pro vzorkování použijte náhodná čísla dle Maxwellova-Boltzmannova rozdělení získaná Metropolisovým-Hastingsovým algoritmem. Hodnotu pro konkrétní zvolené parametry srovnejte s hodnotou z literatury.

1. Nalezněte všechny (tři) reálné kořeny funkce $\exp (x)-5x^2$. Výběr metody je na vás. Nezapomeňte okomentovat, jak a proč jste zvolili daný postup.
2. Newtonova metoda tak, jak jsme si ji představili funguje i pro funkce komplexní proměnné. Vaším úkolem je vykreslit tzv. Newtonovy fraktály, tedy oblasti v komplexní rovině takové, že když v nich zvolíme počáteční odhad kořenu pro Newtonovu metodu, tak dokonvergujeme k určitému kořenu. Fraktál vykreslete pro funkce $z^3-1$ a $z^6+z^3-1$, kde $z$ je komplexní číslo. Derivace těchto funkcí jsou $3z^2$, resp. $6z^5+3z^2$. Pro výpočet a vykreslení můžete použít Pythonní kód přiložený k zadání.
   Poznámka: Komplexní derivaci, pokud existuje, lze technicky spočítat stejně, jako reálnou derivaci, tedy pro ni platí stejné vzorce pro derivaci součtu, součinu a složené funkce.
   Bonus: Nalezněte co nejzajímavější nebo nejhezčí Newtonův fraktál.
3. Simulujte na počítači (nebo napočítejte ručně) elementární buněčný automat s pravidlem 54 na mřížce délky 20 s periodickými podmínkami alespoň na 10 časových kroků (víc určitě neuškodí). Na počátku má jedna buňka hodnotu 1 a zbylé 0, uvažujte periodické podmínky. Výsledek zobrazte v časoprostorovém diagramu.
4. Simulujte hrubnutí 1D povrchu pomocí modelu náhodné depozice popsaném v seriálu. Povrch má rozměr $L = 100$, na počátku je zcela hladký. Nakreslete graf závislosti hrubosti $W$ na čase pro alespoň $10^8$ kroků (jeden krok $=$ jedna nová částice), výsledek diskutujte.

1. Řešte problém dvou těles pomocí Verletovy a Rungovy-Kuttovy metody 4. řádu přes několik (mnoho) period. Krok přitom volte tak velký, aby se projevily numerické chyby, a pozorujte, jakým způsobem se chyby v obou případech projevují na tvaru trajektorie.
2. Řešte pohyb tlumeného lineárního harmonického oscilátoru daného rovnicí $\ddot {x}+2\delta \omega \dot {x}+\omega ^2 x=0$, kde $\omega $ je úhlová frekvence a $\delta $ tlumící člen. Parametry měňte a sledujte změny v chování oscilátoru. Pro jaké hodnoty parametrů se oscilátor utlumí nejrychleji?
3. Modelujte růst povrchu metodou balistické depozice a studujte statistické chování hrubosti povrchu. Nalezněte mocniny $\alpha $ a $\beta $ popisující růst před saturací a po saturaci (viz seriál). Vyjděte z kódu v seriálu. Volte takový počet kroků, abyste byli schopni dobře studovat oba režimy hrubnutí. Lineární rozměr povrchu volte alespoň $L = 256$. (Upozornění: simulace mohou trvat i několik hodin.)
4. Simulujte na čtvercové mřížce šíření zhoubného nádoru pomocí Edenova modelu. Uvažujte přitom následující obměnu: s pravděpodobností $p_1$ dojde k nákaze zdravé buňky v kontaktu s nádorovou a s pravděpodobností $p_2$ dojde k uzdravení nakažené. Volte nejprve $p_1 \gg p_2$, pak $p_1 > p_2$ a nakonec $p_1 < p_2$. Na počátku nechť je nakaženo pět buněk do tvaru kříže. Kvalitativně popište, co pozorujete.
5. Přepište kód ze seriálu pro růst fraktálního krystalu (DLA model) na hexagonální mřížce na růst na čtvercové mřížce a spočtěte dimenzi výsledného fraktálu.

Poznámka: Využít kódy přiložené k seriálu není nutné, ale doporučené.

1. Na základě Lotkova-Volterrova modelu simulujte vývoj populace predátora a kořisti (např. slunéčka sedmitečného a mšice makové) pro následující hodnoty parametrů: $r\_m = 0{,}8$, $D\_m = 1{,}0$, $r\_s = 0{,}75$, $D\_s = 1{,}5$. Počáteční populace volte po dvojicích jako $m = 0{,}5$ a $s = 2{,}0$; $m = 1{,}5$ a $s = 0{,}5$; $m = 1{,}95$ a $s = 0{,}75$. Výsledek zaneste do grafu závislosti populace predátora na populaci kořisti. Výsledky diskutujte.
   Bonus: Nalezněte tvar křivek v grafu pomocí analytických metod (integrací diferenciální rovnice).
2. Použitím kompetitivního Lotkova-Volterrova modelu simulujte vývoj dvou soupeřících populací s omezenou populační kapacitou (např. káně lesní a poštolka obecná) pro tyto hodnoty parametrů: $r\_k = 0{,}8$, $I\_{kp} = 0{,}2$, $k\_k = 2{,}0$, $r\_p = 0{,}6$, $I\_{pk} = 0{,}3$, $k\_p = 1{,}0$. Počáteční populace volte jako $k = 0{,}01$, $p = 1{,}0$. Poté změňte interakční koeficienty na $I\_{kp} = 1{,}5$ a $I\_{pk} = 0{,}6$, zbytek ponechejte. Výsledky zaneste do jednoho grafu závislosti velikosti populací na čase, diskutujte.
3. Ověřte důležitost pivotizace. Vyřešte soustavu \[\begin{equation*} \begin{pmatrix} 10^{-20} & 1\\ 1 & 1 \end{pmatrix} \begin{pmatrix} x_1\\ x_2 \end{pmatrix} = \begin{pmatrix} 1\\ 0 \end{pmatrix} \end {equation*}\] nejprve přesně (na papíře), poté s využitím LU dekompozice s (částečnou) pivotizací (využijte nějakou knihovní funkci, např. scipy.linalg.lu()), a nakonec pomocí LU dekompozice bez pivotizace (to si budete muset sami naprogramovat). Porovnejte výsledky $\vect {x}$ z jednotlivých metod a výsledky zpětného vynásobení matic $L^{-1}\cdot U$ (resp. $P\cdot L^{-1}\cdot U$ v případě s pivotizací).
4. Mějme nekonečný deskový kondenzátor se vzdáleností desek $L=10 \mathrm{cm}$ a napětím mezi deskami $U=5 \mathrm{V}$. Do kondenzátoru vložíme uzemněnou elektrodu ve tvaru nekonečně dlouhého hranolu s čtvercovou podstavou o hraně $a=2 \mathrm{cm}$, jejíž střed leží $l=6{,}5 \mathrm{cm}$ od uzemněné desky původního kondenzátoru (tak, že leží mezi deskami). Hranol je orientován tak, že jedna z jeho kratších hran je kolmá k deskám kondenzátoru. Nalezněte průběh elektrického potenciálu v kondenzátoru. Protože je problém symetrický vůči posunu v ose rovnoběžné s nekonečnou hranou hranolu, stačí jej řešit v řezu kolmém k této ose, jde tedy o 2D problém. V této rovině pak získaný průběh potenciálu také vykreslete. K řešení můžete využít program přiložený k zadání.
   Bonus: Vypočtěte a vykreslete také průběh velikosti intenzity el. pole $\vect {E}$.