Warning
This page is located in archive.

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

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ů

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

  • 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 ' 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];
...
}

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áží
      • <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:
  • 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í 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)
courses/b3b33alp/cviceni/t11.txt · Last modified: 2019/12/16 09:12 by vonasvoj