АСП1/Јун 2020

Први колоквијум

1. задатак

Поставка

Дата је уланчана листа код које сваки елемент има одређени информациони садржај, показивач на следећи елемент у листи, као и показивач на неки произвољан елемент листе. Написати у псеудокоду функцију ДЕЕП_ЦОПY која прихвата показивач на први елемент листе и прави копију листе са истим начином и поретком повезивања као у полазној листи (дубока копија).

Решење

DEEP COPY(head)
p = head
q = r = new_node = nil
new_head = new_tail = nil
while p ≠ nil do
    new_node = GETNODE
    value(new_node) = value(p)
    other_p(new_node) = other_p(p)
    if new_head = nil then
        new_head = new_node
    else
        next(new_tail) = new_node
    end_if
    new_tail = new_node
    p = next(p)
end_while
p = head
q = new_head
while p ≠ nil do
    r = new_head
    while r ≠ nil do
        if other_p(r) = p then
            other_p(r) = q
        end_if
        r = next(r)
    end_while
    p = next(p)
    q = next(q)
end_while
return new_head

2. задатак

Поставка

Нека је датој функцији ПОСТ_ТО_ИНФ прослеђен неки аритметички израз у постфиксном облику (еxпрессион). Операнди су велика слова енглеског алфабета. Написати итеративну имплементацију ове функције која као резултат враћа дати аритметички израз трансформисан у инфиксну форму. Резултујући израз формирати коришћењем потпуних заграда.

Решење

POST TO INF(expression)
stack = nil
expr1 = expr2 = nil
for c in expression do
    if IS_BINARY_OPERATOR(c) then
        expr1 = POP(stack)
        expr2 = POP(stack)
        PUSH(stack, "(" + expr1 + c + expr2 + ")")
    else if IS_UNARY_OPERATOR(c) then
        expr1 = POP(stack)
        PUSH(stack, "(" + c + expr1 + ")")
    else
        PUSH(stack, c)
    end_if
end_for
return POP(stack)
PUSH(stack, value)
node = GETNODE
value(node) = value
next(node) = stack
stack = node
POP(stack, value)
if stack = nil then
    ERROR(Underflow)
else
    node = stack
    value = value(node)
    stack = next(stack)
    FREENODE(node)
    return value
end_if

3. задатак

Поставка

Векторска имплементација приоритетног реда

У приоритетни ред се прво редом убацују следећи елементи 2, 18, 19, 1, 9, 6. Након тога се из реда уклањају два елемента и потом додају елементи 15, 17 и 11, редом. Капацитет вектора у који се смештају елементи је 7. Мањи број означава већи приоритет. За сваки од датих начина имплементације приказати изглед реда након иницијалног уметања, након сваког брисања и сваког уметања последња три елемента (15, 17 и 11). Уколико имплементација користи неке додатне показиваче, назначити их испод одговарајућег индекса у вектору.

Имплементација одржавањем уређености реда
Имплементација маркирањем елемената, без уметања преко маркираног елемента
Имплементација маркирањем елемената, са уметањем преко маркираног елемента

Решење

Имплементација одржавањем уређености реда
1	2	6	9	18	19

2	6	9	18	19

6	9	18	19

6	9	15	18	19

6	9	15	17	18	19

6	9	11	15	17	18	19

Имплементација маркирањем елемената, без уметања преко маркираног елемента
2	18	19	1	9	6

2	18	19	X	9	6

X	18	19	X	9	6

X	18	19	X	9	6	15

18	19	9	6	15	17

18	19	9	6	15	17	11

Имплементација маркирањем елемената, са уметањем преко маркираног елемента
2	18	19	1	9	6

2	18	19	X	9	6

X	18	19	X	9	6

15	18	19	X	9	6

15	18	19	17	9	6

15	18	19	17	9	6	11

4. задатак

Поставка

Нека се блок-дијагонална матрица дефинише као квадратна матрица А димензија н x н чији су ненулти елементи смештени само у оквиру блокова димензије к x к који се налазе на главној дијагонали матрице, као на слици и важи услов н мод к = 0. Укратко објаснити поступак смештања и извести адресну функцију при приступу произвољном елементу матрице А[1:н, 1:н] смештене по врстама. Сматрати да се један елемент матрице смешта у тачно једну меморијску реч.

Пример матрице за $n = 6, k = 2$
-	1	2	3	4	5	6
1	X	X
2	X	X
3			X	X
4			X	X
5					X	X
6					X	X

