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

2024-09-13T00:09:06Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 94:		Ред 94:
	=== Rešenje ===		=== Rešenje ===
	U ovom zadatku je iskorišćeno rešenje iz knjige, tj ono što je u knjizi nazvano dvostrukom rotacijom (dve rotacije suprotnog smera, prvo leva oko levog sina kritičnog čvora a zatim desna oko kritičnog čvora). Dve rotacije ulevo oko kritičnog čvora '''nemaju smisla'''.<ref>Na K1 2022 je bio isti ovaj zadatak i jedan student je uradio dve rotacije ulevo oko x, na šta je Mišić rekao da to nema smisla iako tako piše u zadatku.</ref>		U ovom zadatku je iskorišćeno rešenje iz knjige, tj ono što je u knjizi nazvano dvostrukom rotacijom (dve rotacije suprotnog smera, prvo leva oko levog sina kritičnog čvora a zatim desna oko kritičnog čvora). Dve rotacije ulevo oko kritičnog čvora '''nemaju smisla'''.<ref>Na K1 2022 je bio isti ovaj zadatak i jedan student je uradio dve rotacije ulevo oko x, na šta je Mišić rekao da to nema smisla iako tako piše u zadatku.</ref>
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	L-ROT(x)		L-ROT(x)
	y = x.right		y = x.right
Ред 100:		Ред 100:
	y.left = x		y.left = x
	x.right = temp		x.right = temp
	</~~syntaxhighlight~~>		</nowiki>}}

	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	R-ROT(x)		R-ROT(x)
	y = x.left		y = x.left
Ред 108:		Ред 108:
	y.right = x		y.right = x
	x.left = temp		x.left = temp
	</~~syntaxhighlight~~>		</nowiki>}}

	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	L-DOUBLE-ROT(x)		L-DOUBLE-ROT(x)
	L-ROT(x.left)		L-ROT(x.left)
	R-ROT(x)		R-ROT(x)
	</~~syntaxhighlight~~>		</nowiki>}}

	== 6. zadatak ==		== 6. zadatak ==
Ред 121:		Ред 121:
	=== Rešenje ===		=== Rešenje ===
	U ovom zadatku se koristi algoritam za '''Binarno pretraživanje u tabeli nepoznate veličine''' iz knjige.		U ovom zadatku se koristi algoritam za '''Binarno pretraživanje u tabeli nepoznate veličine''' iz knjige.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	EX-SEARCH(L, key)		EX-SEARCH(L, key)
	high=low=1;		high=low=1;
Ред 135:		Ред 135:
	end_while		end_while
	return -1;		return -1;
	</~~syntaxhighlight~~>		</nowiki>}}

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

