АСП1/К3 2019

Задаци

1. задатак

Поставка

Датотека:АСП1 К3 задатак 1 граф.пнг

Граф из задатка 1.

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

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

Решење

1. АБИЦДМФЛК
2. АИБЦМЛКДФ

2. задатак

Поставка

У неком малом месту се реновира мрежа улица. Све улице у месту су двосмерне. Да би се реновирало што више улица, потребно је обезбедити да између свака два важна објекта у месту (школа, болница, општина, итд.) постоји пут и да укупна дужина свих отворених путева за саобраћај у месту буде минимална. Уколико је мрежа улица и важних објеката представљена неусмереним тежинским графом са слике, навести који алгоритам би се могао искористити за решавање овог проблема и његовом применом одредити улице које треба да остану отворене за саобраћај током реновирања, према наведеним условима. Приказати поступак.

Решење

Могао би се применити Примов или Крушкалов алгоритам за добијање минимланог обухватног стабла. У наредном поступку биће коришћен Примов алгоритам:

1. А-Е
2. Е-Ф
3. Е-D
4. D-Ц
5. C-Х
6. Х-I
7. C-Б
8. Х-Г
9. Г-I

Графови се налазе испод.

• АСП1 К3 2019 задатак 2 граф.јпг

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

• АСП1 К3 2019 задатак 2 граф.пнг

  Поједностављен граф из поставке задатка.

• АСП1 К3 2019 задатак 2 МСТ.пнг

  Минимално обухватно стабло.

3. задатак

Поставка

Нека се посматра секвенцијални програмски код који се извршавана на некој 3А машини. Први операнд инструкције је одредишни, а преостала два су изворишни операнди. Приликом превођења, преводилац може да преуреди редослед извршавања инструкција да би извршио одређене оптимизације. Међутим, преуређивање редоследа две инструкције се може извршити само уколико не постоји зависности по подацима између њих. Зависност по подацима између инструкција постоји уколико се одредишни операнд (резултат) раније операције користи као изворишни операнд касније операције.

1. Описати модел графа који се може искористити за моделовање зависности по подацима између инструкција.
2. Објаснити који алгоритам би се могао искористити за проналажење свих могућих редоследа извршавања инструкција на основу задатог графа зависности по подацима.
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

4. задатак

Поставка

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

5. задатак

Поставка

Флоyд алгоритам

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

Матрица D

0	2	7
∞	0	5
∞	∞	0

Матрица Т

0	1	2
0	0	2
0	0	0

6. задатак

Поставка

Граф из задатка 6.

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

Решење

• Тополошки поредак: АБДЦФЕХГИЈК
• Критични пут: АБЦЕГЈК (или АБЦЕГИЈК)
• Табела:

Чвор	ЕСТ	ЛСТ	L
А	0	0	0
Б	1	1	0
C	3 10	10	0
D	3	6	3
Е	15	15	0
Ф	6 11	13	2
Г	19	19	0
Х	16	16	0
I	21	21	0
Ј	22	22	0
К	24	24	0

7. задатак

Поставка

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

8. задатак

Поставка

Дијкстра-ин алгоритам

1. Колика је сложеност Дијкстра-иног алгоритма и од којих операција у оквиру алгоритма то зависи? Објаснити.
2. Написати псеудокод Дијкстра-иног алгоритма који проналази најкраће растојање између пара чворова x и y под претпоставком да се граф Г представља листама суседности. Специјализовати апстрактне операције где је то могуће.