Решење

Прво гледамо у којем се "блоку" на дијагонали налази елемент који бирамо. Тај блок можемо наћи као $i_b = \left\lfloor\frac{j-1}{k}\right\rfloor$ .
Након тога, можемо на основу индекса блока (који креће од 0) можемо наћи $i$ и $j$ индексе за горњи леви ћошак тог блока као $i_{blok} = j_{blok} = i_b \cdot k + 1$ .
Сада рачунамо индекс тренутног елемента на основу три податка: колико се елемената налази у претходним блоковима, колико се елемената налази изнад тренутног елемента у тренутном блоку и колико се елемената налази лево од тренутног елемента у тренутном блоку.
1. Претходни блокови: $A_{pret} = i_b \cdot k^2$ (у сваком блоку се налази по $k^2$ елемената)
2. Изнад: $A_{izn} = (i - i_{blok}) k$ (у сваком реду налази се $k$ елемената)
3. Лево: $A_{lev} = j - j_{blok}$
Коначна адресна функција: $A = A_{11} + (A_{pret} + A_{izn} + A_{lev}) S = A_{11} + (i_b \cdot k^2 + (i - i_{blok}) k + j - j_{blok}) S =$
$= A_{11} + \left(\left\lfloor\frac{j-1}{k}\right\rfloor \cdot k^2 + \left(i - \left\lfloor\frac{j-1}{k}\right\rfloor \cdot k - 1\right) k + j - \left\lfloor\frac{j-1}{k}\right\rfloor \cdot k - 1\right) S$
Услов: $|i - j| < k$

Други колоквијум

1. задатак

Поставка

Постордер и преордер обилазак

Да ли је, помоћу датог преордер и постордер обиласка бинарног стабла могуће реконструисати јединствено бинарно стабло? Детаљно образложити одговор.
Уколико је преордер обилазак стабла ВАЛДЕЊОМ, а постордер обилазак стабла ДЛЕАОМЈНВ, реконструисати стабло. Уколико постоји више могућих стабала, дати изглед сваког од њих.

Решење

Не може, јер ако неки чвор има само једно дете не може се одредити да ли је то лево или десно дете само из преордер и постордер обиласка тог стабла.
Могуће су четири реконструкције, јер се не зна да ли је чвор D лево или десно дете чвора L и такође да ли је чвор Ј лево или десно дете чвора Н.

        V             V              V                V
     /     \       /     \        /     \          /     \
    A       N     A       N      A       N        A       N
   / \     /     / \     /      / \       \      / \       \
  L   E   J     L   E   J      L   E       J    L   E       J
 /       / \     \     / \    /           / \    \         / \
D       O   M     D   O   M  D           O   M    D       O   M

2. задатак

Поставка

Слова Морзеове азбуке кодирају се као комбинација цртица (-) и тачака (.) (А = .- , Б= -… , итд.). Нека је познат начин кодирања свих слова азбуке и познато је да су кодови префиксни, односно да краћи код може бити префикс дужег кода.

Предложити и описати структуру стабла погодну за операцију декодовања појединачних симбола поруке.
Имплементирати функцију ДЕЦОДЕ_МОРСЕ која на основу структуре предложене под а) декодира неку задату поруку. Порука је прослеђена као аргумент функције (мсг) и представља ниску цртица и тацака. Сматрати да су кодирана слова одвојена бланко знаковима.

Решење

Структура погодна за декодирање Морзеових кодова јесте бинарно стабло где гране улево означавају да код на том месту садржи тачку а гране удесно да код на том месту садржи црту и у сваком чвору се чува у које слово се декодира код чије су гране праћене да би се стигло до тог чвора, или 0 ако се тај код не декодира ни у једно слово.

DECODE MORSE(msg)
i = 0
new_msg = ""
while msg[i] ≠ 0 do
    p = root
    while (msg[i] ≠ ' ') and (p ≠ nil) do
        if msg[i] = '.' then
            p = left(p)
        else if msg[i] = - then
            p = right(p)
        else
            ERROR(Invalid code)
        end_if
        i = i + 1
    end_while
    i = i + 1
    if (p = nil) or (sign(p) = 0) then
        ERROR(Invalid code)
    end_while
    new_msg = new_msg + sign(p)
end_while
return new_msg

3. задатак

Поставка

Применом ЛЗW алгоритма приказати поступак кодирања знаковног низа БИББИДИБОББИДИБОО, ако је дата почетна табела са кодовима симбола. Написати кодирану поруку и изглед табеле симбола након поступка кодирања.

