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

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

2024-09-13T00:09:11Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 45:		Ред 45:
	=== Rešenje ===		=== Rešenje ===
	Prvo proveravamo da li pozajmljujemo u čvoru koji se nalazi u praznom stablu ili u čvoru koji je koren i u tom slučaju signaliziramo grešku. Ukoliko se u čvoru nalazi dovoljan broj ključeva, pozajmica je nepotrebna pa samo izlazimo iz funkcije. Zatim, nalazimo koji je indeks trenutnog čvora u nizu pokazivača na decu njegovog roditelja i na osnovu toga pronalazimo njegovu braću, prvo desnog pa levog. Ako braća ne postoje ili nemaju dovoljno čvorova signaliziramo grešku, u suprotnom premeštamo ključeve i prevezujemo pokazivače.		Prvo proveravamo da li pozajmljujemo u čvoru koji se nalazi u praznom stablu ili u čvoru koji je koren i u tom slučaju signaliziramo grešku. Ukoliko se u čvoru nalazi dovoljan broj ključeva, pozajmica je nepotrebna pa samo izlazimo iz funkcije. Zatim, nalazimo koji je indeks trenutnog čvora u nizu pokazivača na decu njegovog roditelja i na osnovu toga pronalazimo njegovu braću, prvo desnog pa levog. Ako braća ne postoje ili nemaju dovoljno čvorova signaliziramo grešku, u suprotnom premeštamo ključeve i prevezujemo pokazivače.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	B-DEL-BORROW(node)		B-DEL-BORROW(node)
	min_nodes = ceil(m/2)-1		min_nodes = ceil(m/2)-1
Ред 90:		Ред 90:
	ERROR(Borrow impossible)		ERROR(Borrow impossible)
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

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

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	TRIE SUBSTRINGS(str)		TRIE SUBSTRINGS(str)
	root = GETNODE		root = GETNODE
Ред 175:		Ред 175:
	end_for		end_for
	return root		return root
	</~~syntaxhighlight~~>		</nowiki>}}

	== 7. zadatak ==		== 7. zadatak ==

KockaAdmiralac: SVG i konzistentno imenovanje

2022-02-13T20:30:25Z

SVG i konzistentno imenovanje

← Старија измена		Верзија на датум 13. фебруар 2022. у 22:30
Ред 94:		Ред 94:
	== 4. zadatak ==		== 4. zadatak ==
	=== Postavka ===		=== Postavka ===
	[[Датотека:ASP2 K2 2016 4~~. zadatak~~ graf.~~png~~\|thumb\|Graf iz postavke 4. zadatka.]]		[[Датотека:ASP2 K2 2016 zadatak 4 graf.svg\|thumb\|Graf iz postavke 4. zadatka.]]
	Neka se zbog uštede memorije za smeštanje ključeva koji imaju zajedničke sufikse umesto digitalnog stabla koristi usmereni aciklični graf, kao na slici. Objasniti na koji način bi se implementirale operacije pretraživanja i brisanja ključa.		Neka se zbog uštede memorije za smeštanje ključeva koji imaju zajedničke sufikse umesto digitalnog stabla koristi usmereni aciklični graf, kao na slici. Objasniti na koji način bi se implementirale operacije pretraživanja i brisanja ključa.

KockaAdmiralac: Bolje objašenja stavka 8b pošto ovo ni ja nisam mogao da razumem jedno godinu dana nakon pisanja

2021-12-10T21:38:47Z

Bolje objašenja stavka 8b pošto ovo ni ja nisam mogao da razumem jedno godinu dana nakon pisanja