DjoleRkc: Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1_1415.pdf Zadaci na stranici predmeta.] '''Prvi kolokvijum 2014. godine''' održan je 28. oktobra 2014. == 1. zadatak == === Postavka === '''(5p)''' Neka je dat uređeni niz M i sekvenca ključeva 15, 8, 33, 21, 25 na koje se vrši pretraga. Predložiti neophodne strukture podataka i prikazati njihov sadržaj nakon simultane pretrage zadatog niza na više ključeva. {| class="wikitable" |+ Uređe…

2023-02-23T19:04:09Z

Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1_1415.pdf Zadaci na stranici predmeta.] '''Prvi kolokvijum 2014. godine''' održan je 28. oktobra 2014. == 1. zadatak == === Postavka === '''(5p)''' Neka je dat uređeni niz M i sekvenca ključeva 15, 8, 33, 21, 25 na koje se vrši pretraga. Predložiti neophodne strukture podataka i prikazati njihov sadržaj nakon simultane pretrage zadatog niza na više ključeva. {| class="wikitable" |+ Uređe…

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

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

'''Prvi kolokvijum 2014. godine''' održan je 28. oktobra 2014.

== 1. zadatak ==
=== Postavka ===
'''(5p)''' Neka je dat uređeni niz M i sekvenca ključeva 15, 8, 33, 21, 25 na koje se vrši pretraga. Predložiti neophodne strukture podataka i prikazati njihov sadržaj nakon simultane pretrage zadatog niza na više ključeva.
{| class="wikitable"
|+ Uređeni niz M
! 1
! 2
! 3
! 4
! 5
! 6
! 7
! 8
! 9
! 10
! 11
! 12
! 13
! 14
! 15
|-
| 1
| 3
| 7
| 10
| 11
| 15
| 17
| 20
| 25
| 28
| 29
| 31
| 33
| 36
| 40
|}
=== Rešenje ===
Neophodan je dodatni vektor za elemente koji su već nađeni i njihove indekse. Nakon simultane pretrage zadatog niza na više ključeva, vektor će ovako izgledati (primetimo da se brojevi 8 i 21 ne nalaze u nizu):
{| class="wikitable"
|-
! 15
! 25
! 33
|-
| 6
| 9
| 13
|}
== 2. zadatak ==
=== Postavka ===
'''(10p)''' Za stablo binarnog pretraživanja sa slike odrediti prosečan broj pristupa prilikom uspešne pretrage i prilikom neuspešne pretrage, ako je poznato da je vrednost ključeva koji se mogu umetnuti u stablo u opsegu od 1 do 30. Smatrati da su svi ključevi jednako verovatni.
[[Датотека:ASP2 K1 2014 Zadatak 2.png|thumb|600px|center|Stablo iz postavke zadatka]]
=== Rešenje ===
Iz nepoznatog razloga rešenje ovog zadatka je bilo dato u pdfu sa zadacima.
{| class="wikitable"
|-
! Prosečan broj pristupa prilikom uspešne pretrage:
! 36/11=3.28
|-
| Prosečan broj pristupa prilikom neuspešne pretrage:
| 62/19=3.26
|}
== 3. zadatak ==
=== Postavka ===
'''(10p)''' Prikazati po koracima izgled binarnog stabla pretraživanja sa slike, ukoliko izvrši
sledeća sekvenca operacija: umetanje ključeva 19 i 2, a zatim brisanje ključeva 15, 5 i 22.
Prilikom brisanja, koristiti '''sledbenika'''.
[[Датотека:ASP2 K1 2014 Zadatak 3.png|thumb|600px|center|Stablo iz postavke zadatka]]
=== Rešenje ===
[[Датотека:ASP2 K1 2014 Zadatak 3 korak 1.svg|thumb|600px|center|Stablo nakon umetanja ključeva 19 i 2]]
[[Датотека:ASP2 K1 2014 Zadatak 3 korak 2.svg|thumb|600px|center|Stablo nakon brisanja ključeva 15, 5 i 22]]
== 4. zadatak ==
=== Postavka ===
'''(10p)''' U AVL stablo se redom umeću ključevi: 5, 3, 4, 6, 12, 9, 7, 16, 18. Prikazati, postupno, izgled stabla nakon svakog umetanja ključa.
=== Rešenje ===
[[Датотека:ASP2 K1 2014 Zadatak 4 korak 1.png|thumb|600px|center|Stablo nakon umetanja ključeva 5 i 3]]
[[Датотека:ASP2 K1 2014 Zadatak 4 korak 2.png|thumb|600px|center|Stablo nakon umetanja ključa 4]]
[[Датотека:ASP2 K1 2014 Zadatak 4 korak 3.png|thumb|600px|center|Stablo nakon umetanja ključa 6]]
[[Датотека:ASP2 K1 2014 Zadatak 4 korak 4.png|thumb|600px|center|Stablo nakon umetanja ključa 12]]
[[Датотека:ASP2 K1 2014 Zadatak 4 korak 5.png|thumb|600px|center|Stablo nakon umetanja ključa 9]]
[[Датотека:ASP2 K1 2014 Zadatak 4 korak 6.png|thumb|600px|center|Stablo nakon umetanja ključa 7]]
[[Датотека:ASP2 K1 2014 Zadatak 4 korak 7.png|thumb|600px|center|Stablo nakon umetanja ključa 16]]
[[Датотека:ASP2 K1 2014 Zadatak 4 korak 8.png|thumb|600px|center|Konačni izgled stabla]]

== 5. zadatak ==
=== Postavka ===
'''(15p)''' Napisati u pseudokodu operaciju '''dvostruke rotacije ulevo'''. Nacrtati '''opštu''' sliku koja objašnjava napisani pseudokod i na kojem su čvorovi obeleženi odgovarajućim identifikatorima upotrebljenim u pseudokodu.
=== Rešenje ===
U ovom zadatku je iskorišćeno rešenje iz knjige, tj ono što je u knjizi nazvano dvostrukom rotacijom (dve rotacije suprotnog smera, prvo leva oko levog sina kritičnog čvora a zatim desna oko kritičnog čvora). Dve rotacije ulevo oko kritičnog čvora '''nemaju smisla'''.<ref>Na K1 2022 je bio isti ovaj zadatak i jedan student je uradio dve rotacije ulevo oko x, na šta je Mišić rekao da to nema smisla iako tako piše u zadatku.</ref>
<syntaxhighlight lang="milo">
L-ROT(x)
y = x.right
temp = y.left
y.left = x
x.right = temp
</syntaxhighlight>

<syntaxhighlight lang="milo">
R-ROT(x)
y = x.left
temp = y.right
y.right = x
x.left = temp
</syntaxhighlight>

<syntaxhighlight lang="milo">
L-DOUBLE-ROT(x)
L-ROT(x.left)
R-ROT(x)
</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
'''(15p)''' Napisati u pseudokodu i kratko objasniti iterativnu implementaciju algoritma za binarno pretraživanje na ključ k, ukoliko je veličina tabele nepoznata. Smatrati da postoji funkcija IN(index) koja vraća vrednost true ukoliko zadati indeks pripada tabeli, a false u suprotnom.
=== Rešenje ===
U ovom zadatku se koristi algoritam za '''Binarno pretraživanje u tabeli nepoznate veličine''' iz knjige.
<syntaxhighlight lang="milo">
EX-SEARCH(L, key)
high=low=1;
if(IN(high)=false) return -1;
if(key = L[1]) return 1;
while(IN(high)=true && key>L[high]) high *= 2;
low = high/2;
while(low<=high)
mid = (low+high)/2;
if(key=L[mid]) return mid;
if(key<L[mid]) high = mid-1;
else low = mid+1;
end_while
return -1;
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
'''(15p)''' Objasniti šta je samopodešavajuće stablo, kao i motivaciju za ovu strukturu. Ukratko načelno opisati operacije pretraživanja, umetanja i brisanja. Koji algoritam pretraživanja nizova koristi sličnu strategiju?
=== Rešenje ===
Samopodešavajuća stabla su stabla koja održavaju balansiranost bez nekog eksplicitnog kriterijuma pri umetanju i brisanju. Umesto toga, reorganizacija stabla se vrši pri svakom pristupu stablu, pa i pretraživanju. Pritom se ključevi kojima se češće pristupa postavljaju bliže korenu, tako da im se omogući brži pristup pri narednim obraćanjima. Za ovo se koriste operacije koje se zasnivaju na rotacijama. Motivacija je optimizacija zasnovana na vremenskoj lokalnosti, slično kao kod transpozicije i prebacivanja na početak kod sekvencijalne pretrage. Pretraživanje se vrši tako što nađeni ili poslednji ne-null ključ nizom rotacija prebacujemo u koren. Umetanje se vrši tako što prvo uradimo pretraživanje na zadati ključ, a ako on ne postoji, umetnemo ga na odgovarajuće mesto. Brisanje se vrši tako što se prvo vrši pretraživanje na zadati ključ, pa ako se on pronađe, prebacuje se u koren, koji se potom briše i menja prethodnikom.

== 8. zadatak ==
=== Postavka ===
'''(20p)''' Odgovoriti na sledeća pitanja u vezi optimalnog stabla binarnog pretraživanja. '''Napomena:''' Svaki korišćeni simbol treba definisati i objasniti.
<div class="abc-list">
# Precizno definisati optimalno stablo binarnog pretraživanja za ključeve sa vrednostima Kn < Kn+1 < ... < Km.
# Ako je ključ Kr koren ovog stabla, nacrtati opštu sliku.
# Izraziti cenu stabla preko cena njegovih podstabala.
</div>
=== Rešenje ===
<div class="abc-list">
# 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.
# [[Датотека:ASP2 K1 2014 Zadatak 8.png|thumb|600px|center|Opšta slika optimalnog stabla binarnog pretraživanja]]
# <math>C_{ij} = min\left \{ C_{i-1k-1} + C_{kj} \right \} + w_{ij}</math>.

<math>w_{ij} = q_{i} + p_{i+1} + q_{i+1} + ... + p_{j} + q_{j}</math>.

<math>i< k\leq j</math>
</div>
== Napomene ==
<references/>
[[Категорија:Рокови]]
[[Категорија:АСП2]]

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

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