АСП1/Јул 2020

Zadaci

Prvi kolokvijum

1. zadatak

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

Potrebno je retku matricu sa slike predstaviti korišćenjem ulančanih lista na dva načina. Ukratko objasniti kako se to može postići i namenu svakog polja u zapisu kojim je predstavljen jedan element liste, a zatim prikazati i njihov sadržaj ako je podrazumevana vrednost 0 za oba načina.

Retka matrica sa slike

0	3	12	0	0
0	1	0	74	0
0	7	0	32	0
8	0	2	15	0
0	0	0	98	0

2. zadatak

Postavka

Posmatra se stek implementiran dvostruko ulančanom listom sa zaglavljem, koje sadrži pokazivač na prvi element liste. Pored standardnih operacija, neophodno je podržati i efikasnu operaciju dohvatanja maksimalnog elementa na steku (u O(1)).

1. Ako se u zaglavlju nalazi još jedan pokazivač na dodatnu listu, objasniti kako se ta dodatna lista može koristiti za implementaciju dodatne tražene operacije, bez gubitka efikasnosti standardnih operacija.
2. Koristeći ideju opisanu pod a), napisati tražene operacije.

Rešenje

Dohvatanje maksimalnog elementa u O(1) postižemo dodatnom listom koja čuva dotadašnji maksimalni element. Lista koja drži elemente se zove stack, a lista koja drži maksimalne elmente se zove max.

PUSH(header, x)
if header = nil then
    return
end_if
t = GETNODE()
info(t) = x
next(t) = stack(header)
stack(header) = t
t = GETNODE()
if max(header) ≠ NIL and x < max(header) then
    info(t) = info(max(header))
else
    info(t) = x
end_if
next(t) = max(header)
max(header) = t
POP(header)
if header ≠ NIL and stack(header) ≠ NIL then
    t = stack(header)
    stack(header) = next(stack(header))
    value = info(t)
    FREENODE(t)
    t = max(header)
    max(header) = next(max(header))
    FREENODE(t)
    return value
end_if
return NIL
MAX(header)
return info(max(header))

3. zadatak

Postavka

Transformisati izraz u infiksnom obliku A*(B+C)*(A-D!!)+F/G+K u ekvivalentni izraz u postfiksnoj formi. Tabelu prioriteta operatora dopuniti odgovarajućim vrednostima, pri čemu treba usvojiti standardne prioritete i grupisanje za operacije +,-,* i /. Operacija faktorijel ! unarna operacija koja se grupiše sleva na desno i ima najveći prioritet od svih aritmetičkih operacija. Transformaciju izraza prikazati po koracima.

Rešenje

Operator	Ulazni prioritet	Stek prioritet	Rang
+, -	2	2	-1
*, /	3	3	-1
!	5	4	0
(	6	1	0
)	0	-	0

