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

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

2024-09-13T00:09:05Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 14:		Ред 14:
	# Strategija binarnog pretraživanja se zasniva na nalaženju medijane, a zatim polovljenju intervala pretraživanja. Postupak se ponavla sve dok se ne nađe traženi ključ ili se zaključi da se on ne nalazi u nizu. Preduslovi su da je niz uređen i da je moguć linearan pristup. Struktura mora biti linearna.		# Strategija binarnog pretraživanja se zasniva na nalaženju medijane, a zatim polovljenju intervala pretraživanja. Postupak se ponavla sve dok se ne nađe traženi ključ ili se zaključi da se on ne nalazi u nizu. Preduslovi su da je niz uređen i da je moguć linearan pristup. Struktura mora biti linearna.
	# Pri pretrazi na ključ 14 vrše se 4 poređenja, kao i pri pretrazi na ključ 18. Pri pretrazi na ključ 7 vrše se 2 poređenja, što nam u proseku daje <math>\frac{10}{3} = 3.33</math> poređenja.		# Pri pretrazi na ključ 14 vrše se 4 poređenja, kao i pri pretrazi na ključ 18. Pri pretrazi na ključ 7 vrše se 2 poređenja, što nam u proseku daje <math>\frac{10}{3} = 3.33</math> poređenja.
	# <~~syntaxhighlight lang="milo"~~>		# {{Милокод\|<nowiki>
	BIN(arr, key, n)		BIN(arr, key, n)
	high = n;		high = n;
Ред 25:		Ред 25:
	end_while		end_while
	return -1;		return -1;
	</~~syntaxhighlight~~>		</nowiki>}}
	</div>		</div>
	== 2. zadatak ==		== 2. zadatak ==
Ред 43:		Ред 43:
	=== 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;
Ред 53:		Ред 53:
	end_while		end_while
	return P;		return P;
	</~~syntaxhighlight~~>		</nowiki>}}
	== 4. zadatak ==		== 4. zadatak ==
	=== Postavka ===		=== Postavka ===

KockaAdmiralac: Zapravo ispravka

2023-10-29T22:43:11Z

Zapravo ispravka

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

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

KockaAdmiralac: Ispravka linka

2023-10-29T22:42:01Z

Ispravka linka

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

	~~'''Prvi kolokvijum 2009. godine''' održan je 29. oktobra 2009.~~

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

DjoleRkc: Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1_0910.pdf Zadaci na stranici predmeta.] '''Prvi kolokvijum 2009. godine''' održan je 29. oktobra 2009. == 1. zadatak == === Postavka === '''(20p)'''
# Objasniti strategiju binarnog pretraživanja. Koji su preduslovi primene binarne pretrage? Koje uslove mora da zadovolji struktura podataka nad kojom se primenjuje binarno pretraživanje da bi primena bila efikasna? # Nad ta…

2023-02-25T19:36:50Z

Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1_0910.pdf Zadaci na stranici predmeta.] '''Prvi kolokvijum 2009. godine''' održan je 29. oktobra 2009. == 1. zadatak == === Postavka === '''(20p)''' <div class="abc-list"> # Objasniti strategiju binarnog pretraživanja. Koji su preduslovi primene binarne pretrage? Koje uslove mora da zadovolji struktura podataka nad kojom se primenjuje binarno pretraživanje da bi primena bila efikasna? # Nad ta…

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

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

'''Prvi kolokvijum 2009. godine''' održan je 29. oktobra 2009.

