Изворни код странице АСП1/Јул 2020

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S111ASP1_jul_2020.pdf Zadaci]

== Prvi kolokvijum ==
=== 1. zadatak ===
{{delimično rešeno}}
==== 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.
{| class="wikitable"
|+ 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
|}

==== Rešenje ====

=== 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)'').
<div class="abc-list">
# 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.
# Koristeći ideju opisanu pod a), napisati tražene operacije.
</div>

==== 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''.
{{Милокод|<nowiki>
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
</nowiki>}}
{{Милокод|<nowiki>
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
</nowiki>}}
{{Милокод|<nowiki>
MAX(header)
return info(max(header))
</nowiki>}}

=== 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 ====
{| class="wikitable"
! Operator
! Ulazni prioritet
! Stek prioritet
! Rang
|-
| +, - || 2 || 2 || -1
|-
| *, / || 3 || 3 || -1
|-
| !    || 5 || 4 || 0
|-
| (    || 6 || 1 || 0
|-
| )    || 0 || - || 0
|}
{| class="wikitable"
! 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.
<div class="abc-list">
# Objasniti kako se dvostrani red može implementirati korišćenjem tehnike kružnog bafera. Navesti uslove punog i praznog reda.
# Napisati u pseudokodu implementaciju funkcija za umetanje na početak i na kraj dvostranog reda definisanog na prethodni način.
</div>

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

Uslov praznog reda: front = rear
{{Милокод|<nowiki>
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
</nowiki>}}
{{Милокод|<nowiki>
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
</nowiki>}}

== Drugi kolokvijum ==
=== 1. zadatak ===
==== Postavka ====
Povezana binarna stabla
<div class="abc-list">
# Precizno definisati šta je povezano stablo i dati strukturu čvora takvog stabla, sa preciznim opisima svakog polja.
# 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.
</div>

==== 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:
* <code>value</code> — vrednost u čvoru stabla
* <code>left</code> — pokazivač na levo dete ili prethodnika po redosledu obilaska
* <code>right</code> — pokazivač na desno dete ili sledbenika po redosledu obilaska
* <code>lf</code> — bit postavljen na 1 ukoliko <code>left</code> pokazuje na levo dete i 0 ukoliko pokazuje na prethodnika po redosledu obilaska
* <code>rf</code> — bit postavljen na 1 ukoliko <code>right</code> 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.
{{Милокод|<nowiki>
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
</nowiki>}}

=== 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 ====
{{Милокод|<nowiki>
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
</nowiki>}}

=== 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
<div class="mw-collapsible mw-collapsed" data-expandtext="Prikaži postupak">
 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.
</div>

=== 4. zadatak ===
==== Postavka ====
Konverzija ''m''-arnog u binarno stablo
<div class="abc-list">
# 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?
# Za stablo reda 4 sa slike, prikazati postupak konverzije u odgovarajuće binarno stablo iste semantike i nacrtati finalno binarno stablo.
</div>
         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.

<div class="mw-collapsible mw-collapsed" data-expandtext="Prikaži postupak">
''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
</div>

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.
{{Милокод|<nowiki>
GC(G, n, vars, n_vars)
R = ∅
for each v in vars do
    R = R ∪ BFS(G, v)
end_for
return G \ R
</nowiki>}}

=== 2. zadatak ===
==== Postavka ====
[[{{ns:6}}:ASP1 jul 2020 zadatak 3.2 graf.svg|thumb|Graf iz postavke drugog zadatka.]]
Jako povezane komponente
<div class="abc-list">
# Definisati jako povezane komponente i objasniti način kako se one mogu pronaći u usmerenom grafu.
# Za graf sa slike, prikazati po koracima postupak pronalaženja jako povezanih komponenti i nacrtati redukovani graf.
</div>

==== Rešenje ====
[[{{ns:6}}:ASP1 jul 2020 zadatak 3.2 rešenje.png|thumb|Transponovani graf. Jako povezane komponente su označene različitim bojama]]
[[{{ns:6}}:ASP1 jul 2020 zadatak 3.2 redukovani.png|thumb|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:
# Na datom grafu G radimo DFS i pamtimo završna vremena svakog čvora.
# Formiramo transponovani graf G<sup>T</sup> grafa G. Transponovani graf je graf u kome je smer svih grana obrnut.
# Na grafu G<sup>T</sup> 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.
# Sve čvorove koje smo posetili u 3. koraku uklanjamo iz G<sup>T</sup>, te ponavljamo 3. korak dok graf ne postane prazan.
DFS koji kreće od C:
{| class="wikitable"
|-
! Č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:
{| class="wikitable"
|-
! Č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 ====
[[{{ns:6}}:ASP1 jul 2020 zadatak 3.3 graf.svg|thumb|Graf iz postavke trećeg zadatka.]]
Na slici je dat težinski neusmeren graf.
<div class="abc-list">
# 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.
# 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.
# 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.
</div>

==== Rešenje ====
{| class="wikitable"
|-
! 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
<div class="abc-list">
# Formalno definisati i objasniti pojmove ekscentričnosti čvora i središta grafa i na koji način se oni određuju.
# 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.
# 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.
</div>

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

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

{| class="wikitable"
|-
| Određivanje ekscentričnosti čvora:
{{Милокод|<nowiki>
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
</nowiki>}}
|| Određivanje središta grafa:
{{Милокод|<nowiki>
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
</nowiki>}}
|}

[[Категорија:Рокови]]
[[Категорија:АСП1]]