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

2024-09-13T00:09:06Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 7:		Ред 7:
	=== Rešenje ===		=== Rešenje ===
	Vremenska složenost je <math>O(log_3{n})</math>, a prostorna <math>O(n)</math>.		Vremenska složenost je <math>O(log_3{n})</math>, a prostorna <math>O(n)</math>.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FUN(arr,key)		FUN(arr,key)
	high = n;		high = n;
Ред 24:		Ред 24:
	end_while		end_while
	return 0;		return 0;
	</~~syntaxhighlight~~>		</nowiki>}}
	== 2. zadatak ==		== 2. zadatak ==
	=== Postavka ===		=== Postavka ===

KockaAdmiralac: Ispravka linka

2023-10-29T22:39:11Z

Ispravka linka

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

	~~'''Prvi kolokvijum 2011. godine''' održan je 24. oktobra 2011.~~
	== 1. zadatak ==		== 1. zadatak ==
	=== Postavka ===		=== Postavka ===

DjoleRkc: Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1_1112.pdf Zadaci na stranici predmeta.] '''Prvi kolokvijum 2011. godine''' održan je 24. oktobra 2011. == 1. zadatak == === Postavka === '''(30p)''' Koristeći algoritam binarne pretrage uređenog vektora kao osnovu, napisati na jeziku C (ili C++) funkciju za pretragu uređenog vektora jedinstvenih celobrojnih ključeva dužine n na zadati ključ deljenjem intervala pretrage na tri podintervala pr…

2023-02-25T13:06:56Z

Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1_1112.pdf Zadaci na stranici predmeta.] '''Prvi kolokvijum 2011. godine''' održan je 24. oktobra 2011. == 1. zadatak == === Postavka === '''(30p)''' Koristeći algoritam binarne pretrage uređenog vektora kao osnovu, napisati na jeziku C (ili C++) funkciju za pretragu uređenog vektora jedinstvenih celobrojnih ključeva dužine n na zadati ključ deljenjem intervala pretrage na tri podintervala pr…

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

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

'''Prvi kolokvijum 2011. godine''' održan je 24. oktobra 2011.
== 1. zadatak ==
=== Postavka ===
'''(30p)''' Koristeći algoritam binarne pretrage uređenog vektora kao osnovu, napisati na jeziku C (ili C++) funkciju za pretragu uređenog vektora jedinstvenih celobrojnih ključeva dužine n na zadati ključ deljenjem intervala pretrage na tri podintervala približno jednake dužine. Napisati glavni program koji demonstrira upotrebu prethodne funkcije. Koristiti fiksne podatke (nije potrebno čitati podatke iz datoteke ili standardnog ulaza). Komentarisati vremensku i prostornu složenost napisane funkcije. Porediti vremensku složenost napisane funkcije i algoritma binarne pretrage.
=== Rešenje ===
Vremenska složenost je <math>O(log_3{n})</math>, a prostorna <math>O(n)</math>.
<syntaxhighlight lang="milo">
FUN(arr,key)
high = n;
low = 1;
while(low <= high)
left = (low+high)/3;
right = 2(low+high)/3;
if(arr[left]=key) return left;
if(arr[right]=key) return right;
if(key < arr[left]) high = left-1;
if(key > arr[right]) low = right+1;
if(key>arr[left] and key<arr[right])
low = left+1;
high = right-1;
end_if
end_while
return 0;
</syntaxhighlight>
== 2. zadatak ==
=== Postavka ===
'''(20p)''' U stablo binarnog pretraživanja se redom umeću sledeći ključevi: 22, 31, 24, 28, 26, 41, 45, 10, 6, 8, 9, 7, 4, 5, 2. Nakon umetanja se redom brišu ključevi: 41, 6, 22, 10. Prikazati izgled stabla pretraživanja nakon svake od navedenih izmena. Ako dobijeno stablo ne zadovoljava kriterijum balansiranosti AVL stabla, transformisati stablo primenom osnovnih transformacija za održavanje balansiranosti da bi se dobilo AVL stablo. Prikazati izgled stabla nakon primene svake transformacije. Napomena: prilikom brisanja ključeva, koristiti sledbenike.
=== Rešenje ===
[[Датотека:ASP K1 2011 Zadatak 2.svg|thumb|600px|center|Stablo nakon umetanja ključeva 22,31,24,28,26 i 41]]
[[Датотека:ASP K1 2011 Zadatak 2 korak 2.svg|thumb|600px|center|Stablo nakon umetanja ključeva 45,10,6 i 8]]
[[Датотека:ASP K1 2011 Zadatak 2 korak 3.svg|thumb|600px|center|Stablo nakon umetanja ključeva 9 i 7]]
[[Датотека:ASP K1 2011 Zadatak 2 korak 4.svg|thumb|600px|center|Stablo nakon umetanja ključeva 4 i 5]]
[[Датотека:ASP K1 2011 Zadatak 2 korak 5.svg|thumb|600px|center|Stablo nakon svih umetanja]]
[[Датотека:ASP K1 2011 Zadatak 2 korak 6.svg|thumb|600px|center|Stablo nakon brisanja ključeva 41,6 i 22]]
[[Датотека:ASP K1 2011 Zadatak 2 korak 7.svg|thumb|600px|center|Stablo nakon svih brisanja]]
== 3. zadatak ==
=== Postavka ===
'''(20p)''' Definisati AVL stablo i kritični čvor. Kada se javlja potreba za dvostrukom rotacijom? Objasniti ovu operaciju i ilustrovati opštim slikama.
=== Rešenje ===
AVL stablo je stablo binarnog pretraživanja koje ispunjava kriterijum da svaki čvor mora da ima balans 0, 1 ili -1, gde balans predstavlja razliku visina levog i desnog podstabla.

