АСП1/Јул 2020

Zadaci

Prvi kolokvijum

1. zadatak

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
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
+, -
*, /
!
(
)

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

INSERT FRONT(deque, x)

INSERT 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

DELETE-T(x)

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)

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.

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

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

Датотека:ASP1 jul 2020 zadatak 3.2 graf.png

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

Датотека:ASP1 jul 2020 zadatak 3.3 graf.png

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