АСП1/Јул 2020

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

1. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

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

Ретка матрица са слике
0	3	12	0
0	1	0	74
0	7	0	32
8	0	2	15
0	0	0	98

Решење

2. задатак

Поставка

Посматра се стек имплементиран двоструко уланчаном листом са заглављем, које садржи показивач на први елемент листе. Поред стандардних операција, неопходно је подржати и ефикасну операцију дохватања максималног елемента на стеку (у О(1)).

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

Решење

Дохватање максималног елемента у О(1) постижемо додатном листом која чува дотадашњи максимални елемент. Листа која држи елементе се зове стацк, а листа која држи максималне елменте се зове маx.

PUSH(header, x)
if header = nil then
    return
end_if
t = GETNODE()
info(t) = x
next(t) = stack(header)
stack(header) = t
t = GETNODE()
if max(header) ≠ NIL and x < max(header) then
    info(t) = info(max(header))
else
    info(t) = x
end_if
next(t) = max(header)
max(header) = t
POP(header)
if header ≠ NIL and stack(header) ≠ NIL then
    t = stack(header)
    stack(header) = next(stack(header))
    value = info(t)
    FREENODE(t)
    t = max(header)
    max(header) = next(max(header))
    FREENODE(t)
    return value
end_if
return NIL
MAX(header)
return info(max(header))

3. задатак

Поставка

Трансформисати израз у инфиксном облику А*(Б+C)*(А-D!!)+Ф/Г+К у еквивалентни израз у постфиксној форми. Табелу приоритета оператора допунити одговарајућим вредностима, при чему треба усвојити стандардне приоритете и груписање за операције +,-,* и /. Операција факторијел ! унарна операција која се групише слева на десно и има највећи приоритет од свих аритметичких операција. Трансформацију израза приказати по корацима.

Решење

Оператор	Улазни приоритет	Стек приоритет	Ранг
+, -	2	2	-1
*, /	3	3	-1
!	5	4	0
(	6	1	0
)	0	-	0

