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

KockaAdmiralac: Hmmmmmmm

2024-09-13T00:16:16Z

Hmmmmmmm

← Старија измена		Верзија на датум 13. септембар 2024. у 02:16
Ред 166:		Ред 166:
	return num_max		return num_max
	</nowiki>}}		</nowiki>}}

	{{Милокод\|<nowiki>		{{Милокод\|<nowiki>
	IS EXTERNAL NODE(node)		IS EXTERNAL NODE(node)
Ред 174:		Ред 175:
	end_if		end_if
	</nowiki>}}		</nowiki>}}

	{{Милокод\|<nowiki>		{{Милокод\|<nowiki>
	GETNODE(value)		GETNODE(value)
Ред 181:		Ред 183:
	return node		return node
	</nowiki>}}		</nowiki>}}

	{{Милокод\|<nowiki>		{{Милокод\|<nowiki>
	FREENODE(node)		FREENODE(node)

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

2024-09-13T00:09:02Z

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

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

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	PREORDER M I(root, m)		PREORDER M I(root, m)
	if root = nil then		if root = nil then
Ред 39:		Ред 39:
	end_while		end_while
	return list		return list
	</~~syntaxhighlight~~>		</nowiki>}}

	Ovo rešenje se zasniva na čuvanju čvora i nivoa čvora u dva odvojena steka i korišćenju povezane liste (pošto ne znamo unapred količinu čvorova u stablu kako bismo alocirali niz). Za svaki čvor u steku dodajemo njegovu decu na jedan stek, s tim što ih dodajemo s desna na levo kako bi prvi posećeni čvor bio najlevlje (odnosno prvo) dete čvora (kao što je to i slučaj kod ''preorder'' obilaska), a njegov nivo uvećan za jedan na drugi stek.		Ovo rešenje se zasniva na čuvanju čvora i nivoa čvora u dva odvojena steka i korišćenju povezane liste (pošto ne znamo unapred količinu čvorova u stablu kako bismo alocirali niz). Za svaki čvor u steku dodajemo njegovu decu na jedan stek, s tim što ih dodajemo s desna na levo kako bi prvi posećeni čvor bio najlevlje (odnosno prvo) dete čvora (kao što je to i slučaj kod ''preorder'' obilaska), a njegov nivo uvećan za jedan na drugi stek.
Ред 132:		Ред 132:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FIND LONGEST CODES(root)		FIND LONGEST CODES(root)
	tail = head = GETNODE(root)		tail = head = GETNODE(root)
Ред 165:		Ред 165:
	end_while		end_while
	return num_max		return num_max
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	IS EXTERNAL NODE(node)		IS EXTERNAL NODE(node)
	if left(node) = nil and right(node) = nil then		if left(node) = nil and right(node) = nil then
Ред 173:		Ред 173:
	return false		return false
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	GETNODE(value)		GETNODE(value)
	ALLOCATE(node)		ALLOCATE(node)
Ред 180:		Ред 180:
	value(node) = value		value(node) = value
	return node		return node
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FREENODE(node)		FREENODE(node)
	DEALLOCATE(node)		DEALLOCATE(node)
	</~~syntaxhighlight~~>		</nowiki>}}

	== 6. zadatak ==		== 6. zadatak ==
Ред 202:		Ред 202:
	[[File:ASP1 K2 2018 zadatak 6 stablo.svg\|thumb\|Rešenje prvog dela zadatka.]]		[[File:ASP1 K2 2018 zadatak 6 stablo.svg\|thumb\|Rešenje prvog dela zadatka.]]
	Algoritam za obilazak povezanog stabla obrnutim ''inorder'' poretkom dat je ispod.		Algoritam za obilazak povezanog stabla obrnutim ''inorder'' poretkom dat je ispod.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	REVERSE INORDER T(root)		REVERSE INORDER T(root)
	node = root		node = root
Ред 219:		Ред 219:
	end_if		end_if
	end_while		end_while
	</~~syntaxhighlight~~>		</nowiki>}}

	== 7. zadatak ==		== 7. zadatak ==
Ред 254:		Ред 254:
	# U implementaciji ispod smatra se da optimizacije pomenute iznad nisu primenjene (jer bi to malo obesmislilo algoritam). Takođe se smatra da su težine grana čuvane u matrici težina w.		# U implementaciji ispod smatra se da optimizacije pomenute iznad nisu primenjene (jer bi to malo obesmislilo algoritam). Takođe se smatra da su težine grana čuvane u matrici težina w.
	</div>		</div>
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	DEBT(G, i)		DEBT(G, i)
	total_debt = 0		total_debt = 0
