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

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

2024-09-13T00:09:01Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 7:		Ред 7:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	BIN TREE WIDTH(root)		BIN TREE WIDTH(root)
	curr_width = max_width = 0		curr_width = max_width = 0
Ред 55:		Ред 55:
	end_while		end_while
	return max_width		return max_width
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	GETNODE(value)		GETNODE(value)
	ALLOCATE(node)		ALLOCATE(node)
Ред 62:		Ред 62:
	value(node) = value		value(node) = value
	return node		return node
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FREENODE(node)		FREENODE(node)
	DEALLOCATE(node)		DEALLOCATE(node)
	</~~syntaxhighlight~~>		</nowiki>}}

	== 2. zadatak ==		== 2. zadatak ==
Ред 196:		Ред 196:
	=== Rešenje ===		=== Rešenje ===
	Uvodimo polje kojem nam govori koliko se u levom podstablu tog čvora nalazi čvorova. Na taj način možemo da, kad dođemo do nekog čvora, odlučimo da li dalje idemo u njegovo levo ili desno podstablo u zavisnosti od toga da li je broj čvorova u levom podstablu veći ili manji od trenutnog broja traženih čvorova. Na početku procesiranja svakog čvora smanjujemo trenutno traženi broj čvorova i vraćamo trenutni čvor ukoliko je jednak 1.		Uvodimo polje kojem nam govori koliko se u levom podstablu tog čvora nalazi čvorova. Na taj način možemo da, kad dođemo do nekog čvora, odlučimo da li dalje idemo u njegovo levo ili desno podstablo u zavisnosti od toga da li je broj čvorova u levom podstablu veći ili manji od trenutnog broja traženih čvorova. Na početku procesiranja svakog čvora smanjujemo trenutno traženi broj čvorova i vraćamo trenutni čvor ukoliko je jednak 1.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	PREORDER K NODE(root, k)		PREORDER K NODE(root, k)
	next = root		next = root
Ред 212:		Ред 212:
	end_if		end_if
	end_loop		end_loop
	</~~syntaxhighlight~~>		</nowiki>}}

	== 7. zadatak ==		== 7. zadatak ==
Ред 224:		Ред 224:
	=== Rešenje ===		=== Rešenje ===
	Možemo da, nalik povezanim stablima, uvedemo ''rf'' bit koji će biti postavljen na 1 ukoliko desni pokazivač pokazuje na brata trenutnog čvora ili postavljen na 0 ukoliko pokazuje na prvog brata svog roditelja, i zatim sve neiskorišćene desne pokazivače (osim korena) povežemo na prvu braću svojih roditelja. Na taj način svi čvorovi jednog nivoa imaće pristup svim čvorovima narednog nivoa.		Možemo da, nalik povezanim stablima, uvedemo ''rf'' bit koji će biti postavljen na 1 ukoliko desni pokazivač pokazuje na brata trenutnog čvora ili postavljen na 0 ukoliko pokazuje na prvog brata svog roditelja, i zatim sve neiskorišćene desne pokazivače (osim korena) povežemo na prvu braću svojih roditelja. Na taj način svi čvorovi jednog nivoa imaće pristup svim čvorovima narednog nivoa.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	NODE LEVEL(adr)		NODE LEVEL(adr)
	level = 1		level = 1
Ред 235:		Ред 235:
	end_while		end_while
	return level		return level
	</~~syntaxhighlight~~>		</nowiki>}}

	== 8. zadatak ==		== 8. zadatak ==
Ред 247:		Ред 247:
	=== Rešenje ===		=== Rešenje ===
	Graf koji nam je potreban je netežinski usmeren graf u kojem čvorovi predstavljaju knjige a grane reference na knjige, gde grana od A ka B označava da knjiga A sadrži referencu na knjigu B. Optimalna memorijska predstava bi bila preko inverzne liste susednosti, gde je dodatna optimizacija čuvanje dužine te liste u njenom zaglavlju. Pseudokod ispod ne računa tu optimizaciju:		Graf koji nam je potreban je netežinski usmeren graf u kojem čvorovi predstavljaju knjige a grane reference na knjige, gde grana od A ka B označava da knjiga A sadrži referencu na knjigu B. Optimalna memorijska predstava bi bila preko inverzne liste susednosti, gde je dodatna optimizacija čuvanje dužine te liste u njenom zaglavlju. Pseudokod ispod ne računa tu optimizaciju:
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	REF COUNT(k)		REF COUNT(k)
	ref_number = 0		ref_number = 0
