АСП1/Јул 2018

Задаци

1. задатак

Поставка

Одредити бинарно стабло чијим екстерним чворовима су придружене тежине: 3, 6, 3, 1, за које је тежинска екстерна дужина пута најмања и израчунати ту дужину.

Решење

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

Екстерна дужина пута: $1 \cdot 6 + 2 \cdot 3 + 3 \cdot 1 + 3 \cdot 3 = 6 + 6 + 3 + 9 = 24$

2. задатак

Поставка

Дат је аритметички израз у инфиксној нотацији: 3+7+4*(2+1). Претворити дати израз у постфиксни израз, а затим приказати стање стека по корацима током израчунавања вредности добијеног постфиксног израза. Сматрати да показивач врха стека показује на последњу заузету локацију и обележити га на слици.

Решење

Постфиксни израз: 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. задатак

Поставка

Посматра се векторска имплементација комплетног или скоро комплетног стабла реда 3 у виду вектора V[1:н].

1. Приказати стабло чија је векторска репрезентација дата на слици.
2. Написати у псеудокоду функцију која налази пут од чвора са индексом к ка корену и функцију која налази све синове чвора са индексом к.

Слика уз део под а.

1

2

3

4

5

6

7

8

9

10

11

12

13

Решење

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

У псеудокоду испод претпоставља се да нам пут од чвора ка корену као и деца тренутног чвора требају враћени као уланчане листе.

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. задатак

Поставка

Нека је дата општа квадратна матрица А[л:у, л:у] која садржи елементе само испод главне дијагонале, укључујући и ту дијагоналу. Формално дефинисати и кратко објаснити адресну функцију за приступ произвољном елементу А[и, ј], уколико се матрица линеаризује по врстама.

Решење

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

• $A_{ll}$ је адреса почетног елемента матрице.
• $\frac{(i-l)(i-l+1)}{2}$ је број елемената у редовима изнад елемента којег тражимо. $i-l$ је број редова изнад тренутног реда и стога број елемената у реду изнад нашег, а пошто број елемената опада са бројем реда овај збир добијамо као Гаусов збир.
• $j-l$ је број елемената лево од нашег тренутног елемента.

5. задатак

Поставка

Нека се посматра један скуп веб страница у оквиру локалног интранета једне компаније. Свака страница садржи одређени број хиперлинкова који воде ка другим страницама у оквиру интранета.

1. Описати на који начин се овај скуп страница може моделовати графом. Коментарисати тип и усмереност графа.
2. Написати у псеудокоду итеративну функцију која одређује просечан број кликова потребан да се са неке веб странице стигне до неке друге веб странице у оквиру компанијског интранета. Просек рачунати на нивоу свих могућих парова страница.

Решење

Овај скуп страница се може моделовати нетежинским усмереним графом где чворови представљају странице а грана од стране А до стране Б значи да постоји веза на страни А до стране Б.

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. задатак

Поставка

Граф из поставке задатка.

Применом алгоритма за одређивање критичних путева у графу одредити критичне путеве у графу са слике као и дозвољена кашњења свих активности у графу.

Решење

Критични путеви: АЕДЦМ и АЕДВМ.

Чвор	ЕСТ
А	0
Б	6
C	10
D	5
Е	2
К	6
M	13
V	11

Активност	I
А-Б	3
А-Е	0
Е-D	0
D-Б	1
D-Ц	0
Б-C	1
C-М	0
D-В	0
V-М	0
Е-V	2
Е-К	2
К-V	2

7. задатак

Поставка

Дата је двоструко уланчана листа. Имплементирати функцију РЕАРРАНГЕ_ЛИСТ која прослеђену листу преуређује тако да се сви елементи са непарних позиција у оригиналном поретку нађу пре свих елемената са парних позиција у оригиналном поретку.

Решење

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. задатак

Поставка

Приказати поступак кодирања поруке АДБЕЦДААДБЕ применом динамичког Хуффман алгоритма.

Решење

Крајње Хуффман-ово стабло:

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

Крајња порука: А 0Д 00Б 100Е 000Ц 00 00 01 10 00 011

9. задатак

Поставка

Посматра се неусмерен тежински граф представљен матрицом суседности, чији чворови представљају градове у којима се налазе бензинске пумпе на којима се може допунити резервоар, а тежине грана представљају колико литара горива се потроши у путу између повезаних градова. Перица креће из града срц и жели да стигне у град дст. На ефикасан начин одредити минимални капацитет резервоара Перичиног аутомобила да би он могао да успешно да заврши свој пут.

Решење

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. задатак

Поставка

Приликом обиласка неког графа може се добити стабло обиласка.

1. Дефинисати ово стабло.
2. Приликом обиласка усмереног графа по дубини добијена су почетна (т1) и завршна времена (т2) чворова као у приложеној табели. Реконструисати стабло обиласка и прецизно објаснити поступак реконструкције.

	т1	т2
А	3	4
Б	5	10
C	11	12
D	14	15
Е	8	9
Ф	2	13
Г	1	16
Х	6	7

Решење

1. Стабло обиласка је ациклични неусмерени нетежински граф чије гране означавају из ког је чвора посећен који чвор приликом обиласка графа, а чворови су исти као у графу који се обилази.
2. Поступак иде тако што удемо предом кроз бројеве $t = 1 ... 2n$ и чувамо један имагинарни показивач који је у $t = 1$ постављам на корен. Ако $t$ означава почетно време неког чвора, на тренутни показивач додајемо дете са вредношћу тог чвора и пребацујемо показивач на то дете. Ако $t$ означава крајње време неког чвора, пребацујемо показивач на његовог родитеља (ако је показивач на корену, завршавамо).

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