АСП1/Јул 2020

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

1. задатак

Поставка

Дата је ретка квадратна матрица димензије 5. Навести два начина да се прикаже помоћу уланчаних листа.

2. задатак

Поставка

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

3. задатак

Поставка

Пребацити инфиксни израз А*(Б-C)*(А-D!!)+Ф/Г+К у постфиксни и попунити табелу испод.

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

4. задатак

Поставка

Имплементирати операције за додавање елемената на почетак и крај реда имплементираног преко кружног вектора.

Решење

INSERT-BEFORE(Q, value)

INSERT-AFTER(Q, value)

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

1. задатак

Поставка

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

2. задатак

Поставка

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

3. задатак

Поставка

Динамички Хафман. (?) Упоредити дужину карактера са динамичким Хафманом и без њега. (??)

4. задатак

Поставка

1. Објаснити поступак конверзије м-арног стабла у бинарно стабло.
2. На следећем примеру м-арног стабла приказати поступак конверзије по корацима. (?)

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

1. задатак

Поставка

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

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

Решење

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

GC(G, 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. Наћи минимално обухватно стабло применом Примовог алгоритма, ако се за почетни чвор узима чвор С. Приказати редом које гране се додају у обухватно стабло.
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