Ред 256:		Ред 256:
	end_while		end_while
	return ref_number		return ref_number
	</~~syntaxhighlight~~>		</nowiki>}}

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

KockaAdmiralac: Prebacivanje na jednostavno isticanje sintakse

2020-08-28T09:41:06Z

Prebacivanje na jednostavno isticanje sintakse

Прикажи измене

KockaAdmiralac: Kategorizacija

2020-07-27T09:59:04Z

Kategorizacija

← Старија измена		Верзија на датум 27. јул 2020. у 11:59
Ред 249:		Ред 249:

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

KockaAdmiralac: lista susednosti -> inverzna lista susednosti

2020-06-10T14:28:31Z

lista susednosti -> inverzna lista susednosti

← Старија измена		Верзија на датум 10. јун 2020. у 16:28
Ред 48:		Ред 48:
	FREENODE(''t'')		FREENODE(''t'')
	'''end_while'''		'''end_while'''
	'''while'''''max_level'' ≠ nil '''do'''		'''while''' ''max_level'' ≠ nil '''do'''
	''t'' = ''max_level''		''t'' = ''max_level''
	''max_level'' = ''next''(''max_level'')		''max_level'' = ''next''(''max_level'')
Ред 238:		Ред 238:

	=== Rešenje ===		=== Rešenje ===
	Graf koji nam je potreban je netežinski usmeren graf u kojem čvorovi predstavljaju knjige a grane reference na knjige, gde grana od A ka B označava da knjiga B sadrži referencu na knjigu A. Optimalna memorijska predstava bi bila preko liste susednosti, gde je dodatna optimizacija čuvanje dužine te liste u njenom zaglavlju. Pseudokod ispod ne računa tu optimizaciju:		Graf koji nam je potreban je netežinski usmeren graf u kojem čvorovi predstavljaju knjige a grane reference na knjige, gde grana od A ka B označava da knjiga A sadrži referencu na knjigu B. Optimalna memorijska predstava bi bila preko inverzne liste susednosti, gde je dodatna optimizacija čuvanje dužine te liste u njenom zaglavlju. Pseudokod ispod ne računa tu optimizaciju:
	<u>REF COUNT(''k'')</u>		<u>REF COUNT(''k'')</u>
	''ref_number'' = 0		''ref_number'' = 0
	''p'' = ''e''[''k'']		''p'' = ''IAL''[''k'']
	'''while''' ''p'' ≠ nil '''do'''		'''while''' ''p'' ≠ nil '''do'''
	''ref_number'' = ''ref_number'' + 1		''ref_number'' = ''ref_number'' + 1

KockaAdmiralac: Dodat osmi zadatak

2020-04-05T16:08:15Z

Dodat osmi zadatak

← Старија измена		Верзија на датум 5. април 2020. у 18:08
Ред 238:		Ред 238:

	=== Rešenje ===		=== Rešenje ===
			Graf koji nam je potreban je netežinski usmeren graf u kojem čvorovi predstavljaju knjige a grane reference na knjige, gde grana od A ka B označava da knjiga B sadrži referencu na knjigu A. Optimalna memorijska predstava bi bila preko liste susednosti, gde je dodatna optimizacija čuvanje dužine te liste u njenom zaglavlju. Pseudokod ispod ne računa tu optimizaciju:
			<u>REF COUNT(''k'')</u>
			''ref_number'' = 0
			''p'' = ''e''[''k'']
			'''while''' ''p'' ≠ nil '''do'''
			''ref_number'' = ''ref_number'' + 1
			''p'' = ''next''(''p'')
			'''end_while'''
			'''return''' ''ref_number''

	[[Категорија:Рокови]]		[[Категорија:Рокови]]

KockaAdmiralac: +kategorija

2020-04-05T15:36:03Z

+kategorija

