ASP1/Jul 2018

Zadaci

1. zadatak

Postavka

Odrediti binarno stablo čijim eksternim čvorovima su pridružene težine: 3, 6, 3, 1, za koje je težinska eksterna dužina puta najmanja i izračunati tu dužinu.

Rešenje

  13
 /  \
6    7
    / \
   3   4
      / \
     3   1

Eksterna dužina puta: $1 \cdot 6 + 2 \cdot 3 + 3 \cdot 1 + 3 \cdot 3 = 6 + 6 + 3 + 9 = 24$

2. zadatak

Postavka

Dat je aritmetički izraz u infiksnoj notaciji: 3+7+4*(2+1). Pretvoriti dati izraz u postfiksni izraz, a zatim prikazati stanje steka po koracima tokom izračunavanja vrednosti dobijenog postfiksnog izraza. Smatrati da pokazivač vrha steka pokazuje na poslednju zauzetu lokaciju i obeležiti ga na slici.

Rešenje

Postfiksni izraz: 3 7 + 4 2 1 + * +

3		7		+		4		2		1		+		*		+
	--		--		--		--		--		--		--		--		--
	--		--		--		--		--		--		--		--		--
	--		--		--		--		--		--		--		--		--
	--		--		--		--		--	→	1		--		--		--
	--		--		--		--	→	2		2	→	3		--		--
	--	→	7		--	→	4		4		4		4	→	12		--
→	3		3	→	10		10		10		10		10		10	→	22

3. zadatak

Postavka

Posmatra se vektorska implementacija kompletnog ili skoro kompletnog stabla reda 3 u vidu vektora V[1:n].

1. Prikazati stablo čija je vektorska reprezentacija data na slici.
2. Napisati u pseudokodu funkciju koja nalazi put od čvora sa indeksom k ka korenu i funkciju koja nalazi sve sinove čvora sa indeksom k.

Slika uz deo pod a.

1

2

3

4

5

6

7

8

9

10

11

12

13

Rešenje

            1
       /    |    \
   2        3         4
 / | \    / | \    /  |  \
5  6  7  8  9 10  11  12  13

U pseudokodu ispod pretpostavlja se da nam put od čvora ka korenu kao i deca trenutnog čvora trebaju vraćeni kao ulančane liste.

NODE TO ROOT(V, n, k)
t = 0
path = nil
p = k
while p ≠ 0 do
    LIST_INSERT(path, v[p])
    t = p mod 3
    if t = 0 then
        p = p / 3
    else if t = 1 then
        p = (p - 1) / 3
    else
        p = (p + 1) / 3
    end_if
end_while
return path

CHILD NODES(V, n, k)
children = nil
if 3 * k - 1 ≤ n then
    LIST_INSERT(children, v[3 * k - 1])
end_if
if 3 * k ≤ n then
    LIST_INSERT(children, v[3 * k])
end_if
if 3 * k + 1 ≤ n then
    LIST_INSERT(children, v[3 * k + 1])
end_if
return children

4. zadatak

Postavka

Neka je data opšta kvadratna matrica A[l:u, l:u] koja sadrži elemente samo ispod glavne dijagonale, uključujući i tu dijagonalu. Formalno definisati i kratko objasniti adresnu funkciju za pristup proizvoljnom elementu A[i, j], ukoliko se matrica linearizuje po vrstama.

Rešenje

$A_{ij} = A_{ll} + \left(\frac{(i-l)(i-l+1)}{2} + j - l\right) \cdot S$

• $A_{ll}$ je adresa početnog elementa matrice.
• $\frac{(i-l)(i-l+1)}{2}$ je broj elemenata u redovima iznad elementa kojeg tražimo. $i-l$ je broj redova iznad trenutnog reda i stoga broj elemenata u redu iznad našeg, a pošto broj elemenata opada sa brojem reda ovaj zbir dobijamo kao Gausov zbir.
• $j-l$ je broj elemenata levo od našeg trenutnog elementa.

5. zadatak

Postavka

Neka se posmatra jedan skup veb stranica u okviru lokalnog intraneta jedne kompanije. Svaka stranica sadrži određeni broj hiperlinkova koji vode ka drugim stranicama u okviru intraneta.

1. Opisati na koji način se ovaj skup stranica može modelovati grafom. Komentarisati tip i usmerenost grafa.
2. Napisati u pseudokodu iterativnu funkciju koja određuje prosečan broj klikova potreban da se sa neke veb stranice stigne do neke druge veb stranice u okviru kompanijskog intraneta. Prosek računati na nivou svih mogućih parova stranica.

Rešenje

Ovaj skup stranica se može modelovati netežinskim usmerenim grafom gde čvorovi predstavljaju stranice a grana od strane A do strane B znači da postoji veza na strani A do strane B.

AVG CLICKS NUM(G)
for i = 1 to n do
    for i = 1 to n do
        if (i, j) ∈ E then
            d[i, j] = 1
        else
            d[i, j] = ∞
        end_if
    end_for
