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

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

2024-09-13T00:09:05Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 67:		Ред 67:
	#* <code>ADD G, F, H</code>		#* <code>ADD G, F, H</code>
	</div>		</div>
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	TOP SORT ALL PATHS R(G)		TOP SORT ALL PATHS R(G)
	if V = {} then		if V = {} then
Ред 86:		Ред 86:
	end_for		end_for
	return return_paths		return return_paths
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==
Ред 94:		Ред 94:
	=== Rešenje ===		=== Rešenje ===
	Implementacija ispod čvorove vraća u ulančanoj listi.		Implementacija ispod čvorove vraća u ulančanoj listi.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	K-DISTANCE(G, n, k, id)		K-DISTANCE(G, n, k, id)
	dist[n]		dist[n]
Ред 130:		Ред 130:

	return tail		return tail
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	GETNODE(node)		GETNODE(node)
	ALLOCATE(node)		ALLOCATE(node)
Ред 137:		Ред 137:
	value(node) = value		value(node) = value
	return node		return node
	</~~syntaxhighlight~~>		</nowiki>}}

	== 5. zadatak ==		== 5. zadatak ==
Ред 183:		Ред 183:
	# U pseudokodu ispod podrazumeva se da je put predstavljen ulančanom listom. Ukoliko je vraćeno nil to znači da nema puta.		# U pseudokodu ispod podrazumeva se da je put predstavljen ulančanom listom. Ukoliko je vraćeno nil to znači da nema puta.
	</div>		</div>
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	PATH(T, A, B, C)		PATH(T, A, B, C)
	curr = GETNODE(C)		curr = GETNODE(C)
Ред 205:		Ред 205:

	return curr		return curr
	</~~syntaxhighlight~~>		</nowiki>}}

	== 6. zadatak ==		== 6. zadatak ==
Ред 302:		Ред 302:
	=== Rešenje ===		=== Rešenje ===
	Složenost Dajkstrinog algoritma zavisi od operacija pronalaženja sledećeg čvora do kojeg je put najkraći i ažuriranja matrice D sa dodavanjem novog čvora u skup S. Može biti <math>\mathcal{O(n^2)}</math> u slučaju da se pronalaženje sledećeg čvora do kojeg je put najkraći izvršava u <math>\mathcal{O(n)}</math> i da je graf predstavljen matricom susednosti. Bolja složenost dostiže se onda kada je graf predstavljen listom susednosti i operacija pronalaženja sledećeg čvora sa najkraćim putem ima složenost od <math>\mathcal{O(\log{n})}</math>, kada je složenost <math>\mathcal{O(e + n\log{n})}</math>.		Složenost Dajkstrinog algoritma zavisi od operacija pronalaženja sledećeg čvora do kojeg je put najkraći i ažuriranja matrice D sa dodavanjem novog čvora u skup S. Može biti <math>\mathcal{O(n^2)}</math> u slučaju da se pronalaženje sledećeg čvora do kojeg je put najkraći izvršava u <math>\mathcal{O(n)}</math> i da je graf predstavljen matricom susednosti. Bolja složenost dostiže se onda kada je graf predstavljen listom susednosti i operacija pronalaženja sledećeg čvora sa najkraćim putem ima složenost od <math>\mathcal{O(\log{n})}</math>, kada je složenost <math>\mathcal{O(e + n\log{n})}</math>.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	DIJKSTRA ADJ LIST(G, x, y)		DIJKSTRA ADJ LIST(G, x, y)
	S = {x}		S = {x}
Ред 332:		Ред 332:

	return d[y]		return d[y]
	</~~syntaxhighlight~~>		</nowiki>}}

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

KockaAdmiralac: PNG u SVG

2022-02-13T21:18:02Z

PNG u SVG

