АСП1/К3 Јул 2021

Овај рок није решен. Помозите SI Wiki тако што ћете га решити.

Jul 2021. godine nema postavku dostupnu sa stranice predmeta.

1. zadatak

Postavka

Posmatra se plan za realizaciju jednog softverskog projekta dat tabelom. Faza S je početna.

Plan za realizaciju projekta

A	S – 7 dana
B	G – 6 dana, R – 2 dana
F	L – 11 dana
L	S – 7 dana
G	L – 3 dana, A – 4 dana
M	F – 5 dana, B – 3 dana
R	A – 5 dana
T	B – 7 dana, M – 2 dana

1. (5p) Predstaviti projekat grafom.
2. (10p) Ako faza B predstavlja beta fazu projekta i želimo da znamo da ni ona neće kasniti naći kritični put (ili puteve) i kritične aktivnosti za beta fazu.
3. (10p) Naći kritični put (ili puteve) za uspešnu realizaciju ovog projekta kao i kritične aktivnosti.

2. zadatak

Postavka

Data je mreža puteva između gradova predstavljena matričnom reprezentacijom grafa. Putarina između bilo koja dva povezana grada iznosi 1. Međutim pri ulasku u svaki grad, postoji određena taksa koju je potrebno platiti. Cena takse se definiše na nivou grada.

1. Mika voli da putuje i nalazi se u gradu X. Izračunati za svaki grad koliko je novca Miki potrebno da ga obiđe ukoliko uvek kreće iz mesta X. Implementirati funkciju koja efikasno računa minimalnu potrebnu količinu novca za posetu svakom gradu. Funkciji su prosleđeni broj gradova, graf, cene taksi za svaki grad (niz prirodnih brojeva) i indeks početnog grada.
2. Jedan od gradova je zbog nedostatka turista uveo da turisti pri ulasku ne plaćaju taksu, već da dobiju beneficiju u vidu novca. Ukratko prokomentarisati kako ova modifikacija utiče na predloženi algoritam pod a). Da li bi se u tom slučaju koristio isti algoritam ili bi bio pogodniji neki drugi (ako da, koji)?

Rešenje

CALC EXPENSES(N, G, taxes, X)

3. zadatak

Postavka

Slika iz trećeg zadatka.

Uparivanje neusmerenog netežinskog grafa.

1. Predložiti i ukratko opisati način na koji se vrši pronalaženje maksimalnog uparenog skupa grafa.
2. Za graf sa slike prikazati pronalaženje maksimalnog uparenog skupa po koracima.

4. zadatak

Postavka

Obilazak po dubini

1. Definisati stablo obilaska.
2. Definisati početno i završno vreme prilikom obilaska grafa po dubini. Koja je njegova uloga?
3. Napisati u pseudokodu implementaciju funkcije koja na osnovu zapisanih početnih i završnih vremena obilaska svakog čvora obilaskom po dubini određuje da li se čvor X nalazi u podstablu čvora Y u stablu obilaska.

IS SUCCESSOR(start_time, finish_time, x, y)