← Старија измена		Верзија на датум 10. децембар 2021. у 23:38
Ред 207:		Ред 207:
	<div class="abc-list">		<div class="abc-list">
	# Uniformnost heš funkcije je osobina koja znači da je svaki od <math>n</math> izlaza podjednako verovatan: <math>P(H(K)) = \frac{1}{n}, 1 \leq H(K) \leq n</math>		# Uniformnost heš funkcije je osobina koja znači da je svaki od <math>n</math> izlaza podjednako verovatan: <math>P(H(K)) = \frac{1}{n}, 1 \leq H(K) \leq n</math>
	# ~~Na svakih~~ <math>n</math> ~~unetih ključeva za svaki ključ možemo da očekujemo po~~ jednu koliziju ~~više na svakom unetom ključu. Umetanje zatim možemo podeliti u više faza~~, tako ~~da je u svakoj fazi za po jedna~~ kolizija ~~više~~ po ključu ~~od prošle, i broj tih (potpunih) faza će biti~~ <math>m = \left\lfloor\frac{k}{n}\right\rfloor</math>. To znači da će ukupan očekivani broj kolizija biti <math>n \cdot (0 + 1 + 2 + ... + m-1) + m \cdot (k \mod n) = n \cdot \frac{(m-1)(m-2)}{2} + m \cdot (k \mod n)</math>.		# Zamislimo da ključeve umećemo u tabelu jedan po jedan. Pošto je naša heš funkcija uniformna, prvih <math>n</math> umetanja nećemo imati nijednu koliziju. Narednih <math>n</math> umetanja ćemo imati jednu koliziju po umetanju, sledećih <math>n</math> dve kolizije, i tako dalje. Ukupan broj puta koliko će se povećanje broja kolizija po ključu desiti jeste <math>m = \left\lfloor\frac{k}{n}\right\rfloor</math>, i on će na kraju biti povećan na <math>m</math>. To znači da će ukupan očekivani broj kolizija biti <math>n \cdot (0 + 1 + 2 + ... + m-1) + m \cdot (k \mod n) = n \cdot \frac{(m-1)(m-2)}{2} + m \cdot (k \mod n)</math>. Drugi deo jednačine ima veze sa time što kada umetnemo <math>m \cdot n</math> ključeva naš broj kolizija će biti jednak <math>m</math>, ali će nama i dalje ostati <math>k - m \cdot n</math>, odnosno <math>k \mod n</math> ključeva koji nisu umetnuti (pri računanju <math>m</math> smo zaokružili na manji broj) i na njima će broj kolizija biti <math>m</math>.
	</div>		</div>

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

KockaAdmiralac: Milova knjiga kaže da se ključevi u levi sin desni brat reprezentaciji digitalnog stabla generalno sortiraju; dijagrami zamenjeni sa SVG varijantama

2021-12-10T20:56:43Z

Milova knjiga kaže da se ključevi u levi sin desni brat reprezentaciji digitalnog stabla generalno sortiraju; dijagrami zamenjeni sa SVG varijantama

← Старија измена		Верзија на датум 10. децембар 2021. у 22:56
Ред 9:		Ред 9:
	Ispod su data stabla nakon poslednjeg umetanja i brisanja.		Ispod su data stabla nakon poslednjeg umetanja i brisanja.
	<gallery>		<gallery>
	ASP2 K2 2016 1~~. zadatak~~ stablo umetanje.~~png~~ \| Stablo nakon poslednjeg umetanja.		ASP2 K2 2016 zadatak 1 stablo umetanje.svg \| Stablo nakon poslednjeg umetanja.
	ASP2 K2 2016 1~~. zadatak~~ stablo brisanje.~~png~~ \| Stablo nakon poslednjeg brisanja.		ASP2 K2 2016 zadatak 1 stablo brisanje.svg \| Stablo nakon poslednjeg brisanja.
	</gallery>		</gallery>

KockaAdmiralac: LaTeX ispravka

2021-02-16T15:59:23Z

LaTeX ispravka