← Старија измена		Верзија на датум 13. фебруар 2022. у 23:18
Ред 34:		Ред 34:
	Grafovi se nalaze ispod.		Grafovi se nalaze ispod.
	<gallery>		<gallery>
	ASP1 K3 2019 zadatak 2 graf.~~png~~ \| Pojednostavljen graf iz postavke zadatka.		ASP1 K3 2019 zadatak 2 graf.svg \| Pojednostavljen graf iz postavke zadatka.
	ASP1 K3 2019 zadatak 2 MST.~~png~~ \| Minimalno obuhvatno stablo.		ASP1 K3 2019 zadatak 2 MST.svg \| Minimalno obuhvatno stablo.
	</gallery>		</gallery>

Ред 178:		Ред 178:

	=== Rešenje ===		=== Rešenje ===
	[[{{ns:6}}:ASP1 K3 2019 zadatak 5 graf.~~png~~\|thumb\|Graf iz zadatka 5.]]		[[{{ns:6}}:ASP1 K3 2019 zadatak 5 graf.svg\|thumb\|Graf iz zadatka 5.]]
	<div class="abc-list">		<div class="abc-list">
	# Pretpostavljajući da nema grana negativne težine vidimo da je najkraći put dužine 2 i zato sigurno mora biti direktna grana između A i B. Pošto vidimo da matrica D nije simetrična pretpostavljamo da se radi o usmerenom težinskom grafu. Na osnovu trenutnog grafa i D matrice vidimo da je grana B-C težine 5, i sve ostalo se slaže.		# Pretpostavljajući da nema grana negativne težine vidimo da je najkraći put dužine 2 i zato sigurno mora biti direktna grana između A i B. Pošto vidimo da matrica D nije simetrična pretpostavljamo da se radi o usmerenom težinskom grafu. Na osnovu trenutnog grafa i D matrice vidimo da je grana B-C težine 5, i sve ostalo se slaže.
Ред 288:		Ред 288:
	Grafovi su dati ispod.		Grafovi su dati ispod.
	<gallery>		<gallery>
	ASP1 K3 2019 zadatak 7 graf.~~png~~ \| Graf iz postavke zadatka.		ASP1 K3 2019 zadatak 7 graf.svg \| Graf iz postavke zadatka.
	ASP1 K3 2019 zadatak 7 rezidualni graf.~~png~~ \| Rezidualni graf.		ASP1 K3 2019 zadatak 7 rezidualni graf.svg \| Rezidualni graf.
	</gallery>		</gallery>

KockaAdmiralac: Čišćenje keša za pogrešno istaknute blokove koda

2020-08-28T00:54:16Z

Čišćenje keša za pogrešno istaknute blokove koda

← Старија измена		Верзија на датум 28. август 2020. у 02:54
Ред 128:		Ред 128:
	FREENODE(temp)		FREENODE(temp)
	end_while		end_while

	return tail		return tail
	</syntaxhighlight>		</syntaxhighlight>
Ред 202:		Ред 203:
	curr = next		curr = next
	end_while		end_while

	return curr		return curr
	</syntaxhighlight>		</syntaxhighlight>
Ред 328:		Ред 330:
	end_while		end_while
	end_for		end_for

	return d[y]		return d[y]
	</syntaxhighlight>		</syntaxhighlight>

KockaAdmiralac: Prebacivanje na jednostavno isticanje sintakse

2020-08-28T00:39:12Z

Prebacivanje na jednostavno isticanje sintakse

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

KockaAdmiralac: Kategorizacija

2020-07-27T09:59:57Z

Kategorizacija

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

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

KockaAdmiralac: Nema potrebe da ovde držimo dva ista grafa

2020-07-27T00:38:10Z

Nema potrebe da ovde držimo dva ista grafa

← Старија измена		Верзија на датум 27. јул 2020. у 02:38
Ред 34:		Ред 34:
	Grafovi se nalaze ispod.		Grafovi se nalaze ispod.
	<gallery>		<gallery>
	~~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 graf.png \| Pojednostavljen graf iz postavke zadatka.
	ASP1 K3 2019 zadatak 2 MST.png \| Minimalno obuhvatno stablo.		ASP1 K3 2019 zadatak 2 MST.png \| Minimalno obuhvatno stablo.

KockaAdmiralac: Dopunjen osmi zadatak

2020-06-10T17:19:55Z

Dopunjen osmi zadatak

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

