АСП1/К3 2019

Zadaci

1. zadatak

Postavka

Graf iz zadatka 1.

Na slici je prikazan netežinski usmereni graf.

1. Prikazati redosled čvorova nakon obilaska grafa sa slike po širini, ukoliko se kao početni čvor zada čvor A. Čvorovi se ubacuju u strukturu prema leksikografskom poretku ukoliko postoji više mogućnosti.
2. Prikazati redosled čvorova nakon iterativnog obilaska grafa sa slike po dubini, ukoliko se kao početni čvor zada čvor A. Čvorovi se ubacuju u strukturu prema leksikografskom poretku ukoliko postoji više mogućnosti.

Rešenje

1. ABICDMFLK
2. AIBCMLKDF

2. zadatak

Postavka

U nekom malom mestu se renovira mreža ulica. Sve ulice u mestu su dvosmerne. Da bi se renoviralo što više ulica, potrebno je obezbediti da između svaka dva važna objekta u mestu (škola, bolnica, opština, itd.) postoji put i da ukupna dužina svih otvorenih puteva za saobraćaj u mestu bude minimalna. Ukoliko je mreža ulica i važnih objekata predstavljena neusmerenim težinskim grafom sa slike, navesti koji algoritam bi se mogao iskoristiti za rešavanje ovog problema i njegovom primenom odrediti ulice koje treba da ostanu otvorene za saobraćaj tokom renoviranja, prema navedenim uslovima. Prikazati postupak.

Rešenje

Mogao bi se primeniti Primov ili Kruškalov algoritam za dobijanje minimlanog obuhvatnog stabla. U narednom postupku biće korišćen Primov algoritam:

1. A-E
2. E-F
3. E-D
4. D-C
5. C-H
6. H-I
7. C-B
8. H-G
9. G-I

Grafovi se nalaze ispod.

• 

  Pojednostavljen graf iz postavke zadatka.

• 

  Minimalno obuhvatno stablo.

3. zadatak

Postavka

Neka se posmatra sekvencijalni programski kod koji se izvršavana na nekoj 3A mašini. Prvi operand instrukcije je odredišni, a preostala dva su izvorišni operandi. Prilikom prevođenja, prevodilac može da preuredi redosled izvršavanja instrukcija da bi izvršio određene optimizacije. Međutim, preuređivanje redosleda dve instrukcije se može izvršiti samo ukoliko ne postoji zavisnosti po podacima između njih. Zavisnost po podacima između instrukcija postoji ukoliko se odredišni operand (rezultat) ranije operacije koristi kao izvorišni operand kasnije operacije.

1. Opisati model grafa koji se može iskoristiti za modelovanje zavisnosti po podacima između instrukcija.
2. Objasniti koji algoritam bi se mogao iskoristiti za pronalaženje svih mogućih redosleda izvršavanja instrukcija na osnovu zadatog grafa zavisnosti po podacima.
3. Na primeru zadatog programskog koda, nacrtati graf zavisnosti po podacima i odrediti (napisati) još jedan moguć redosled izvršavanja instrukcija koji zadovoljava prisutne zavisnosti po podacima.

ADD A, B, C
MUL C, E, D
SUB B, E, C
ADD A, D, E
SUB E, F, G
DIV D, F, H
ADD G, F, H

Rešenje

1. U pitanju je acikličan netežinski usmeren graf u kom čvorovi predstavljaju instrukcije a grane od jednog ka drugom čvoru predstavljaju zavisnost izvorišnih operanada drugog čvora od odredišnog operanda prvog.
2. Može se iskoristiti modifikacija topološkog sortiranja gde se nakon svakog prikupljanja čvorova sa ulaznim stepenom 0 za svaki od njih pokušavaju naći svi putevi koji na tom mestu sadrže taj čvor. Rekurzivna implementacija ovog algoritma je data ispod (gde su putevi predstavljeni ulančanim listama).
3. Graf se sastoji od svih čvorova odvojenih i jedne grane između čvorova MUL C, E, D i SUB B, E, C.
   • ADD A, B, C
   • ADD A, D, E
   • MUL C, E, D
   • SUB B, E, C
   • SUB E, F, G
   • DIV D, F, H
   • ADD G, F, H

TOP SORT ALL PATHS R(G)
if V = {} then
    return nil
end_if
return_paths = {}
for {n : (n ∈ V) and ((u, n) ∉ E)} do
    MARK_REMOVED(G, n)
    paths = TOP_SORT_ALL_PATHS_R(G)
    for path ∈ paths do
        new_path = GETNODE
        value(new_path) = n
        next(new_path) = path
        path = new_path
    end_for
    UNMARK_REMOVED(G, n)
    return_paths = return_paths + paths
end_for
return return_paths

4. zadatak

Postavka

Posmatra se usmeren netežinski graf. Napisati iterativnu funkciju u pseudokodu koja za prosleđeni graf sa datim brojem čvorova n pronalazi sve čvorove koji su putevima dužine tačno k udaljeni od zadatog početnog čvora id.

Rešenje

Implementacija ispod čvorove vraća u ulančanoj listi.

K-DISTANCE(G, n, k, id)
dist[n]
for i = 1 to n do
    dist[i] = ∞
