АСП1/К3 2019
1. задатак
Поставка
На слици је приказан нетежински усмерени граф.
- Приказати редослед чворова након обиласка графа са слике по ширини, уколико се као почетни чвор зада чвор А. Чворови се убацују у структуру према лексикографском поретку уколико постоји више могућности.
- Приказати редослед чворова након итеративног обиласка графа са слике по дубини, уколико се као почетни чвор зада чвор А. Чворови се убацују у структуру према лексикографском поретку уколико постоји више могућности.
Решење
- АБИЦДМФЛК
- АИБЦМЛКДФ
2. задатак
Поставка
У неком малом месту се реновира мрежа улица. Све улице у месту су двосмерне. Да би се реновирало што више улица, потребно је обезбедити да између свака два важна објекта у месту (школа, болница, општина, итд.) постоји пут и да укупна дужина свих отворених путева за саобраћај у месту буде минимална. Уколико је мрежа улица и важних објеката представљена неусмереним тежинским графом са слике, навести који алгоритам би се могао искористити за решавање овог проблема и његовом применом одредити улице које треба да остану отворене за саобраћај током реновирања, према наведеним условима. Приказати поступак.
Решење
Могао би се применити Примов или Крушкалов алгоритам за добијање минимланог обухватног стабла. У наредном поступку биће коришћен Примов алгоритам:
- А-Е
- Е-Ф
- Е-D
- D-Ц
- C-Х
- Х-I
- C-Б
- Х-Г
- Г-I
Графови се налазе испод.
Поједностављен граф из поставке задатка.
Минимално обухватно стабло.
3. задатак
Поставка
Нека се посматра секвенцијални програмски код који се извршавана на некој 3А машини. Први операнд инструкције је одредишни, а преостала два су изворишни операнди. Приликом превођења, преводилац може да преуреди редослед извршавања инструкција да би извршио одређене оптимизације. Међутим, преуређивање редоследа две инструкције се може извршити само уколико не постоји зависности по подацима између њих. Зависност по подацима између инструкција постоји уколико се одредишни операнд (резултат) раније операције користи као изворишни операнд касније операције.
- Описати модел графа који се може искористити за моделовање зависности по подацима између инструкција.
- Објаснити који алгоритам би се могао искористити за проналажење свих могућих редоследа извршавања инструкција на основу задатог графа зависности по подацима.
- На примеру задатог програмског кода, нацртати граф зависности по подацима и одредити (написати) још један могућ редослед извршавања инструкција који задовољава присутне зависности по подацима.
ADD A, B, C MUL C, E, D SUB B, E, C ADD A, D, E SUB E, F, G DIV D, F, H ADD G, F, H
Решење
- У питању је ацикличан нетежински усмерен граф у ком чворови представљају инструкције а гране од једног ка другом чвору представљају зависност изворишних операнада другог чвора од одредишног операнда првог.
- Може се искористити модификација тополошког сортирања где се након сваког прикупљања чворова са улазним степеном 0 за сваки од њих покушавају наћи сви путеви који на том месту садрже тај чвор. Рекурзивна имплементација овог алгоритма је дата испод (где су путеви представљени уланчаним листама).
- Граф се састоји од свих чворова одвојених и једне гране између чворова
MUL C, E, DиSUB B, E, C.ADD A, B, CADD A, D, EMUL C, E, DSUB B, E, CSUB E, F, GDIV D, F, HADD G, F, H
TOP SORT ALL PATHS R(G)
if V = {} then
return nil
end_if
return_paths = {}
for {n : (n ∈ V) and ((u, n) ∉ E)} do
MARK_REMOVED(G, n)
paths = TOP_SORT_ALL_PATHS_R(G)
for path ∈ paths do
new_path = GETNODE
value(new_path) = n
next(new_path) = path
path = new_path
end_for
UNMARK_REMOVED(G, n)
return_paths = return_paths + paths
end_for
return return_paths
4. задатак
Поставка
Посматра се усмерен нетежински граф. Написати итеративну функцију у псеудокоду која за прослеђени граф са датим бројем чворова н проналази све чворове који су путевима дужине тачно к удаљени од задатог почетног чвора ид.
Решење
Имплементација испод чворове враћа у уланчаној листи.
K-DISTANCE(G, n, k, id)
dist[n]
for i = 1 to n do
dist[i] = ∞
end_for
dist[id] = 0
curr_dist = 0
tail = head = GETNODE(id)
next(head) = GETNODE(0)
head = next(head)
curr = 0
temp = nil
while (tail ≠ nil) and (curr_dist ≠ k) do
curr = value(tail)
if curr = 0 then
curr_dist = curr_dist + 1
if head ≠ tail then
next(head) = GETNODE(0)
head = next(head)
end_if
else
for node ∈ {v : (curr, v) ∈ E} do
if dist[node] ≠ curr_dist + 1 then
dist[node] = curr_dist + 1
next(head) = GETNODE(node)
head = next(head)
end_if
end_for
end_if
temp = tail
tail = next(tail)
FREENODE(temp)
end_while
return tail
GETNODE(node)
ALLOCATE(node)
next(node) = nil
value(node) = value
return node
5. задатак
Поставка
Флоyд алгоритам
- На слици је дат изглед матрица D и Т добијених као излаз Флоyд алгоритма. Нацртати могући изглед улазног графа и образложити одговор.
- Написати у псеудокоду функцију која на основу матрице Т добијене као излаз Флоyд-овог алгоритма реконструише најкраћи пут од чвора А до чвора C такав да се на њему налази чвор Б.
| 0 | 2 | 7 |
| ∞ | 0 | 5 |
| ∞ | ∞ | 0 |
| 0 | 1 | 2 |
| 0 | 0 | 2 |
| 0 | 0 | 0 |
Решење
- Претпостављајући да нема грана негативне тежине видимо да је најкраћи пут дужине 2 и зато сигурно мора бити директна грана између А и Б. Пошто видимо да матрица D није симетрична претпостављамо да се ради о усмереном тежинском графу. На основу тренутног графа и D матрице видимо да је грана Б-C тежине 5, и све остало се слаже.
- У псеудокоду испод подразумева се да је пут представљен уланчаном листом. Уколико је враћено нил то значи да нема пута.
PATH(T, A, B, C)
curr = GETNODE(C)
next = nil
while value(curr) ≠ B do
if T[B][value(curr)] = 0 then
return nil
end_if
next = GETNODE(T[B][value(curr)])
next(next) = curr
curr = next
end_while
while value(curr) ≠ A do
if T[A][value(curr)] = 0 then
return nil
end_if
next = GETNODE(T[A][value(curr)])
next(next) = curr
curr = next
end_while
return curr
6. задатак
Поставка
За граф са слике одредити тополошки поредак, а затим наћи критични пут и дозвољена кашњења за појединачне чворове.
Решење
- Тополошки поредак: АБДЦФЕХГИЈК
- Критични пут: АБЦЕХГЈК (или АБЦЕХГИЈК)
- Табела:
| Чвор | ЕСТ | ЛСТ | L |
| А | 0 | 0 | 0 |
| Б | 1 | 1 | 0 |
| C | 10 | 0 | |
| D | 3 | 6 | 3 |
| Е | 15 | 15 | 0 |
| Ф | 13 | 2 | |
| Г | 19 | 19 | 0 |
| Х | 16 | 16 | 0 |
| I | 21 | 21 | 0 |
| Ј | 22 | 22 | 0 |
| К | 24 | 24 | 0 |
7. задатак
Поставка
Која су два карактеристична начина за избор пута повећаног протока у проточном графу? На примеру проточног графа са слике у оквиру кога постоји већ успостављен проток по појединим гранама, нацртати резидуални граф и навести два карактеристична пута који илуструју наведене ситуације.
Решење
Два карактеристична начина за избор пута повећаног протока су:
- обичан БФС који ће наћи најкраћи пут од С до Т, на пример СБТ, и
- бирање пута који највише повећава проток, на пример СБАТ.
Графови су дати испод.
Граф из поставке задатка.
Резидуални граф.
8. задатак
Поставка
Дијкстра-ин алгоритам
- Колика је сложеност Дијкстра-иног алгоритма и од којих операција у оквиру алгоритма то зависи? Објаснити.
- Написати псеудокод Дијкстра-иног алгоритма који проналази најкраће растојање између пара чворова x и y под претпоставком да се граф Г представља листама суседности. Специјализовати апстрактне операције где је то могуће.
Решење
Сложеност Дајкстриног алгоритма зависи од операција проналажења следећег чвора до којег је пут најкраћи и ажурирања матрице D са додавањем новог чвора у скуп С. Може бити у случају да се проналажење следећег чвора до којег је пут најкраћи извршава у и да је граф представљен матрицом суседности. Боља сложеност достиже се онда када је граф представљен листом суседности и операција проналажења следећег чвора са најкраћим путем има сложеност од , када је сложеност .
DIJKSTRA ADJ LIST(G, x, y)
S = {x}
for i = 1 to n do
d[i] = w[x, i]
if d[i] = ∞ then
t[i] = 0
else
t[i] = x
end_if
end_for
for k = 1 to n-1 do
start_node = -1
for i ∈ (V - S) do
if (start_node = -1) or (d[i] < d[start_node]) then
start_node = i
end_if
end_for
S = S + {start_node}
adj_node = AL[start_node]
while adj_node ≠ nil do
if w[start_node, value(adj_node)] + d[start_node] < d[value(adj_node)] then
d[value(adj_node)] = w[start_node, value(adj_node)] + d[start_node]
t[value(adj_node)] = start_node
end_if
adj_node = next(adj_node)
end_while
end_for
return d[y]