Cvičení 11 Halda, asociativní pole

• 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

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:

• 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ů

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.

• 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.

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

• 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.

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$.

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

# 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

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]

• 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í.

• 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

• Napište program parcel.py, který implementuje simulaci odbavení zásilek v depu podle priority a dostupných dodávek.
• 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
• Objeví-li se na vstupu dodávka, program vypíše její identifikátor a id balíčků, které odváží <ID_dodavka>: <id> <id> …, 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 <ID_dodavka>:
• Na poslední řádek vypíše program stav depa. Pokud zůstaly v depu balíčky, program vypíše řádek Depo: <id> <id> …, balíčky se vypisují seřazené podle priority sestupně. Je-li depo prázdné, vypíše se pouze Depo:
• Odevzdejte do odevzdávacího systému jako HW10.

• Vstup:
• 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

24 K
13 H
25 R
 1 M
-4 T0
 4 C
-4 T1
-3 T2
15 G
12 Y

T0: R K H M
T1: C
T2:
Depo: G 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 4, ale odváží pouze balík C, který je jako jediný ve frontě
• Dodávka T2 odjíždí prázdná, v depu není žádný balík
• Na konci v depu zůstaly balíky G a Y

Úkolem je implementovat kódování a dekódování textu pomocí Hammingova kódu Hamming(8,12) - tedy na 8 bitů kódu znaku, se použijí 4 bity pro opravu.

• Program čte data ze standardního vstupu
• Program buď kóduje, nebo dekóduje v závislosti na zadaném vstupu
  • Kódování:
    • Vstupní data jsou určena buď pro kódování, nebo dekódování. Rozhodující je první znak 'c' - pro kódování a 'd' pro dekódování.
    • Pro kódování je řetězec na zakódování hned za písmenem c.
    • Příklad:

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í
  • 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:

d
001000010110
010100100111
011111100100
110010110110
010010010100
000100010010
011000000100
111011100110
111001100100
101100100111
100110100110
101001000110
101001011110
100000010100

• Při dekódování je nutné odhalit, zda byla data poškozena a případně jeden bit zprávy opravit
• Pokud by první znak nebyl ani d, ani c, nebo pokud by pro dekódování zprávy nebylo zadáno 12 bitů (znaků 0 nebo 1), pak program vypíše ERROR
• Pokud je zadaný vstup programu správný, výstupem je dekódovaný řetězec vytištěný na jeden řádek

Ahoj Hammingu!

• 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)
• 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)
• Program splňující zadání odevzdejte do odevzdávacího systému jako hamming.py, úkol HW10.