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
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)
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:
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
Schéma rodiny ve family.txt:
Uložení načtených dat do ' Dot ' souboru, který lze pak vykreslit do png nástrojem dot z balíku nástrojů Graphviz:
dot -Tpng family.dot > family.png
Příklad family.dot:
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]; ... }
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:
Binární haldu lze samozřejmě realizovat i s opačnou vlastností:
Použití binární haldy:
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:
Předpokládejme, že máme existující binární haldu. Vložení prvku se provede takto:
Tento algoritmus se nazývá bubble-up, jelikož při něm procházíme haldu ze spodní úrovně nahoru.
Nejjednodušší realizací binární haldy je implementaci na poli. Použijeme jednoduchý trik:
# 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
Implementujte metody pro odebrání prvku na pozici i z binární haldy:
delete(i)
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):
pole=[10,21,7,11,31,6,1,-11,31,42,-12,80,25,-7,-12,9,14]
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']]
conv={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
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 kuchařce celých čísel.
x = ( (ord(a)*256 + ord(b))*256 + ord( c ) )*256 + ord(d)
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
python3 sifruj.py 1015282856477 914394312011
na standardni vstup:
ahoj, jak se mate?vygeneruje výstup:
647324878004 696320697151 743669304106 886127950532 29493035087
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.
python3 sifruj.py 940600625927 1031749
na standardni vstup:
Uz je to jasnejsi?vygeneruje výstup:
220880649389 164682853469 771838036852 276855377185 166690468278
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.
python3 sifruj.py 854757130933 339289
na standardni vstup:
Slava! Mate to hotove.vygeneruje výstup:
237393968415 4435742947 83633252887 427633018709 332159983823 451324201656
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.
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:
Tento predmet proste nejlepsi genialni
python3 attack.py 865149046207
352566354542 704277294015 506632666345 494928356066 824421528359 325069048254 839239812833 536096809854 278474205010
Výstupem programu bude:
Tento predmet je proste genialni!!
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.
python3 attack.py 983293323431
842181607974 871844623718 433288674900 698725571210 783570923028 327222551412 311846871040 379330380505 84902973359 15529751204
Výstupem programu bude:
Na ALP je nejlepsi zkusit si nove veci.
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.
python3 attack.py 952371739433
727632176438 36244668976 814914613242 835595208469 315384816693 483612417694 400515700122 599076310518 552651231198 183702874860
Výstupem programu bude:
Bavi vas proste programovat v Pythonu3?
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.