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

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

2024-09-13T00:09:10Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 200:		Ред 200:
	[[Датотека:ASP2 K1 2020 Zadatak 4a.svg\|thumb\|400px\|center\|Struktura indeksa]]		[[Датотека:ASP2 K1 2020 Zadatak 4a.svg\|thumb\|400px\|center\|Struktura indeksa]]

	# <~~syntaxhighlight lang="milo"~~>		# {{Милокод\|<nowiki>
	FIND KEY LIST(list, index, size, key)		FIND KEY LIST(list, index, size, key)
	int i=0;		int i=0;
Ред 212:		Ред 212:
	end_while		end_while
	end_for		end_for
	</~~syntaxhighlight~~>		</nowiki>}}
	</div>		</div>

Ред 237:		Ред 237:
	=== Rešenje ===		=== Rešenje ===
	U ovom rešenju su korišćene funkcije inicijalizacije, brisanja i dodavanja u red, kao i funkcija provere da li je red prazan, koje su podrazumevano znanje sa ASP1 i kao takve mogu da se koriste bez posebnog pseudokoda za te operacije.		U ovom rešenju su korišćene funkcije inicijalizacije, brisanja i dodavanja u red, kao i funkcija provere da li je red prazan, koje su podrazumevano znanje sa ASP1 i kao takve mogu da se koriste bez posebnog pseudokoda za te operacije.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	PRINT ALL BST(root)		PRINT ALL BST(root)
	Q.insert(root)		Q.insert(root)
Ред 247:		Ред 247:
	if(tr.right) Q.insert(tr.right)		if(tr.right) Q.insert(tr.right)
	end_while		end_while
	</~~syntaxhighlight~~>		</nowiki>}}

	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	CHECK(root)		CHECK(root)
	Q.insert(root, -∞,+∞)		Q.insert(root, -∞,+∞)
Ред 270:		Ред 270:
	root.bst=1		root.bst=1
	return		return
	</~~syntaxhighlight~~>		</nowiki>}}

	== 7. zadatak ==		== 7. zadatak ==
Ред 277:		Ред 277:
	=== Rešenje ===		=== Rešenje ===
	U rešenju se koristi binarno pretraživanje u tabeli nepoznate veličine.		U rešenju se koristi binarno pretraživanje u tabeli nepoznate veličine.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FIND FIRST POSITIVE(f)		FIND FIRST POSITIVE(f)
	int high=1;		int high=1;
Ред 290:		Ред 290:
	else low=mid+1;		else low=mid+1;
	end_while		end_while
	</~~syntaxhighlight~~>		</nowiki>}}

	== 8. zadatak ==		== 8. zadatak ==

KockaAdmiralac: /* Rešenje */ Ispravke imena fajlova

2023-11-01T09:33:11Z

Rešenje: Ispravke imena fajlova

← Старија измена		Верзија на датум 1. новембар 2023. у 11:33
Ред 223:		Ред 223:
	=== Rešenje ===		=== Rešenje ===
	U stablu se već nalazi ključ 33, tako da on ne treba da se ubacuje.		U stablu se već nalazi ključ 33, tako da on ne treba da se ubacuje.
	~~[[Датотека:~~ASP2 K1 2020 Zadatak 5 korak 1.svg~~\|thumb\|600px\|center~~\|Nakon umetanja ključa 30]]		<gallery>
	~~[[Датотека:~~ASP2 K1 2020 ~~Zadatak~~ 5 korak 2 ~~novi~~.svg~~\|thumb\|600px\|center~~\|Nakon brisanja ključa 29]]		ASP2 K1 2020 Zadatak 5 korak 1.svg \| Nakon umetanja ključa 30.
	~~[[Датотека:~~ASP2 K1 2020 Zadatak 5 korak 3.svg~~\|thumb\|600px\|center~~\|Nakon brisanja ključa 61]]		ASP2 K1 2020 zadatak 5 korak 2.svg \| Nakon brisanja ključa 29.
			ASP2 K1 2020 Zadatak 5 korak 3.svg \| Nakon brisanja ključa 61.
			</gallery>

	== 6. zadatak ==		== 6. zadatak ==

DjoleRkc: /* Rešenje */

2023-02-25T11:42:31Z

Rešenje

