# Search

## other

### (10 points)4. Series 31. Year - S. Rootses and automatons

1. Find all (three) real roots of the function $\exp (x)-5x^2$. Choose an appropriate method yourself and comment on the reasons behind your choice.
2. Newton’s method works even for functions of complex variable. Your task is to render so called Newton fractals, i.e. areas in complex plane in which choosing an initial guess for Newton’s method leads to converging on a specific root. Render the fractals for the functions $z^3-1$ and $z^6+z^3-1$, where $z$ is a complex number. The derivations of these functions are $3z^2$, and $6z^5+3z^2$ respectively. For calculations and rendering you may utilize the Python code attached to this task.
Note: Complex derivation, if it exists, can be calculated the same way as normal derivation..
Bonus: Find as beautiful or interesting Newton fractal as you can.
3. Simulate on computer (or calculate by hand) an elementary cellular automaton abiding by the rule 54 on a grid with size 20 and periodical conditions for at least 10 time steps (more certainly can’t hurt). At the beginning, one arbitrary cell has the value 1, the rest 0. Plot the result on a spacetime diagram.
4. Simulate the changes in roughness $W$ of a 1D surface using a model of random deposition. The roughness $W$ is given by the equation $\begin{equation*} W(t,L) = \sqrt {\frac {1}{L^d}\sum _i h_i^2-$\frac {1}{L^d}\sum _i h_i$^2} \, . \end {equation*}$ Where $d$ is the dimension, $L = 100$ is the length of the surface and $h_i$ is the height of the i-th column. Initially, the surface is perfectly flat. Plot the roughness as a function of time for at least $10^8$ steps (one step $=$ one new particle), discuss the results.
Note: Random deposition simply means that in each step of the simulation, the height of one randomly selected column will increase by one.

Lukáš and Mirek take inspiration from their lectures.

### (8 points)3. Series 31. Year - P. folded paper

Everyone has certainly heard and surely tried it: „Sheet of paper can not be folded in a half more than seven times.“ Is it really true? Find boundary conditions.

Kuba was bored and folded a paper.

### (10 points)3. Series 31. Year - S. a walk with integrals

1. Propose three different examples of Markov chains, at least one of which is related to physics. Is a random walk without backtracking (a step cannot be time reversed previous step) an example of Markov chain? What about a random walk without a crossing (it can lead to each point at most once)?
2. Consider a 2D random walk without backtracking on a square grid beginning at the point $(x,y) = (0,0)$. It is constrained by absorbing states $b_1\colon y = -5$, $b_2\colon y = 10$. Find the probability of the walk ending in $b_1$ rather than in $b_2$.
3. Simulate the motion of a brownian particle in 2D and plot the mean distance from the origin as a function of time. Assume a discrete time and a constant step size. (One step takes $\Delta t = \textrm{const}$, and the step size is $\Delta l = \textrm{const}$). A step in any arbitrary direction is possible, i.e. every step is described by it’s length and an angle $\theta \in [0,2\pi )$, while all directions are equally probable. Focus especially on the asymptotic behavior, i.e. the mean distance for $t \gg \Delta t$.
4. Error function is defined as $\begin{equation*} {erf}(x)=\frac {2}{\sqrt {\pi }}\int _0^x \eu ^{-t^2} \d t . \end {equation*}$ Calculate the integral for many different values of $x$ and plot it’s value as a function of $x$. What do you get by numerically deriving this function?
5. Look up the definition of Maxwell-Boltzmann probability distribution $f(v)$, i.e. the probability distribution of speeds of particles in an idealized gas. Utilizing MC integration calculate the mean value of speed defined as $\begin{equation*} \langle v\rangle = \int _0^{\infty } vf(v) \d v , \end {equation*}$ Use the Metropolis-Hastings algorithm for sampling the Maxwell-Boltzmann distribution. Compare the values of particular parameters with the values from literature.

Mirek and Lukáš random-walk to school.

### (3 points)2. Series 31. Year - 1. Tooth Fairy

How big would the storage facilities of the Tooth Fairy need to be, to store all of the primary teeth of all of the children of the world? Or, in other words, how rapidly would they need to grow? How long would it take for the whole Earth supply of phosphorous to be contained in those storage facilities?

Karel's mind wandered to the Discworld

### (12 points)2. Series 31. Year - E. grainy

Measure the angle of repose for at least two granular materials commonly found in the kitchen (e.g flour, sugar, salt, etc.).

Michal almost slumped.

### (10 points)2. Series 31. Year - S. derivatives and Monte Carlo integration