Ред 263:		Ред 263:
	end_while		end_while
	return total_debt		return total_debt
	</~~syntaxhighlight~~>		</nowiki>}}

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

KockaAdmiralac: Zamena SVG u šestom zadatku

2022-02-13T17:39:21Z

Zamena SVG u šestom zadatku

← Старија измена		Верзија на датум 13. фебруар 2022. у 19:39
Ред 200:		Ред 200:

	=== Rešenje ===		=== Rešenje ===
	[[File:ASP1 K2 2018 zadatak 6 stablo.~~png~~\|thumb\|Rešenje prvog dela zadatka.]]		[[File:ASP1 K2 2018 zadatak 6 stablo.svg\|thumb\|Rešenje prvog dela zadatka.]]
	Algoritam za obilazak povezanog stabla obrnutim ''inorder'' poretkom dat je ispod.		Algoritam za obilazak povezanog stabla obrnutim ''inorder'' poretkom dat je ispod.
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">

Etfsibg: /* Rešenje */

2021-08-26T23:31:40Z

Rešenje

← Старија измена		Верзија на датум 27. август 2021. у 01:31
Ред 48:		Ред 48:

	=== Rešenje ===		=== Rešenje ===
	Binarno stablo sa minimalnom visinom teži da ima svaki nivo popunjen, tj. teži da bude kompletno stablo. Pošto znamo da kompletno stablo na nivou <math>i</math> ima <math>2^i</math> čvorova (svaki čvor osim listova ima maksimalni izlazni stepen, što je 2), i da je stoga ukupan broj čvorova u stablu jednak <math>n = 2^0 + 2^1 + ... + 2^h = 2^{h + 1} - 1</math>. To znači da je <math>\log_2(n + 1)</math> jednako <math>h + 1</math> i time dobijamo da je <math>h_{min} = \left\lceil{\log_2(n + 1) ~~- 1~~}\right\rceil</math>.		Binarno stablo sa minimalnom visinom teži da ima svaki nivo popunjen, tj. teži da bude kompletno stablo. Pošto znamo da kompletno stablo na nivou <math>i</math> ima <math>2^i</math> čvorova (svaki čvor osim listova ima maksimalni izlazni stepen, što je 2), i da je stoga ukupan broj čvorova u stablu jednak <math>n = 2^0 + 2^1 + ... + 2^h = 2^{h + 1} - 1</math>. To znači da je <math>\log_2(n + 1)</math> jednako <math>h + 1</math> i time dobijamo da je <math>h_{min} = \left\lceil{\log_2(n + 1)}\right\rceil - 1</math>.

	== 3. zadatak ==		== 3. zadatak ==

KockaAdmiralac: Prebacivanje na jednostavno isticanje sintakse

2020-08-28T09:41:04Z

Prebacivanje na jednostavno isticanje sintakse

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

KockaAdmiralac: Kategorizacija

2020-07-27T09:59:16Z

Kategorizacija

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

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

KockaAdmiralac: puno stablo -> kompletno stablo; lista susednosti -> inverzna lista susednosti

2020-06-10T14:05:56Z

puno stablo -> kompletno stablo; lista susednosti -> inverzna lista susednosti

← Старија измена		Верзија на датум 10. јун 2020. у 16:05
Ред 45:		Ред 45:

	=== Rešenje ===		=== Rešenje ===
	Binarno stablo sa minimalnom visinom teži da ima svaki nivo popunjen, tj. teži da bude ~~puno~~ stablo. Pošto znamo da ~~puno~~ stablo na nivou <math>i</math> ima <math>2^i</math> čvorova, i da je stoga ukupan broj čvorova u stablu jednak <math>n = 2^0 + 2^1 + ... + 2^h = 2^{h + 1} - 1</math>. To znači da je <math>\log_2(n + 1)</math> jednako <math>h + 1</math> i time dobijamo da je <math>h_{min} = \log_2(n + 1) - 1</math>.		Binarno stablo sa minimalnom visinom teži da ima svaki nivo popunjen, tj. teži da bude kompletno stablo. Pošto znamo da kompletno stablo na nivou <math>i</math> ima <math>2^i</math> čvorova (svaki čvor osim listova ima maksimalni izlazni stepen, što je 2), i da je stoga ukupan broj čvorova u stablu jednak <math>n = 2^0 + 2^1 + ... + 2^h = 2^{h + 1} - 1</math>. To znači da je <math>\log_2(n + 1)</math> jednako <math>h + 1</math> i time dobijamo da je <math>h_{min} = \left\lceil{\log_2(n + 1) - 1}\right\rceil</math>.

	== 3. zadatak ==		== 3. zadatak ==