Kritični čvor je koren najmanjeg podstabla koje nije visinski balansirano.

Dvostruka rotacija se vrši kada kritični čvor i sin sa one strane na koju naginje kritični čvor naginju na suprotne strane (npr kritični čvor na desno a njegov levi sin na levo). Prvo se vrši odgovarajuća rotacija nad sinom tako da kritični čvor i sin naginju na istu stranu, a zatim se vrši rotacija u suprotnu stranu nad kritičnim čvorom, čime se dobija visinski balansirano stablo.

[[Датотека:ASP K1 2011 Zadatak 3.svg|thumb|300px|center|Početno stanje]]
[[Датотека:ASP K1 2011 Zadatak 3 korak 2.svg|thumb|300px|center|Stablo nakon prve rotacije udesno oko sina]]
[[Датотека:ASP K1 2011 Zadatak 3 korak 3.svg|thumb|300px|center|Stablo nakon rotacije ulevo oko kritičnog čvora]]

== 4. zadatak ==
{{делимично решено}}
=== Postavka ===
'''(30p)''' Pitanja:
<div class="abc-list">
# Dati pseudokod i objasniti sekvencijalno pretraživanje sa graničnikom. Kakvo poboljšanje ono donosi?
# Objasniti organizaciju 2-3-4 stabla. Kakva je njihova prednost i kako se implementiraju?<ref>Ovo više nije gradivo K1</ref>
# Objasniti strategiju dobijanja približno optimalnog stabla koja uzima u obzir i uspešna i neuspešna pretraživanja.
</div>
=== Rešenje ===
c) Približno optimalno stablo se formira od korena na dole i bira se tako da se minimizira težina levog i desnog podstabla, a zatim se u blizini korena traži mogući novi koren sa većom verovatnoćom pristupa, i ako se takav čvor pronađe, pređašnji čvor se pomera malo ulevo ili udesno. Postupak se ponavlja rekurzivno.

== Napomene ==
<references/>
[[Категорија:Рокови]]
[[Категорија:АСП2]]

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

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

KockaAdmiralac: Ispravka linka