KockaAdmiralac: Zapravo ispravka

2023-10-29T22:42:57Z

Zapravo ispravka

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

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

KockaAdmiralac: Ispravka linka

2023-10-29T22:41:08Z

Ispravka linka

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

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

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

DjoleRkc: Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1_0809.pdf Zadaci na stranici predmeta.] '''Prvi kolokvijum 2008. godine''' održan je 29. oktobra 2008. == 1. zadatak == === Postavka === '''(20p)''' Posmatra se niz celobrojnih ključeva, implementiran u vidu jednostruko ulančane liste. Ključevi se umeću u proizvoljnom redosledu, ali nije neophodno zadržati poredak. Potrebno je izabrati efikasnu metodu pretrage opisanog niza. Od interesa su sl…

2023-02-25T18:05:17Z

Нова страница: {{tocright}} [https://rti.etf.bg.ac.rs/rti/ri3sp/rokovi/SI2AS2_K1_0809.pdf Zadaci na stranici predmeta.] '''Prvi kolokvijum 2008. godine''' održan je 29. oktobra 2008. == 1. zadatak == === Postavka === '''(20p)''' Posmatra se niz celobrojnih ključeva, implementiran u vidu jednostruko ulančane liste. Ključevi se umeću u proizvoljnom redosledu, ali nije neophodno zadržati poredak. Potrebno je izabrati efikasnu metodu pretrage opisanog niza. Od interesa su sl…

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

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

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

== 1. zadatak ==
=== Postavka ===
'''(20p)''' Posmatra se niz celobrojnih ključeva, implementiran u vidu jednostruko ulančane liste. Ključevi se umeću u proizvoljnom redosledu, ali nije neophodno zadržati poredak. Potrebno je izabrati efikasnu metodu pretrage opisanog niza. Od interesa su sledeći parametri: brzina pretrage, brzina umetanja i brisanja ključa, vreme režije. Razmatraju se sledeći pristupi:
<div class="abc-list">
# Binarna pretraga
# Sekvencijalna pretraga sa transpozicijom ključeva
</div>
Komentarisati efikasnost ponuđenih metoda prema navedenim parametrima. Za metodu koja se proceni kao bolja skicirati postupak pretrage na jedan ključ.
=== Rešenje ===
<div class="abc-list">
# Za binarnu pretragu je neophodno čuvati uređenu listu, pa je i umetanje i brisanje ključa iste složenosti, kao i nalaženje ključa, što u slučaju ulančane liste nije dobra složenost (svodi se na sekvencijalnu pretragu).
# Sekvencijalna pretraga sa transpozicijom ključeva ima mnogo bolju složenost za datu strukturu - umetanje je O(1). Brisanje se svodi na nalaženje pa je složenost O(n), a pretraga je takođe O(n), sa mogućim ubrzanjem ukoliko se često pretražuju isti elementi.
</div>
[[Датотека:ASP2 K1 2008 Zadatak 1.svg|thumb|600px|center|Primer sekvencijalne pretrage na ključ 3 sa transpozicijom]]
== 2. zadatak ==
=== Postavka ===
'''(30p)''' U AVL stablo se redom umeću sledeći ključevi: 30, 12, 15, 14, 22, 35,18, 26, 32, 20, 33, 31, 24, 25, 28, 27. Nakon umetanja se redom brišu ključevi: 22, 15, 32. Prikazati izgled stabla nakon svake od navedenih izmena. '''Napomena''': prilikom brisanja ključeva, menjati im mesta sa prethodnicima.
=== 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 2008 Zadatak 2 umetanje.svg|thumb|600px|center|Stablo nakon svih umetanja]]
[[Датотека:ASP2 K1 2008 Zadatak 2 brisanje.svg|thumb|600px|center|Stablo nakon svih brisanje]]
== 3. zadatak ==
=== Postavka ===
'''(20p)''' Skicirati i objasniti algoritam određivanja prethodnika zadatog čvora u stablu binarnog pretraživanja. Ilustrovati primerima različite slučajeve.
=== 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]]
== 4. zadatak ==
=== Postavka ===
'''(30p)''' Pitanja:
<div class="abc-list">
# Objasniti šta su samopodešavajuća stabla, princip na kojem su zasnovana i diskutovati performanse.
# Zašto se uvode 2-3 stabla? Objasniti njihovu organizaciju i glavne osobine.
# Definisati optimalno stablo binarnog pretraživanja i navesti osnovnu osobinu na kojoj se zasniva algoritam za njegovo određivanje.
</div>
=== Rešenje ===
<div class="abc-list">
# Samopodešavajuća stabla su stabla binarnog pretraživanja kod kojih se raspored ključeva zasniva na vremenskoj lokalnosti. To znači da se prilikom svake operacije (umetanje, brisanje i pretraga) traženi ključ, ili njemu najbliži (ukoliko je u pitanju neuspešna operacija) prebaci u koren nizom rotacija zig ili zag tipa. Složenost je O(n) u najgorem slučaju, jer se ne garantuje balansiranost stabla (nemaju nikakav kriterijum balansiranosti).
# <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]]

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

KockaAdmiralac: Zapravo ispravka

KockaAdmiralac: Ispravka linka