Seriál 31. ročníku

Text seriálu

Přílohy a pomocné materiály k seriálu

  • Tutoriál do jazyka Java Poměrně ucelený úvod do jednoho z nejpoužívanějších programovacích jazyků, který byl sepsán pro přednášku na FYKOSím soustředění.

Úlohy

(10 bodů)1. Série 31. Ročníku - S. Rozjezdová

 

  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.

Mirek a Lukáš oprašovali staré učební texty.

(10 bodů)2. Série 31. Ročníku - S. derivace a Monte Carlo integrace

 

  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.

Mirek a Lukáš čtou dokumentaci k Pythonu.

(10 bodů)3. Série 31. Ročníku - S. na procházce s integrály

  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.
Tato stránka využívá cookies pro analýzu provozu. Používáním stránky souhlasíte s ukládáním těchto cookies na vašem počítači.Více informací

Partneři

Pořadatel

Mediální partner


Created with <love/> by ©FYKOS – webmaster@fykos.cz