11. Tréning testu


Cvičenia

tréning

  • úlohy riešte na papieri bez počítača


Test z ADŠ 2018/2019


  1. Zistiť zložitosť funkcií:

    def fun1(pole):
        vysl = i = j = 0
        while i < len(pole):
            if i < len(pole)-1:
                vysl += pole[i] - pole[i+1]
                i += 1
            else:
                i = j = j+1
        return vysl
    
    def fun2(n):
        if n == 0:
            return 1
        return n * fun2(n - 1)
    
    def fun3(n):
        x, i = 0, n
        while i > 0:
            x += fun3(i)
            i //= 2
        return x
    
    def fun4(n, mem={}):
        if n in mem:
            return mem[n]
        if n < 2:
            res = n
        else:
            res = fun4(n-1) + fun4(n-2)
        mem[n] = res
        return res
    
    def fun5(n):
        if n == 0: return 1
        return fun5(n-1) + fun5(n-1)
    
    def fun6(n):
        if n == 1: return 0
        return 1 + fun6(n//2)
    

  1. Vyrob iterátor z algoritmu prechádzania stromu do šírky (po úrovniach). Dopíš dve vyznačené metódy tak, aby iterátor postupne vracal vrcholy v poradí po úrovniach. Nepouži pritom yield.

    def breadthfirst(t):
        q = [t.root]
        while q:
            p = q.pop(0)
            print(p.data)
            for node in t.children(p):
                q.append(node)
    
    class Tree:
        root = None
        def __iter__(self):
            ...
        def __next__(self):
            ...
    

  1. Pre danú postupnosť hodnôt:

    7, 4, 10, 12, 5, 6, 3, 9, 11, 8, 2, 1
    

    vytvor haldu v 13-prvkovom poli. Prvky vkladaj (add()) presne v tomto poradí:

    ...
    

    Teraz z nej postupne trikrát odstráň minimálny prvok (remove_min()) a zakaždým vypíš obsah haldy:

    ...
    ...
    ...
    

  1. Aký tvar bude mať strom Huffmanovho kódovania a aké budú potom bitové kódy pre každé písmeno, ak máme 9 písmen 'a''i' a kde 'a' a 'b' majú frekvenciu 10 a všetky ostatné písmená majú 1.


  1. Zostav prefixový strom pre množinu slov:

    {pero, pes, para, por, ropa, rasa, rosa, rok, rak, samo, seno, seka, sal}
    

  1. Zapísali sme funkciu test(), ktorá pracuje s binárnymi stromami (s vrcholmi Node):

    class Node:
        def __init__(self, data, left=None, right=None):
            self.data = data
            self.left = left
            self.right = right
    
    def test(node):
        if node is None:
            return 0, True
        height1, test1 = test(node.left)
        height2, test2 = test(node.right)
        if not test1 or not test2:
            return 0, False
        return max(height1, height2) + 1, abs(height1 - height2) < 2
    

    Nakresli tento strom a zisti, čo na ňom vráti volanie funkcie test():

    t = Node(0, Node(1, Node(3)), Node(2, Node(4, None, Node(6)), Node(5, Node(7), Node(8))))
    >>> test(t)
    

  1. Operácie enqueue a degueue pre dátovú štruktúru front (Queue) sme realizovali poľom: pridávaním na koniec a odoberaním prvého prvku poľa:

    class Queue:
        def __init__(self):
            self.__pole = []
    
        def enqueue(self, prvok):
            self.__pole.append(prvok)
    
        def dequeue(self):
            if self.is_empty():
                raise Empty('prázdny front pre dequeue')
            return self.__pole.pop(0)
    

    Vidíme, že dequeue má zložitosť O(n). Prepíš tieto metódy: namiesto obyčajného poľa (pythonovský list) použiješ asociatívne pole (pythonovský dict), o ktorom vieme, že jeho niektoré operácie majú zložitosť O(1). Operácie takéhoto frontu by mali mať zložitosť O(1).


  1. Máme danú rekurzívnu funkciu p(i, j):

    def p(i, j):
        if j == 0:
            return 0
        if i == 0:
            return 1
        return (p(i-1, j) + p(i, j-1)) * 2
    

    Prepíš ju tak, aby ostala rekurzívna, ale aby využila asociatívne pole mem na memoizáciu výpočtu:

    def p(i, j, mem={}):
    
    
    
    
    
    
    
    .
    

  1. Pri riešení problému UNION-FIND môžeme algoritmus UNION(p, q) implementovať pomocou stromov. Začneme s 10 jednoprvkovými množinami, ktoré reprezentujú vrcholy <0, 9>:

    def FIND(p):
        while p != p.parent: p = p.parent
        return p
    
    def UNION(p, q):
        r1, r2 = FIND(p), FIND(q)
        if r1 != r2:
            if r1.rank > r2.rank: r2.parent = r1
            else:
                r1.parent = r2
                if r1.rank == r2.rank: r2.rank += 1
    

    Postupne aplikuj Union pre tieto dvojice vrcholov:

    (3, 4), (7, 6), (4, 6), (9, 2), (5, 2), (1, 8), (8, 0), (9, 2), (5, 2), (2, 6), (4, 9), (9, 8)
    

    Nakresli výsledné stromčeky.


  1. Dijkstrov algoritmus štartujeme pre graf na obrázku z vrcholu číslo 15:

    _images/test18_1.png

    Zapíš do tabuľky priebežný obsah prioritného frontu na začiatku každého prechodu cyklu algoritmu. V každom prvku je buď '-' (označuje nekonečno) alebo je tam momentálna dĺžka (obsah poľa D[vrchol]) a číslo vrcholu:

    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |0/15|  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |  - |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+----+
    |    |    |    |    |    |    |    |
    +----+----+----+----+----+----+----+
    |    |    |    |    |    |    |
    +----+----+----+----+----+----+
    |    |    |    |    |    |
    +----+----+----+----+----+
    |    |    |    |    |
    +----+----+----+----+
    |    |    |    |
    +----+----+----+
    |    |    |
    +----+----+
    |    |
    +----+
    

9. Domáce zadanie

L.I.S.T.


Dijkstrov algoritmus pre graf pomocou zoznamu hrán


Naprogramuj metódy triedy Graph (neorientovaný ohodnotený graf) pre reprezentáciu pomocou zoznamu hrán (z úlohového servera L.I.S.T. si stiahni kompletnú verziu riesenie.py):

class Vertex:
    def __init__(self, name):
        self.name = name
        self.d = None

class Edge:
    def __init__(self, start, end, weight):    # start a end sú typu Vertex
        self.start = start
        self.end = end
        self.weight = weight

class Graph:
    def __init__(self, filename):
        self.vertices = []
        self.edges = []
        ...

    def get_vertex(self, name):
        return ...

    def insert_edge(self, name1, name2, weight):
        ...

    def incident_edges(self, vertex):
        ...

Dátová štruktúra Graph bude využívať triedy Vertex (pre vrcholy) a Edge (pre hrany). Atribút vertices bude obsahovať zoznam všetkých vrcholov grafu (inštancie Vertex), atribút edges bude obsahovať všetky hrany grafu (inštancie Edge), keďže graf je neorientovaný, každá hrana bude v tomto zozname dvakrát (pre oba smery). Nepoužívaj žiadne ďalšie atribúty.

Metóda

  • __init__ prečíta textový súbor a vytvorí z neho neorientovaný graf. Každý riadok súboru popisuje jednu hranu: mená dvoch vrcholov a celočíselnú váhu (hodnotu na hrane)

  • get_vertex vráti inštanciu Vertex: ak už existuje vrchol s týmto menom v zozname vertices vráti tento objekt, inak vyrobí nový a pridá ho do zoznamu vertices

  • insert_edge vloží do edges novú hranu - vloží oba smery (parametrami sú dva reťazce a celé číslo)

  • incident_edges vráti generátor so všetkými hranami (inštancie Edge), ktoré vychádzajú z daného vrcholu (typu Vertex)

Teraz doprogramuj dijkstrov algoritmus z prednášky (metódu dijkstra(vertex) s parametrom typu Vertex), pseudokód:

def dijkstra(vrchol1):
    # pole D sú momentálne vzdialenosti od vrchol1
    D[všetky vrcholy] = inf      # nekonečno
    D[vrchol1] = 0
    queue = prioritný front všetkých vrcholov podľa kľúčov D
    visited = set()
    while queue:
        vrchol1 = queue.remove_min()
        visited.add(vrchol1)
        for vrchol2 in susediace_vrcholy(vrchol1):
            if vrchol2 nie je v visited:
                if D[vrchol1] + vaha(vrchol1, vrchol2) < D[vrchol2]:
                    D[vrchol2] = D[vrchol1] + vaha(vrchol1, vrchol2)
                    zmeň kľúč D[vrchol2] v queue pre vrchol2
    return D     # pole vzdialeností všetkých vrcholov od vrchol1

Pritom

  • namiesto poľa D použi atribút d v každom vrchole

  • prioritný front vrcholov nemusíš programovať ako optimálnu dátovú štruktúru - stačí použiť obyčajný zoznam dvojíc (d[vrchol], vrchol), ktorý bude treba udržiavať utriedený

  • metóda nebude vracať žiadnu hodnotu

Ďalej doprogramuj metódu get_path(vertex1, vertex2), ktorá pre vypočítané vzdialeností (atribút d vo vrcholoch) z dijkstrovho algoritmu dokáže zrekonštruovať cestu od štartu vertex1 do cieľa vertex2:

  • začni od konca: pre cieľový vrchol nájdi jeho predchodcu na trase (je to vrchol, ktorého vzdialenosť od štartu sa líši od cieľového presne o hodnotu na hrane)

  • metóda by mala túto cestu vrátiť ako postupnosť (list) vrcholov (inštancií Vertex), alebo vráti None, ak cesta neexistuje

Napríklad, pre subor1.txt:

7 8 6
0 3 3
1 2 6
4 7 1
4 5 1
6 7 1
3 6 2
2 5 6
3 4 5
1 4 6
5 8 1
0 1 5

program môžeš testovať, napríklad takto:

if __name__ == '__main__':
    g = Graph('subor1.txt')
    v1 = g.get_vertex('0')
    g.dijkstra(v1)
    path = g.get_path(v1, g.get_vertex('8'))
    print(*(v.name for v in path))
    path = g.get_path(v1, g.get_vertex('5'))
    print(*(v.name for v in path))

Výpis potom bude:

0 3 6 7 4 5 8
0 3 6 7 4 5

Aby si mohol spúšťať skúškové testy, program ulož do súboru skuska.py. Pozri si testovacie dáta v súboroch 'subor1.txt', 'subor2.txt', 'subor3.txt', …, ktoré bude používať testovač. Mal by si dodržať tieto vlastnosti programu:

  • Nemeň mená už zadaných atribútov (metód a premenných).

  • Do existujúcich tried môžeš pridávať vlastné atribúty a metódy.

Na začiatok súboru riesenie.py pridaj tieto tri komentárové riadky (s tvojim menom a dátumom):

# 9. zadanie: dijkstra1
# autor: Alan Turing
# datum: 30.12.2019

Riešenie odovzdaj na úlohový server L.I.S.T. najneskôr do 23:00 10. januára 2020. Môžeš zaň získať 10 bodov.


10. Domáce zadanie

L.I.S.T.


Dijkstrov algoritmus pre graf pomocou slovníka susedov


Naprogramuj metódy triedy Graph (neorientovaný ohodnotený graf) pre reprezentáciu asociatívne pole susedov (z úlohového servera L.I.S.T. si stiahni kompletnú verziu riesenie.py):

class Graph:
    def __init__(self, filename):
        self.vertices = {}
        self.d = {}
        ...

    def incident_edges(self, name1):   # generátor, vracia dvojice meno a vahu
        ...

    def dijkstra(self, name1):
        ...

    def get_path(self, name1, name2):
        ...
        return None

Atribút vertices popisuje všetky vrcholy spolu aj s príslušnými hranami a ich váhami. Realizujte ho asociatívnym poľom, v ktorom pre každé meno vrcholu priradíme asociatívne pole susediacich vrcholov. Keďže graf je neorientovaný, každá hrana bude v tejto štruktúre zaznačená dvakrát (pre oba smery). Atribút d bude asociatívne pole, ktoré sa využije pri dijkstrovom algoritme.

Metóda

  • __init__ prečíta textový súbor a vytvorí z neho neorientovaný graf. Každý riadok súboru popisuje jednu hranu: mená dvoch vrcholov a celočíselnú váhu (hodnotu na hrane)

  • incident_edges vráti generátor so všetkými susediacimi vrcholmi aj s príslušnými váhami (dvojice meno vrcholu a váha), ktoré vychádzajú z daného vrcholu

Teraz doprogramuj dijkstrov algoritmus z prednášky (metódu dijkstra(meno1) s parametrom meno štartového vrcholu), pseudokód:

def dijkstra(vrchol1):
    # pole D sú momentálne vzdialenosti od vrchol1
    D[všetky vrcholy] = inf      # nekonečno
    D[vrchol1] = 0
    queue = prioritný front všetkých vrcholov podľa kľúčov D
    visited = set()
    while queue:
        vrchol1 = queue.remove_min()
        visited.add(vrchol1)
        for vrchol2 in susediace_vrcholy(vrchol1):
            if vrchol2 nie je v visited:
                if D[vrchol1] + vaha(vrchol1, vrchol2) < D[vrchol2]:
                    D[vrchol2] = D[vrchol1] + vaha(vrchol1, vrchol2)
                    zmeň kľúč D[vrchol2] v queue pre vrchol2
    return D     # pole vzdialeností všetkých vrcholov od vrchol1

Pritom

  • namiesto poľa D použi asociatívne pole v atribúte d (kľúčom je meno vrcholu)

  • prioritný front vrcholov nemusíš programovať ako optimálnu dátovú štruktúru - stačí použiť obyčajný zoznam mien vrcholov, ktorý bude utriedený podľa príslušných hodnôt v poli d

  • metóda nebude vracať žiadnu hodnotu

Ďalej doprogramuj metódu get_path(meno1, meno2), ktorá pre vypočítané vzdialeností (v atribúte d) z dijkstrovho algoritmu dokáže zrekonštruovať cestu od štartového vrcholu s meno1 do cieľového s meno2:

  • začni od konca: pre cieľový vrchol nájdeš jeho predchodcu na trase (je to vrchol, ktorého vzdialenosť od štartu sa líši od cieľového presne o hodnotu na hrane)

  • metóda by mala túto cestu vrátiť ako postupnosť (list) vrcholov (mien), alebo vráti None, ak cesta neexistuje

Napríklad pre subor1.txt:

7 8 6
0 3 3
1 2 6
4 7 1
4 5 1
6 7 1
3 6 2
2 5 6
3 4 5
1 4 6
5 8 1
0 1 5

môžeš testovať svoj program, napríklad takto:

if __name__ == '__main__':
    g = Graph('subor1.txt')
    g.dijkstra('0')
    print('d = ', *(g.d[name] for name in sorted(g.vertices)))
    path = g.get_path('0', '8')
    print(*path)
    path = g.get_path('0', '5')
    print(*path)
    path = g.get_path('0', '0')
    print(*path)

Výpis potom bude:

d =  0 5 11 3 7 8 5 6 9
0 3 6 7 4 5 8
0 3 6 7 4 5
0

Aby si mohol spúšťať skúškové testy, program ulož do súboru reisenie.py. Pozri si testovacie dáta v súboroch 'subor1.txt', 'subor2.txt', 'subor3.txt', …, ktoré bude používať testovač. Mal by si dodržať tieto vlastnosti programu:

  • Nemeň mená už zadaných atribútov (metód a premenných).

  • Do existujúcich tried môžeš pridávať vlastné atribúty a metódy.

Na začiatok súboru riesenie.py pridaj tieto tri komentárové riadky (s tvojim menom a dátumom):

# 10. zadanie: dijkstra2
# autor: Alan Turing
# datum: 30.12.2019

Riešenie odovzdaj na úlohový server L.I.S.T. najneskôr do 23:00 10. januára 2020. Môžeš zaň získať 10 bodov.