Решење

Крајње кодирано: 0204153628033

Таблица ЛЗW кодова (прва четири дата у поставци)
Слово	Код
Б	0
D	1
I	2
О	3
БИ	4
ИБ	5
ББ	6
БИД	7
DI	8
ИБО	9
ОБ	10
ББИ	11
ИД	12
ДИБ	13
БО	14
ОО	15

Поступак декодовања
Унос	Стринг	Испис	Додаје се у табелу
Б	Б
I	БИ	0 (Б)	БИ
Б	ИБ	2 (I)	ИБ
Б	ББ	0 (Б)	ББ
I	БИ
D	БИД	4 (БИ)	БИД
I	DI	1 (D)	DI
Б	ИБ
О	ИБО	5 (ИБ)	ИБО
Б	ОБ	3 (О)	ОБ
Б	ББ
I	ББИ	6 (ББ)	ББИ
D	ИД	2 (I)	ИД
I	DI
Б	ДИБ	8 (DI)	ДИБ
О	БО	0 (Б)	БО
О	ОО	3 (О)	ОО
	О	3 (О)

4. задатак

Поставка

Дужине путева у стаблу

Формално дефинисати и објаснити интерну, екстерну и тежинску екстерну дужину пута у бинарном стаблу.
Написати у псеудокоду имплементацију функције која израчунава тежинску екстерну дужину пута бинарног стабла на чији корен указује показивач роот. Сматрати да листови стабла поседују информацију о тежини чвора. Дозвољено користити готове линеарне структуре података.

Решење

Интерна дужина пута је збир дужина путева од корена до сваког интерног чвора.
Екстерна дужина пута је збир дужина путева од корена до сваког екстерног чвора.
Екстерна тежинска дужина пута је збир производа дужина путева од корена до сваког екстерног чвора и тежине тих екстерних чворова.

За потребе овог алгоритма сматра се да су екстерни чворови изједначени са листовима.

CALC EXT WPL(root)
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_levels)
INSERT(Q_nodes, root)
INSERT(Q_levels, 0)
node = nil
level = 0
pwe = 0
while not QUEUE_EMPTY(Q_nodes) do
    node = DELETE(Q_nodes)
    level = DELETE(Q_levels)
    if (left(node) = nil) and (right(node) = nil) then
        pwe = pwe + level * weight(node)
    end_if
    if left(node) ≠ nil then
        INSERT(Q_nodes, left(node))
        INSERT(Q_levels, level + 1)
    end_if
    if right(node) ≠ nil then
        INSERT(Q_nodes, right(node))
        INSERT(Q_levels, level + 1)
    end_if
end_while
return pwe

Трећи колоквијум

1. задатак

Поставка

Дат је усмерен, ациклични граф представљен помоћу матрице суседности код кога су чворови нумерисани од 1 до н. Објаснити како се коришћењем одговарајућег графовског алгоритма могу пренумерисати чворови тако да матрица суседности постане горња троугаона и написати у псеудокоду функцију РЕЛАБЕЛ која пренумерисање.

Решење

RELABEL(G, n)
topsort_length = 0
for i = 1 to n do
    in_deg[i] = 0
    for j = 1 to n do
        if M[j, i] then
            in_deg[i] = in_deg[i] + 1
        end_if
    end_for
    if in_deg[i] = 0 then
        topsort_length = topsort_length + 1
        topsort[topsort_length] = i
    end_if
end_for
for i = 1 to n do
    node = topsort[i]
    for j = 1 to n do
        if M[node, j] then
            in_deg[j] = in_deg[j] - 1
            if in_deg[j] = 0 then
                topsort_length = topsort_length + 1
                topsort[topsort_length] = j
            end_if
        end_if
    end_for
end_for
return topsort

2. задатак

Поставка

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

Флоyд-ов алгоритам. На слици је дат усмерени тежински граф.

Представити дати граф одговарајућом матричном репрезентацијом.
Пронаћи најкраћа растојања међу чворовима употребом Флоyд-овог алгоритма. Поступак приказати по корацима.
На основу резултат под б) реконструисати најкраћу путању између чворова б и д.

Решење

Решење ставке под ц је бфацед.

Матрична репрезентација графа
-	а	б	ц	д	е	ф
а	∞	7	3	10	8	∞
б	∞	∞	∞	22	∞	1
ц	∞	∞	∞	5	2	∞
д	∞	∞	∞	∞	∞	12
е	∞	∞	∞	1	∞	∞
ф	6	∞	∞	∞	∞	∞

