АСП1/К2 2018

Zadaci

1. zadatak

Postavka

Napisati u pseudokodu iterativnu funkciju koja vrši generalizovani preorder obilazak m-arnog stabla na koje pokazuje pokazivač root. Svaki čvor stabla sadrži oznaku čvora i m pokazivača na potomke. Funkcija treba da vrati niz koji za svaki čvor stabla sadrži njegovu oznaku i nivo u stablu na kome se čvor nalazi. Komentarisati rešenje. Dozvoljeno je koristiti gotove linearne strukture podataka.

Rešenje

PREORDER M I(root, m)
if root = nil then
    return nil
end_if
INIT_STACK(S1)
INIT_STACK(S2)
STACK_PUSH(S1, root)
STACK_PUSH(S2, 1)
node = nil
depth = 0
list = nil
p = nil
while not STACK_EMPTY(S1) do
    node = STACK_POP(S1)
    depth = STACK_POP(S2)
    if list = nil then
        list = p = GETNODE
    else
        next(p) = GETNODE
        p = next(p)
    end_if
    symbol(p) = symbol(node)
    depth(p) = depth
    for i = m to 1 do
        if children(node)[i] ≠ nil then
            STACK_PUSH(S1, children(node)[i])
            STACK_PUSH(S2, depth + 1)
        end_if
    end_for
end_while
return list

Ovo rešenje se zasniva na čuvanju čvora i nivoa čvora u dva odvojena steka i korišćenju povezane liste (pošto ne znamo unapred količinu čvorova u stablu kako bismo alocirali niz). Za svaki čvor u steku dodajemo njegovu decu na jedan stek, s tim što ih dodajemo s desna na levo kako bi prvi posećeni čvor bio najlevlje (odnosno prvo) dete čvora (kao što je to i slučaj kod preorder obilaska), a njegov nivo uvećan za jedan na drugi stek.

2. zadatak

Postavka

Izvesti i objasniti izraz za određivanje minimalne visine h_min za binarno stablo sa n čvorova. Kakve osobine ima binarno stablo sa minimalnom visinom?

Rešenje

Binarno stablo sa minimalnom visinom teži da ima svaki nivo popunjen, tj. teži da bude kompletno stablo. Pošto znamo da kompletno stablo na nivou $i$ ima $2^i$ čvorova (svaki čvor osim listova ima maksimalni izlazni stepen, što je 2), i da je stoga ukupan broj čvorova u stablu jednak $n = 2^0 + 2^1 + ... + 2^h = 2^{h + 1} - 1$. To znači da je $\log_2(n + 1)$ jednako $h + 1$ i time dobijamo da je $h_{min} = \left\lceil{\log_2(n + 1)}\right\rceil - 1$.

3. zadatak

Postavka

Za neko binarno stablo preorder obilazak daje poredak ABDCEFGHI, a postorder obilazak DBFIHGECA.

1. Navesti sve čvorove koji predstavljaju listove ovog stabla.
2. Odrediti sve pretke čvora E.
3. Navesti sve čvorove koji se nalaze u podstablu čiji je koren čvor E.

Rešenje

    A
   / \
  B   C
 /   /
D   E
   / \
  F   G
     /
    H
   /
  I

1. D, F, I
2. C, A
3. F, G, H, I

4. zadatak

Postavka

Primenom LZW algoritma prikazati postupak kodiranja znakovnog niza LESQUELLES, ako je data početna tabela sa kodovima simbola. Napisati kodiranu poruku i izgled tabele simbola nakon postupka kodiranja.

Rešenje

Kodirana poruka: 012341052

Simbol	Kôd
L	0
E	1
S	2
Q	3
U	4
LE	5
ES	6
SQ	7
QU	8
UE	9
EL	10
LL	11
LES	12

5. zadatak

Postavka

Dato je stablo formirano primenom algoritma statički Huffman. Implementirati funkciju FIND_LONGEST_CODES koja vraća broj simbola koji se kodiraju najvećim brojem bita prema formiranom stablu. Funkciji je prosleđen pokazivač na koren stabla root. Napisati u pseudokodu i metodu IS EXTERNAL NODE koja proverava da li je čvor na koji pokazuje prosleđeni pokazivač eksterni.

Rešenje

FIND LONGEST CODES(root)
tail = head = GETNODE(root)
next(head) = GETNODE(nil)
head = next(head)
num_max = 0
t = nil
while tail ≠ nil do
    if value(tail) = nil then
        if tail ≠ head then
            next(head) = GETNODE(nil)
            head = next(head)
            num_max = 0
        end_if
    else
        if IS_EXTERNAL_NODE(value(tail)) then
            num_max = num_max + 1
        else
            if left(value(tail)) ≠ nil then
                next(head) = GETNODE(left(value(tail)))
                head = next(head)
            end_if
            if right(value(tail)) ≠ nil then
                next(head) = GETNODE(right(value(tail)))
                head = next(head)
            end_if
        end_if
    end_if
    t = next(tail)
    FREENODE(tail)
    tail = t