← Старија измена		Верзија на датум 5. април 2020. у 17:36
Ред 238:		Ред 238:

	=== Rešenje ===		=== Rešenje ===

			[[Категорија:Рокови]]

KockaAdmiralac: Dodata rešenja

2020-03-27T23:05:15Z

Dodata rešenja

Прикажи измене

KockaAdmiralac: Pokrenuta strana

2020-03-27T19:56:10Z

Pokrenuta strana

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

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

== 1. zadatak ==
=== Postavka ===
Napisati u pseudokodu iterativnu funkciju koja određuje širinu binarnog stabla na čiji koren pokazuje pokazivač ''root''. Širina stabla se definiše kao najveća širina svih njegovih nivoa. Funkcija treba da ispiše sve čvorove na nivou najveće širine i vrati određenu širinu. Dozvoljena je upotreba gotovih linearnih struktura podataka

=== Rešenje ===

== 2. zadatak ==
=== Postavka ===
Posmatra se jedno binarno stablo.
<div class="abc-list">
# Objasniti šta su eksterni čvorovi stabla i za zadato binarno stablo odrediti broj eksternih čvorova. Eksterne čvorove docrtati na zadatom stablu.
# Izvesti i objasniti vezu između broja eksternih čvorova binarnog stabla ''e'' i čvorova stabla ''n''.
</div>

=== Rešenje ===

== 3. zadatak ==
=== Postavka ===
Primenom LZW algoritma, prikazati postupak kodiranja poruke ANTANANARIVE, za dati početni sadržaj tabele simbola. Napisati kodiranu poruku i izgled tabele simbola nakon postupka kodiranja

=== Rešenje ===

== 4. zadatak ==
=== Postavka ===
Korišćenjem dinamičkog ''Huffman'' algoritma dekodirati sledeću poruku 00001010010001101101 ako je poznato da su simbolima A, B i C dodeljeni kodovi fiksne dužine 00, 01 i 10 respektivno. Za dobijenu sekvencu karaktera predložiti njihov drugačiji raspored takav da se pri kodiranju izmenjene sekvence dobije što veća ušteda u memoriji (kraći kod). Izbor obrazložiti.

=== Rešenje ===

== 5. zadatak ==
=== Postavka ===
Ako za neko binarno stablo preorder obilazak daje poredak NMCOLAGFBDPRSHQ, a inorder obilazak COALGMBFNPHSRQD, rekonstruisati zadatog stabla.

=== Rešenje ===

== 6. zadatak ==
=== Postavka ===
Dato je binarno stablo na čiji koren pokazuje pokazivač ''root''. Treba pronaći čvor koji je ''k''-ti po ''preorder'' poretku, ali tako da se zapravo obiđe što manje čvorova.
<div class="abc-list">
# Dozvoljeno je uvođenje jednog dodatnog polja u čvor stabla, pored postojećih polja ''left'' i ''right'', radi što efikasnijeg iterativnog algoritma. Ukratko objasniti svrhu tog polja i algoritam za nalaženje ''k''-tog čvora.
# Napisati u pseudokodu funkciju koja vraća pokazivač na ''k''-ti čvor po ''preorder'' poretku na što je moguće efikasniji način.
</div>

=== Rešenje ===

== 7. zadatak ==
=== Postavka ===
Dato je odgovarajuće binarno stablo dobijeno konverzijom stabla višeg reda:
<div class="abc-list">
# Predložiti kako u stablo ugraditi informaciju koja omogućava kretanje uz stablo od listova ka korenu.
# Na osnovu gornjeg predloga napisati funkciju koja za čvor sa zadatom adresom ''adr'' vraća njegov nivo u stablu.
</div>

=== Rešenje ===

== 8. zadatak ==
=== Postavka ===
Na kraju svake knjige postoji lista referenci na druge knjige.
<div class="abc-list">
# Predložiti memorijsku predstavu grafa koji predstavlja referenciranje knjiga tako da je olakšano nalaženje broja referenci na neku knjigu.
# Na osnovu gornjeg predloga napisati funkciju koja za zadatu knjigu nalazi broj referenci na nju.
</div>

=== Rešenje ===