====== Cvičení 12, Náhodná čísla, grafický výstup ======

===== Quick Testy =====

V průběhu týdne se zde objeví zadání pro Quick Test Q1 a Q2. Tyto testy nejsou povinné, slouží hlavně jako trénink ke zkoušce.
Doporučujeme všem si quick test vyzkoušet, necháváme na Vás, kdy si test zkusíte. Vyčleňte si na test alespoň 1 hodinu a změřte si, jak dlouho Vám bude trvat odevzdat funkční program. Optimálně byste měli quick test vyřešit do 30 minut. Ten kdo nevyřeší quick test ani do 1.5 hodiny tak by zkouškou z ALP neprošel a měl by si zkusit vyřešit před zkouškou ještě více příkladů.

==== Quick test QT1 ====

Napište program **polyvalue.py** a odevzdejte ho jako příklad QT1. 

Program polyvalue.py přečte jednu řádku ze standardního vstupu, která obsahuje reálná čísla oddělená mezerou.
Mějme zadanou funkci $f(x)=(\frac{1}{2})x^4-x^3-2 \cdot x^2 +x$.
Výstupem programu budou tři čísla na jedné řádce oddělené mezerou:
  * první číslo je index prvku ve vstupním poli, ve kterém funkce $f(x)$ nabývá největší hodnoty. Pokud $f(x)$ nabývá maxima pro více prvků, vraťte nejmenší index. Prvky ve vstupním poli jsou indexovány od 0.
  * Druhé čílo je počet prvků ze vstupního pole, pro které je $f(x)<0$
  * Třetí číslo je index prvku ve vstupním poli, pro které funkce $f(x) \cdot x^2$ nabývá minima. Pokud funkce $f(x) \cdot x$ nabývá minima ve více prvcích, vraťte nejmenší index.
:"
Předpokládejte, že vstup je zadán korektně, tj. vždy je zadáno alespoň jedno reálné číslo a na vstupu není nic kromě reálných čísel.

=== Bodování ===

Pole různých délek - 10 testů - 2s/test - 6 bodů - 0.6 za každý správný výsledek

Při řešení můžete použít libovolné funkce jazyka Python, včetně standartních knihoven dostupných v systému Brute


== Příklad 1 ==
Vstup:
<code>1 0 0.5</code>

Výstup:
<code>1 2 0</code>

Hodnoty $f(x)$ pro $x$ ze vstupního pole jsou [−1.5, 0.0, −0.09375],    tedy   maximum   je   na   pozici 1, dále pro  dva vstupy nabývá $f(x)$ záporných  hodnot,  tedy druhé číslo na výstupu je 2.  Pro poslední část je $x^2·f(x)$ nejmenší pro vstup s indexem 0, tedy $x= 1$ $1^2·f(1) = −1.5$.

== Příklad 2 ==

Vstup:
<code>0.5 1 -1</code>

Výstup:
<code>0 3 1</code>

== Příklad 3 ==

Vstup:
<code>-0.5 0.2 0.4 -0.7 1.0 1.5 3.4 -2.5</code>

Výstup:
<code>7 4 5</code>


==== Quick test QT2 ====

Napište program **word_prefix.py** a odevzdejte ho jako příklad QT2. 

Program word_prefix.py dostane dva vstupní argumenty z příkazové řádky:
  * první argument je název souboru, který obsahuje na každém řádku jedno slovo
  * druhý argument je prefix, který budeme hledat

Výstup:
  * první řádka obsahuje číslo, kolik slov ze zadaného souboru začíná na zadaný prefix
  * druhá řádka obsahuje nejdelší slovo ze souboru, které začíná na daný prefix. Pokud žádné slovo v zadaném souboru nezačíná na zadaný prefix vypíše se <code>None</code>

Předpokládejte, že vstup je zadán korektně, tj. zadaný soubor existuje

=== Bodování ===

10 testů - 2s/test - 6 bodů - 0.6 za každý správný výsledek

Při řešení můžete použít libovolné funkce jazyka Python, včetně standartních knihoven dostupných v systému Brute


== Příklad 1 ==
Následující příklady používají tento soubor slova.txt
<code>
INTEGRITY
LONER
LANGRELS
NONCOLLEGE
INTERRUPTIVE
MONOCRYSTALLINE
NOSTALGIST
MONGOE
MOBILISE
ITALIC
NEUROSIS
ISOGONS
NANDINS
LURINGLY
OATER
MYCELIA
NITPICKIEST
MILLBOARDS
OVEREXPLAINS
NONSUGARS
INCURVE
INFANCIES
</code>

