АСП1/Јул 2020

Задаци

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

1. задатак

Поставка

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

Ретка матрица са слике

0	3	12	0	0
0	1	0	74	0
0	7	0	32	0
8	0	2	15	0
0	0	0	98	0

2. задатак

Поставка

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

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

Решење

PUSH(header, x)

POP(header)

MAX(header)

3. задатак

Поставка

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

Решење

Оператор	Улазни приоритет	Стек приоритет	Ранг
+, -
*, /
!
(
)

4. задатак

Поставка

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

deque = RECORD
    array, front, rear, size
END

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

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

Решење

INSERT FRONT(deque, x)

INSERT REAR(deque, x)

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

1. задатак

Поставка

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

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

Решење

DELETE-T(x)

2. задатак

Поставка

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

Решење

CHECK SUM(root)

3. задатак

Поставка

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

4. задатак

Поставка

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

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

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

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

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

Поставка

Датотека:АСП1 јул 2020 задатак 3.2 граф.пнг

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

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

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

Решење

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

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

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

1. На датом графу Г радимо ДФС и памтимо завршна времена сваког чвора.
2. Формирамо транспоновани граф Г^Т графа Г. Транспоновани граф је граф у коме је смер свих грана обрнут.
3. На графу Г^Т радимо ДФС почевши од чвора са највећим завршним временом. Скуп посећених чворова који враћа ДФС чини јако повезану компоненту тојест један чвор у редукованом графу.
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. задатак

Поставка

Датотека:АСП1 јул 2020 задатак 3.3 граф.пнг

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

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

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

Решење

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

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

4. задатак

Поставка

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

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

Решење

Ексцентричност чвора се дефинише као максимум од најкраћих растојања од свих чворова графа до тог чвора тј. $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