← Старија измена		Верзија на датум 16. фебруар 2021. у 17:59
Ред 207:		Ред 207:
	<div class="abc-list">		<div class="abc-list">
	# Uniformnost heš funkcije je osobina koja znači da je svaki od <math>n</math> izlaza podjednako verovatan: <math>P(H(K)) = \frac{1}{n}, 1 \leq H(K) \leq n</math>		# Uniformnost heš funkcije je osobina koja znači da je svaki od <math>n</math> izlaza podjednako verovatan: <math>P(H(K)) = \frac{1}{n}, 1 \leq H(K) \leq n</math>
	# Na svakih <math>n</math> unetih ključeva za svaki ključ možemo da očekujemo po jednu koliziju više na svakom unetom ključu. Umetanje zatim možemo podeliti u više faza, tako da je u svakoj fazi za po jedna kolizija više po ključu od prošle, i broj tih (potpunih) faza će biti <math>m = \left\lfloor\frac{k}{n}\right\rfloor</math>. To znači da će ukupan očekivani broj kolizija biti <math>n \cdot (0 + 1 + 2 + ... + m-1) + m \cdot (k \mod n) = n \cdot frac{(m-1)(m-2)}{2} + m \cdot (k \mod n)</math>.		# Na svakih <math>n</math> unetih ključeva za svaki ključ možemo da očekujemo po jednu koliziju više na svakom unetom ključu. Umetanje zatim možemo podeliti u više faza, tako da je u svakoj fazi za po jedna kolizija više po ključu od prošle, i broj tih (potpunih) faza će biti <math>m = \left\lfloor\frac{k}{n}\right\rfloor</math>. To znači da će ukupan očekivani broj kolizija biti <math>n \cdot (0 + 1 + 2 + ... + m-1) + m \cdot (k \mod n) = n \cdot \frac{(m-1)(m-2)}{2} + m \cdot (k \mod n)</math>.
	</div>		</div>

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

Ivan Pešić: /* Rešenje */

2021-01-27T21:42:59Z

Rešenje

← Старија измена		Верзија на датум 27. јануар 2021. у 23:42
Ред 168:		Ред 168:
	pos = getPosition(str[j])		pos = getPosition(str[j])
	if nodes(node)[pos] = nil then		if nodes(node)[pos] = nil then
	~~node~~(node)[pos] = GETNODE		nodes(node)[pos] = GETNODE
	end_if		end_if
	node = ~~node~~(node)[pos]		node = nodes(node)[pos]
	value(node) = substr		value(node) = substr
	end_for		end_for

Ivan Pešić: /* Rešenje */

2021-01-27T19:04:06Z

Rešenje

← Старија измена		Верзија на датум 27. јануар 2021. у 21:04
Ред 79:		Ред 79:
	pointers(node)[i+1] = pointers(node)[i]		pointers(node)[i+1] = pointers(node)[i]
	if i < num(node) then		if i < num(node) then
	keys(~~sibling~~)[i+2] = keys(~~sibling~~)[i+1]		keys(node)[i+2] = keys(node)[i+1]
	end_if		end_if
	end_for		end_for

Ivan Pešić: zaboravio sam da promenim granice

2021-01-27T18:56:41Z

zaboravio sam da promenim granice

← Старија измена		Верзија на датум 27. јануар 2021. у 20:56
Ред 76:		Ред 76:
	else if (parent_index > 0) and (num(pointers(parent)[parent_index-1]) > min_nodes) then		else if (parent_index > 0) and (num(pointers(parent)[parent_index-1]) > min_nodes) then
	sibling = pointers(parent)[parent_index-1]		sibling = pointers(parent)[parent_index-1]
	for i = ~~0 downto~~ num(node) do		for i = num(node) downto 0 do
	pointers(node)[i+1] = pointers(node)[i]		pointers(node)[i+1] = pointers(node)[i]
	if i < num(node) then		if i < num(node) then

Ivan Pešić: to->downto

2021-01-27T18:55:40Z

to->downto

← Старија измена		Верзија на датум 27. јануар 2021. у 20:55
Ред 76:		Ред 76:
	else if (parent_index > 0) and (num(pointers(parent)[parent_index-1]) > min_nodes) then		else if (parent_index > 0) and (num(pointers(parent)[parent_index-1]) > min_nodes) then
	sibling = pointers(parent)[parent_index-1]		sibling = pointers(parent)[parent_index-1]
	for i = 0 to num(node) do		for i = 0 downto num(node) do
	pointers(node)[i+1] = pointers(node)[i]		pointers(node)[i+1] = pointers(node)[i]
	if i < num(node) then		if i < num(node) then

KockaAdmiralac: Ispravka Milokoda

2021-01-25T15:37:41Z

Ispravka Milokoda

← Старија измена		Верзија на датум 25. јануар 2021. у 17:37
Ред 55:		Ред 55:
	end_if		end_if
	parent = parent(node)		parent = parent(node)
	for i to 0 to num(parent) do		for i = 0 to num(parent) do
	if pointers(parent)[i] = node then		if pointers(parent)[i] = node then
	parent_index = i		parent_index = i