end_while
return num_max

IS EXTERNAL NODE(node)
if left(node) = nil and right(node) = nil then
    return true
else
    return false
end_if

GETNODE(value)
ALLOCATE(node)
next(node) = nil
value(node) = value
return node

FREENODE(node)
DEALLOCATE(node)

6. zadatak

Postavka

Posmatra se stablo sa slike. Povezati ga po inorder-u i ilustrovati slikom na kojoj su obeležene sve potrebne dodatne informacije. Precizno objasniti na koji način se može izvršiti ispisivanje stabla po inverznom inorder poretku.

    A
   / \
  B   C
 / \   \
F   G   Y
   /   /
  E   M
   \
    X

Rešenje

Rešenje prvog dela zadatka.

Algoritam za obilazak povezanog stabla obrnutim inorder poretkom dat je ispod.

REVERSE INORDER T(root)
node = root
while right(node) ≠ nil do
    node = right(node)
end_while
while node ≠ nil do
    P(node)
    if lf(node) = 0 then
        node = left(node)
    else
        node = left(node)
        while node ≠ nil and rf(node) = 1 do
            node = right(node)
        end_while
    end_if
end_while

7. zadatak

Postavka

Primenog algoritma dinamički Huffman dekodovati poruku 0000100101011011111101101101 ukoliko se sastoji od karaktera A, B i C koji imaju početne fiksne kodove 00, 01 i 10. Proces dekodovanja prikazati po koracima.

Rešenje

• Dekodovana poruka: ABCCAACBBB
• Krajnje Huffman-ovo stablo:

  10
 /  \
B    6
4   / \
   3   C
  / \  3
NYT  A
 0   3

8. zadatak

Postavka

U jednom programu treba modelirati odnose dugovanja i potraživanja između n firmi.

1. Predložiti odgovarajuću logičku strukturu i detaljno opisati njene osobine.
2. Predložiti i obrazložiti odgovarajaću memorijsku reprezentaciju ove strukture ako je potrebno optimizovati operaciju izračunavanja ukupnog iznosa dugovanja prema nekoj firmi, kao i određivanje njenog najvećeg dužnika.
3. Napisati pseudokod funkcije koja za zadatu firmu vraća ukupna iznos dugovanja koja ona potražuje.

Rešenje

1. Graf koji nam je u ovom slučaju potreban jeste težinski usmeren graf u kom čvorovi predstavljaju firme a grane predstavljaju dugovanja, gde grana težine w od čvora A do čvora B označava da firma A duguje firmi B iznos od w jedinica valute. Operacije koje nad njim moraju biti realizovane jesu dodavanje novog čvora i povezivanje dva čvora.
2. Optimalna memorijska reprezentacija jeste preko inverzne liste susednosti, tj. niza dužine n koji sadrži pokazivače ka ulančanim listama u kojima se nalaze svi čvorovi koji su povezani sa trenutnim čvorom. Težine grana se mogu čuvati ili u samim čvorovima ulančane liste ili u odvojenoj matrici w gde w[i, j] označava težinu grane od i ka j i može biti postavljena na ∞ ukoliko ta grana ne postoji.

   Operacija izračunavanja ukupnog iznosa dugovanja može se realizovati prolaskom kroz listu susednosti i sabiranjem svih težina grana koje ti čvorovi čine s zadatim čvorom, a može se i izmeniti struktura tako da se u zaglavlju lista susednosti čuva ukupno dugovanje bez da se poveća složenost neke druge operacije.

   Operacija određivanja najvećeg dužnika može se isto realizovati linearnim prolaskom kroz listu koji čuva najvećeg dužnika i najveći dug. Dodatna optimizacija može se postići time što se povezane liste pretvore u prioritetne redove što operaciji povezivanja dva čvora povećava složenost sa konstantne na logaritamsku ali operaciji pronalaženja najvećeg dužnika smanjuje složenost sa linearne na konstantnu, za šta smo i optimizovali.

3. U implementaciji ispod smatra se da optimizacije pomenute iznad nisu primenjene (jer bi to malo obesmislilo algoritam). Takođe se smatra da su težine grana čuvane u matrici težina w.

DEBT(G, i)
total_debt = 0
p = first(e[i])
while p ≠ nil do
    total_debt = total_debt + w[i, value(p)]
    p = next(p)
end_while
return total_debt