АСП1/Јул 2020

Prvi kolokvijum

1. zadatak

Postavka

Data je retka kvadratna matrica dimenzije 5. Navesti dva načina da se prikaže pomoću ulančanih lista.

2. zadatak

Postavka

Napisati pseudokod za osnovne operacije sa stekom implementiranog pomoću ulančanih lista sa zaglavljem, tako da se u konstantnoj složenosti može dobiti maksimalni element. Dozvoljeno je koristiti još jednu listu.

3. zadatak

Postavka

Prebaciti infiksni izraz A*(B-C)*(A-D!!)+F/G+K u postfiksni i popuniti tabelu ispod.

Operator	Ulazni prioritet	Stek prioritet	Rang
+, -	?	?	?
*, /	?	?	?
!	?	?	?
(	?	?	?
)	?	?	?

4. zadatak

Postavka

Implementirati operacije za dodavanje elemenata na početak i kraj reda implementiranog preko kružnog vektora.

Rešenje

INSERT-BEFORE(Q, value)

INSERT-AFTER(Q, value)

Drugi kolokvijum

1. zadatak

Postavka

1. Precizno definisati povezana stabla. Koja nova polja se moraju uvesti u normalno stablo kako bi postalo povezano?
2. Napisati pseudokod funkcije koja prima čvor i izbacuje ga iz stabla povezanog po inorder-u ako je poznato da taj čvor nema levog sina.

2. zadatak

Postavka

Napisati pseudokod funkcije koja za svaki čvor u stablu proverava da li je suma vrednosti svih potomaka tog čvora jednaka vrednosti tog čvora za svaki čvor koji ima potomke.

3. zadatak

Postavka

Dinamički Hafman. (?) Uporediti dužinu karaktera sa dinamičkim Hafmanom i bez njega. (??)

4. zadatak

Postavka

1. Objasniti postupak konverzije m-arnog stabla u binarno stablo.
2. Na sledećem primeru m-arnog stabla prikazati postupak konverzije po koracima. (?)

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, 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.

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

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, onda postoje sve 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

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