АСП1/К3 2017 - Историја измена

KockaBot: Замена начина истицања милокода.

2024-09-13T00:09:03Z

Замена начина истицања милокода.

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 27:		Ред 27:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	TOPSORT(G, n)		TOPSORT(G, n)
	p = nil		p = nil
Ред 68:		Ред 68:
	end_while		end_while
	return ret		return ret
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	PRIORITY QUEUE INSERT(tail, head, E, value)		PRIORITY QUEUE INSERT(tail, head, E, value)
	p = tail		p = tail
Ред 96:		Ред 96:
	end_if		end_if
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

	== 3. zadatak ==		== 3. zadatak ==
Ред 108:		Ред 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.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	GET PERICA HOME(G, work, home)		GET PERICA HOME(G, work, home)
	S = {home}		S = {home}
Ред 139:		Ред 139:
	end_while		end_while
	GO(home)		GO(home)
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==
Ред 223:		Ред 223:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	MAX STRONG CC(G, n)		MAX STRONG CC(G, n)
	</~~syntaxhighlight~~>		</nowiki>}}

	== 7. zadatak ==		== 7. zadatak ==
Ред 237:		Ред 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.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FLOW CAP(F, R)		FLOW CAP(F, R)
	num_total = 0		num_total = 0
Ред 255:		Ред 255:
	end_for		end_for
	return num_total		return num_total
	</~~syntaxhighlight~~>		</nowiki>}}

	== 8. zadatak ==		== 8. zadatak ==
Ред 267:		Ред 267:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	IS CYCLIC(G)		IS CYCLIC(G)
	</~~syntaxhighlight~~>		</nowiki>}}

	[[Категорија:Рокови]]		[[Категорија:Рокови]]
	[[Категорија:АСП1]]		[[Категорија:АСП1]]

KockaAdmiralac: PNG u SVG

2022-02-13T21:11:10Z

PNG u SVG

← Старија измена		Верзија на датум 13. фебруар 2022. у 23:11
Ред 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.~~png~~ \| Graf iz postavke zadatka.		ASP1 K3 2017 zadatak 1 graf.svg \| Graf iz postavke zadatka.
	ASP1 K3 2017 zadatak 1 MST.~~png~~ \| Minimalno obuhvatno stablo za graf iz postavke zadatka.		ASP1 K3 2017 zadatak 1 MST.svg \| Minimalno obuhvatno stablo za graf iz postavke zadatka.
	</gallery>		</gallery>