Spuštění programu:
<code>python3 word_prefix.py slova.txt IN</code>

Výstup:
<code>
4
INTERRUPTIVE
</code>

== Příklad 2 ==

Spuštění programu:
<code>python3 word_prefix.py slova.txt NON</code>

Výstup:
<code>
2
NONCOLLEGE
</code>

== Příklad 3 ==

Spuštění programu:
<code>python3 word_prefix.py slova.txt NOT</code>

Výstup:
<code>
0
None
</code>





==== Genealogie ====

  * Využijte následující třídu pro reprezentaci rodinných vztahů
<code python>
class Person:
    def __init__(self, name, sex):
        self.name = name
        self.sex = sex   
        self.children = []  
        self.parents = []   # parents of this node
        self.partner = None   # partner (=husband/wife of this node)

    def add_child(self, node):
        self.children.append(node)

    def add_parent(self, node):
        self.parents.append(node)
        
    def set_partner(self, node):
        self.partner = node

    def __str__(self):
        s = "Female" if self.sex == 'F' else "Male" 
        return self.name + " " + s

</code>
    * Každá osoba může mít více potomků a max. jednoho partnera (manžela/manželku)
    * Třída by měla obsahovat:
      * Seznam potomků, odkaz na rodiče, a partnera
      * Metody pro manipulaci s těmito prvky (např. addChild, setPartner ..)
  
  * Vytvořte objekt Tree - genealogický strom, který bude obsahovat seznam všech lidí a bude umět přidávat lidi i vztahy mezi nimi.
  * Objekt Tree otestujte přidáním 4 objekty: dva partnery a dvě děti. 
  * Otestujte, zda byly vytvořeny správné vazby, tj. aby objekty děti ukazovaly na rodiče a naopak.

  * Napište funkce pro:
    * nalezení všech vnuků dané osoby
    * nalezení všech vnuček dané osoby
    * nalezení všech babiček dané osoby


  * Rozšiřte předchozí kód o načítání ze souboru:
    * na každém řádku je jeden záznam
    * záznam pro rodiče-děti: 'P name1 name2 sex1 sex2', kde P definuje vztah osoba name1 je rodičem osoby name2 a sex1, sex2 označují pohlaví těchto osob (buď F nebo M)
    * záznam pro partnery: 'M name1 name2 sex1 sex2', name1 a name2 jsou partneri, sex1, sex2 je F/M 
    

Vstupní soubor family.txt:
<code>
M Jana Jan F M
P Jana Martin F M
P Jana Robert F M
P Robert Gabriel M M
P Robert Oleg M M
P Robert Ondrej M M
P Martin Jiri M M
P Martin Rudolf M M
P Jan Petra M F
P Jan Uxana M F
P Uxana Klara  F F
P Uxana Jakub F M
P Uxana Adam F M
P Petra Alex F M
P A C M M
P A D M F
P D K F F
P C J M M 
P C I M F
P C H M M
P B E F F
P B F F M 
P B G F F
</code>

Schéma rodiny ve family.txt:

   * Červeně: females
   * Modrá hrana: partneři
   
{{courses:b3b33alp:cviceni:family.png?800|}} 




==== Generování (pseudo)náhodných čísel ====

  * Co je to "náhodné" číslo? 
  * Lze generovat náhodná čísla na deterministickém stroji?
  * Pro generování opravdu náhodný čísel je nutné použít vnější zdroj, např. šum diody, což je ne vždy možné.
  * Jiné řešení spočívá ve výpočtu takové řady čísel, která se na 'dostatečně krátkém' úseku jeví jako náhodná 
  * Nejčastěji používané: [[https://en.wikipedia.org/wiki/Linear_congruential_generator | LCG ]] 
 
=== Princip LCG ===
  * Generujeme posloupnost čísel $x_{n+1} = (ax_n + c)\,\, \mathrm{mod}\,\, m $
  * kde $x_n$ je předchozí číslo, $x_{n+1}$ je následující číslo
  * $a,c,m$ jsou konstanty.
  * $m$ určuje periodu posloupnosti. 
  * Naprogramujte toto LCG s parametry $a=1$, $c=1$, $m=5$. 
  * Pozorujte, co se stane při $m=6$.
  * Prvnímu číslu posloupnosti říkáme **seed**
  
=== Generování náhodných čísel v Pythonu === 

  * Modul **random**
  * funkce 'random()': generuje náhodné číslo z rovnoměrného rozdělení v rozsahu $<0,1)$.
  * funkce 'randint(a,b)': náhodné int číslo z rovnoměrného rozdělení v rozsahu $<a,b)$.
  * Uvědomte si, že horní mez není zahrnuta!
   