end_for
dist[id] = 0
curr_dist = 0
tail = head = GETNODE(id)
next(head) = GETNODE(0)
head = next(head)
curr = 0
temp = nil
while (tail ≠ nil) and (curr_dist ≠ k) do
    curr = value(tail)
    if curr = 0 then
        curr_dist = curr_dist + 1
        if head ≠ tail then
            next(head) = GETNODE(0)
            head = next(head)
        end_if
    else
        for node ∈ {v : (curr, v) ∈ E} do
            if dist[node] ≠ curr_dist + 1 then
                dist[node] = curr_dist + 1
                next(head) = GETNODE(node)
                head = next(head)
            end_if
        end_for
    end_if
    temp = tail
    tail = next(tail)
    FREENODE(temp)
end_while

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

5. zadatak

Postavka

Floyd algoritam

1. Na slici je dat izgled matrica D i T dobijenih kao izlaz Floyd algoritma. Nacrtati mogući izgled ulaznog grafa i obrazložiti odgovor.
2. Napisati u pseudokodu funkciju koja na osnovu matrice T dobijene kao izlaz Floyd-ovog algoritma rekonstruiše najkraći put od čvora A do čvora C takav da se na njemu nalazi čvor B.

Matrica D

0	2	7
∞	0	5
∞	∞	0

Matrica T

0	1	2
0	0	2
0	0	0

Rešenje

Graf iz zadatka 5.

1. Pretpostavljajući da nema grana negativne težine vidimo da je najkraći put dužine 2 i zato sigurno mora biti direktna grana između A i B. Pošto vidimo da matrica D nije simetrična pretpostavljamo da se radi o usmerenom težinskom grafu. Na osnovu trenutnog grafa i D matrice vidimo da je grana B-C težine 5, i sve ostalo se slaže.
2. U pseudokodu ispod podrazumeva se da je put predstavljen ulančanom listom. Ukoliko je vraćeno nil to znači da nema puta.

PATH(T, A, B, C)
curr = GETNODE(C)
next = nil
while value(curr) ≠ B do
    if T[B][value(curr)] = 0 then
        return nil
    end_if
    next = GETNODE(T[B][value(curr)])
    next(next) = curr
    curr = next
end_while
while value(curr) ≠ A do
    if T[A][value(curr)] = 0 then
        return nil
    end_if
    next = GETNODE(T[A][value(curr)])
    next(next) = curr
    curr = next
end_while

return curr

6. zadatak

Postavka

Graf iz zadatka 6.

Za graf sa slike odrediti topološki poredak, a zatim naći kritični put i dozvoljena kašnjenja za pojedinačne čvorove.

Rešenje

• Topološki poredak: ABDCFEHGIJK
• Kritični put: ABCEHGJK (ili ABCEHGIJK)
• Tabela:

Čvor	EST	LST	L
A	0	0	0
B	1	1	0
C	3 10	10	0
D	3	6	3
E	15	15	0
F	6 11	13	2
G	19	19	0
H	16	16	0
I	21	21	0
J	22	22	0
K	24	24	0

7. zadatak

Postavka

Koja su dva karakteristična načina za izbor puta povećanog protoka u protočnom grafu? Na primeru protočnog grafa sa slike u okviru koga postoji već uspostavljen protok po pojedinim granama, nacrtati rezidualni graf i navesti dva karakteristična puta koji ilustruju navedene situacije.

Rešenje

Dva karakteristična načina za izbor puta povećanog protoka su:

1. običan BFS koji će naći najkraći put od S do T, na primer SBT, i
2. biranje puta koji najviše povećava protok, na primer SBAT.

Grafovi su dati ispod.

• 

  Graf iz postavke zadatka.

• 

  Rezidualni graf.

8. zadatak

Postavka

Dijkstra-in algoritam

1. Kolika je složenost Dijkstra-inog algoritma i od kojih operacija u okviru algoritma to zavisi? Objasniti.
2. Napisati pseudokod Dijkstra-inog algoritma koji pronalazi najkraće rastojanje između para čvorova x i y pod pretpostavkom da se graf G predstavlja listama susednosti. Specijalizovati apstraktne operacije gde je to moguće.

Rešenje

Složenost Dajkstrinog algoritma zavisi od operacija pronalaženja sledećeg čvora do kojeg je put najkraći i ažuriranja matrice D sa dodavanjem novog čvora u skup S. Može biti $\mathcal{O(n^2)}$ u slučaju da se pronalaženje sledećeg čvora do kojeg je put najkraći izvršava u $\mathcal{O(n)}$ i da je graf predstavljen matricom susednosti. Bolja složenost dostiže se onda kada je graf predstavljen listom susednosti i operacija pronalaženja sledećeg čvora sa najkraćim putem ima složenost od $\mathcal{O(\log{n})}$, kada je složenost $\mathcal{O(e + n\log{n})}$.

DIJKSTRA ADJ LIST(G, x, y)
S = {x}
for i = 1 to n do
    d[i] = w[x, i]
    if d[i] = ∞ then
        t[i] = 0
    else
        t[i] = x
    end_if
end_for
for k = 1 to n-1 do
    start_node = -1
    for i ∈ (V - S) do
        if (start_node = -1) or (d[i] < d[start_node]) then
            start_node = i
        end_if
    end_for
    S = S + {start_node}
    adj_node = AL[start_node]
    while adj_node ≠ nil do
        if w[start_node, value(adj_node)] + d[start_node] < d[value(adj_node)] then
            d[value(adj_node)] = w[start_node, value(adj_node)] + d[start_node]
            t[value(adj_node)] = start_node
        end_if
        adj_node = next(adj_node)
    end_while
end_for

return d[y]