====== Cvičení 6, Pole, matice, třídění ======

==== Úkol 1 Life ====
  * Hru [[https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life|Life]] navrhl v roce 1970 matematik John Horton Conway.
  * Pravidla hry jsou jednoduchá:
    * pokud jsou v okolí jedné buňky živé právě 3 buňky, pak v této buňce život vznikne (nebo zůstane)
    * pokud je buňka živá a v jejím okolí jsou právě 2 živé buňky, pak tato buňka bude žít i nadále
    * v ostatních případech buňka zahyne buď na osamění, nebo přemnoženost
  * Budeme uvažovat uzavřený svět, tedy sousední políčko pro první pole řádku je poslední pole řádku, sousední pole pro první řádek je poslední řádek
  * Napište program, který bude simulovat 40 kroků hry life pro toto počáteční pole:
<code python>
a = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 1, 1, 1, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
     [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
     [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
   ]
</code>

  * Vygenerování prázdného pole
<code python>[[0]*len(a[0]) for i in a]</code>
  * Využití funkce modulo (%) Vám pomůže implementovat uzavřený svět
  * Pro lepší zobrazení udělejte po každém kroku pausu 
<code python>import time
time.sleep(0.5)</code>
  * Také můžete vylepšit zobrazení tak, že místo 1 budete tisknout X a místo 0 mezeru 
<code python>''.join('X' if i!=0 else ' ' for i in x))</code>


==== Úkol 2 Prohození řádků matice ====
  * Napište program, který načte matici a následně permutaci, která definuje prohození řádků zadané matice. Na výstup program vytiskne matici s řádky prohozenými podle zadané permutace.




==== Úkol 3 Gaussova eliminační metoda ====
  * Gaussova eliminační metoda je způsob řešení soustavy lineárních rovnic, případně hledání inverzní matice, nebo i počítání determinantu

=== Úkol 3a Nalezení největšího prvku ve sloupci ===
  * Napište funkci **maximum(m,i)**, která pro zadanou matici **m** a číslo **i** najde číslo řádku v rozsahu **range(i,len(m))** takové, že prvek **m[max][i]** má největší absolutní hodnotu (funkce abs je v pythonu vestavěná standardně)

=== Úkol 3b Prohození řádku ===
  * Napište funkci **set(m,i)**, která zavolá funkci **maximum(m,i)** a pokud je návratová hodnota rozdílná od **i**, prohodí řádek **i** a **maximum(m,i)**

=== Úkol 3c Úprava řádku ===
  * Napište funkci **do_line(m,i)**, která zavolá funkci **set(m,i)** a pokud:
    * **m[i][i]** se nerovná 0 pak:
      * celý řádek **i** matice **m** vydělí hodnotou **m[i][i]**  
      * pro všechny ostatní řádky **r** matice **m** odečte od řádku **r** hodnotu **m[r][i]** násobek řádku **i**
      * vrátí hodnotu True
    * jinak vrátí False

=== Úkol 3d Gausova eliminace ===
  * Napište funkci **Gauss_elim(m)**, která pro všechna **i** z rozsahu **range(len(m))** zavolá funkci **do_line(m,i)**
  * Pokud je návratová hodnota funkce **do_line** rovna False, pak přeruší cyklus a vrací False
  * Pokud byly všechny návratové hodnoty True, pak vrátí funkce True

=== Příklad ===
  * Spusťte funkci Gauss_elim pro matici:
<code python>
m=[[12,-7,3, 26],
   [4 ,5,-6, -5],
   [-7 ,8,9, 21]]
</code>
  * Zkuste program spustit znova s použítím modulu fraction (from fractions import Fraction) a přemapováním matice na typ Fraction 
<code python>
mm = [list(map(Fraction, v)) for v in m]
</code>
  * a po výpočtu výsledek transformovat opět na reálná čísla
<code python>
result = [list(map(Fraction, v)) for v in mm]
</code>



===== domácí práce =====

==== Lehká varianta ====
  * Napište program **integral.py**, který načte ze standardního vstupu první řádek, který obsahuje polynom jako v příkladech s polynomy, na druhém řádku budou zadána dvě reálná čísla značící dolní a horní mez integrálu, který má program spočítat.
  * Výstupem programu je hodnota určitého integrálu zadaného polynomu od dolní meze po horní mez.
  * Program v souboru **integral.py** odevzdejte pomocí odevzdávacího systému (úloha HW06).
  * Tolerance odchylky řešení od referenční hodnoty je 1e-8

=== Příklad ===
Vstup:
  1 2 -2
  0.0 10.0

Výstup:
<code>
  -556.666666667
</code>

==== Těžká varianta ==== 
  * Napište program **odd.py**, který v matici celých čísel zadané na příkazové řádce (''sys.argv[1]'') najde největší souvislou podmatici libovolného rozměru, která obsahuje pouze liché hodnoty. Příklad volání:

  python3 odd.py rectangle.txt

  * Výstupem programu je plocha nalezené oblasti, na dlaší řádce jsou souřadnice levého horního rohu a na třetí řádce souřadnice pravého dolního rohu podmatice. Na prvním řádku výstupu je pouze jedno číslo označující počet prvků nalezené podmatice, na druhé řádce je levý horní roh ve formátu řádek, sloupec, na druhém řádku pravý dolní roh. Řádky i sloupce se číslují od 0 a oddělují čárkami. 
  * Velikost podmatice je určena jejím počet prvků.
  * Snažte se, aby Váš program byl co nejefektivnější, ideálně, aby jeho časová složitost odpovídala velikosti matice. Bodové ohodnocení této úlohy bude záviset na efektivnosti (rychlosti) Vašeho algoritmu.

=== Příklad ===
Matice {{courses:b3b33alp:cviceni:rectangle.txt|rectangle.txt}}:
   1  9  2  8  6  1
   8  1 11  7  6  4
  10 12  1  9 12 14
   8 10  3  5 17  8
   6  4 10 13 16 19

Výstup:
  6
  1, 2
  3, 3