Ред 292:		Ред 293:

	=== Rešenje ===		=== Rešenje ===
	Složenost Dajkstrinog algoritma ~~može~~ biti <math>\mathcal{O(n^2)}</math> u slučaju da se pronalaženje sledećeg čvora ~~sa najkraćim putem~~ izvršava u <math>\mathcal{O(n)}</math> i da je graf predstavljen matricom susednosti. Bolja složenost dostiže se onda kada je graf predstavljen listom susednosti i operacija pronalaženja sledećeg čvora sa najkraćim putem ima složenost od <math>\mathcal{O(\log{n})}</math>, kada je složenost <math>\mathcal{O(e + n\log{n})}</math>.		Složenost Dajkstrinog algoritma zavisi od operacija pronalaženja sledećeg čvora do kojeg je put najkraći i ažuriranja matrice D sa dodavanjem novog čvora u skup S. Može biti <math>\mathcal{O(n^2)}</math> u slučaju da se pronalaženje sledećeg čvora do kojeg je put najkraći izvršava u <math>\mathcal{O(n)}</math> i da je graf predstavljen matricom susednosti. Bolja složenost dostiže se onda kada je graf predstavljen listom susednosti i operacija pronalaženja sledećeg čvora sa najkraćim putem ima složenost od <math>\mathcal{O(\log{n})}</math>, kada je složenost <math>\mathcal{O(e + n\log{n})}</math>.
	<u>DIJKSTRA ADJ LIST(''G'', ''x'', ''y'')</u>		<u>DIJKSTRA ADJ LIST(''G'', ''x'', ''y'')</u>
	''S'' = {''x''}		''S'' = {''x''}
Ред 311:		Ред 312:
	'''end_for'''		'''end_for'''
	''S'' = ''S'' + {''start_node''}		''S'' = ''S'' + {''start_node''}
	''adj_node'' = ''e''[''start_node'']		''adj_node'' = ''AL''[''start_node'']
	'''while''' ''adj_node'' ≠ nil '''do'''		'''while''' ''adj_node'' ≠ nil '''do'''
	'''if''' ''w''[''start_node'', ''value''(''adj_node'')] + ''d''[''start_node''] < ''d''[''value''(''adj_node'')] '''then'''		'''if''' ''w''[''start_node'', ''value''(''adj_node'')] + ''d''[''start_node''] < ''d''[''value''(''adj_node'')] '''then'''

KockaAdmiralac: Zapravo ovo je potpuno imalo smisla

2020-06-08T19:25:14Z

Zapravo ovo je potpuno imalo smisla

← Старија измена		Верзија на датум 8. јун 2020. у 21:25
Ред 94:		Ред 94:
	<u>K-DISTANCE(''G'', ''n'', ''k'', ''id'')</u>		<u>K-DISTANCE(''G'', ''n'', ''k'', ''id'')</u>
	''dist''[''n'']		''dist''[''n'']
	'''for''' ''i'' = 0 '''to''' ''n'' '''do'''		'''for''' ''i'' = 1 '''to''' ''n'' '''do'''
	''dist''[''i''] = ∞		''dist''[''i''] = ∞
	'''end_for'''		'''end_for'''
Ред 100:		Ред 100:
	''curr_dist'' = 0		''curr_dist'' = 0
	''tail'' = ''head'' = GETNODE(''id'')		''tail'' = ''head'' = GETNODE(''id'')
	''next''(''head'') = GETNODE(~~nil~~)		''next''(''head'') = GETNODE(0)
	''head'' = ''next''(''head'')		''head'' = ''next''(''head'')
	''curr'' = 0		''curr'' = 0
