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

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

2024-09-13T00:09:10Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 7:		Ред 7:
	=== Rešenje ===		=== Rešenje ===
	Pretraživanje ide od početka niza K sa prvim ključem iz S dok se ne pronađe (i njegova pozicija zapamti u P) ili do prve veće vrednosti. Pretraživanje na sledeći ključ iz S počinje tamo gde se sa pretraživanjem na prethodni ključ stalo, pa se zato niz K prolazi samo jednom. Niz K je rastuće uređeni niz sa n ključeva koji se pretražuje na pojavu m ključeva zadatih u nizu S. Izlaz predstavlja vektor P gde se na poziciji koja odgovara ključu u nizu S nalazi pozicija ključa u nizu K, ako se on tamo pronađe, ili vrednost 0 ako se ne pronađe. Složenost ovog algoritma je O(n) za slučaj kada je m << n.		Pretraživanje ide od početka niza K sa prvim ključem iz S dok se ne pronađe (i njegova pozicija zapamti u P) ili do prve veće vrednosti. Pretraživanje na sledeći ključ iz S počinje tamo gde se sa pretraživanjem na prethodni ključ stalo, pa se zato niz K prolazi samo jednom. Niz K je rastuće uređeni niz sa n ključeva koji se pretražuje na pojavu m ključeva zadatih u nizu S. Izlaz predstavlja vektor P gde se na poziciji koja odgovara ključu u nizu S nalazi pozicija ključa u nizu K, ako se on tamo pronađe, ili vrednost 0 ako se ne pronađe. Složenost ovog algoritma je O(n) za slučaj kada je m << n.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	SEQ-SEARCH-MUL(K,S)		SEQ-SEARCH-MUL(K,S)
	for(int i=0;i<m;i++) P[i] = 0;		for(int i=0;i<m;i++) P[i] = 0;
Ред 17:		Ред 17:
	end_while		end_while
	return P;		return P;
	</~~syntaxhighlight~~>		</nowiki>}}
	== 2. zadatak ==		== 2. zadatak ==
	=== Postavka ===		=== Postavka ===
Ред 33:		Ред 33:
	=== Rešenje ===		=== Rešenje ===
	Ukoliko čvor ima desnog sina, onda je njegov sledbenik najlevlji čvor u desnom podstablu, a ako nema, onda je njegov sledbenik najbliži predak čiji je levi sin takođe predak zadatog čvora.		Ukoliko čvor ima desnog sina, onda je njegov sledbenik najlevlji čvor u desnom podstablu, a ako nema, onda je njegov sledbenik najbliži predak čiji je levi sin takođe predak zadatog čvora.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	BST-SUCC(k)		BST-SUCC(k)
	if(right(k) != nil)		if(right(k) != nil)
Ред 46:		Ред 46:
	end_while		end_while
	return s;		return s;
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==

KockaAdmiralac: Zapravo ispravka

2023-10-29T22:43:46Z

Zapravo ispravka

← Старија измена		Верзија на датум 30. октобар 2023. у 00:43
Ред 1:		Ред 1:
	{{tocright}}		{{tocright}}
	'''Popravni prvi kolokvijum 2012. godine''' održan je 9. januara 2012. Postavka zadataka je dostupna sa [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1p_1112.pdf stranice predmeta.]		'''Popravni prvi kolokvijum 2012. godine''' održan je 9. januara 2012. Postavka zadataka je dostupna sa [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/arhiva/SI2AS2_K1p_1112.pdf stranice predmeta.]

	== 1. zadatak ==		== 1. zadatak ==

KockaAdmiralac: Ispravka linka

2023-10-29T22:42:35Z

Ispravka linka

← Старија измена		Верзија на датум 30. октобар 2023. у 00:42
Ред 1:		Ред 1:
	{{tocright}}		{{tocright}}
	[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1p_1112.pdf ~~Zadaci na stranici~~ predmeta.]		'''Popravni prvi kolokvijum 2012. godine''' održan je 9. januara 2012. Postavka zadataka je dostupna sa [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1p_1112.pdf stranice predmeta.]

	~~'''Popravni prvi kolokvijum 2012. godine''' održan je 9. januara 2012.~~

	== 1. zadatak ==		== 1. zadatak ==

DjoleRkc: Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1p_1112.pdf Zadaci na stranici predmeta.] '''Popravni prvi kolokvijum 2012. godine''' održan je 9. januara 2012. == 1. zadatak == === Postavka === '''(30p)''' Predložiti adekvatnu strukturu podataka i detaljno navesti uslove njene upotrebe, a zatim skicirati algoritam za efikasnu pretragu na više celobrojnih ključeva nad neopadajuće uređenom tabelom. Smatrati da u tabeli ne postoje duplirani…

2023-02-26T18:47:14Z

Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1p_1112.pdf Zadaci na stranici predmeta.] '''Popravni prvi kolokvijum 2012. godine''' održan je 9. januara 2012. == 1. zadatak == === Postavka === '''(30p)''' Predložiti adekvatnu strukturu podataka i detaljno navesti uslove njene upotrebe, a zatim skicirati algoritam za efikasnu pretragu na više celobrojnih ključeva nad neopadajuće uređenom tabelom. Smatrati da u tabeli ne postoje duplirani…

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

{{tocright}}
[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1p_1112.pdf Zadaci na stranici predmeta.]