1. Plot the error as a function of step size for the method $\begin{equation*} f'(x)\approx \frac {-f(x+2h)+f(x-2h)+8f(x+h)-8f(x-h)}{12h} \end {equation*}$ derived using Richardson extrapolation. What are the optimal step size and minimum error? Compare with forward and central differences. Use $\exp (\sin (x))$ at $x=1$ as the function you are differentiating.
Bonus: Use error estimate to determine the theoretical optimal step size.
2. There is a file with experimentally determined $t$, $x$ and $y$ coordinates of a point mass on the website. Using numerical differentiation, find the time dependence of components of speed and acceleration and plot both functions. What is the most likely physical process behind this movement? Choose your own numerical method but justify your choice.
Bonus: Is there a better method for obtaining velocity and acceleration, then direct application of numerical differentiation?
3. We have an integral $\int _0^{\pi } \sin ^2 x \d x$.
1. Find the value of the integral from a geometrical construction using Pythagoras theorem.
2. Find the value of the integral using a Monte Carlo simulation. Determine the standard deviation.
Bonus: Solve the Buffon's needle problem (an estimate of the value of $\pi$) using MC simulation.
4. Find the formula for the volume of a six-dimensional sphere using Monte Carlo method.
Hint: You can use the Pythagoras theorem to measure distances even in higher dimensions.

Mirek and Lukáš read the Python documentation.

### (10 points)1. Series 31. Year - S. Taking Off

1. Modify the expression $\sqrt {x+1}-\sqrt {x}$, so that it isn't so prone to the problems of cancellation, ordering and smearing. Which of these problems would have originally caused a trouble with the expression and why? What is the difference between the original and the corrected expression when we evaluate it using double precision with $x=1{,}0 \cdot 10^{10}$?
2. Describe the effects of the following code. What is the difference between the functions \texttt {a()} and \texttt {b()}? With which values of \texttt {x} can they be evaluated? Don't be afraid to run the code and play with different values of the variable \texttt {x}. What is the asymptotic computation time complexity as a function of the variable 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. Let's designate $o_k$ and $O_k$ as the circumference of a regular $k$sided polygon inscribed and circumscribed respectively in a circle. The following recurrent relationships then apply $\begin{equation*} O_{2k}=\frac {2o_k O_k}{o_k + O_k} ,\; o_{2k}=\sqrt {o_k O_{2k}} . \end {equation*}$ Write a program that can calculate the value of $\pi$ using these relations. Start with an inscribed and a circumscribed square. How accurately can you approximate $\pi$ using this method? (A similar method has been originally used by Archimedes for this purpose.)

4. Lukas and Mirek play a game. They toss a fair coin: when it's tails (reverse) Mirek gives Lukas one Fykos t-shirt when it's heads (obverse) Lukas gives one to Mirek. Together they have $t$ t-shirts of which $l$ belongs to Lukas and $m$ to Mirek. When one of them runs out of t-shirts the game ends.
1. Let $m = 3$ and Lukas's supply be infinite. Determine the most probable length of the game, i.e. the number of tosses after which the game ends (because Mirek runs out of t-shirts).
2. Let $m = 10$, $l = 20$. Simulate the game using pseudorandom number generator and find the probability of Mirek winning all of Lukas's t-shirts. Use at least 100 games (more games means more precise answer).
3. How will the result of the previous task change in case Mirek „improves“ the coin and heads now occur with the probability of $5/9$?
Bonus: Calculate the probability analytically and compare the result with the simulation.
5. Consider a linear congruential generator with parameters $a = 65 539$, $m = 2^{31}$, $c = 0$.
1. Generate at least $1 000$ numbers and determine their mean and variance. Compare it to the mean and variance of a uniform distribution over the same interval.
2. Find the relationship that gives the next number in the generated sequence as a linear combination of the two preceding numbers. I.e. find the coefficients $A$, $B$ in the recurrence relationship $x_{k+2} = Ax_{k+1} + Bx_k$. If we consider each three sequential numbers as the coordinates of a point in 3D, how does the recurrence relationship influence the spatial distribution of these points?
Bonus: Generate a sequence of at least $10 000$ numbers and plot the points on a 3D graph that will illustrate the significance of the given recurrence relationship.

Mirek and Lukas dusted off some old textbooks.

### (3 points)0. Series 31. Year - 2.

We are sorry. This type of task is not translated to English.

### (9 points)0. Series 31. Year - P.

We are sorry. This type of task is not translated to English.

### (12 points)6. Series 30. Year - E. composition as if by Cimrman

Get a wine glass, ideally a thin one with a ground edge. First measure the internal diameter of the glass as a function of height from the bottom. Then use it to create sound by moving a wet finger along its edge (this requires pations). Measure how do the frequencies of tones created in this way depend on the height of water in the glass (measure at least 5 different heights and 2 frequencies at each height). Hint: If the walls of the glass are thin, we can assume the internal dimensions are the same as external and measure the diameter as a function of height from an appropriate photograph with a scale. For measuring sound we recommend the free software Audacity (Analyze $→$ Plot spectrum).

Karel likes playing with glasses at formal dinners.