Ред 143:		Ред 143:
	== 4. zadatak ==		== 4. zadatak ==
	=== Postavka ===		=== Postavka ===
	[[{{ns:6}}:ASP1 K3 2017 zadatak 4 graf.~~png~~\|thumb\|Graf iz postavke zadatka.]]		[[{{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.

KockaAdmiralac: Delimično rešen rok

2021-06-27T17:58:10Z

Delimično rešen rok

← Старија измена		Верзија на датум 27. јун 2021. у 19:58
Ред 218:		Ред 218:

	== 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.
Ред 257:		Ред 258:

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

KockaAdmiralac: Prebacivanje na jednostavno isticanje sintakse

2020-08-28T09:41:10Z

Prebacivanje na jednostavno isticanje sintakse

Прикажи измене

KockaAdmiralac: Kategorizacija

2020-07-27T09:59:36Z

Kategorizacija

← Старија измена		Верзија на датум 27. јул 2020. у 11:59
Ред 259:		Ред 259:

	[[Категорија:Рокови]]		[[Категорија:Рокови]]
			[[Категорија:АСП1]]

KockaAdmiralac: Ispravka rešenja

2020-07-10T01:33:09Z

Ispravka rešenja

← Старија измена		Верзија на датум 10. јул 2020. у 03:33
Ред 210:		Ред 210:

	=== Rešenje ===		=== Rešenje ===
	~~Predlažemo strukturu neusmerenog težinskog grafa u kojem~~ čvorovi ~~predstavljaju~~ pozicije i ~~igrače a grana između igrača~~ pozicije ~~označava~~ da taj ~~igrač~~ može ~~da igra tu poziciju (ocena je~~ težina grane). ~~Na početku odabira pozicije~~ se ~~čuvaju u opadajućem prioritetnom redu po broju suseda~~, ~~i onda~~ se ~~ide po tom redu~~ i ~~svakoj poziciji dodeljuje igrač koji je najsposobniji za tu poziciju, a zatim se izbacuju čvor~~ pozicije i ~~igrača iz grafa i ažurira broj suseda u prioritetnom redu. Taj proces se ponavlja dok ima čvorova u prioritetnom redu~~.		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 ==

KockaAdmiralac: Ispravka uslova za prebrojavanje grana u sedmom zadatku

2020-07-01T19:01:36Z

Ispravka uslova za prebrojavanje grana u sedmom zadatku

← Старија измена		Верзија на датум 1. јул 2020. у 21:01
Ред 233:		Ред 233:
	'''for''' ''x'' = 1 '''to''' ''n'' '''do'''		'''for''' ''x'' = 1 '''to''' ''n'' '''do'''
	'''for''' ''y'' = 1 '''to''' ''n'' '''do'''		'''for''' ''y'' = 1 '''to''' ''n'' '''do'''
	'''if''' (''x'' > ''y'') ~~and~~ ((''F''[''x'', ''y''] > 0) or (''R''[''x'', ''y''] > 0)) '''then'''		'''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		''num_total'' = ''num_total'' + 1
	'''end_if'''		'''end_if'''

KockaAdmiralac: Sve osim šestog i osmog zadatka

2020-04-11T12:31:34Z

Sve osim šestog i osmog zadatka

Прикажи измене

KockaAdmiralac: Sadržaj na desno

2020-04-09T08:24:13Z

Sadržaj na desno

← Старија измена		Верзија на датум 9. април 2020. у 10:24
Ред 1:		Ред 1:
			{{tocright}}
	[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S111ASP1_K3_1617.pdf Zadaci]		[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S111ASP1_K3_1617.pdf Zadaci]

KockaAdmiralac: Samo postavke za sad

2020-04-09T08:23:35Z

Samo postavke za sad

Нова страница

[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S111ASP1_K3_1617.pdf Zadaci]

== 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 ===
<gallery>
ASP1 K3 2017 zadatak 1 graf.png | Graf iz postavke zadatka.
ASP1 K3 2017 zadatak 1 MST.png | Minimalno obuhvatno stablo za graf iz postavke zadatka.
</gallery>

== 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 ===
<u>TOPSORT(''G'', ''n'')</u>

== 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.
<div class="abc-list">
# 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.
</div>

=== Rešenje ===
<u>GET PERICA HOME(''G'', ''work'', ''home'')</u>

== 4. zadatak ==
=== Postavka ===
[[{{ns:6}}:ASP1 K3 2017 zadatak 4 graf.png|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.

=== Rešenje ===
Kritičan put:
{| class="wikitable"
! Čvor
! EST
! LST
! L
|-
! A
|
|
|
|-
! C
|
|
|
|-
! E
|
|
|
|-
! F
|
|
|
|-
! G
|
|
|
|-
! H
|
|
|
|-
! K
|
|
|
|-
! N
|
|
|
|-
! R
|
|
|
|-
! S
|
|
|
|-
! T
|
|
|
|}

== 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 ===

== 6. zadatak ==
=== 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 ===
<u>MAX STRONG CC(''G'', ''n'')</u>

== 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''.
<div class="abc-list">
# 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.
</div>

=== Rešenje ===
<u>FLOW CAP(''F'', ''R'')</u>

== 8. zadatak ==
=== Postavka ===
Potrebno je utvrditi da li je dati povezani neusmereni graf cikličan na što efikasniji način.
<div class="abc-list">
# Objasniti postupak i dati vremensku složenost.
# Na osnovu predloženog postupka napisati pseudokod.
</div>

=== Rešenje ===
<u>IS CYCLIC(''G'')</u>

[[Категорија:Рокови]]