====== Cvičení 11 Objekty, Halda, Asociativní pole, Stromy ====== ===== náplň cvičení ===== ==== Objekty ==== Třídy pro komplexní čísla: * Třída obsahuje dvě proměnné ''real'' a ''imag'' * Konstruktor (metoda _init_) nastavuje tyto proměnné defaultně na 0 * Pro přímý výpis funkcí print je vhodné definovat metodu ''_repr_'', která vrací string * **Pozor: init a repr má v názvu dvě podtržítka!!! ** class Complex: def __init__(self, real=0, imag=0): self.real = real self.imag = imag def amplitude(self): return self.real*self.real + self.imag*self.imag def add(self, rhs): self.real += rhs.real self.imag += rhs.imag def sub(self, rhs): self.real -= rhs.real self.imag -= rhs.imag def __repr__(self): sign = "+"; if (self.imag < 0): sign = "-"; return str(self.real) + sign + str(abs(self.imag)) + "i" def mul(self, rhs): r = self.real*rhs.real - self.imag*rhs.imag; i = self.real*rhs.imag + self.imag*rhs.real; self.real = r self.imag = i if __name__=="__main__": a = Complex() print("a=",a) b = Complex(1,-1) print("b=",b) a.add(b) print("a=",a) a.mul(b) print("a=",a) print("|a|=",a.amplitude()) print("|b|=",b.amplitude()) ==== 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. * **V tomto cvičení budeme předpokládat tuto variantu.** * 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í 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 === # 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 ==== Úkol 1: 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): pole=[10,21,7,11,31,6,1,-11,31,42,-12,80,25,-7,-12,9,14] ==== Úkol 2: Karty v haldě ==== * Upravte implementaci haldy tak, aby byla realizována min-halda s kartami ve formátu cvičení 8 příklad 1. * Vytvořte hladu z následujících karet: 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']] * 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 3: Asociativní pole a římská čísla ==== * Využijte následující asociativní pole k převodu římského čísla na dekadické číslo: conv={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000} * Převeďte na číslo např. MCMXCIX ===== 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]]: 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]; ... } ===== Domácí úkol ===== ==== Lehčí varianta:==== * Napište program **parcel.py**, který implementuje simulaci odbavení zásilek v depu podle priority a dostupných dodávek. * **Vstup** * Program čte ze standardního vstupu, na každé řádce je údaj ve tvaru: PRIORITA ID * PRIORITA je typu ''int'', ID je typu ''str'' * je-li první číslo kladné, jedná se o balíček, který zařadíme do prioritní fronty obdržených balíčků * je-li první číslo záporne, jedná se o dodávku s kapacitou -PRIORITA, která odváží maximální počet zásilek s nejvyšší prioritou * **Výstup** * Obsah dodávek uvedením identifikátoru dodávky a seznamu balíčků (jejich identifikátory oddělené mezerou), které dodávka odváží * '': ...'', * balíčky jsou v dodávce **seřazené podle priority sestupně** * není-li v depu aktuálně žádný balík, dodávka odjíždí prázdná, tj. vypíše se '':'' * Na poslední řádek vypíše program stav depa. Pokud zůstaly v depu balíčky, program vypíše řádek ''Depo: ...'', balíčky se vypisují **seřazené podle priority sestupně**. Je-li depo prázdné, vypíše se pouze ''Depo:'' * Pro načtení celého vstupu lze použít modul ''sys'' a funkci ''input_str = sys.stdin.read()'', která do stringu ''input_str'' zapíše všechny řádky ze vstupu * Při lokálním testování je potřeba ukončit zadávání vstupu kombinací kláves ''Ctrl+D'', pak bude ''sys.stdin.read()'' fungovat i lokálně. ** Příklad ** * Vstup: 24 K 13 H 25 R 1 M -4 T0 15 G 4 C -1 T1 -3 T2 12 Y * Pozn.: úvodní mezera na 4. a 6. řádku je vložena pouze pro zlepšení čitelnosti, při testování bude na vstupu mezera pouze mezi PRIORITA a ID T0: R K H M T1: G T2: C Depo: Y * Výstup: * Dodávka ''T0'' odjíždí plná, balíčky podle priority: ''R(25) K(24) H(13) M(1)'' * Dodávka ''T1'' má kapacitu 1, odváží pouze jeden balík ''G'', který má nejvyšší prioritu * Dodávka ''T2'' odveze balík ''C'', který je jako jediný v depu * Na konci v depu zůstal balík ''Y'' **Příklad II** * Vstup: -4 T2 89 KX 82 OA -3 T1 21 CN 35 QW 37 MY 32 Wg -3 T0 99 SW 33 Or * Výstup T2: T1: KX OA T0: MY QW Wg Depo: SW Or CN ==== Těžší varianta:==== * Napište program **hamming.py**, který implementuje kódování a dekódování textu pomocí [[ https://en.wikipedia.org/wiki/Hamming_code | Hammingova kódu]] Hamming(8,12) - tedy na 8 bitů kódu znaku, se použijí 4 bity pro opravu. * **Vstup** * textové řetězce ze standardního vstupu, může být více řádek * **Výstup** * v režimu kódování vypíše Hammingův kód pro danou zprávu na vstupu, bity jednotlivých znaků vstupní zprávy vypsané na jednotlivé řádky * v režimu dekódování textový řetězec s dekódovanou zprávou * ''ERROR'', pokud během načítání, dekódování došlo k chybě * **Kódování:** * První znak vstupního řetězce je 'c'. * Pro kódování je řetězec na zakódování hned za písmenem c. * **Vstup** cAhoj Hammingu! * Řetězec je od písmena c do konce řádky * **Výstup** je na každou novou řádku zakódované jedno písmeno vstupu 001000010010 010100100110 011111100110 110010100110 010000010100 000100110010 011000000110 111001100110 111001100110 101100100110 100111100110 101011000110 101101011110 101000010100 * **Dekódování** * První znak vstupního řetězce je 'd', další znaky na první řádce vstupu nejsou * Pro dekódování je na každém dalším řádku zakódováno 12 bity - hodnoty 0/1 jedno písmeno zprávy. * **Příklad vstupu:** d 010001110010 011111100110 100110011110 001101000110 111001100110 010000010100 101100100110 000000011110 011110011110 101101011110 111001100110 * **Výstup:** Lorem ipsum * **Možné zdroje chyb** * nelze určit, zda je potřeba kódovat nebo dekódovat (chybí 'c' nebo 'd' na začátku) * délka některých zakódovaných znaků se liší * v zakódovaných bitech jsou čísla mimo dvojkovou soustavu * v takovém případě je výstup ''ERROR'' * Upřesnění charakteristiky kódu: * Bity ve zprávě jsou kódovány v pořadí: * p1, p2, d1, p4, d2, d3, d4, p8, d5, d6, d7 d8 * bit d1 je nejméně vyznamný (LSB), bit d8 je nejvíce významný (MSB) * Při dekódování mohou některá písmena obsahovat jeden poškozený bit, použijte paritní bity pro verifikaci a případnou opravu poškozeného bitu před dekódováním písmene * Znak je kódován svým vnitřním kódem dostupným operací ord(znak), zpět je převeden operací chr(kod)