====== Cvičení 11 Halda, asociativní pole ======
===== náplň cvičení =====
==== Úkol 1: Genealogie ====
* Využijte následující třídu pro reprezentaci rodinných vztahů
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
* 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:
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:
* Č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]]:
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 ====
[[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:internal: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:
""" binární halda, implementovaná pomocí metod """
def __init__(self):
self.heap = [] # indexujeme od nuly
def bubble_up(self,i):
""" probublá prvek 'i', zajistí splnění vlastnosti haldy """
while i>0:
j=(i-1)//2 # index rodiče
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):
self.heap+=[k]
self.bubble_up(len(self.heap)-1)
def peek(self):
""" vrátí nejmenší prvek """
return self.heap[0]
def size(self):
return len(self.heap)
def is_empty(self):
return self.size()==0
def bubble_down(self,i):
n=self.size()
while 2*i+1 < n:
j=2*i+1 # zjisti index menšího 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):
""" odeber a vrať nejmenší prvek """
element=self.heap[0]
self.heap[0]=self.heap[-1]
self.heap.pop() # smaž poslední 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
===== Domácí úkol =====
==== Lehká varianta:====
* Napište program **print.py**, který implementuje prioritní tiskovou frontu.
* Program čte ze standardního vstupu, na každé řádce je:
* jedna tisková dávka ve tvaru: číslo mezera řetězec. Číslo reprezentuje prioritu dávky, řetězec její obsah.
* požadavek od tiskárny na vytisknutí ve tvaru:-1
* pro načítání použijte smyčku
for line in sys.stdin:
# zpracuj line
* Program ukládá tiskové dávky do prioritní fronty. Pokud je požadavek od tiskárny, odebere nejdříve dávku s nejvyšší prioritou, vytiskne její obsah na standardní výstup.
* Pokud je standardní vstup prázdný, program vyprázdní frontu v pořadí priorit na standardní výstup.
* Váš program **print.py** odevzdejte do odevzdávacího systému jako **HW10.**
== Příklad ==
60 se
58 zbraní
90 zelnou
38 mě
100 Polévku
57 střelnou
80 jedla
-1
-1
-1
32 polila
20 skolila
51 pasem
24 ji
75 jsem
-1
-1
40 kdyby
55 za
-1
-1
25 bych
30 na
-1
-1
35 byla
27 místě
má výstup:
Polévku
zelnou
jedla
jsem
se
zbraní
střelnou
za
pasem
kdyby
mě
byla
polila
na
místě
bych
ji
skolila
==== Těžká varianta:====
Úkolem je implementovat kompresi textu pomocí [[ https://cs.wikipedia.org/wiki/LZ77 | algoritmu LZ77]].
* Program **lz77.py** buď kóduje, nebo dekóduje v závislosti na zadaném vstupním parametru (viz dále)
* Kódování:
* Vstupní data se čtou ze standardního vstupu - pro načítání použijte smyčku for line in sys.stdin:
* Vstupní data obsahují pouze text se znaky v rozsahu 0-127 (anglická abeceda a základní symboly) [[ https://cs.wikipedia.org/wiki/ASCII | ASCII 7-bit ]]
* Algoritmus bude pracovat pouze na jedné řádce, pro novou řádku začne s prázdným bufferem.
* Velikost bufferu pro najití opakující se sekvence bude 32 znaků, maximální délka opakující se sekvence bude 5.
* Pokud v bufferu nebude nalezena sekvence, pak se písmeno zkopíruje na výstup a do bufferu.
* Pokud v bufferu bude nalezena sekvence o délce více než jeden znak, pak se zakóduje následujícím způsobem:
* nastaví se bit číslo 7
* pro zakódování vzdálenosti (//offset//) od začátku bufferu se použije následujících 5 bitů (bity 2-6)
* pro zakédování délky (//length//) se použijí 2 spodní bity, přičemž získaná délka se zmenší o 2 (tedy délka 2 se kóduje 0, délka 3 kód 1, délka 4 kód 2 a délka 5 kód 3) (bity 0-1)
* výstupní znak se tedy získá zn = chr(0x80 | (offset << 2) | ((length-2)&0x3))
* celá sekvence se přesune do bufferu
* pokud by buffer obsahoval více výskytů té samé sekvence, pak se pro zakódování použije sekvence s nejmenším offsetem
* Příklad:
Vstupní řádka obsahuje
nenaolejuje-li te julie naolejuje te julian
Výstupem je text:
nenaolejuje-li te °À·µan
kde špatně tisknutelné znaky jsou dvojice informací (offset, length):
nenaolejuje-li te (7,2)(12,2)(16,2)(2,5)(7,4)(13,5)(13,3)an
Protože v případě (7,2) je hodnota bufferu:
nenaole|ju|je-li te (7,2)
0123456|78|911111111
| | 01234567
|ju|
V případě (13,5) je hodnota bufferu:
enaolejuje-li| te j|ulie naolejuje(13,5)
0123456789111|11111|11222222222233
012|34567|89012345678901
| te j|
* Dekódování
* Pro dekódování je nutné zadat jako první vstupní argument programu hodnotu **-d**
* Dekódování probíhá opět po řádkách
* Znak, jehož hodnota //ord(zn)// je menší než 128 se vytiskne na výstup
* Znak, jehož hodnota //ord(zn)// je větší nebo rovna 128 se zpracuje:
* na výstup i do bufferu se vloží nalezený úsek z bufferu, začínající //offset// od začátku bufferu a mající délku //length//
length = 2+(ord(zn)&3)
offset = ((ord(zn)>>2) & 0x1f)
=== Příklad ===
* K otestování správné činnosti můžete zkusit rozbalit následující soubor {{courses:b3b33alp:rikadla_lz.txt | rikadla_lz.txt}} a měly byste dostat tento výchozí soubor {{courses:b3b33alp:rikadla.txt | rikadla.txt}}.
* Příklad spuštění dekomprese:
python3 lz77.py -d rikadla.txt
* Příklad spuštění komprese:
python3 lz77.py rikadla.lz