Simbol	Stek	Postfiksni izraz	Rang
A		A	1
*	*	A	1
(	*(	A	1
B	*(	AB	2
+	*(+	AB	2
C	*(+	ABC	3
)	*	ABC+	2
*	*	ABC+*	1
(	*(	ABC+*	1
A	*(	ABC+*A	2
-	*(-	ABC+*A	2
D	*(-	ABC+*AD	3
!	*(-!	ABC+*AD	3
!	*(-!!	ABC+*AD	3
)	*	ABC+*AD!!-	2
+	+	ABC+*AD!!-*	1
F	+	ABC+*AD!!-*F	2
/	+/	ABC+*AD!!-*F	2
G	+/	ABC+*AD!!-*FG	3
+	+	ABC+*AD!!-*FG/+	1
K	+	ABC+*AD!!-*FG/+K	2
EOF		ABC+*AD!!-*FG/+K+	1

4. zadatak

Postavka

Neka se dvostrani red u pseudojeziku opisuje sledećim zapisom:

deque = RECORD
    array, front, rear, size
END

gde array predstavlja niz ograničenog kapaciteta size, a front i rear pokazivače početka i kraja reda. Indeksi u nizu počinju od 0.

1. Objasniti kako se dvostrani red može implementirati korišćenjem tehnike kružnog bafera. Navesti uslove punog i praznog reda.
2. Napisati u pseudokodu implementaciju funkcija za umetanje na početak i na kraj dvostranog reda definisanog na prethodni način.

Rešenje

Uslov punog reda: (rear + 1) % size = front

Uslov praznog reda: front = rear

INSERT FRONT(deque, x)
if deque = NIL or (rear(deque) + 1) % size(deque) = front(deque) then
    return
front(deque) = (front(deque) - 1) % size(deque)
array(deque)[front(deque)] = x
INSERT REAR(deque, x)
if deque = NIL or (rear(deque) + 1) % size(deque) = front(deque) then
    return
rear(deque) = (rear(deque) + 1) % size(deque)
array(deque)[rear(deque)] = x

Drugi kolokvijum

1. zadatak

Postavka

Povezana binarna stabla

1. Precizno definisati šta je povezano stablo i dati strukturu čvora takvog stabla, sa preciznim opisima svakog polja.
2. Napisati u pseudokodu funkciju za uklanjanje čvora x iz povezanog binarnog stabla po inorder načinu obilaska, ako je poznato da čvor x nema levog sina.

Rešenje

Povezano binarno stablo je stablo u kojem su neiskorišćeni pokazivači na levu i desnu decu iskorišćeni u svrhu lakšeg obilaska stabla nekim načinom obilaska. Struktura čvora takvog stabla ima sledeća polja:

• value — vrednost u čvoru stabla
• left — pokazivač na levo dete ili prethodnika po redosledu obilaska
• right — pokazivač na desno dete ili sledbenika po redosledu obilaska
• lf — bit postavljen na 1 ukoliko left pokazuje na levo dete i 0 ukoliko pokazuje na prethodnika po redosledu obilaska
• rf — bit postavljen na 1 ukoliko right pokazuje na desno dete i 0 ukoliko pokazuje na sledbenika po redosledu obilaska

U pseudokodu za tačku pod b, kako bi povezano stablo ostalo povezano, potrebno je da pronađemo prethodnika čvora x po inorder-u i prvog sledbenika čvora x po inorder-u koji se ne nalazi u njegovom podstablu, povežemo ih a sve ostale čvorove između oslobodimo.

DELETE-T(x)
prethodnik = left(x)
sledbenik = right(x)
next_sledbenik = nil
while sledbenik ≠ nil do
    if lf(sledbenik) = 1 then
        if left(sledbenik) = x then
            break
        else
            next_sledbenik = left(sledbenik)
            while (next_sledbenik ≠ nil) and ((lf(next_sledbenik) = 1) or (left(next_sledbenik) = nil)) do
                 if left(next_sledbenik) = x then
                     break
                 end_if
                 next_sledbenik = left(next_sledbenik)
            end_while
            if (next_sledbenik ≠ nil) and (left(next_sledbenik) = x) then
                FREENODE(sledbenik)
                sledbenik = next_sledbenik
                break
            end_if
        end_if
    else
        next_sledbenik = right(sledbenik)
    end_if
    FREENODE(sledbenik)
    sledbenik = next_sledbenik
end_while
if (prethodnik ≠ nil) and (rf(prethodnik) = 0) then
    right(prethodnik) = sledbenik
end_if
if sledbenik ≠ nil then
    left(sledbenik) = prethodnik
    lf(sledbenik) = 0
end_if

2. zadatak

Postavka

Neka se posmatra binarno stablo čiji čvorovi sadrže cele brojeve. Napisati u pseudokodu iterativnu implementaciju funkcije CHECK_SUM koja proverava da li sadržaj svakog čvora-oca u stablu na čiji koren ukazuje pokazivač root predstavlja zbir sadržaja svih njegovih potomaka.

Rešenje

CHECK SUM(root)
p = root
STACK_INIT(S)
while p ≠ nil do
    PUSH(S, p)
    p = left(p)
end_while
while not STACK_EMPTY(S) do
    p = POP(S)
    if p > 0 then
        while left(p) ≠ nil do
            PUSH(S, -p)
            p = left(p)
        end_while
        if right(p) ≠ nil then
            PUSH(S, right(p))
        end_if
    else
        sum = 0
        if (left(p) ≠ nil) or (right(p) ≠ nil) then
            if left(p) ≠ nil then
                sum = sum + value(left(p))
            end_if
            if right(p) ≠ nil then
                sum = sum + value(right(p))
            end_if
            if sum * 2 ≠ value(p) then
                return false
            end_if
        end_if
    end_if
end_while
return true

3. zadatak

Postavka

Primenom dinamičkog Huffman algoritma kodirati poruku ABCDBBCAAABC i prikazati postupak kodiranja ukoliko su početni kodovi simbola A, B, C i D 00, 01, 10 i 11 respektivno. Uporediti prosečnu dužinu simbola primenom ovog algoritma sa inicijalno dodeljenim kodovima.

Rešenje

• Krajnje transmitovano: 00 001 0010 10011 11 11 111 111 111 10 10 101
• Krajnje stablo:

   12
 /    \
A      8
4     / \
     4   4
    / \
   1   C
  / \  3
 NYT D
  0  1

NYT
 0

00

  1
 / \
NYT A
 0  1

001

    2
   / \
  1   A
 / \  1
NYT B
 0  1

0010

  3
 / \
A   2
1  / \
  1   B
 / \  1
NYT C
 0  1

10011

       4
     /   \
    2     2
   / \   / \
  1   C A   B
 / \  1 1   1
NYT D
 0  1

11

       5
     /   \
    2     3
   / \   / \
  1   C A   B
 / \  1 1   2
NYT D
 0  1

11

  6
 / \
B   3
3  / \
  A   2
  1  / \
    1   C
   / \  1
  NYT D
   0  1

111

  7
 / \
B   4
3  / \
  C   2
  2  / \
    1   A
   / \  1
  NYT D
   0  1

111

  8
 / \
B   5
3  / \
  C   3
  2  / \
    1   A
   / \  2
  NYT D
   0  1

111

  9
 / \
B   6
3  / \
  A   3
  3  / \
    1   C
   / \  2
  NYT D
   0  1

10

  10
 /  \
A    6
4   / \
   B   3
   3  / \
     1   C
    / \  2
   NYT D
    0  1

10

   11
  /  \
 A    7
 4   / \
    3   B
   / \  4
  1   C
 / \  2
NYT D
 0  1

101

Kraj.

4. zadatak

Postavka

Konverzija m-arnog u binarno stablo

1. Objasniti na koji način se vrši konverzija stabala višeg reda u odgovarajuće binarno stablo iste semantike. Koje dodatne informacije su potrebne?
2. Za stablo reda 4 sa slike, prikazati postupak konverzije u odgovarajuće binarno stablo iste semantike i nacrtati finalno binarno stablo.

        X
     / / \ \
   Y  A   F  C
 / | \   /  / \
B  G  E J  K   M
     /
    D

Rešenje

m-arno stablo se konvertuje u binarno tako što se svaki čvor stabla pretvori tako da njegovo levo dete pokazuje na njegovo prvo dete a desno dete na sledećeg brata. Ovo se može realizovati tako što se postorder obilaskom m-arnog stabla svi čvorovi konvertuju tako da im se kao levo dete nalazi prvo dete, kao desno dete levog deteta drugo dete, kao desno dete desnog deteta levog deteta treće dete itd.

Postorder poredak čvorova: BGDEYAJFKMCX

• B, G, D — Nemaju decu
• E — Već je konvertovan u čvor binarnog stabla
• Y —

       X
    / / \  \
  Y  A   F  C
 /      /  / \
B      J  K   M
 \
  G
   \
    E
   /
  D

• A, J — Nemaju decu
• F — Već je konvertovan u čvor binarnog stabla
• K, M — Nemaju decu
• C —

       X
    / / \  \
  Y  A   F  C
 /      /  /
B      J  K
 \         \
  G         M
   \
    E
   /
  D

• X — Vidi konačno stablo

Konačno stablo:

     X
    /
   Y
 /   \
B     A
 \     \
  G     F
   \   / \
    E J   C
   /     /
  D     K
         \
          M

Treći kolokvijum

1. zadatak

Postavka

Potrebno je implementirati jednostavan algoritam za pomoć pri brisanju nedostižnih objekata u memoriji kao podrška nekom programskom jeziku (garbage collection). Neka se alocirani objekti u memoriji i njihove veze modeluju usmerenim netežinskim grafom matrične reprezentacije G sa n čvorova. Čvorovi grafa predstavljuju objekte, a grane grafa predstavljaju veze između njih, tako da grana (x,y) modelira postojanje reference u okviru objekta x na objekat y.

Neka je dat niz promenljivih vars dužine n_vars koji pokazuju na objekte i počev od kojih je potrebno proveriti da li se do svih alociranih objekata u nekom programu može doći. Implementirati funkciju GC koja treba da vrati skup svih onih objekata koji su nedostižni iz perspektive početnog skupa promenljivih (vars).

Rešenje

Dato je generalno rešenje radi čitljivosti, rešenje u matričnoj reprezentaciji je vežba za čitaoca. Neophodna je implementacija BFS (ili bilo kog algoritma pretrage grafa preko grana) koji vraća skup posećenih čvorova. R (reachable) je skup čvorova koji su dostižni. Vraćaju se oni čvorovi koji nakon ovih pretraga nisu bili dostižni.

GC(G, n, vars, n_vars)
R = ∅
for each v in vars do
    R = R ∪ BFS(G, v)
end_for
return G \ R

2. zadatak

Postavka

Graf iz postavke drugog zadatka.

Jako povezane komponente

1. Definisati jako povezane komponente i objasniti način kako se one mogu pronaći u usmerenom grafu.
2. Za graf sa slike, prikazati po koracima postupak pronalaženja jako povezanih komponenti i nacrtati redukovani graf.

Rešenje

Transponovani graf. Jako povezane komponente su označene različitim bojama

Redukovani graf.

Jako povezanom komponentom nazivamo podgraf u kome je svaki čvor dostižan svim ostalim čvorovima. Algoritam za nalaženje jako povezanih komponenti možemo podeliti na 4 dela:

1. Na datom grafu G radimo DFS i pamtimo završna vremena svakog čvora.
2. Formiramo transponovani graf G^T grafa G. Transponovani graf je graf u kome je smer svih grana obrnut.
3. Na grafu G^T radimo DFS počevši od čvora sa najvećim završnim vremenom. Skup posećenih čvorova koji vraća DFS čini jako povezanu komponentu tojest jedan čvor u redukovanom grafu.
4. Sve čvorove koje smo posetili u 3. koraku uklanjamo iz G^T, te ponavljamo 3. korak dok graf ne postane prazan.

DFS koji kreće od C:

Čvor	Početno vreme	Završno vreme
C	1	20
A	2	19
B	3	12
F	4	11
H	5	10
J	6	9
I	7	8
E	13	18
G	14	17
D	15	16

Jako povezane komponente:

Čvor	Završno vreme
C	20
Čvor	Završno vreme
A	19
Čvor	Završno vreme
E	18
D	16
G	17
Čvor	Završno vreme
B	12
I	8
J	9
H	10
F	11

3. zadatak

Postavka

Graf iz postavke trećeg zadatka.

Na slici je dat težinski neusmeren graf.

1. Naći minimalno obuhvatno stablo primenom Primovog algoritma, ako se za početni čvor uzima čvor S. Prikazati redom koje grane se dodaju u obuhvatno stablo.
2. Naći minimalno obuhvatno stablo primenom Primovog algoritma, ako se za početni čvor uzima čvor B. Prikazati redom koje grane se dodaju u obuhvatno stablo.
3. Ukratko i precizno objasniti da li je prilikom traženja minimalnog obuhvatnog stabla u prethodnim tačkama moglo da se dobije i drugačije minimalno obuhvatno stablo? Ako da, napisati od čega to zavisi i navesti odovarajući korak u kome se to desilo.

Rešenje

Od S	Od B
S-M 3	B-A 3
M-K 2	A-T 2
K-B 4	B-K 4
B-A 3	K-M 2
A-T 2	M-S 3
T-F 6	S-F 5

Moguće je dobiti drugačije stablo ukoliko se desi da imamo dve grane koje su minimalne ali iste težine. Ako ne postoje dodatni kriterijumi gde bi jedna grana bila bolja od druge i pri biranju jedne grane neće doći do toga da i druga bude dodata u krajnje stablo, onda postoje dve opcije. U ovom zadatku to se dešava u 3. koraku kada krećemo od S, gde možemo birati ili K-B 4 ili M-B 4.

4. zadatak

Postavka

Ekscentričnost čvora i središte grafa

1. Formalno definisati i objasniti pojmove ekscentričnosti čvora i središta grafa i na koji način se oni određuju.
2. Napisati u pseudokodu iterativnu implementaciju funkcije koja u grafu sa n čvorova i poznatom matricom najkraćih rastojanja D određuje ekcentričnost svih čvorova grafa. Funkcija vraća vektor koji sadrži izračunate ekscentričnosti čvorova.
3. Napisati u pseudokodu iterativnu implementaciju funkcije koja u grafu sa n čvorova i poznatim ekscentričnostima čvorova u vektoru ecc određuje središte grafa.

Rešenje

Ekscentričnost čvora se definiše kao maksimum od najkraćih rastojanja od svih čvorova grafa do tog čvora tj. $ecc(v) = max \{ d[i,v] : i \in V \}$.

Središte grafa je čvor sa najmanjom ekscentičnošću.

Određivanje ekscentričnosti čvora: G_ECC(D, n) ecc = ALLOC(n) for i = 1 to n do ecc[1] = D[i][1] for j = 2 to n do if D[i][j] > ecc[i] then ecc[i] = D[i][j] end_if end_for end_for return ecc

Određivanje središta grafa: G_CENTER(ecc, n) c = 1 for i = 2 to n do if ecc[c] > ecc[i] then c = i end_if end_for return c