АСП1/К3 2017 — разлика између измена
м (Sve osim šestog i osmog zadatka) |
м (Замена начина истицања милокода.) |
||
(Није приказано 6 међуизмена другог корисника) | |||
Ред 17: | Ред 17: | ||
# <strike>A-E (25)</strike> - svi čvorovi su nam već u stablu | # <strike>A-E (25)</strike> - svi čvorovi su nam već u stablu | ||
# <strike>M-E (30)</strike> - svi čvorovi su nam već u stablu | # <strike>M-E (30)</strike> - svi čvorovi su nam već u stablu | ||
<gallery> | <gallery class="transparent-svg"> | ||
ASP1 K3 2017 zadatak 1 graf. | ASP1 K3 2017 zadatak 1 graf.svg | Graf iz postavke zadatka. | ||
ASP1 K3 2017 zadatak 1 MST. | ASP1 K3 2017 zadatak 1 MST.svg | Minimalno obuhvatno stablo za graf iz postavke zadatka. | ||
</gallery> | </gallery> | ||
Ред 27: | Ред 27: | ||
=== Rešenje === | === Rešenje === | ||
{{Милокод|<nowiki> | |||
TOPSORT(G, n) | |||
p = nil | |||
for i = 1 to n do | |||
in[i] = 0 | |||
end_for | |||
for i = 1 to n do | |||
p = first(e[i]) | |||
while p ≠ nil do | |||
in[value(p)] = in[value(p)] + 1 | |||
p = next(p) | |||
end_while | |||
end_for | |||
tail = head = nil | |||
for i = 1 to n do | |||
if in[i] = 0 then | |||
if tail = nil then | |||
tail = head = GETNODE | |||
value(tail) = i | |||
else | |||
PRIORITY_QUEUE_INSERT(tail, head, E, i) | |||
end_if | |||
end_if | |||
end_for | |||
i = 1 | |||
while tail ≠ nil do | |||
ret[i] = value(tail) | |||
p = first(e[i]) | |||
while p ≠ nil do | |||
in[value(p)] = in[value(p)] - 1 | |||
if in[value(p)] = 0 then | |||
PRIORITY_QUEUE_INSERT(tail, head, E, value(p)) | |||
end_if | |||
p = next(p) | |||
end_while | |||
i = i + 1 | |||
p = tail | |||
tail = next(tail) | |||
FREENODE(p) | |||
end_while | |||
return ret | |||
</nowiki>}} | |||
{{Милокод|<nowiki> | |||
PRIORITY QUEUE INSERT(tail, head, E, value) | |||
p = tail | |||
found = false | |||
t = nil | |||
if num(e[value]) > num(e[value(p)]) then | |||
tail = GETNODE | |||
value(tail) = value | |||
next(tail) = p | |||
else | |||
while next(p) ≠ nil do | |||
if num(e[value]) > num(e[value(next(p))]) then | |||
t = next(p) | |||
next(p) = GETNODE | |||
value(next(p)) = value | |||
next(next(p)) = t | |||
found = true | |||
break | |||
end_if | |||
p = next(p) | |||
end_while | |||
if not found then | |||
next(head) = GETNODE | |||
value(next(head)) = value | |||
head = next(head) | |||
end_if | |||
end_if | |||
</nowiki>}} | |||
== 3. zadatak == | == 3. zadatak == | ||
Ред 105: | Ред 108: | ||
=== Rešenje === | === Rešenje === | ||
Ovaj sistem možemo modelovati neusmerenim težinskim grafom u kojem su posao, kuća i raskrsnice čvorovi, ulice između njih su grane a težina tih grana je broj ljudskih bića sa kojima će Perica nažalost morati da se sukobi u njegovoj najneomiljenijoj disciplini: prijateljskom razgovoru. | Ovaj sistem možemo modelovati neusmerenim težinskim grafom u kojem su posao, kuća i raskrsnice čvorovi, ulice između njih su grane a težina tih grana je broj ljudskih bića sa kojima će Perica nažalost morati da se sukobi u njegovoj najneomiljenijoj disciplini: prijateljskom razgovoru. | ||
{{Милокод|<nowiki> | |||
GET PERICA HOME(G, work, home) | |||
S = {home} | |||
p = nil | |||
curr = 0 | |||
for i = 1 to n do | |||
d[i] = w(home, i) | |||
if d[i] = ∞ then | |||
t[i] = 0 | |||
else | |||
t[i] = home | |||
end_if | |||
end_for | |||
for k = 1 to n-1 do | |||
find min {d[i] : i ∈ (V - S)} | |||
p = e[i] | |||
while p ≠ nil do | |||
if d[i] + w(i, value(p)) < d[value(p)] then | |||
d[value(p)] = d[i] + w(i, value(p)) | |||
t[value(p)] = i | |||
end_if | |||
p = next(p) | |||
end_while | |||
S = S + {i} | |||
end_for | |||
curr = t[work] | |||
while curr ≠ home then | |||
GO(curr) | |||
curr = t[curr] | |||
end_while | |||
GO(home) | |||
</nowiki>}} | |||
== 4. zadatak == | == 4. zadatak == | ||
=== Postavka === | === Postavka === | ||
[[{{ns:6}}:ASP1 K3 2017 zadatak 4 graf. | [[{{ns:6}}:ASP1 K3 2017 zadatak 4 graf.svg|thumb|Graf iz postavke zadatka.]] | ||
Za graf sa slike naći kritični put i dozvoljena kašnjenja za pojedinačne čvorove. Kritični put označiti i na samom grafu. | Za graf sa slike naći kritični put i dozvoljena kašnjenja za pojedinačne čvorove. Kritični put označiti i na samom grafu. | ||
Ред 210: | Ред 215: | ||
=== Rešenje === | === Rešenje === | ||
Ovaj problem se može modelovati bipartitnim grafom gde čvorovi jednog dela označavaju fudbalere, čvorovi drugog pozicije na kojima oni mogu igrati, grane između fudbalera i pozicije označavaju da taj fudbaler može igrati na toj poziciji a težina te grane njegova ocena. Uparivanje se vrši brute-force metodom, tako što se isprobaju sva moguća uparivanja fudbalera i pozicija gde su sve pozicije zauzete i izabere ono gde je zbir težina grana najveći. | |||
== 6. zadatak == | == 6. zadatak == | ||
{{delimično rešeno}} | |||
=== Postavka === | === Postavka === | ||
Neka se posmatra netežinski usmereni graf ''G'' sa ''n'' čvorova. Za posmatrani graf su korišćenjem DFS algoritma određena početna i završna vremena svih čvorova i smeštena u nizovima F i L dužine ''n''. Napisati u pseudokodu funkciju koja pronalazi najveću jako povezanu komponentu po broju čvorova. Smatrati da je graf predstavljen pomoću matrice susednosti. | Neka se posmatra netežinski usmereni graf ''G'' sa ''n'' čvorova. Za posmatrani graf su korišćenjem DFS algoritma određena početna i završna vremena svih čvorova i smeštena u nizovima F i L dužine ''n''. Napisati u pseudokodu funkciju koja pronalazi najveću jako povezanu komponentu po broju čvorova. Smatrati da je graf predstavljen pomoću matrice susednosti. | ||
=== Rešenje === | === Rešenje === | ||
{{Милокод|<nowiki> | |||
MAX STRONG CC(G, n) | |||
</nowiki>}} | |||
== 7. zadatak == | == 7. zadatak == | ||
Ред 229: | Ред 237: | ||
=== Rešenje === | === Rešenje === | ||
Rezidualni graf najmanje može imati <math>n-1</math> grana u slučaju da su svi protoci puni ili prazni i ima tačno onoliko grana koliko je potrebno da bi graf bio povezan, ili <math>n(n-1)</math> grana u slučaju da nijedan protok nije pun ili prazan i svaki čvor je povezan sa svakim. | Rezidualni graf najmanje može imati <math>n-1</math> grana u slučaju da su svi protoci puni ili prazni i ima tačno onoliko grana koliko je potrebno da bi graf bio povezan, ili <math>n(n-1)</math> grana u slučaju da nijedan protok nije pun ili prazan i svaki čvor je povezan sa svakim. | ||
{{Милокод|<nowiki> | |||
FLOW CAP(F, R) | |||
num_total = 0 | |||
for x = 1 to n do | |||
for y = 1 to n do | |||
if (F[x, y] > 0) or ((F[x, y] = 0) and (F[y, x] = 0) and (R[x, y] > 0)) then | |||
num_total = num_total + 1 | |||
end_if | |||
if F[x, y] = 0 then | |||
if R[x, y] ≠ 0 then | |||
C[x, y] = R[x, y] | |||
end_if | |||
else | |||
C[x, y] = F[x, y] + R[x, y] | |||
end_if | |||
end_for | |||
end_for | |||
return num_total | |||
</nowiki>}} | |||
== 8. zadatak == | == 8. zadatak == | ||
{{delimično rešeno}} | |||
=== Postavka === | === Postavka === | ||
Potrebno je utvrditi da li je dati povezani neusmereni graf cikličan na što efikasniji način. | Potrebno je utvrditi da li je dati povezani neusmereni graf cikličan na što efikasniji način. | ||
Ред 256: | Ред 267: | ||
=== Rešenje === | === Rešenje === | ||
{{Милокод|<nowiki> | |||
IS CYCLIC(G) | |||
</nowiki>}} | |||
[[Категорија:Рокови]] | [[Категорија:Рокови]] | ||
[[Категорија:АСП1]] |
Тренутна верзија на датум 13. септембар 2024. у 02:09
1. zadatak
Postavka
Na slici je dat težinski neusmereni graf. Formirati minimalno obuhvatno stablo korišćenjem Kruskalovog algoritma. Prikazati postupak izbora grana i finalno stablo.
Rešenje
Kada uredimo grane po težini dobijamo redosled po kojem možemo da ih biramo za ubacivanje u graf.
- B-D (2)
- C-E (5)
- A-C (8)
- C-D (10)
A-B (12)- A i B su već povezani preko A-C, C-D i B-DD-E (13)- D i E su već povezani preko C-D i C-E- B-M (15)
A-E (25)- svi čvorovi su nam već u stabluM-E (30)- svi čvorovi su nam već u stablu
2. zadatak
Postavka
Napisati u pseudokodu iterativnu implementaciju funkcije za topološko sortiranje usmerenog netežinskog grafa. Ukoliko u nekom trenutku više čvorova može biti kandidat za istu poziciju u finalnom redosledu, bira se čvor sa najviše neposećenih suseda. Graf se predstavlja pomoću liste susednosti u čijem se zaglavlju za svaki čvor, pored pokazivača na odgovorajuću listu suseda, nalazi i broj suseda. Funkcija treba da vrati niz čvorova u topološkom poretku.
Rešenje
TOPSORT(G, n) p = nil for i = 1 to n do in[i] = 0 end_for for i = 1 to n do p = first(e[i]) while p ≠ nil do in[value(p)] = in[value(p)] + 1 p = next(p) end_while end_for tail = head = nil for i = 1 to n do if in[i] = 0 then if tail = nil then tail = head = GETNODE value(tail) = i else PRIORITY_QUEUE_INSERT(tail, head, E, i) end_if end_if end_for i = 1 while tail ≠ nil do ret[i] = value(tail) p = first(e[i]) while p ≠ nil do in[value(p)] = in[value(p)] - 1 if in[value(p)] = 0 then PRIORITY_QUEUE_INSERT(tail, head, E, value(p)) end_if p = next(p) end_while i = i + 1 p = tail tail = next(tail) FREENODE(p) end_while return ret PRIORITY QUEUE INSERT(tail, head, E, value) p = tail found = false t = nil if num(e[value]) > num(e[value(p)]) then tail = GETNODE value(tail) = value next(tail) = p else while next(p) ≠ nil do if num(e[value]) > num(e[value(next(p))]) then t = next(p) next(p) = GETNODE value(next(p)) = value next(next(p)) = t found = true break end_if p = next(p) end_while if not found then next(head) = GETNODE value(next(head)) = value head = next(head) end_if end_if
3. zadatak
Postavka
Perica je vodoinstalater. Završio je posao za danas i vraća se kući, gde ga žena čeka za ručkom. Na putu do svoje kuće prolazi pored kuća svojih prijatelja i zna da će ga svaki od njih zaustaviti da popriča sa njim (malo mesto, svi se znaju, a i naš Perica je dobar vodoinstalater). Perica je gladan i nije danas mnogo raspoložen za priču, pa želi da stigne kući i pritom popriča sa što manjim brojem ljudi. Put do kuće sadrži određeni broj raskrsnica koje spajaju ulice sa određenim brojem kuća.
- Objasniti na koji način se izloženi problem može modelovati putem grafa.
- Napisati u pseudokodu funkciju koja navodi Pericu od posla do kuće tako da na putu popriča sa što je moguće manjim brojem ljudi.
Rešenje
Ovaj sistem možemo modelovati neusmerenim težinskim grafom u kojem su posao, kuća i raskrsnice čvorovi, ulice između njih su grane a težina tih grana je broj ljudskih bića sa kojima će Perica nažalost morati da se sukobi u njegovoj najneomiljenijoj disciplini: prijateljskom razgovoru.
GET PERICA HOME(G, work, home) S = {home} p = nil curr = 0 for i = 1 to n do d[i] = w(home, i) if d[i] = ∞ then t[i] = 0 else t[i] = home end_if end_for for k = 1 to n-1 do find min {d[i] : i ∈ (V - S)} p = e[i] while p ≠ nil do if d[i] + w(i, value(p)) < d[value(p)] then d[value(p)] = d[i] + w(i, value(p)) t[value(p)] = i end_if p = next(p) end_while S = S + {i} end_for curr = t[work] while curr ≠ home then GO(curr) curr = t[curr] end_while GO(home)
4. zadatak
Postavka
Za graf sa slike naći kritični put i dozvoljena kašnjenja za pojedinačne čvorove. Kritični put označiti i na samom grafu.
Rešenje
Kritičan put: ACGSRT
Čvor | EST | LST | L |
---|---|---|---|
A | 0 | 0 | 0 |
C | 11 | 11 | 0 |
E | 13 | 25 | 12 |
F | 26 | 31 | 5 |
G | 18 | 18 | 0 |
H | 10 | 13 | 3 |
K | 32 | 36 | 4 |
N | 35 | 39 | 4 |
R | 40 | 40 | 0 |
S | 38 | 38 | 0 |
T | 43 | 43 | 0 |
5. zadatak
Postavka
Neka se posmatra jedan fudbalski tim sa 25 članova koji konkurišu za 11 pozicija u timu. Svaki igrač ima definisan skup pozicija na kojima može da igra, a za svaku poziciju mu se dodeljuje odgovarajuća ocena. Dati predlog na koji način se dati problem može modelovati grafom i izvršiti selekcija prve postave, tako da se izabere postava od 11 igrača koji imaju najbolje ocene. Smatrati da je svaka pozicija u timu pokrivena najmanje jednim igračem.
Rešenje
Ovaj problem se može modelovati bipartitnim grafom gde čvorovi jednog dela označavaju fudbalere, čvorovi drugog pozicije na kojima oni mogu igrati, grane između fudbalera i pozicije označavaju da taj fudbaler može igrati na toj poziciji a težina te grane njegova ocena. Uparivanje se vrši brute-force metodom, tako što se isprobaju sva moguća uparivanja fudbalera i pozicija gde su sve pozicije zauzete i izabere ono gde je zbir težina grana najveći.
6. zadatak
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Postavka
Neka se posmatra netežinski usmereni graf G sa n čvorova. Za posmatrani graf su korišćenjem DFS algoritma određena početna i završna vremena svih čvorova i smeštena u nizovima F i L dužine n. Napisati u pseudokodu funkciju koja pronalazi najveću jako povezanu komponentu po broju čvorova. Smatrati da je graf predstavljen pomoću matrice susednosti.
Rešenje
MAX STRONG CC(G, n)
7. zadatak
Postavka
Neka je dato neko stanje protočnog grafa preko matrice trenutnih protoka F kao i odgovarajuće stanje rezidualnog grafa preko matrice R.
- Napisati funkciju koja određuje matricu kapaciteta i izračunava broj grana polaznog protočnog grafa.
- U odnosu na broj grana početnog protočnog grafa, odrediti koliko najmanje i koliko najviše grana može imati rezidulani graf.
Rešenje
Rezidualni graf najmanje može imati grana u slučaju da su svi protoci puni ili prazni i ima tačno onoliko grana koliko je potrebno da bi graf bio povezan, ili grana u slučaju da nijedan protok nije pun ili prazan i svaki čvor je povezan sa svakim.
FLOW CAP(F, R) num_total = 0 for x = 1 to n do for y = 1 to n do if (F[x, y] > 0) or ((F[x, y] = 0) and (F[y, x] = 0) and (R[x, y] > 0)) then num_total = num_total + 1 end_if if F[x, y] = 0 then if R[x, y] ≠ 0 then C[x, y] = R[x, y] end_if else C[x, y] = F[x, y] + R[x, y] end_if end_for end_for return num_total
8. zadatak
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Postavka
Potrebno je utvrditi da li je dati povezani neusmereni graf cikličan na što efikasniji način.
- Objasniti postupak i dati vremensku složenost.
- Na osnovu predloženog postupka napisati pseudokod.
Rešenje
IS CYCLIC(G)