'''Popravni prvi kolokvijum 2012. godine''' održan je 9. januara 2012.

== 1. zadatak ==
=== Postavka ===
'''(30p)''' Predložiti adekvatnu strukturu podataka i detaljno navesti uslove njene upotrebe, a zatim skicirati algoritam za efikasnu pretragu na više celobrojnih ključeva nad neopadajuće uređenom tabelom. Smatrati da u tabeli ne postoje duplirani ključevi niti da se više puta vrši pretraga nad istim ključem.
=== Rešenje ===
Pretraživanje ide od početka niza K sa prvim ključem iz S dok se ne pronađe (i njegova pozicija zapamti u P) ili do prve veće vrednosti. Pretraživanje na sledeći ključ iz S počinje tamo gde se sa pretraživanjem na prethodni ključ stalo, pa se zato niz K prolazi samo jednom. Niz K je rastuće uređeni niz sa n ključeva koji se pretražuje na pojavu m ključeva zadatih u nizu S. Izlaz predstavlja vektor P gde se na poziciji koja odgovara ključu u nizu S nalazi pozicija ključa u nizu K, ako se on tamo pronađe, ili vrednost 0 ako se ne pronađe. Složenost ovog algoritma je O(n) za slučaj kada je m << n.
<syntaxhighlight lang="milo">
SEQ-SEARCH-MUL(K,S)
for(int i=0;i<m;i++) P[i] = 0;
i=j=1;
while(i<=n) and (j<=m)
while(i<n) and (S[j] > K[i]) i++;
if(S[j] = K[i]) P[j] = i;
j++;
end_while
return P;
</syntaxhighlight>
== 2. zadatak ==
=== Postavka ===
'''(20p)''' U AVL stablo se redom umeću sledeći celobrojni ključevi: 13, 32, 14, 28, 15, 35, 44, 47, 22, 30, 24, 19, 20, a zatim se brišu ključevi 15, 30, 28, 24. Nacrtati izgled stabla nakon svake od navedenih izmena. Izračunati prosečan broj pristupa stablu za uspešnu pretragu nakon svih umetanja i u konačnom stanju.
=== Rešenje ===
Ukoliko želite da zadatak proverite korak po korak, to možete uraditi na [https://www.cs.usfca.edu/~galles/visualization/AVLtree.html linku.]
[[Датотека:ASP2 K1 2011p Zadatak 2 umetanje.svg|thumb|600px|center|Stablo nakon svih umetanja]]
[[Датотека:ASP2 K1 2011p Zadatak 2 brisanje.svg|thumb|600px|center|Stablo nakon svih brisanja]]
Nakon svih umetanja: <math>S_{n} = \frac{5 + 5\cdot4 + 4\cdot3 + 2\cdot2 + 1}{13} = \frac{42}{13} = 3.23</math>

Nakon svih brisanja: <math>S_{n} = \frac{2\cdot4 + 4\cdot3 + 2\cdot2 + 1}{9} = \frac{25}{9} = 2.78</math>
== 3. zadatak ==
=== Postavka ===
'''(20p)''' Dati pseudokod i objasniti algoritam za određivanje sledbenika proizvoljno zadatog čvora u stablu binarnog pretraživanja.
=== Rešenje ===
Ukoliko čvor ima desnog sina, onda je njegov sledbenik najlevlji čvor u desnom podstablu, a ako nema, onda je njegov sledbenik najbliži predak čiji je levi sin takođe predak zadatog čvora.
<syntaxhighlight lang="milo">
BST-SUCC(k)
if(right(k) != nil)
p = right(k);
while(left(p) != nil) p = left(p);
return p;
end_if
p = parent(k), s = k;
while(p != nil and right(p) = s)
s = p;
p = parent(p);
end_while
return s;
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
'''(30p)''' Pitanja:
<div class="abc-list">
# Objasniti kako i zašto metod transpozije optimizuje sekvencijalno pretraživanje.
# Ako se stablo binarnog pretraživanja koristi kao prioritetni red, objasniti kako izgedaju operacije PQ_INSERT i PQ_MIN_DELETE. Kolika je vremenska složenost ovih operacija?
# Precizno definisati optimalno stablo binarnog pretraživanja.
</div>
=== Rešenje ===
<div class="abc-list">
# Metod transpozicije optimizuje sekvencijalno pretraživanje tako što svaki put kada se traženi element nađe, on zameni mesto sa elementom levo od sebe i tako se priblližava početku niza. Time se obezbeđuje da su oni elementi kojima se češće pristupa bliže početku, pa pošto se sekvencijalno pristupa, i samo vreme pristupa tim elementima je skraćeno.
# <ref>Ovo više nije gradivo K1</ref>
# Optimalno stablo binarnog pretraživanja je ono stablo čija je cena najmanja, gde cenu definišemo kao: <math>C = \sum_{i}^{m-n} p_{i}(h_{i} + 1) + \sum_{i}^{m-n} q_{i}h_{i}</math>, gde su Pi verovatnoće pristupa ključevima Kn...Km, a Qi verovatnoće pristupa eksternim čvorovima. Osobina na kojoj se zasniva algoritam za nalaženje optimalnog stabla binarnog pretraživanja je da su sva podstabla optimalnog stabla pretraživanja takođe optimalna.
</div>

== Napomene ==
<references/>


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