====== Cvičení 11: Objekty, halda, asociativní pole ======


==== Úkol 1: Genealogie (Objekty dokončení) ====

  * 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 addChild(self, node):
        self.children.append(node)

    def addParent(self, node):
        self.parents.append(node)
        
    def setPartner(self, node):
        self.partner = node

    def __repr__(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 objektů: 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'' značí že osoba ''name1'' je rodičem osoby ''name2''. ''sex1'' a ''sex2'' označují pohlaví těchto osob (buď F nebo M)
    * záznam pro partnery: ''M name1 name2 sex1 sex2'' značí že osoby ''name1'' a ''name2'' jsou partneři, ''sex1'' a ''sex2'' jsou opět F nebo 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|}} 

===== Prémie navíc: zobrazení přes dot format =====

Uložení načtených dat do '[[ https://en.wikipedia.org/wiki/DOT_(graph_description_language) | Dot ]]' souboru, který lze pak vykreslit do png nástrojem **dot** z balíku nástrojů [[http://www.graphviz.org/|Graphviz]]:
<code>
dot -Tpng family.dot  > family.png
</code>


Příklad family.dot:
<code>
digraph G {
Jana[ color=red];
Jana->Martin [label="child"];
Jana->Robert [label="child"];
Jana->Jan[color=blue; penwidth=4];
Jan[ color=green];
Jan->Petra [label="child"];
Jan->Uxana [label="child"];
Jan->Jana[color=blue; penwidth=4];
Martin[ color=green];
Martin->Jiri [label="child"];
Martin->Rudolf [label="child"];
Martin->Jana [style=dashed];
...
}
</code>








==== Binární halda ====

[[https://en.wikipedia.org/wiki/Binary_heap |  Binární halda ]] je binární stromová datová struktura. Je tvořena uzly, které mají max. dva potomky (levý a pravý potomek) (odtud přídavné jméno binární), pričemž potomek je opět uzel. Její důležitou vlastností je, že:
   * hodnota každého uzlu je **rovna nebo menší** než hodnoty jejich potomků.  
   * Pokud je tato vlastnost splněna tak platí, že prvek v tzv. kořenu stromu obsahuje **nejmenší** prvek mezi všemi prvky.
   * <fc #ff0000>**V tomto cvičení budeme předpokládat tuto variantu.**</fc>
   * Takové haldě se někdy říká min-halda.


Binární haldu lze samozřejmě realizovat i s opačnou vlastností:
   * hodnota každého uzlu je **rovna nebo větší** než hodnoty jejich potomků.  
   * Pokud je tato vlastnost splněna tak platí, že prvek v tzv. kořenu stromu obsahuje **největší** prvek mezi všemi prvky.
   * Takové haldě se říká max-halda.

Použití binární haldy:
   * Pro realizaci prioritní fronty, v důsledku toho např. pro hledání cest v grafech, mapách, plánování pohybu robotů



{{courses:b3b33alp:cviceni:heap.png?400|}}


=== Binární halda: vyjmutí nejmenšího prvku ===

Předpokládejme, že máme existující binární haldu. Při vyjmutí prvky stačí vzít prvek v kořeni stromu, neboť ten již z definice obsahuje nejmenší hodnotu mezi všemi uzly.
Po odebrání prvku je ale nutné zbylé prvky přeskupit a určit nový kořen haldy. Postup je:

  * Vyjmout prvek z kořene haldy ( prvek s nejmenší hodnotou )
  * Vzít poslední prvek v poslední úrovni a přesunout na pozici kořene.
  * Nyní je třeba nahrat prvky v haldě tak, aby byla splněna vlastnost min-haldy. Jelikož budeme začínat od kořene a procházet strom směrem dolu, říká se tomuto postupu tzv. bubble-down.
  
  
==Bubble-down:==
  * Předpokládejme, že jsme v uzlu $U$.
  * Porovnáme hodnotu $U$, $U$.left a $U$.right. Pokud je splěna vlastnost min-haldy (tj. hodnota $U$ je menší nebo rovna hodnotám jejích potomků), končíme.
  * Pokud ne, vybereme toho potomka, který je menší než $U$. Vyměníme hodnotu $U$ s tímto potomek. 
  * Pokračujeme bubble-down z tohoto potomka.
  * Algoritmus končí, pokud už jsme narazili na uzel bez potomka.


=== Binární halda: vložení prvku ===

Předpokládejme, že máme existující binární haldu. Vložení prvku se provede takto:

===Bubble-up===
  * Vložíme prvek na poslední nejpravější místo v poslední úrovni.
  * Porovnáme hodnotu tohoto prvku s jeho rodičem. Pokud je splněna vlastnost haldy (tj. u min-haldy: hodnota prvku je větší nebo rovna hodnotě jeho rodiče), pak končíme.
  * Pokud ne, vyměníme hodnotu prvku za hodnotu rodiče a opakujeme tento postup od změněného rodiče.
 
Tento algoritmus se nazývá bubble-up, jelikož při něm procházíme haldu ze spodní úrovně nahoru.


==== Realizace binární haldy na poli ====

Nejjednodušší realizací binární haldy je implementaci na poli. Použijeme jednoduchý trik:

  * Nechť uzel má v poli index $i$.
  * Jeho levý potomek má v poli index $2i+1$.
  * Jeho pravý potomek má v poli index $2i+2$.

{{courses:b3b33alp:cviceni:heap1.png?200|}}

  * Jaký je index rodiče, pokud má potomek index v poli $i$?


=== Implementace haldy z přednášky ===

<code python>
# Implementace haldy
#
# http://interactivepython.org/runestone/static/pythonds/Trees/BinaryHeapImplementation.html
# Jan Kybic, 2016

class MinHeap:
  """ binarni halda __init__ konstruktor """
  def __init__(self):
     self.heap = [] # indexujeme od nuly

  def bubble_up(self,i):
    """ probubla prvek i nahoru, zajisti splneni podminek haldy """
    while i>0:
      j=(i-1)//2 # index rodice
      if self.heap[i] >= self.heap[j]:
        break
      self.heap[j],self.heap[i]=self.heap[i],self.heap[j]
      i = j
  
  def insert(self,k):
    """ vloz prvek do haldy """    
    self.heap+=[k]
    self.bubble_up(len(self.heap)-1)

  def peek(self):
    """ vrati nejmensi prvek """
    return self.heap[0]

  def size(self):
    """ vrati pocet prvku v halde """
    return len(self.heap)

  def is_empty(self):
    """ je halda prazdna? """
    return self.size()==0 
  
  def bubble_down(self,i):
     """ probublej prvek dolu """
     n=self.size()
     while 2*i+1 < n:
        j=2*i+1 # zjisti index mensiho syna
        if j+1 < n and self.heap[j] > self.heap[j+1]:
          j+=1
        if self.heap[i]>self.heap[j]:
          self.heap[i],self.heap[j]=self.heap[j],self.heap[i]
        i=j
                  
  def pop(self):
    """ odebere nejmensi prvek a uprav haldu """
    element=self.heap[0]
    self.heap[0]=self.heap[-1]
    self.heap.pop() # smaz posledni prvek
    self.bubble_down(0)
    return element
</code>

==== Úkol 2: implementace funkce delete ===

Implementujte metody pro odebrání prvku na pozici i z binární haldy:

  * Metodu pojmenujte ''delete(i)''
  * metoda dále smaže tento prvek z haldy
  * ošetřete tuto metodu tak, aby ji bylo možné volat i na prázdnou haldu, případně pokud je i větší než velikost haldy

Pomocí této funkce smažte z haldy vytvořené z pole všechna sudá čísla (Nejdříve haldu vytvořte se všemi čísly a pak smažte všechna sudá čísla z haldy):
<code>
pole=[10,21,7,11,31,6,1,-11,31,42,-12,80,25,-7,-12,9,14]
</code>

==== Úkol 3: Karty v haldě ====
  * Upravte implementaci haldy tak, aby byla realizována min-halda s kartami ve formátu cvičení 7 příklad 6.
  * Vytvořte haldu z následujících karet:
<code>
cards = [[0, 'Q'], [2, '6'], [1, 'K'], 
         [1, '8'], [2, '10'], [2, '4'], 
         [3, '4'], [0, '4'], [1, '3'], 
         [2, '5'], [0, 'K'], [3, 'A'], 
         [1, 'J'], [0, '3'], [0, '9']]
</code>  
  * V cvičení 8 jsme pro porovnání karet využívali funkci index a dvojího porovnání (nejdříve barvu a pak hodnotu). Nyní definujte pořadí pomocí asociativního pole a operací sčítání a násobení.
==== Úkol 4: Asociativní pole a římská čísla ====
  * Využijte následující asociativní pole k převodu římského čísla na dekadické číslo:
<code>
conv={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
</code>
  * Převeďte na číslo např. MCMXCIX




===== Domácí úkol =====

Tento domácí úkol bude ohledně šifrování algoritmem RSA. Algoritmus RSA rozlišuje **veřejný** klíč a **soukromý** klíč. Pro oba klíče je potřeba mít dvě prvočísla //p//, //q//, která budou v našem případě "malá", $p< 2^{20}$ a $q < 2^{20}$.

Základem každého klíče je číslo $n = p \cdot q$.
Druhé významné číslo pro definici klíčů je hodnota funkce $\varphi(n) = (p-1)(q-1)$.
Pro skutečně velká //n// (čísla o velikosti $2^{2048}$) je pro výpočet funkce $\varphi$ nutné najít prvočísla //p//,//q//, což je v současné době prakticky neřešitelné.

**Veřejný** klíč je určen dvěma čísly $(n, e)$, kdy pro //e// platí $nsd(e, \varphi(n)) = 1$ (funkce ''nsd()'' značí největšího společného dělitele), tedy čísla //e// a $\varphi(n)$ jsou nesoudělná.

Pokud již máme definovaný veřejný klíč, pak **soukromý** klíč je definován dvěma čísly $(n, d)$, kde $d = e^{-1} \in \mathbb{Z}_{\varphi(n)}$. Číslo //d// lze spočítat pomocí rozšířeného Euklidova algoritmu. Rozšířený Euklidův algoritmus při hledání největšího společného dělitele najde i dvě čísla $\alpha$ a $\beta$, pro která platí $nsd(e, \varphi(n)) = \alpha \cdot e + \beta \cdot \varphi(n)$. I přes to, že čísla $\alpha$ nebo $\beta$ mohou být záporná, lze je použít k výpočtu //d// z čísel //e// a $\varphi(n)$.

Pokud chce Bob poslat zprávu Alici, tak zprávu zakóduje veřejným klíčem Alice, tedy pomocí dvou čísel $(n, e)$, která Alice zveřejnila. Pokud tedy Bob chce zakódovat číslo //a//, pak s využitím veřejného klíče Alice $(n,e)$ spočte číslo $b = a^e \in \mathbb{Z}_n$. Dešifrování privátním klíčem $(n, d)$ se provede obdobně, pro kód //b// se spočte číslo $c = b^d \in \mathbb{Z}_n$. Číslo //c// je rovno původnímu číslu //a//.

Tedy pro zakódování čísla a = 1634234218 veřejným klíčem $(n = 1015282856477, e = 914394312011)$ je potřeba spočítat $(1634234218^{914394312011}) \% 1015282856477$. K výpočtu této mocniny je nutné použít algoritmus rychlého mocnění.

Algoritmus pro rozšířený Euklidův algoritmus i algoritmus rychlého mocnění můžete nastudovat třeba v této [[https://ksp.mff.cuni.cz/kucharky/teorie-cisel/| kuchařce celých čísel]].




==== Lehká varianta:====

  * Napište program **sifruj.py**, který jako parametr dostane veřejný klíč Alice, tedy dvě čísla //n// a //e//. Dále si program přečte ze standardního vstupu jeden řádek textu a tento text zakóduje následujícím způsobem:
    * ze čtyř po sobě jdoucích znaků 'abcd' textové zprávy vypočtěte číslo ''x = ( (ord(a)*256 + ord(b))*256 + ord( c ) )*256 + ord(d)''
      * pokud by vstupní řetězec neobsahoval 4 znaky, pak se doplní nulovými znaky jejichž hodnota ord je rovna 0
    * na výstup se zapíše šifra čísla x, tedy hodnota $(x^e)\%n$
    * Př.: pro řetězec ''pes kocka slon'' se postupně zakódují podslova ''pes '', ''kock'', ''a sl'' a ''on'' a šifry těchto 4 řetězců se vypíší na výstup
  * Vstup programu:
    * sys.argv[1] - obsahuje číslo //n// z veřejného klíče Alice
    * sys.argv[2] - obsahuje číslo //e// z veřejného klíče Alice
    * input() - vrátí řetězec, tedy zprávu, kterou máte zašifrovat veřejným klíčem
  * Výstup programu:
    * celá čísla oddělená mezerami, každé číslo odpovídá šifře pro 4 znaky vstupní zprávy

=== Příklady ===
  * Po spuštění programu ''python3 sifruj.py 1015282856477 914394312011'' na standardni vstup:
<code>
ahoj, jak se mate?
</code>
vygeneruje výstup:
<code>
647324878004 696320697151 743669304106 886127950532 29493035087
</code>

Zdůvodnění: Text ''ahoj, jak se mate?'' se převede na čísla  1634234218, 740321889, 1797288805, 544039284, 1698627584, která se veřejným klíčem zašifrují na uvedené kódy.

  * Po spuštění programu ''python3 sifruj.py 940600625927 1031749'' na standardni vstup:
<code>
Uz je to jasnejsi?
</code>
vygeneruje výstup:
<code>
220880649389 164682853469 771838036852 276855377185 166690468278
</code>

Zdůvodnění: Text ''Uz je to jasnejsi?'' se převede na čísla  1434067050, 1696625775, 543842675, 1852140147, 1765736448, která se veřejným klíčem zašifrují na uvedené kódy.

  * Po spuštění programu ''python3 sifruj.py 854757130933 339289'' na standardni vstup:
<code>
Slava! Mate to hotove.
</code>
vygeneruje výstup:
<code>
237393968415 4435742947 83633252887 427633018709 332159983823 451324201656
</code>

Zdůvodnění: Text ''Slava! Mate to hotove.'' se převede na čísla  1399611766, 1629560909, 1635018016, 1953439848, 1869901686, 1697513472, která se veřejným klíčem zašifrují na uvedené kódy.


==== Těžká varianta:====

  * Napište program ''attack.py'', který dostane číslo //n// z veřejného klíče a zprávu zakódovanou veřejným klíčem Alice. Víte, že číslo //e// z veřejného klíče Alice je větší než $2^{18}$ a menší než $2^{20}$. Program ''attack.py'' dekóduje zprávu a na standardní výstup vypíše tuto dekódovanou zprávu. O vstupní zprávě víte, že obsahuje alespoň jedno z následujících slov:
<code>
Tento predmet proste nejlepsi genialni
</code>

  * Vstup programu:
    * sys.argv[1] - číslo //n// z veřejného i privátního klíče Alice
    * input() - zpráva zakódovaná veřejným klíčem Alice
  * Výstup programu:
    * dekódovaná zpráva - jeden řádek textu.
  * Poznámka:
    * Nejdříve si naprogramujte lehkou úlohu, až budete umět zprávu kódovat, pak obdobným způsobem můžete zprávu dekódovat po výpočtu čísel $\varphi(n)$, $e$ a $d$.
    * Pro dekódování je nutné vyzkoušet všechny hodnoty //e// která jsou větší než $2^{18}$ a menší než $2^{20}$ a pro která platí $nsd(e, \varphi(n)) = 1$

=== Příklad ===

  * Při spuštění programu ''python3 attack.py 865149046207''
<code>
352566354542 704277294015 506632666345 494928356066 824421528359 325069048254 839239812833 536096809854 278474205010
</code>

Výstupem programu bude:
<code>
Tento predmet je proste genialni!!
</code>

protože $p=932119$ a $q=928153$, pak $\varphi(n)=865147185936$ a $e=305867$ a $d=696989570531$. Tyto hodnoty jsou použity pro dekódování zprávy.

  * Při spuštění programu ''python3 attack.py 983293323431''
<code>
842181607974 871844623718 433288674900 698725571210 783570923028 327222551412 311846871040 379330380505 84902973359 15529751204</code>

Výstupem programu bude:
<code>
Na ALP je nejlepsi zkusit si nove veci.
</code>

protože $p=1025147$ a $q=959173$, pak $\varphi(n)=983291339112$ a $e=599311$ a $d=538813418959$. Tyto hodnoty jsou použity pro dekódování zprávy.

  * Při spuštění programu ''python3 attack.py 952371739433''
<code>
727632176438 36244668976 814914613242 835595208469 315384816693 483612417694 400515700122 599076310518 552651231198 183702874860</code>

Výstupem programu bude:
<code>
Bavi vas proste programovat v Pythonu3?
</code>

protože $p=1011817$ a $q=941249$, pak $\varphi(n)=952369786368$ a $e=766663$ a $d=247562256631$. Tyto hodnoty jsou použity pro dekódování zprávy.