end_for
for k = 1 to n do
    for i = 1 to n do
        for j = 1 to n do
            if d[i, k] + d[k, j] < d[i, j] then
                d[i, j] = d[i, k] + d[k, j]
            end_if
        end_for
    end_for
end_for
for i = 1 to n do
    for j = 1 to n do
        if i ≠ j then
            sum = sum + d[i, j]
        end_if
    end_for
end_for
return sum / (n * (n - 1))

6. zadatak

Postavka

Graf iz postavke zadatka.

Primenom algoritma za određivanje kritičnih puteva u grafu odrediti kritične puteve u grafu sa slike kao i dozvoljena kašnjenja svih aktivnosti u grafu.

Rešenje

Kritični putevi: AEDCM i AEDVM.

Čvor	EST
A	0
B	6
C	10
D	5
E	2
K	6
M	13
V	11

Aktivnost	I
A-B	3
A-E	0
E-D	0
D-B	1
D-C	0
B-C	1
C-M	0
D-V	0
V-M	0
E-V	2
E-K	2
K-V	2

7. zadatak

Postavka

Data je dvostruko ulančana lista. Implementirati funkciju REARRANGE_LIST koja prosleđenu listu preuređuje tako da se svi elementi sa neparnih pozicija u originalnom poretku nađu pre svih elemenata sa parnih pozicija u originalnom poretku.

Rešenje

LIST REMOVE(node)
next(prev(node)) = next(node)
prev(next(node)) = prev(node)
return node

LIST INSERT(before, node)
t = prev(before)
prev(before) = node
next(t) = node
prev(node) = t
next(node) = before
return node

REARRANGE LIST(head)
if head = nil then
    return
end_if
p = head
n = nil
loop
    for k = 1 to i + 1 do
        p = next(p)
        if p = nil then
            return
        end_if
    end_for
    n = LIST_REMOVE(p)
    for k = 1 to i do
        p = prev(p)
    end_for
    LIST_INSERT(p, n)
    p = n
    i = i + 1
end_loop

8. zadatak

Postavka

Prikazati postupak kodiranja poruke ADBECDAADBE primenom dinamičkog Huffman algoritma.

Rešenje

Krajnje Huffman-ovo stablo:

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

Krajnja poruka: A 0D 00B 100E 000C 00 00 01 10 00 011

9. zadatak

Postavka

Posmatra se neusmeren težinski graf predstavljen matricom susednosti, čiji čvorovi predstavljaju gradove u kojima se nalaze benzinske pumpe na kojima se može dopuniti rezervoar, a težine grana predstavljaju koliko litara goriva se potroši u putu između povezanih gradova. Perica kreće iz grada src i želi da stigne u grad dst. Na efikasan način odrediti minimalni kapacitet rezervoara Peričinog automobila da bi on mogao da uspešno da završi svoj put.

Rešenje

GETNODE(i, j)
ALLOCATE(node)
from(node) = i
to(node) = j
next(node) = nil
return node

GASOLINE TRAVEL(G, src, dst)
branches = nil
t = nil
for i = 1 to n do
    for j = 1 to n do
        if e[i, j] = 1 then
            if branches = nil then
                branches = GETNODE(i, j)
            else
                t = next(branches)
                next(branches) = GETNODE(i, j)
                next(next(branches)) = t
            end_if
        end_if
    end_for
end_for
S = {src}
loop
    t = branches
    min_branch = nil
    while t ≠ nil do
        if (from(t) ∈ S) and (to(t) ∈ (V - S) then
            if (min_branch = nil) or (w(from(t), to(t)) < w(from(min_branch), to(min_branch))) then
                min_branch = t
            end_if
        end_if
        t = next(t)
    end_while
    if to(min_branch) = dst then
        return last_min
    end_if
    S = S + {to(min_branch)}
end_loop

10. zadatak

Postavka

Prilikom obilaska nekog grafa može se dobiti stablo obilaska.

1. Definisati ovo stablo.
2. Prilikom obilaska usmerenog grafa po dubini dobijena su početna (t1) i završna vremena (t2) čvorova kao u priloženoj tabeli. Rekonstruisati stablo obilaska i precizno objasniti postupak rekonstrukcije.

	t1	t2
A	3	4
B	5	10
C	11	12
D	14	15
E	8	9
F	2	13
G	1	16
H	6	7

Rešenje

1. Stablo obilaska je aciklični neusmereni netežinski graf čije grane označavaju iz kog je čvora posećen koji čvor prilikom obilaska grafa, a čvorovi su isti kao u grafu koji se obilazi.
2. Postupak ide tako što udemo predom kroz brojeve $t = 1 ... 2n$ i čuvamo jedan imaginarni pokazivač koji je u $t = 1$ postavljam na koren. Ako $t$ označava početno vreme nekog čvora, na trenutni pokazivač dodajemo dete sa vrednošću tog čvora i prebacujemo pokazivač na to dete. Ako $t$ označava krajnje vreme nekog čvora, prebacujemo pokazivač na njegovog roditelja (ako je pokazivač na korenu, završavamo).

     G
    / \
   F   D
 / | \
A  B  C
  / \
 H   E