<code python>
import random

for i in range(10):
   print(random.random())
</code>

<code python>
import random

for i in range(10):
   print(random.randint(-10,10))
</code>

  * Python defaultně nastavuje **seed** tohoto generátoru na aktuální čas.
  * Seed lze nastavit ručně: ''random.seed( cislo )''





==== Vytváření jednoduché grafiky ====
  * Existuje mnoho knihoven realizujících grafiku.
  * Knihovna Matplotlib: {{http://matplotlib.org/}}
    * podobné ovládání jako příkaz ''plot'' v Matlabu
   
Hlavním objektem je ''plt'' z modulu ''matplotlib.pyplot'', který poskytuje spoustu metod ke kreslení různých funkcí.<code python>
import numpy as np
import matplotlib.pyplot as plt

x = np.arange(0.,10.,0.1)
y = np.sin(x)
plt.plot(y)
plt.show()
</code>
  
{{courses:b3b33alp:cviceni:graf1.png?300|}}  

Všimněte si, ze výsledný graf je na ose 'x' číslován od 0 do 100, neboť to je velikost pole 'y'. Další možností je na zobrazit funkci sinus společně s osou 'x' definovanou dle pole 'x':<code python>
plt.plot(x,y)
</code>
    
{{courses:b3b33alp:cviceni:graf2.png?300|}}

A pomocí volání funkcí 'x/ylabel' nastavíme popisky jednotlivých os<code python>
plt.xlabel('osa x')
plt.ylabel('osa y')
</code>

  
**Samostatné úsečky:** je třeba zadat pole počátečních x-ových a y-ových souřadnic.
  
<code python>
plt.plot([x1,x2],[y1,y2],'k-');
</code>




**Uložení obrázků** do souboru: příkaz: [[ http://matplotlib.org/api/pyplot_api.html#matplotlib.pyplot.savefig | savefig ]]. Pro současné ulozeni obrázků do souboru a zobrazení je třeba volat ''savefig'' před příkazem ''show''.
<code python>
plt.savefig('jmeno.png')
</code>


**Kreslení histogramu** - příkaz [[ http://matplotlib.org/api/pyplot_api.html#matplotlib.pyplot.hist | hist ]]

<code python>
import numpy as np
import matplotlib.pyplot as plt

size = 10000
y = np.random.randn(size)
n, bins, patches = plt.hist(y, 50, normed=0, alpha=0.74)
plt.savefig('histogram1.png', dpi=600)
plt.show()
</code>


{{courses:b3b33alp:cviceni:histogram1.png?300|}}

Poznámka: meze grafu lze určit i ručně příkazem [[ http://matplotlib.org/api/pyplot_api.html#matplotlib.pyplot.axis | axis ]]

<code python>
plt.axis([-5,5, 0, 0.5])
</code>

zobrazí graf na ose 'x' v rozsahu -5,5 a na ose 'y' v rozsahu 0 až 0.5.


==== Úkol 4: zobrazení histogramu ====

  * Vygenerujte náhodná čísla z Gaussova rozdělení se střední hodnotou 5 a $\sigma=15$.
  * Vygenerujte náhodná čísla z Gaussova rozdělení se střední hodnotou 0 a $\sigma=5$.
  * Zobrazte příslušné histogramy do jednoho grafu


==== Kreslení fraktálů ====

{{courses:b3b33alp:cviceni:fractal_example.png?300}}

<code python>
import numpy as np
import matplotlib.pyplot as plt

def drawBranch(x, y, length, angle):

    # Konec rekurze
    if (length < 0.3):
        return
        
    a1 = 0.15
    a2 = -0.15

    s = 0.7
    l2 = s*length
    
    x1 = x + l2 * np.cos(angle)
    y1 = y + l2 * np.sin(angle)

    plt.plot([x,x1],[y,y1], 'k-')
    drawBranch(x1, y1, l2, angle+a1)
    drawBranch(x1, y1, l2, angle+a2)
    
if __name__ == '__main__':

    drawBranch(5,0,6,1.57)
    plt.show()

</code>

{{courses:b3b33alp:cviceni:fractal_example.png?300}}