Ред 238:		Ред 238:
	=== Rešenje ===		=== Rešenje ===
	<div class="abc-list">		<div class="abc-list">
	# Graf koji nam je u ovom slučaju potreban jeste težinski usmeren graf u kom čvorovi predstavljaju firme a grane predstavljaju dugovanja, gde grana težine w od čvora A do čvora B označava da firma B duguje firmi B iznos od w jedinica valute. Operacije koje nad njim moraju biti realizovane jesu dodavanje novog čvora i povezivanje dva čvora.		# Graf koji nam je u ovom slučaju potreban jeste težinski usmeren graf u kom čvorovi predstavljaju firme a grane predstavljaju dugovanja, gde grana težine w od čvora A do čvora B označava da firma A duguje firmi B iznos od w jedinica valute. Operacije koje nad njim moraju biti realizovane jesu dodavanje novog čvora i povezivanje dva čvora.
	# Optimalna memorijska reprezentacija jeste preko liste susednosti, tj. niza dužine n koji sadrži pokazivače ka ~~povezanim~~ listama u kojima se nalaze svi čvorovi sa ~~kojima je trenutni čvor povezan~~. Težine grana se mogu čuvati ili u samim čvorovima ~~povezane~~ liste ili u odvojenoj matrici w gde w[i, j] označava težinu grane od i ka j i može biti postavljena na ∞ ukoliko ta grana ne postoji.		# Optimalna memorijska reprezentacija jeste preko inverzne liste susednosti, tj. niza dužine n koji sadrži pokazivače ka ulančanim listama u kojima se nalaze svi čvorovi koji su povezani sa trenutnim čvorom. Težine grana se mogu čuvati ili u samim čvorovima ulančane liste ili u odvojenoj matrici w gde w[i, j] označava težinu grane od i ka j i može biti postavljena na ∞ ukoliko ta grana ne postoji.
	#: Operacija izračunavanja ukupnog iznosa dugovanja može se realizovati prolaskom kroz listu susednosti i sabiranjem svih težina grana koje ti čvorovi čine s zadatim čvorom, a može se i izmeniti struktura tako da se u zaglavlju lista susednosti čuva ukupno dugovanje bez da se poveća složenost neke druge operacije.		#: Operacija izračunavanja ukupnog iznosa dugovanja može se realizovati prolaskom kroz listu susednosti i sabiranjem svih težina grana koje ti čvorovi čine s zadatim čvorom, a može se i izmeniti struktura tako da se u zaglavlju lista susednosti čuva ukupno dugovanje bez da se poveća složenost neke druge operacije.
	#: Operacija određivanja najvećeg dužnika može se isto realizovati linearnim prolaskom kroz listu koji čuva najvećeg dužnika i najveći dug. Dodatna optimizacija može se postići time što se povezane liste pretvore u prioritetne redove što operaciji povezivanja dva čvora povećava složenost sa konstantne na logaritamsku ali operaciji pronalaženja najvećeg dužnika smanjuje složenost sa linearne na konstantnu, za šta smo i optimizovali.		#: Operacija određivanja najvećeg dužnika može se isto realizovati linearnim prolaskom kroz listu koji čuva najvećeg dužnika i najveći dug. Dodatna optimizacija može se postići time što se povezane liste pretvore u prioritetne redove što operaciji povezivanja dva čvora povećava složenost sa konstantne na logaritamsku ali operaciji pronalaženja najvećeg dužnika smanjuje složenost sa linearne na konstantnu, za šta smo i optimizovali.

KockaAdmiralac: Nemam pojma šta je head a šta tail ali ovaj red je bio gluplje nazvan ranije; popravka root -> GETNODE(root); max_depth je nepotrebno

2020-05-07T11:23:39Z

Nemam pojma šta je head a šta tail ali ovaj red je bio gluplje nazvan ranije; popravka root -> GETNODE(root); max_depth je nepotrebno

