АСП1/К3 2019

Zadaci

1. zadatak

Postavka

Датотека:ASP1 K3 zadatak 1 graf.png

Graf iz zadatka 1.

Na slici je prikazan netežinski usmereni graf.

1. Prikazati redosled čvorova nakon obilaska grafa sa slike po širini, ukoliko se kao početni čvor zada čvor A. Čvorovi se ubacuju u strukturu prema leksikografskom poretku ukoliko postoji više mogućnosti.
2. Prikazati redosled čvorova nakon iterativnog obilaska grafa sa slike po dubini, ukoliko se kao početni čvor zada čvor A. Čvorovi se ubacuju u strukturu prema leksikografskom poretku ukoliko postoji više mogućnosti.

Rešenje

1. ABICDMFLK
2. AIBCMLKDF

2. zadatak

Postavka

U nekom malom mestu se renovira mreža ulica. Sve ulice u mestu su dvosmerne. Da bi se renoviralo što više ulica, potrebno je obezbediti da između svaka dva važna objekta u mestu (škola, bolnica, opština, itd.) postoji put i da ukupna dužina svih otvorenih puteva za saobraćaj u mestu bude minimalna. Ukoliko je mreža ulica i važnih objekata predstavljena neusmerenim težinskim grafom sa slike, navesti koji algoritam bi se mogao iskoristiti za rešavanje ovog problema i njegovom primenom odrediti ulice koje treba da ostanu otvorene za saobraćaj tokom renoviranja, prema navedenim uslovima. Prikazati postupak.

Rešenje

Mogao bi se primeniti Primov ili Kruškalov algoritam za dobijanje minimlanog obuhvatnog stabla. U narednom postupku biće korišćen Primov algoritam:

1. A-E
2. E-F
3. E-D
4. D-C
5. C-H
6. H-I
7. C-B
8. H-G
9. G-I

Grafovi se nalaze ispod.

• ASP1 K3 2019 zadatak 2 graf.jpg

  Graf iz postavke zadatka.

• ASP1 K3 2019 zadatak 2 graf.png

  Pojednostavljen graf iz postavke zadatka.

• ASP1 K3 2019 zadatak 2 MST.png

  Minimalno obuhvatno stablo.

3. zadatak

Postavka

Neka se posmatra sekvencijalni programski kod koji se izvršavana na nekoj 3A mašini. Prvi operand instrukcije je odredišni, a preostala dva su izvorišni operandi. Prilikom prevođenja, prevodilac može da preuredi redosled izvršavanja instrukcija da bi izvršio određene optimizacije. Međutim, preuređivanje redosleda dve instrukcije se može izvršiti samo ukoliko ne postoji zavisnosti po podacima između njih. Zavisnost po podacima između instrukcija postoji ukoliko se odredišni operand (rezultat) ranije operacije koristi kao izvorišni operand kasnije operacije.

1. Opisati model grafa koji se može iskoristiti za modelovanje zavisnosti po podacima između instrukcija.
2. Objasniti koji algoritam bi se mogao iskoristiti za pronalaženje svih mogućih redosleda izvršavanja instrukcija na osnovu zadatog grafa zavisnosti po podacima.
3. Na primeru zadatog programskog koda, nacrtati graf zavisnosti po podacima i odrediti (napisati) još jedan moguć redosled izvršavanja instrukcija koji zadovoljava prisutne zavisnosti po podacima.

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. zadatak

Postavka

Posmatra se usmeren netežinski graf. Napisati iterativnu funkciju u pseudokodu koja za prosleđeni graf sa datim brojem čvorova n pronalazi sve čvorove koji su putevima dužine tačno k udaljeni od zadatog početnog čvora id.

5. zadatak

Postavka

Floyd algoritam

1. Na slici je dat izgled matrica D i T dobijenih kao izlaz Floyd algoritma. Nacrtati mogući izgled ulaznog grafa i obrazložiti odgovor.
2. Napisati u pseudokodu funkciju koja na osnovu matrice T dobijene kao izlaz Floyd-ovog algoritma rekonstruiše najkraći put od čvora A do čvora C takav da se na njemu nalazi čvor B.

Matrica D

0	2	7
∞	0	5
∞	∞	0

Matrica T

0	1	2
0	0	2
0	0	0

6. zadatak

Postavka

Graf iz zadatka 6.

Za graf sa slike odrediti topološki poredak, a zatim naći kritični put i dozvoljena kašnjenja za pojedinačne čvorove.

Rešenje

• Topološki poredak: ABDCFEHGIJK
• Kritični put: ABCEGJK (ili ABCEGIJK)
• Tabela:

Čvor	EST	LST	L
A	0	0	0
B	1	1	0
C	3 10	10	0
D	3	6	3
E	15	15	0
F	6 11	13	2
G	19	19	0
H	16	16	0
I	21	21	0
J	22	22	0
K	24	24	0

7. zadatak

Postavka

Koja su dva karakteristična načina za izbor puta povećanog protoka u protočnom grafu? Na primeru protočnog grafa sa slike u okviru koga postoji već uspostavljen protok po pojedinim granama, nacrtati rezidualni graf i navesti dva karakteristična puta koji ilustruju navedene situacije.

8. zadatak

Postavka

Dijkstra-in algoritam

1. Kolika je složenost Dijkstra-inog algoritma i od kojih operacija u okviru algoritma to zavisi? Objasniti.
2. Napisati pseudokod Dijkstra-inog algoritma koji pronalazi najkraće rastojanje između para čvorova x i y pod pretpostavkom da se graf G predstavlja listama susednosti. Specijalizovati apstraktne operacije gde je to moguće.