← Старија измена		Верзија на датум 25. фебруар 2023. у 13:42
Ред 222:		Ред 222:
	[[Датотека:ASP2 K1 2020 Zadatak 5.png\|thumb\|400px\|center\|Početno stanje]]		[[Датотека:ASP2 K1 2020 Zadatak 5.png\|thumb\|400px\|center\|Početno stanje]]
	=== Rešenje ===		=== Rešenje ===
			U stablu se već nalazi ključ 33, tako da on ne treba da se ubacuje.
	[[Датотека:ASP2 K1 2020 Zadatak 5 korak 1.svg\|thumb\|600px\|center\|Nakon umetanja ključa 30]]		[[Датотека:ASP2 K1 2020 Zadatak 5 korak 1.svg\|thumb\|600px\|center\|Nakon umetanja ključa 30]]
	[[Датотека:ASP2 K1 2020 Zadatak 5 korak 2 novi.svg\|thumb\|600px\|center\|Nakon brisanja ključa 29]]		[[Датотека:ASP2 K1 2020 Zadatak 5 korak 2 novi.svg\|thumb\|600px\|center\|Nakon brisanja ključa 29]]
	[[Датотека:ASP2 K1 2020 Zadatak 5 korak 3.svg\|thumb\|600px\|center\|Nakon brisanja ključa 61]]		[[Датотека:ASP2 K1 2020 Zadatak 5 korak 3.svg\|thumb\|600px\|center\|Nakon brisanja ključa 61]]
	~~[[Датотека:ASP2 K1 2020 Zadatak 5 korak 4.svg\|thumb\|600px\|center\|Nakon umetanja ključa 33]]~~

	== 6. zadatak ==		== 6. zadatak ==

DjoleRkc у 15:50, 23. фебруар 2023.

2023-02-23T15:50:39Z

← Старија измена		Верзија на датум 23. фебруар 2023. у 17:50
Ред 2:		Ред 2:
	[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_2021.pdf Zadaci na stranici predmeta.]		[https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_2021.pdf Zadaci na stranici predmeta.]

	'''Prvi kolokvijum 2020. godine''' održan je 3. novembra.		'''Prvi kolokvijum 2020. godine''' održan je 3. novembra 2020.

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

DjoleRkc: Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_2021.pdf Zadaci na stranici predmeta.] '''Prvi kolokvijum 2020. godine''' održan je 3. novembra. == 1. zadatak == === Postavka === '''(10p)''' Posmatra se tabela celobrojnih ključeva data na slici. Prikazati izgled tabele u svakom koraku prilikom pretrage na skup ključeva {25, 40, 25, 40} metodom transpozicije kao i metodom prebacivanja na početak i u oba slučaja izračunati prosečan bro…

2023-02-23T15:43:36Z

Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/13S112ASP2_K1_2021.pdf Zadaci na stranici predmeta.] '''Prvi kolokvijum 2020. godine''' održan je 3. novembra. == 1. zadatak == === Postavka === '''(10p)''' Posmatra se tabela celobrojnih ključeva data na slici. Prikazati izgled tabele u svakom koraku prilikom pretrage na skup ključeva {25, 40, 25, 40} metodom transpozicije kao i metodom prebacivanja na početak i u oba slučaja izračunati prosečan bro…

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

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

'''Prvi kolokvijum 2020. godine''' održan je 3. novembra.

== 1. zadatak ==
=== Postavka ===
'''(10p)''' Posmatra se tabela celobrojnih ključeva data na slici. Prikazati izgled tabele u svakom
koraku prilikom pretrage na skup ključeva {25, 40, 25, 40} metodom transpozicije kao i
metodom prebacivanja na početak i u oba slučaja izračunati prosečan broj poređenja
prilikom pretraživanja.

{| class="wikitable"
|+ Stanje niza iz postavke zadatka
! 12
! 7
! 3
! 27
! 25
! 78
! 98
! 21
! 22
! 40
! 51
|}
=== Rešenje ===
'''Transpozicija:'''
{| class="wikitable"
|+ Stanje niza nakon pretrage na ključ 25
! 12
! 7
! 3
! 25
! 27
! 78
! 98
! 21
! 22
! 40
! 51
|}

Broj poređenja u ovom koraku - 5

{| class="wikitable"
|+ Stanje niza nakon pretrage na ključ 40
! 12
! 7
! 3
! 25
! 27
! 78
! 98
! 21
! 40
! 22
! 51
|}

Broj poređenja u ovom koraku - 10

{| class="wikitable"
|+ Stanje niza nakon pretrage na ključ 25
! 12
! 7
! 25
! 3
! 27
! 78
! 98
! 21
! 40
! 22
! 51
|}

Broj poređenja u ovom koraku - 4

{| class="wikitable"
|+ Stanje niza nakon pretrage na ključ 40
! 12
! 7
! 25
! 3
! 27
! 78
! 98
! 40
! 21
! 22
! 51
|}