← Старија измена		Верзија на датум 7. мај 2020. у 13:23
Ред 130:		Ред 130:
	=== Rešenje ===		=== Rešenje ===
	<u>FIND LONGEST CODES(''root'')</u>		<u>FIND LONGEST CODES(''root'')</u>
	''~~list~~'' = ''~~root''~~		''tail'' = ''head'' = GETNODE(''root'')
	~~''p~~'' = ''~~list~~''		''next''(''head'') = GETNODE(nil)
	''next''(''p'') = GETNODE(nil)		''head'' = ''next''(''head'')
	''p'' = ''next''(''p'')
	~~''max_depth'' = 1~~
	''num_max'' = 0		''num_max'' = 0
	''t'' = nil		''t'' = nil
	'''while''' ''~~list~~'' ≠ nil '''do'''		'''while''' ''tail'' ≠ nil '''do'''
	'''if''' ''value''(''~~list~~'') = nil '''then'''		'''if''' ''value''(''tail'') = nil '''then'''
	'''if''' ''~~list~~'' ≠ ''p'' '''then'''		'''if''' ''tail'' ≠ ''head'' '''then'''
	''next''(''p'') = GETNODE(nil)		''next''(''head'') = GETNODE(nil)
	''p'' = ''next''(''p'')		''head'' = ''next''(''head'')
	~~''max_depth'' = ''max_depth'' + 1~~
	''num_max'' = 0		''num_max'' = 0
	'''end_if'''		'''end_if'''
	'''else'''		'''else'''
	'''if''' IS_EXTERNAL_NODE(''value''(''~~list~~'')) '''then'''		'''if''' IS_EXTERNAL_NODE(''value''(''tail'')) '''then'''
	''num_max'' = ''num_max'' + 1		''num_max'' = ''num_max'' + 1
	'''else'''		'''else'''
	'''if''' ''left''(''value''(''~~list~~'')) ≠ nil '''then'''		'''if''' ''left''(''value''(''tail'')) ≠ nil '''then'''
	''next''(''p'') = GETNODE(''left''(''value''(''~~list~~'')))		''next''(''head'') = GETNODE(''left''(''value''(''tail'')))
	''p'' = ''next''(''p'')		''head'' = ''next''(''head'')
	'''end_if'''		'''end_if'''
	'''if''' ''right''(''value''(''~~list~~'')) ≠ nil '''then'''		'''if''' ''right''(''value''(''tail'')) ≠ nil '''then'''
	''next''(''p'') = GETNODE(''right''(''value''(''~~list~~'')))		''next''(''head'') = GETNODE(''right''(''value''(''tail'')))
	''p'' = ''next''(''p'')		''head'' = ''next''(''head'')
	'''end_if'''		'''end_if'''
	'''end_if'''		'''end_if'''
	'''end_if'''		'''end_if'''
	''t'' = ''next''(''~~list~~'')		''t'' = ''next''(''tail'')
	FREENODE(''~~list~~'')		FREENODE(''tail'')
	''~~list~~'' = ''t''		''tail'' = ''t''
	'''end_while'''		'''end_while'''
	'''return''' ''num_max''		'''return''' ''num_max''

KockaAdmiralac: Popravka imena datoteke

2020-04-09T23:26:59Z

Popravka imena datoteke

← Старија измена		Верзија на датум 10. април 2020. у 01:26
Ред 195:		Ред 195:

	=== Rešenje ===		=== Rešenje ===
	[[File:ASP1 K2 2018 6 ~~zadatak~~ stablo.png\|thumb\|Rešenje prvog dela zadatka.]]		[[File:ASP1 K2 2018 zadatak 6 stablo.png\|thumb\|Rešenje prvog dela zadatka.]]
	Algoritam za obilazak povezanog stabla obrnutim ''inorder'' poretkom dat je ispod.		Algoritam za obilazak povezanog stabla obrnutim ''inorder'' poretkom dat je ispod.
	<u>REVERSE INORDER T(''root'')</u>		<u>REVERSE INORDER T(''root'')</u>

KockaAdmiralac: +kategorija

2020-04-05T15:36:11Z

+kategorija

← Старија измена		Верзија на датум 5. април 2020. у 17:36
Ред 255:		Ред 255:
	'''end_while'''		'''end_while'''
	'''return''' ''total_debt''		'''return''' ''total_debt''

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