Ред 106:		Ред 106:
	'''while''' (''tail'' ≠ nil) and (''curr_dist'' ≠ k) '''do'''		'''while''' (''tail'' ≠ nil) and (''curr_dist'' ≠ k) '''do'''
	''curr'' = ''value''(''tail'')		''curr'' = ''value''(''tail'')
	'''if''' ''curr'' = ~~nil~~ '''then'''		'''if''' ''curr'' = 0 '''then'''
	''curr_dist'' = ''curr_dist'' + 1		''curr_dist'' = ''curr_dist'' + 1
	'''if''' ''head'' ≠ ''tail'' '''then'''		'''if''' ''head'' ≠ ''tail'' '''then'''
	''next''(''head'') = GETNODE(~~nil~~)		''next''(''head'') = GETNODE(0)
	''head'' = ''next''(''head'')		''head'' = ''next''(''head'')
	'''end_if'''		'''end_if'''
	'''else'''		'''else'''
	'''for''' ''node'' ∈ {''v'' : ~~(''id''~~(''curr''), ''v'') ∈ ''E''} '''do'''		'''for''' ''node'' ∈ {''v'' : (''curr'', ''v'') ∈ ''E''} '''do'''
	''if'' ''dist''[''node''] ≠ ''curr_dist'' + 1 '''then'''		''if'' ''dist''[''node''] ≠ ''curr_dist'' + 1 '''then'''
	''dist''[''node''] = ''curr_dist'' + 1		''dist''[''node''] = ''curr_dist'' + 1

KockaAdmiralac: De-apstrakcija find min dela Dajkstrinog algoritma, smislen raspored indeksa prilikom ažuriranja D i T

2020-06-08T18:22:15Z

De-apstrakcija find min dela Dajkstrinog algoritma, smislen raspored indeksa prilikom ažuriranja D i T

← Старија измена		Верзија на датум 8. јун 2020. у 20:22
Ред 303:		Ред 303:
	'''end_if'''		'''end_if'''
	'''end_for'''		'''end_for'''
	'''for''' ''k'' = 1 '''to''' n-1 '''do'''		'''for''' ''k'' = 1 '''to''' ''n''-1 '''do'''
	~~find min {~~''d''[''i''~~] :~~ ''i'' ∈ (''V'' - ''S'')}		''start_node'' = -1
	~~''S'' = ''S'' + {i}~~		'''for''' ''i'' ∈ (''V'' - ''S'') '''do'''
	~~''j'' = ''e''[''i'']~~		'''if''' (''start_node'' = -1) or (''d''[''i''] < ''d''[''start_node'']) '''then'''
	~~'''while''' ''j'' ≠ nil~~ '''do'''		''start_node'' = ''i''
	'''if'~~'' ''w''[''value~~''(''j'')~~, ''i''] +~~ ''d''[''~~value''(~~''~~j'')~~] < ''d''[''i''] '''then'''
	''d''~~[''i'']~~ = ~~''w''[''value''(''j''), ''i''] + ''d''[''value''(''j'')]~~
	~~''t''[~~''i''~~] = ''value''(''j'')~~
	'''end_if'''		'''end_if'''
	''j'' = ''next''(''j'')		'''end_for'''
			''S'' = ''S'' + {''start_node''}
			''adj_node'' = ''e''[''start_node'']
			'''while''' ''adj_node'' ≠ nil '''do'''
			'''if''' ''w''[''start_node'', ''value''(''adj_node'')] + ''d''[''start_node''] < ''d''[''value''(''adj_node'')] '''then'''
			''d''[''value''(''adj_node'')] = ''w''[''start_node'', ''value''(''adj_node'')] + ''d''[''start_node'']
			''t''[''value''(''adj_node'')] = ''start_node''
			'''end_if'''
			''adj_node'' = ''next''(''adj_node'')
	'''end_while'''		'''end_while'''
	'''end_for'''		'''end_for'''

KockaAdmiralac: Ispravka kritičnog puta

2020-06-08T17:26:49Z

Ispravka kritičnog puta

← Старија измена		Верзија на датум 8. јун 2020. у 19:26
Ред 205:		Ред 205:
	=== Rešenje ===		=== Rešenje ===
	* Topološki poredak: '''ABDCFEHGIJK'''		* Topološki poredak: '''ABDCFEHGIJK'''
	* Kritični put: '''~~ABCEGJK~~''' (ili '''~~ABCEGIJK~~''')		* Kritični put: '''ABCEHGJK''' (ili '''ABCEHGIJK''')
	* Tabela:		* Tabela:
	{\| class="wikitable"		{\| class="wikitable"