== 1. zadatak ==
=== Postavka ===
'''(20p)'''
<div class="abc-list">
# Objasniti strategiju binarnog pretraživanja. Koji su preduslovi primene binarne pretrage? Koje uslove mora da zadovolji struktura podataka nad kojom se primenjuje binarno pretraživanje da bi primena bila efikasna?
# Nad tabelom u koju su umetnuti ključevi 2, 18, 33, 14, 25, 5, 7, 12, 11, 16, 20, 22, 26 se vrši pretraga na ključeve 14, 7 i 18 primenom strategije binarnog pretraživanja. Odrediti prosečan broj poređenja vrednosti ključeva.
# Napisati na jeziku C (ili C++) funkciju koja u zadatom nizu celih brojeva zadate dužine traži zadati celobrojni ključ. Funkcija vraća indeks pod kojim je ključ nađen u nizu ili -1 u slučaju neuspešne pretrage.
</div>
=== Rešenje ===
<div class="abc-list">
# Strategija binarnog pretraživanja se zasniva na nalaženju medijane, a zatim polovljenju intervala pretraživanja. Postupak se ponavla sve dok se ne nađe traženi ključ ili se zaključi da se on ne nalazi u nizu. Preduslovi su da je niz uređen i da je moguć linearan pristup. Struktura mora biti linearna.
# Pri pretrazi na ključ 14 vrše se 4 poređenja, kao i pri pretrazi na ključ 18. Pri pretrazi na ključ 7 vrše se 2 poređenja, što nam u proseku daje <math>\frac{10}{3} = 3.33</math> poređenja.
# <syntaxhighlight lang="milo">
BIN(arr, key, n)
high = n;
low = 1;
while(high>=low)
mid = (low+high)/2;
if(arr[mid]=key) return mid;
if(arr[mid]<key) low = mid+1;
else high = mid-1;
end_while
return -1;
</syntaxhighlight>
</div>
== 2. zadatak ==
=== Postavka ===
'''(30p)''' U AVL stablo prikazano na slici se redom umeću sledeći ključevi: 20, 21, 19, 7, 10, 12, 14. Nakon umetanja se redom brišu ključevi: 22, 15, 18. Prikazati izgled stabla nakon svake od navedenih izmena. Izračunati prosečan broj pristupa stablu prilikom uspešne pretrage nakon svih umetanja i u konačnom stanju. '''Napomena''': prilikom brisanja ključeva, koristiti sledbenike.
[[Датотека:ASP2 K1 2009 Zadatak 2.png|thumb|600px|center|Stablo iz postavke zadatka]]
=== Rešenje ===
[[Датотека:ASP2 K1 2009 Zadatak 2 umetanje.svg|thumb|600px|center|Stablo nakon svih umetanja]]
[[Датотека:ASP2 K1 2009 Zadatak 2 brisanje.svg|thumb|600px|center|Stablo nakon svih brisanja]]
Nakon svih umetanja: <math>PI = \sum R_{i} \cdot n_{i} = 3\cdot5 + 4\cdot4 + 4\cdot3 + 5 = 15+16+12+5=48</math>, pa je <math>S_{n} = \frac{48}{14} = 3.43</math>

Nakon svih brisanja: <math>PI = \sum R_{i} \cdot n_{i} = 33</math>, pa je <math>S_{n} = \frac{33}{11} = 3</math>.

== 3. zadatak ==
=== Postavka ===
'''(20p)''' Dati pseudokod i objasniti algoritam za istovremeno sekvencijalno pretraživanje uređenog niza na više ključeva. Kolika je složenost algoritma?
=== 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>
== 4. zadatak ==
=== Postavka ===
'''(30p)''' Pitanja:
<div class="abc-list">
# Kolike su performanse pretraživanja u stablu binarnog pretraživanja u najboljem, srednjem i najgorem slučaju i diskutovati implikacije.
# Definisati Fibonacci-jeva stabla i navesti njihove glavne osobine.
# Zašto se uvode 2-3 stabla? Objasniti njihovu organizaciju i glavne osobine.
</div>
=== Rešenje ===
<div class="abc-list">
# Složenost je u funkciji visine - O(h). U najboljem slučaju h = log(n), a u najgorem h = n.
# Fibonačijevo stablo je najgori slučaj AVL stabla, tj. stablo najveće visine za određen broj čvorova. Broj čvorova u Fibonačijevom stablu visine h je <math>n_{h} = n_{h-1} + n_{h-2} + 1</math>. Svi čvorovi imaju balans 1. Brisanje bilo kog čvora smanjuje visinu stabla. Svaki koren će biti Fibonačijev broj.
# 2-3 stabla se uvode da bi se osigurala balansiranost, pa su sve operacije O(log(n)). Glavno svojstvo je postojanje 3-čvorova, koji imaju levo, desno i srednje podstablo, i time se omogućava da svi listovi budu na istom nivou. 3-čvorovi imaju dva ključa, K1 i K2 i u zavisnosti od intervala pripadanja određujemo podstablo.
</div>

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