*Флоyд*-ов алгоритам за $k = 1$
∞	7	3	10	8	∞
∞	∞	∞	22	∞	1
∞	∞	∞	5	2	∞
∞	∞	∞	∞	∞	12
∞	∞	∞	1	∞	∞
6	13	9	16	14	∞

Матрица претходника за $k = 1$
0	0	0	0
0	0	0	0
0	0	0	0
0	0	0	0
0	0	0	0
1	1	1	1

*Флоyд*-ов алгоритам за $k = 2$
∞	7	3	10	8	8
∞	∞	∞	22	∞	1
∞	∞	∞	5	2	∞
∞	∞	∞	∞	∞	12
∞	∞	∞	1	∞	∞
6	13	9	16	14	14

Матрица претходника за $k = 2$
0	0	0	0	2
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
1	1	1	1	2

*Флоyд*-ов алгоритам за $k = 3$
∞	7	3	8	5	8
∞	∞	∞	22	∞	1
∞	∞	∞	5	2	∞
∞	∞	∞	∞	∞	12
∞	∞	∞	1	∞	∞
6	13	9	14	11	14

Матрица претходника за $k = 3$
0	0	3	3	2
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
1	1	3	3	2

*Флоyд*-ов алгоритам за $k = 4$
∞	7	3	8	5	8
∞	∞	∞	22	∞	1
∞	∞	∞	5	2	17
∞	∞	∞	∞	∞	12
∞	∞	∞	1	∞	13
6	13	9	14	11	14

Матрица претходника за $k = 4$
0	0	3	3	2
0	0	0	0	0
0	0	0	0	4
0	0	0	0	0
0	0	0	0	4
1	1	3	3	2

*Флоyд*-ов алгоритам за $k = 5$
∞	7	3	6	5	8
∞	∞	∞	22	∞	1
∞	∞	∞	3	2	15
∞	∞	∞	∞	∞	12
∞	∞	∞	1	∞	13
6	13	9	12	11	14

Матрица претходника за $k = 5$
0	0	5	3	2
0	0	0	0	0
0	0	5	0	5
0	0	0	0	0
0	0	0	0	4
1	1	5	3	2

*Флоyд*-ов алгоритам за $k = 6$
14	7	3	6	5	8
7	14	10	13	12	1
21	28	24	3	2	15
18	25	21	24	23	12
19	26	22	1	24	13
6	13	9	12	11	14

Матрица претходника за $k = 6$
6	0	0	5	3	2
6	6	6	6	6	0
6	6	6	5	0	5
6	6	6	6	6	0
6	6	6	0	6	4
0	1	1	5	3	2

3. задатак

Поставка

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

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

Решење

Резидуални граф за трећи задатак.

Могући путеви повећаног протока:

СЦБТ (2)
САЦБТ (2)
СДЕЦБТ (2)
САДЕЦБТ (2)

4. задатак

Поставка

Нека се посматра се неусмерен нетежински граф.

На који начин се у оваквом графу може остварити провера цикличности графа коришћењем алгоритама за обилазак по ширини и по дубини? Објаснити и нацртати пример.
Написати у псеудокоду имплементацију функције која коришћењем обиласка по ширини одређује да ли је прослеђени граф цикличан. Сматрати да је граф представљен матрицом суседности. Дозвољено је користити готове линеарне структуре података.

Решење

Обиласком по ширини или дубини се у неусмереном графу може детектовати циклус тако што приликом обиласка детектујемо да посећујемо чвор који смо већ посетили, а да то није отац тренутног чвора у стаблу обиласка.

IS CYCLIC(G)
for i = 1 to n do
    visited[i] = 0
end_for
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_parents)
INSERT(Q_nodes, 1)
INSERT(Q_parents, 0)
node = parent = 0
while not QUEUE_EMPTY(Q_nodes) do
    node = DELETE(Q_nodes)
    parent = DELETE(Q_parents)
    for (node, i) ∈ E do
        if i = parent then
            continue
        end_if
        if visited[i] then
            return true
        end_if
        INSERT(Q_nodes, i)
        INSERT(Q_parents, node)
        visited[i] = true
    end_for
end_while
return false

АСП1/Јун 2020

Први колоквијум

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

Други колоквијум

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

Трећи колоквијум

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

Мени за навигацију

Претрага