Симбол	Стек	Постфиксни израз	Ранг
А		А	1
*	*	А	1
(	*(	А	1
Б	*(	АБ	2
+	*(+	АБ	2
C	*(+	АБЦ	3
)	*	АБЦ+	2
*	*	АБЦ+*	1
(	*(	АБЦ+*	1
А	*(	АБЦ+*А	2
-	*(-	АБЦ+*А	2
D	*(-	АБЦ+*АД	3
!	*(-!	АБЦ+*АД	3
!	*(-!!	АБЦ+*АД	3
)	*	АБЦ+*АД!!-	2
+	+	АБЦ+АД!!-	1
Ф	+	АБЦ+АД!!-Ф	2
/	+/	АБЦ+АД!!-Ф	2
Г	+/	АБЦ+АД!!-ФГ	3
+	+	АБЦ+АД!!-ФГ/+	1
К	+	АБЦ+АД!!-ФГ/+К	2
ЕОФ		*АБЦ+АД!!-ФГ/+К+*	1

4. задатак

Поставка

Нека се двострани ред у псеудојезику описује следећим записом:

deque = RECORD
    array, front, rear, size
END

где арраy представља низ ограниченог капацитета сизе, а фронт и реар показиваче почетка и краја реда. Индекси у низу почињу од 0.

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

Решење

Услов пуног реда: (реар + 1) % сизе = фронт

Услов празног реда: фронт = реар

INSERT FRONT(deque, x)
if deque = NIL or (rear(deque) + 1) % size(deque) = front(deque) then
    return
front(deque) = (front(deque) - 1) % size(deque)
array(deque)[front(deque)] = x
INSERT REAR(deque, x)
if deque = NIL or (rear(deque) + 1) % size(deque) = front(deque) then
    return
rear(deque) = (rear(deque) + 1) % size(deque)
array(deque)[rear(deque)] = x

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

1. задатак

Поставка

Повезана бинарна стабла

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

Решење

Повезано бинарно стабло је стабло у којем су неискоришћени показивачи на леву и десну децу искоришћени у сврху лакшег обиласка стабла неким начином обиласка. Структура чвора таквог стабла има следећа поља:

value — вредност у чвору стабла
left — показивач на лево дете или претходника по редоследу обиласка
right — показивач на десно дете или следбеника по редоследу обиласка
lf — бит постављен на 1 уколико left показује на лево дете и 0 уколико показује на претходника по редоследу обиласка
rf — бит постављен на 1 уколико right показује на десно дете и 0 уколико показује на следбеника по редоследу обиласка

У псеудокоду за тачку под б, како би повезано стабло остало повезано, потребно је да пронађемо претходника чвора x по инордер-у и првог следбеника чвора x по инордер-у који се не налази у његовом подстаблу, повежемо их а све остале чворове између ослободимо.

DELETE-T(x)
prethodnik = left(x)
sledbenik = right(x)
next_sledbenik = nil
while sledbenik ≠ nil do
    if lf(sledbenik) = 1 then
        if left(sledbenik) = x then
            break
        else
            next_sledbenik = left(sledbenik)
            while (next_sledbenik ≠ nil) and ((lf(next_sledbenik) = 1) or (left(next_sledbenik) = nil)) do
                 if left(next_sledbenik) = x then
                     break
                 end_if
                 next_sledbenik = left(next_sledbenik)
            end_while
            if (next_sledbenik ≠ nil) and (left(next_sledbenik) = x) then
                FREENODE(sledbenik)
                sledbenik = next_sledbenik
                break
            end_if
        end_if
    else
        next_sledbenik = right(sledbenik)
    end_if
    FREENODE(sledbenik)
    sledbenik = next_sledbenik
end_while
if (prethodnik ≠ nil) and (rf(prethodnik) = 0) then
    right(prethodnik) = sledbenik
end_if
if sledbenik ≠ nil then
    left(sledbenik) = prethodnik
    lf(sledbenik) = 0
end_if

2. задатак

Поставка

Нека се посматра бинарно стабло чији чворови садрже целе бројеве. Написати у псеудокоду итеративну имплементацију функције ЦХЕЦК_СУМ која проверава да ли садржај сваког чвора-оца у стаблу на чији корен указује показивач роот представља збир садржаја свих његових потомака.

Решење

CHECK SUM(root)
p = root
STACK_INIT(S)
while p ≠ nil do
    PUSH(S, p)
    p = left(p)
end_while
while not STACK_EMPTY(S) do
    p = POP(S)
    if p > 0 then
        while left(p) ≠ nil do
            PUSH(S, -p)
            p = left(p)
        end_while
        if right(p) ≠ nil then
            PUSH(S, right(p))
        end_if
    else
        sum = 0
        if (left(p) ≠ nil) or (right(p) ≠ nil) then
            if left(p) ≠ nil then
                sum = sum + value(left(p))
            end_if
            if right(p) ≠ nil then
                sum = sum + value(right(p))
            end_if
            if sum * 2 ≠ value(p) then
                return false
            end_if
        end_if
    end_if
end_while
return true

3. задатак

Поставка

Применом динамичког Хуффман алгоритма кодирати поруку АБЦДББЦАААБЦ и приказати поступак кодирања уколико су почетни кодови симбола А, Б, C и D 00, 01, 10 и 11 респективно. Упоредити просечну дужину симбола применом овог алгоритма са иницијално додељеним кодовима.

Решење

Крајње трансмитовано: 00 001 0010 10011 11 11 111 111 111 10 10 101
Крајње стабло:

NYT
 0

00

  1
 / \
NYT A
 0  1

001

    2
   / \
  1   A
 / \  1
NYT B
 0  1

0010

  3
 / \
A   2
1  / \
  1   B
 / \  1
NYT C
 0  1

10011

       4
     /   \
    2     2
   / \   / \
  1   C A   B
 / \  1 1   1
NYT D
 0  1

11

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

11

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

111

  7
 / \
B   4
3  / \
  C   2
  2  / \
    1   A
   / \  1
  NYT D
   0  1

111

  8
 / \
B   5
3  / \
  C   3
  2  / \
    1   A
   / \  2
  NYT D
   0  1

111

  9
 / \
B   6
3  / \
  A   3
  3  / \
    1   C
   / \  2
  NYT D
   0  1

10

10

101

Крај.

4. задатак

Поставка

Конверзија м-арног у бинарно стабло

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

        X
     / / \ \
   Y  A   F  C
 / | \   /  / \
B  G  E J  K   M
     /
    D

Решење

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

Постордер поредак чворова: БГДЕYАЈФКМЦX

Б, Г, D — Немају децу
Е — Већ је конвертован у чвор бинарног стабла
Y —

       X
    / / \  \
  Y  A   F  C
 /      /  / \
B      J  K   M
 \
  G
   \
    E
   /
  D

А, Ј — Немају децу
Ф — Већ је конвертован у чвор бинарног стабла
К, M — Немају децу
C —

       X
    / / \  \
  Y  A   F  C
 /      /  /
B      J  K
 \         \
  G         M
   \
    E
   /
  D

X — Види коначно стабло

Коначно стабло:

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

1. задатак

Поставка

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

Нека је дат низ променљивих варс дужине н_варс који показују на објекте и почев од којих је потребно проверити да ли се до свих алоцираних објеката у неком програму може доћи. Имплементирати функцију ГЦ која треба да врати скуп свих оних објеката који су недостижни из перспективе почетног скупа променљивих (варс).

Решење

Дато је генерално решење ради читљивости, решење у матричној репрезентацији је вежба за читаоца. Неопходна је имплементација БФС (или било ког алгоритма претраге графа преко грана) који враћа скуп посећених чворова. Р (реацхабле) је скуп чворова који су достижни. Враћају се они чворови који након ових претрага нису били достижни.

GC(G, n, vars, n_vars)
R = ∅
for each v in vars do
    R = R ∪ BFS(G, v)
end_for
return G \ R

2. задатак

Поставка

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

Јако повезане компоненте

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

Решење

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

Редуковани граф.

Јако повезаном компонентом називамо подграф у коме је сваки чвор достижан свим осталим чворовима. Алгоритам за налажење јако повезаних компоненти можемо поделити на 4 дела:

На датом графу Г радимо ДФС и памтимо завршна времена сваког чвора.
Формирамо транспоновани граф Г^Т графа Г. Транспоновани граф је граф у коме је смер свих грана обрнут.
На графу Г^Т радимо ДФС почевши од чвора са највећим завршним временом. Скуп посећених чворова који враћа ДФС чини јако повезану компоненту тојест један чвор у редукованом графу.
Све чворове које смо посетили у 3. кораку уклањамо из Г^Т, те понављамо 3. корак док граф не постане празан.

ДФС који креће од C:

Чвор	Почетно време	Завршно време
C	1	20
А	2	19
Б	3	12
Ф	4	11
Х	5	10
Ј	6	9
I	7	8
Е	13	18
Г	14	17
D	15	16

Јако повезане компоненте:

Чвор	Завршно време
C	20
Чвор	Завршно време
А	19
Чвор	Завршно време
Е	18
D	16
Г	17
Чвор	Завршно време
Б	12
I	8
Ј	9
Х	10
Ф	11

3. задатак

Поставка

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

На слици је дат тежински неусмерен граф.

Наћи минимално обухватно стабло применом Примовог алгоритма, ако се за почетни чвор узима чвор С. Приказати редом које гране се додају у обухватно стабло.
Наћи минимално обухватно стабло применом Примовог алгоритма, ако се за почетни чвор узима чвор Б. Приказати редом које гране се додају у обухватно стабло.
Укратко и прецизно објаснити да ли је приликом тражења минималног обухватног стабла у претходним тачкама могло да се добије и другачије минимално обухватно стабло? Ако да, написати од чега то зависи и навести одоварајући корак у коме се то десило.

Решење

Од С	Од Б
С-M 3	Б-А 3
M-К 2	А-Т 2
К-Б 4	Б-К 4
Б-А 3	К-M 2
А-Т 2	M-С 3
Т-Ф 6	С-Ф 5

Могуће је добити другачије стабло уколико се деси да имамо две гране које су минималне али исте тежине. Ако не постоје додатни критеријуми где би једна грана била боља од друге и при бирању једне гране неће доћи до тога да и друга буде додата у крајње стабло, онда постоје две опције. У овом задатку то се дешава у 3. кораку када крећемо од С, где можемо бирати или К-Б 4 или M-Б 4.

4. задатак

Поставка

Ексцентричност чвора и средиште графа

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

Решење

Ексцентричност чвора се дефинише као максимум од најкраћих растојања од свих чворова графа до тог чвора тј. $ecc(v) = max \{ d[i,v] : i \in V \}$ .

Средиште графа је чвор са најмањом ексцентичношћу.

Одређивање ексцентричности чвора:

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

Одређивање средишта графа:

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

АСП1/Јул 2020

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

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

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

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

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

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

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

Претрага