Broj poređenja u ovom koraku - 9

Prosečan broj poređenja: <math>\frac{5+10+4+9}{4} = \frac{28}{4} = 7</math>

'''Prebacivanje na početak:'''
{| class="wikitable"
|+ Stanje niza nakon pretrage na ključ 25
! 25
! 12
! 7
! 3
! 27
! 78
! 98
! 21
! 22
! 40
! 51
|}

Broj poređenja u ovom koraku - 5

{| class="wikitable"
|+ Stanje niza nakon pretrage na ključ 40
! 40
! 25
! 12
! 7
! 3
! 27
! 78
! 98
! 21
! 22
! 51
|}

Broj poređenja u ovom koraku - 10

{| class="wikitable"
|+ Stanje niza nakon pretrage na ključ 25
! 25
! 40
! 12
! 7
! 3
! 27
! 78
! 98
! 21
! 22
! 51
|}

Broj poređenja u ovom koraku - 2

{| class="wikitable"
|+ Stanje niza nakon pretrage na ključ 40
! 40
! 25
! 12
! 7
! 3
! 27
! 78
! 98
! 21
! 22
! 51
|}

Broj poređenja u ovom koraku - 2

Prosečan broj poređenja: <math>\frac{5+10+2+2}{4} = \frac{19}{4} = 4.75</math>

== 2. zadatak ==
=== Postavka ===
'''(10p)''' Ukratko objasniti i ilustrovati primerima slučajeve pronalaženja čvora prethodnika po
inorder poretku za zadati čvor u stablu binarnog pretraživanja.
=== Rešenje ===
Ukoliko čvor ima levo podstablo, njegov prethodnik je najdešnji potomak njegovog levog sina, a ukoliko nema levo podstablo, njegov prethodnik je njegov najniži predak čiji je desni sin takođe njegov predak. U primeru ispod, prethodnik od 3 je 1, a prethodnik od 6 je 5.

[[Датотека:ASP2 K1 2020 Zadatak 1.svg|thumb|600px|center|Primer]]
== 3. zadatak ==
=== Postavka ===
'''(15p)''' U AVL stablo sa slike se redom umeću ključevi 44, 72, 19, 22, 21, 5 i 1, nakon čega se
uklanjaju ključevi 23 i 39. Prikazati stanja stabla nakon svake promene.<ref> Prepisivač ovog roka je zaboravio kako se postupno radi umetanje i brisanje, tako da su dostupna rešenja samo posle svih umetanja i posle svih brisanja (u prevodu nisam radio postupno)</ref>
[[Датотека:ASP2 K1 2020 Zadatak 3 Pocetno.svg|thumb|400px|center|Početno stanje]]
=== Rešenje ===
[[Датотека:ASP2 K1 2020 Zadatak 3 Posle umetanja.svg|thumb|400px|center|Posle svih umetanja]]

[[Датотека:ASP2 K1 2020 Zadatak 3 Posle brisanja.svg|thumb|400px|center|Posle svih brisanja]]
== 4. zadatak ==
=== Postavka ===
'''(15p)''' Neka je data velika, uređena jednostruko ulančana lista list koju treba pretražiti na zadati
ključ key. Kao pomoćna struktura, raspoloživ je indeks index veličine size.
<div class="abc-list">
# '''(5p)''' Objasniti i nacrtati strukturu indeksa i način povezivanja sa listom koja se pretražuje.
# '''(10p)''' Napisati u pseudokodu implementaciju funkcije za sekvencijalnu pretragu liste list uz korišćenje indeksa index na ključ key.
</div>
=== Rešenje ===
<div class="abc-list">
# Struktura index predstavlja niz čvorova koji sadrže informaciono polje sa vrednošću pronađenih ključeva i polje-pokazivač na taj pronađen ključ. Struktura index se čuva uređenom.
[[Датотека:ASP2 K1 2020 Zadatak 4a.svg|thumb|400px|center|Struktura indeksa]]

# <syntaxhighlight lang="milo">
FIND KEY LIST(list, index, size, key)
int i=0;
for(i<size)
if(key<index[i].info) Node poc = index[i];
if(key>=index[i].info) break;
while(poc!=nil)
if(key==poc.info) return poc;
if(key>poc.info) return nil;
poc=poc.next
end_while
end_for
</syntaxhighlight>
</div>

== 5. zadatak ==
=== Postavka ===
'''(10p)''' Neka se u dato samopodešavajuće stablo ubacuje ključ 30, nakon čega se brišu ključevi
29 i 61, i na kraju se ubacuje ključ 33. Prikazati izgled stabla nakon svakog izvršenog koraka
pri umetanju i brisanju.
[[Датотека:ASP2 K1 2020 Zadatak 5.png|thumb|400px|center|Početno stanje]]
=== Rešenje ===
[[Датотека:ASP2 K1 2020 Zadatak 5 korak 1.svg|thumb|600px|center|Nakon umetanja ključa 30]]
[[Датотека:ASP2 K1 2020 Zadatak 5 korak 2 novi.svg|thumb|600px|center|Nakon brisanja ključa 29]]
[[Датотека:ASP2 K1 2020 Zadatak 5 korak 3.svg|thumb|600px|center|Nakon brisanja ključa 61]]
[[Датотека:ASP2 K1 2020 Zadatak 5 korak 4.svg|thumb|600px|center|Nakon umetanja ključa 33]]

== 6. zadatak ==
=== Postavka ===
'''(15p)''' Napisati u pseudokodu implementaciju funkcije koja u datom binarnom stablu na čiji
koren ukazuje pokazivač root pronalazi i ispisuje adrese korenova svih podstabala koja
zadovoljavaju osobine stabla binarnog pretraživanja. Dozvoljeno je uvoditi dodatna polja u
čvor stabla koja mogu olakšati implementaciju funkcije.
=== Rešenje ===
U ovom rešenju su korišćene funkcije inicijalizacije, brisanja i dodavanja u red, kao i funkcija provere da li je red prazan, koje su podrazumevano znanje sa ASP1 i kao takve mogu da se koriste bez posebnog pseudokoda za te operacije.
<syntaxhighlight lang="milo">
PRINT ALL BST(root)
Q.insert(root)
while(!Q.empty())
tr = Q.delete
CHECK(tr)
if(tr.bst) print(tr)
if(tr.left) Q.insert(tr.left)
if(tr.right) Q.insert(tr.right)
end_while
</syntaxhighlight>

<syntaxhighlight lang="milo">
CHECK(root)
Q.insert(root, -∞,+∞)
while(!Q.empty())
{tr,min.max} = Q.delete
if(tr.left)
if(tr.left.info < min || tr.left.info > tr.info)
root.bst = 0
return
end_if
Q.insert(tr.left,min,tr.info)
end_if
if(tr.right)
if(tr.right.info < key || tr.right.info > tr.info)
root.bst = 0
return
end_if
end_if
end_while
root.bst=1
return
</syntaxhighlight>

== 7. zadatak ==
=== Postavka ===
'''(15p)''' Neka se posmatra jedna strogo monotono rastuća funkcija f(x). Na primer,<math>x^3 - 3x^2 +6x - 1</math> ili <math>3^x</math>. Korišćenjem strategije binarnog pretraživanja, napisati u pseudokodu iterativnu implementaciju funkcije koja pronalazi vrednost n za koju funkcija f(x) postaje pozitivna prvi put, ukoliko važi da je x ≥ 0. Kratko objasniti postupak.
=== Rešenje ===
U rešenju se koristi binarno pretraživanje u tabeli nepoznate veličine.
<syntaxhighlight lang="milo">
FIND FIRST POSITIVE(f)
int high=1;
while(f(high)<0)
high *= 2;
end_while
int low = high/2;
while(low<=high)
mid = (high+low)/2;
if(f(mid)>=0 && f(mid-1)<0) return mid;
if(f(mid)>0) high = mid-1;
else low=mid+1;
end_while
</syntaxhighlight>

== 8. zadatak ==
=== Postavka ===
'''(10p)''' Analiza performansi stabla binarnog pretraživanja.
<div class="abc-list">
# '''(5p)''' Formalno definisati i objasniti prosečan broj poređenja Sn prilikom uspešnog pretraživanja i prosečan broj poređenja Un prilikom neuspešnog pretraživanja u stablu binarnog pretraživanja koje je nastalo umetanjem n čvorova u proizvoljnom poretku.
# '''(5p)''' Izvesti i kratko objasniti vezu između Sn i Un koji su definisani pod a). Odgovor ilustrovati slikom.
</div>
=== Rešenje ===
<div class="abc-list">
# Sn možemo predstaviti kao <math> Sn = (PI + n)/n</math>, jer ima za 1 više poređenja nego čvorova, a Un možemo predstaviti kao <math> Un = PE/n_{e} = PE/(n+1)</math>.
# <math>PE = PI + 2n</math>

<math>Un(n+1) - 2n = PI</math>

<math>Sn = (Un \frac{n+1}{n}) - 1</math>
</div>
== Napomene ==
<references/>


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