АСП1/Август 2021 - Историја измена

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

2024-09-13T00:08:42Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:08
Ред 20:		Ред 20:
	Zadato je binarno stablo S i date su adrese dva čvora ''x'' i ''y''. Napisati funkciju u pseudokodu koja pronalazi najnižeg zajedničkog pretka zadata dva čvora.		Zadato je binarno stablo S i date su adrese dva čvora ''x'' i ''y''. Napisati funkciju u pseudokodu koja pronalazi najnižeg zajedničkog pretka zadata dva čvora.
	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	LOWEST_COMMON_ANCESTOR(S,x,y)		LOWEST_COMMON_ANCESTOR(S,x,y)
	return FIND(S,x,y)		return FIND(S,x,y)
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FIND(S,x,y)		FIND(S,x,y)
	if S == null		if S == null
Ред 43:		Ред 43:
	return null		return null
	end_if		end_if
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==
Ред 57:		Ред 57:
	''Rešenje je krajnje trivijalno i ovde je navedeno jedno koje je bodovano maksimalnim brojem poena.''		''Rešenje je krajnje trivijalno i ovde je navedeno jedno koje je bodovano maksimalnim brojem poena.''
	Za oba se može koristiti jednostruko ulančana lista (jer nije bitan redosled kojim će se operacije izvršavati jer će se svakako sve izvršiti na svim slikama), a ulančane liste su pogodno za lako dodavanje i brisanje elemenata.		Za oba se može koristiti jednostruko ulančana lista (jer nije bitan redosled kojim će se operacije izvršavati jer će se svakako sve izvršiti na svim slikama), a ulančane liste su pogodno za lako dodavanje i brisanje elemenata.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	PROCESS_IMAGES(images, operations)		PROCESS_IMAGES(images, operations)
	S = head(images)		S = head(images)
Ред 66:		Ред 66:
	end_while		end_while
	end_while		end_while
	</~~syntaxhighlight~~>		</nowiki>}}
	== 6. zadatak ==		== 6. zadatak ==
	=== Postavka ===		=== Postavka ===

KockaAdmiralac: Link do zadatka

2022-02-20T15:38:00Z

Link do zadatka

← Старија измена		Верзија на датум 20. фебруар 2022. у 17:38
Ред 90:		Ред 90:
	</div>		</div>
	=== Rešenje ===		=== Rešenje ===
	Videti zadatak iz [[АСП1/Јул 2020#~~Treći kolokvijum~~\|julskog roka 2020.]]		Videti zadatak iz [[АСП1/Јул 2020#2. zadatak 3\|julskog roka 2020.]]

	== 10. zadatak ==		== 10. zadatak ==

Lukahrvacevic: /* 9. zadatak */

2022-02-20T15:35:52Z

9. zadatak

← Старија измена		Верзија на датум 20. фебруар 2022. у 17:35
Ред 90:		Ред 90:
	</div>		</div>
	=== Rešenje ===		=== Rešenje ===
	~~{{delimično rešeno}}~~		Videti zadatak iz [[АСП1/Јул 2020#Treći kolokvijum\|julskog roka 2020.]]

	== 10. zadatak ==		== 10. zadatak ==
	=== Postavka ===		=== Postavka ===

Lukahrvacevic: /* 3. zadatak */

2022-02-20T15:23:01Z

3. zadatak

← Старија измена		Верзија на датум 20. фебруар 2022. у 17:23
Ред 26:		Ред 26:
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	FIND(S,x,y)		FIND(S,x,y)
	if S==null		if S == null
	return null		return null
	end_if		end_if

Lukahrvacevic: /* 3. zadatak */

2022-02-20T15:17:27Z

3. zadatak

@@ Ред 17: / Ред 17: @@
 Potrebno je samo napisati i prokomentarisati tabelu 7.1 sa strane 161 iz udžbenika.
 == 3. zadatak ==
 === Postavka ===
 Zadato je binarno stablo S i date su adrese dva čvora ''x'' i ''y''. Napisati funkciju u pseudokodu koja pronalazi najnižeg zajedničkog pretka zadata dva čvora.
 === Rešenje ===
 == 4. zadatak ==
 === Postavka ===

TopOfKeks: formatiranje, ispravke

2021-09-18T09:32:45Z

formatiranje, ispravke

← Старија измена		Верзија на датум 18. септембар 2021. у 11:32
Ред 1:		Ред 1:
	{{tocright}}		{{tocright}}
	~~{{nerešeno}}~~
	Ovaj članak je rekreacija avgustovskog roka koji nije objavljen.		Ovaj članak je rekreacija avgustovskog roka koji nije objavljen.

	== 1. zadatak ==		== 1. zadatak ==
			{{delimično rešeno}}
	=== Postavka ===		=== Postavka ===
	Data je retka matrica koja je prikazana na slici. (Data je matrica npr. 5*6 sa 5 ili 6 random nenultih elemenata).		Data je retka matrica koja je prikazana na slici. (Data je matrica npr. 5*6 sa 5 ili 6 random nenultih elemenata).
	a) Nacrtati izgled delova memorije u kojima se čuva ova retka matrica, ako se primenjuje ''Compressed Sparse Row'' način čuvanja.		<div class="abc-list">
	b) Napisati funkciju u pseudokodu koja na osnovu sačuvane ''Compressed Sparse Row'' reprezentacije matrice M i unetog broja ''i'' štampa sve nenulte elemente ''i''-te vrste.		# Nacrtati izgled delova memorije u kojima se čuva ova retka matrica, ako se primenjuje ''Compressed Sparse Row'' način čuvanja.
			# Napisati funkciju u pseudokodu koja na osnovu sačuvane ''Compressed Sparse Row'' reprezentacije matrice M i unetog broja ''i'' štampa sve nenulte elemente ''i''-te vrste.
			</div>
	=== Rešenje ===		=== Rešenje ===
	== 2. zadatak ==		== 2. zadatak ==
Ред 13:		Ред 15:
	Navedite načine reprezentacije grafova i njihove prednosti i mane.		Navedite načine reprezentacije grafova i njihove prednosti i mane.
	=== Rešenje ===		=== Rešenje ===
	~~potrebno~~ je samo napisati i prokomentarisati tabelu 7.1 sa strane 161 iz udžbenika		Potrebno je samo napisati i prokomentarisati tabelu 7.1 sa strane 161 iz udžbenika.
	== 3. zadatak ==		== 3. zadatak ==
			{{delimično rešeno}}
	=== Postavka ===		=== Postavka ===
	Zadato je binarno stablo S i date su adrese dva čvora ''x'' i ''y''. Napisati funkciju u pseudokodu koja pronalazi najnižeg zajedničkog pretka zadata dva čvora.		Zadato je binarno stablo S i date su adrese dva čvora ''x'' i ''y''. Napisati funkciju u pseudokodu koja pronalazi najnižeg zajedničkog pretka zadata dva čvora.
Ред 22:		Ред 25:
	Potpuno formalno izvesti međusobnu zavisnost interne i eksterne dužine puta u binarnom stablu i kratko obrazložiti.		Potpuno formalno izvesti međusobnu zavisnost interne i eksterne dužine puta u binarnom stablu i kratko obrazložiti.
	=== Rešenje ===		=== Rešenje ===
	PE = PI + 2n, gde je n broj čvorova u stablu		<math> PE = PI + 2n </math>, gde je <math>n</math> broj čvorova u stablu
	izvođenje indukcijom, kao u knjizi/na predavanju		izvođenje indukcijom, kao u knjizi/na predavanju.
	== 5. zadatak ==		== 5. zadatak ==
	=== Postavka ===		=== Postavka ===
	Potrebno je realizovati aplikaciju za obradu slika. Korisniku je potrebno da za uneti set slika i unet set operacija omogućiti da se sve operacije izvrše nad svim unetim slikama. Navesti koje strukture je pogodno koristiti za čuvanje seta slika i seta operacija i objasniti zašto. Napisati ~~fuknciju~~ u ~~pesudokodu~~ koja obrađuje uneti set slika unetim setom operacija, u skladu sa odabranim strukturama podataka.		Potrebno je realizovati aplikaciju za obradu slika. Korisniku je potrebno da za uneti set slika i unet set operacija omogućiti da se sve operacije izvrše nad svim unetim slikama. Navesti koje strukture je pogodno koristiti za čuvanje seta slika i seta operacija i objasniti zašto. Napisati funkciju u pseudokodu koja obrađuje uneti set slika unetim setom operacija, u skladu sa odabranim strukturama podataka.
	=== Rešenje ===		=== Rešenje ===
	//''Rešenje je krajnje trivijalno i ovde je navedeno jedno koje je bodovano maksimalnim brojem poena''		''Rešenje je krajnje trivijalno i ovde je navedeno jedno koje je bodovano maksimalnim brojem poena.''
	Za oba se može koristiti jednostruko ulančana lista (jer nije bitan redosled kojim će se operacije izvršavati jer će se svakako sve izvršiti na svim slikama), a ulančane liste su pogodno za lako dodavanje i brisanje elemenata.		Za oba se može koristiti jednostruko ulančana lista (jer nije bitan redosled kojim će se operacije izvršavati jer će se svakako sve izvršiti na svim slikama), a ulančane liste su pogodno za lako dodavanje i brisanje elemenata.
	<syntaxhighlight lang="milo">		<syntaxhighlight lang="milo">
	~~OBRADI_SLIKE~~(~~slike~~, ~~operacije~~)		PROCESS_IMAGES(images, operations)
	s = ~~slike.~~head;		S = head(images)
	o = ~~operacije.~~head;		O = head(operations)
	while (s ~~!= NULL)~~		while s ≠ NIL do
	while (o ~~!= NULL)~~		while o ≠ NIL do
	~~s.info~~ = ~~o.operacija~~(~~s.info~~);		data(S) = (operation(O))(data(S))
			end_while
			end_while
	</syntaxhighlight>		</syntaxhighlight>
	== 6. zadatak ==		== 6. zadatak ==
Ред 46:		Ред 51:
	== 7. zadatak ==		== 7. zadatak ==
	=== Postavka ===		=== Postavka ===
	Dat je grad koji je ~~mnodelovan~~ usmerenim grafom, tako što su čvorovi lokacije u gradu (pekara, apoteka, biblioteka itd), a težine grana između čvorova vreme u minutima koje je potrebno da se peške dođe od izvorišne do odredišne lokacije. Dete želi da stigne od škole (čvor X) do kuće (čvor Y) najbrže moguće. Međutim, postoji opasan deo grada (čvor Z), koji nije bezbedan za decu i koji ona treba da izbegavaju. Napisati funkciju u pseudokodu koja na osnovu zadatog grafa G (nije data reprezentacija, ~~nego~~ treba ~~apstraktno~~ da ~~se piše~~), zadatih lokacija kuće i škole, Y i X, i opasnog dela grada Z, pronalazi najkraće vreme koje je detetu potrebno od škole do kuće.		Dat je grad koji je modelovan usmerenim grafom, tako što su čvorovi lokacije u gradu (pekara, apoteka, biblioteka itd), a težine grana između čvorova vreme u minutima koje je potrebno da se peške dođe od izvorišne do odredišne lokacije. Dete želi da stigne od škole (čvor ''X'') do kuće (čvor ''Y'') najbrže moguće. Međutim, postoji opasan deo grada (čvor Z), koji nije bezbedan za decu i koji ona treba da izbegavaju. Napisati funkciju u pseudokodu koja na osnovu zadatog grafa ''G'' (nije data reprezentacija, rešenje treba da bude konceptualno), zadatih lokacija kuće i škole, ''Y'' i ''X'', i opasnog dela grada ''Z'', pronalazi najkraće vreme koje je detetu potrebno od škole do kuće.
	=== Rešenje ===		=== Rešenje ===
	Zadatak se rešava implementacijom Dijkstrinog algortima, tako što kada se u uzimanju čvorova redom po težinskoj udaljenosti od početnog dođe do "opasnog" čvora z, za njega se ~~upise tezina~~ beskonačno i ta petlja preskoči sa continue. Na kraju se samo proveri dostižnost ciljnog čvora.		Zadatak se rešava implementacijom Dijkstrinog algortima, tako što kada se u uzimanju čvorova redom po težinskoj udaljenosti od početnog dođe do "opasnog" čvora ''Z'', za njega se upiše težina beskonačno i ta petlja preskoči sa '''continue'''. Na kraju se samo proveri dostižnost ciljnog čvora.
	== 8. zadatak ==		== 8. zadatak ==
	=== Postavka ===		=== Postavka ===
	Dat je graf na slici (ima nekih 7-8 čvorova). Za dati graf uraditi topološko sortiranje i prikazati graf dobijen tako.		Dat je graf na slici (ima nekih 7-8 čvorova). Za dati graf uraditi topološko sortiranje i prikazati graf dobijen tako.
	=== Rešenje ===		=== Rešenje ===
	== 9. zadatak ==		{{delimično rešeno}}
			== 9. zadatak==
	=== Postavka ===		=== Postavka ===
	a) Detaljno opisati postupak za pronalaženje jako povezanih komponenti u grafu.		<div class="abc-list">
	b) Za graf sa slike (nekih 7-8 čvorova) po koracima primeniti algoritam za pronalaženje jako povezanih komponenti i rezultujući graf.		# Detaljno opisati postupak za pronalaženje jako povezanih komponenti u grafu.
			# Za graf sa slike (nekih 7-8 čvorova) po koracima primeniti algoritam za pronalaženje jako povezanih komponenti i rezultujući graf.
			</div>
	=== Rešenje ===		=== Rešenje ===
			{{delimično rešeno}}
	== 10. zadatak ==		== 10. zadatak ==
	=== Postavka ===		=== Postavka ===
	Potrebno je čuvati neki skup brojeva koji će biti u opsegu između 1 i 100.		Potrebno je čuvati neki skup brojeva koji će biti u opsegu između 1 i 100.
	a) Uporediti sekvencijalnu i ulančanu reprezentaciju skupa i ~~uprediti~~ složenost operacija dodavanja elementa, brisanja elementa i provere ~~pripadnosi~~ elementa skupu za ove dve reprezentacije.		<div class="abc-list">
	b) Neka je dat skup (npr. 5, 14, 44, 45, 78, 98) prikazati jednu i drugu reprezenatciju nakon operacija (npr. dodavanje 7, dodavanje 46, dodavanje 97, brisanje 78).		# Uporediti sekvencijalnu i ulančanu reprezentaciju skupa i uporediti složenost operacija dodavanja elementa, brisanja elementa i provere pripadnosti elementa skupu za ove dve reprezentacije.
			# Neka je dat skup (npr. 5, 14, 44, 45, 78, 98) prikazati jednu i drugu reprezenatciju nakon operacija (npr. dodavanje 7, dodavanje 46, dodavanje 97, brisanje 78).
			</div>
			=== Rešenje ===
			Kod sekvencijalne se alocira vektor S[1:100] i ukoliko je element ''X'' u skupu, u polje ''S''[''X''] se upisuje 1, inače 0. Kod ulančane reprezentacije je najefikasnije čuvati ulančanu listu u rastućem ili opadajućem poretku. Dodavanje/brisanje u sekvencijalnoj se radi u O(1) tako što se samo proveri ili izmeni indeks u nizu. Kod ulančane reprezentacije je potrebno proći kroz listu do lokacije na koju treba umetnuti/obrisati element (po rastućem ili opadajućem poretku).

	~~=== Rešenje ===~~
	Kod sekvencijalne se alocira vektor S[1:100] i ukoliko je element X u skupu, u polje S[X] se upisuje 1, inače 0. Kod ulančane reprezentacije je najefikasnije čuvati ulančanu listu u rastućem ili opadajućem poretku. Dodavanje/brisanje u sekvencijalnoj se radi u O(1) tako što se samo proveri ili izmeni indeks u nizu. Kod ulančane reprezentacije je potrebno proći kroz listu do lokacije na koju treba umetnuti/obrisati element (po rastućem ili opadajućem poretku).
	[[Категорија:АСП1]]		[[Категорија:АСП1]]
	[[Категорија:Рокови]]		[[Категорија:Рокови]]

Koldzic.filip у 00:10, 18. септембар 2021.

2021-09-18T00:10:05Z

← Старија измена		Верзија на датум 18. септембар 2021. у 02:10
Ред 1:		Ред 1:
	{{tocright}}		{{tocright}}
	{{nerešeno}}		{{nerešeno}}
	Ovaj članak je rekreacija ~~septembarskog~~ roka koji nije objavljen.		Ovaj članak je rekreacija avgustovskog roka koji nije objavljen.

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

Koldzic.filip: /* Postavka */

2021-09-18T00:08:34Z

Postavka

← Старија измена		Верзија на датум 18. септембар 2021. у 02:08
Ред 60:		Ред 60:
	== 10. zadatak ==		== 10. zadatak ==
	=== Postavka ===		=== Postavka ===
	~~POtrebnjo~~ je čuvati neki skup brojeva koji će biti u opsegu između 1 i 100.		Potrebno je čuvati neki skup brojeva koji će biti u opsegu između 1 i 100.
	a) Uporediti sekvencijalnu i ulančanu reprezentaciju skupa i uprediti složenost operacija dodavanja elementa, brisanja elementa i provere pripadnosi elementa skupu za ove dve reprezentacije.		a) Uporediti sekvencijalnu i ulančanu reprezentaciju skupa i uprediti složenost operacija dodavanja elementa, brisanja elementa i provere pripadnosi elementa skupu za ove dve reprezentacije.
	b) Neka je dat skup (npr. 5, 14, 44, 45, 78, 98) prikazati jednu i drugu reprezenatciju nakon operacija (npr. dodavanje 7, dodavanje 46, dodavanje 97, brisanje 78).		b) Neka je dat skup (npr. 5, 14, 44, 45, 78, 98) prikazati jednu i drugu reprezenatciju nakon operacija (npr. dodavanje 7, dodavanje 46, dodavanje 97, brisanje 78).

	=== Rešenje ===		=== Rešenje ===
	Kod sekvencijalne se alocira vektor S[1:100] i ukoliko je element X u skupu, u polje S[X] se upisuje 1, inače 0. Kod ulančane reprezentacije je najefikasnije čuvati ulančanu listu u rastućem ili opadajućem poretku. Dodavanje/brisanje u sekvencijalnoj se radi u O(1) tako što se samo proveri ili izmeni indeks u nizu. Kod ulančane reprezentacije je potrebno proći kroz listu do lokacije na koju treba umetnuti/obrisati element (po rastućem ili opadajućem poretku).		Kod sekvencijalne se alocira vektor S[1:100] i ukoliko je element X u skupu, u polje S[X] se upisuje 1, inače 0. Kod ulančane reprezentacije je najefikasnije čuvati ulančanu listu u rastućem ili opadajućem poretku. Dodavanje/brisanje u sekvencijalnoj se radi u O(1) tako što se samo proveri ili izmeni indeks u nizu. Kod ulančane reprezentacije je potrebno proći kroz listu do lokacije na koju treba umetnuti/obrisati element (po rastućem ili opadajućem poretku).
	[[Категорија:АСП1]]		[[Категорија:АСП1]]
	[[Категорија:Рокови]]		[[Категорија:Рокови]]

Koldzic.filip: /* Rešenje */

2021-09-18T00:08:13Z

Rešenje

← Старија измена		Верзија на датум 18. септембар 2021. у 02:08
Ред 42:		Ред 42:
	'''Huffman-ov algoritam''': Dat јe tekst sa 6 slova dužine 21 slovo. Odrediti izgled stabla dobijenog statičkim Huffman-om za ovaj tekst i uporediti prosečan broj bitova za čuvanje ovog teksta, kao i jednog slova u slučaju da se čuva podrazumevano i na osnovu ovog Huffman stabla. Frekvenciju slova zaključiti iz teksta.		'''Huffman-ov algoritam''': Dat јe tekst sa 6 slova dužine 21 slovo. Odrediti izgled stabla dobijenog statičkim Huffman-om za ovaj tekst i uporediti prosečan broj bitova za čuvanje ovog teksta, kao i jednog slova u slučaju da se čuva podrazumevano i na osnovu ovog Huffman stabla. Frekvenciju slova zaključiti iz teksta.
	=== Rešenje ===		=== Rešenje ===
	Najobičniji ~~dinamički~~ Huffman za zadatim frekvencijama.		Najobičniji statički Huffman za zadatim frekvencijama.

	== 7. zadatak ==		== 7. zadatak ==
	=== Postavka ===		=== Postavka ===

Koldzic.filip: napravljena je nova stranica za rok koji pre nije postojao; Nisam se setio detaljno svih zadataka, ali suština je tu

2021-09-18T00:07:42Z

napravljena je nova stranica za rok koji pre nije postojao; Nisam se setio detaljno svih zadataka, ali suština je tu

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

{{tocright}}
{{nerešeno}}
Ovaj članak je rekreacija septembarskog roka koji nije objavljen.

== 1. zadatak ==
=== Postavka ===
Data je retka matrica koja je prikazana na slici. (Data je matrica npr. 5*6 sa 5 ili 6 random nenultih elemenata).
a) Nacrtati izgled delova memorije u kojima se čuva ova retka matrica, ako se primenjuje ''Compressed Sparse Row'' način čuvanja.
b) Napisati funkciju u pseudokodu koja na osnovu sačuvane ''Compressed Sparse Row'' reprezentacije matrice M i unetog broja ''i'' štampa sve nenulte elemente ''i''-te vrste.
=== Rešenje ===
== 2. zadatak ==
=== Postavka ===
Navedite načine reprezentacije grafova i njihove prednosti i mane.
=== Rešenje ===
potrebno je samo napisati i prokomentarisati tabelu 7.1 sa strane 161 iz udžbenika
== 3. zadatak ==
=== Postavka ===
Zadato je binarno stablo S i date su adrese dva čvora ''x'' i ''y''. Napisati funkciju u pseudokodu koja pronalazi najnižeg zajedničkog pretka zadata dva čvora.
=== Rešenje ===
== 4. zadatak ==
=== Postavka ===
Potpuno formalno izvesti međusobnu zavisnost interne i eksterne dužine puta u binarnom stablu i kratko obrazložiti.
=== Rešenje ===
PE = PI + 2n, gde je n broj čvorova u stablu
izvođenje indukcijom, kao u knjizi/na predavanju
== 5. zadatak ==
=== Postavka ===
Potrebno je realizovati aplikaciju za obradu slika. Korisniku je potrebno da za uneti set slika i unet set operacija omogućiti da se sve operacije izvrše nad svim unetim slikama. Navesti koje strukture je pogodno koristiti za čuvanje seta slika i seta operacija i objasniti zašto. Napisati fuknciju u pesudokodu koja obrađuje uneti set slika unetim setom operacija, u skladu sa odabranim strukturama podataka.
=== Rešenje ===
//''Rešenje je krajnje trivijalno i ovde je navedeno jedno koje je bodovano maksimalnim brojem poena''
Za oba se može koristiti jednostruko ulančana lista (jer nije bitan redosled kojim će se operacije izvršavati jer će se svakako sve izvršiti na svim slikama), a ulančane liste su pogodno za lako dodavanje i brisanje elemenata.
<syntaxhighlight lang="milo">
OBRADI_SLIKE(slike, operacije)
s = slike.head;
o = operacije.head;
while (s != NULL)
while (o != NULL)
s.info = o.operacija(s.info);
</syntaxhighlight>
== 6. zadatak ==
=== Postavka ===
'''Huffman-ov algoritam''': Dat јe tekst sa 6 slova dužine 21 slovo. Odrediti izgled stabla dobijenog statičkim Huffman-om za ovaj tekst i uporediti prosečan broj bitova za čuvanje ovog teksta, kao i jednog slova u slučaju da se čuva podrazumevano i na osnovu ovog Huffman stabla. Frekvenciju slova zaključiti iz teksta.
=== Rešenje ===
Najobičniji dinamički Huffman za zadatim frekvencijama.
== 7. zadatak ==
=== Postavka ===
Dat je grad koji je mnodelovan usmerenim grafom, tako što su čvorovi lokacije u gradu (pekara, apoteka, biblioteka itd), a težine grana između čvorova vreme u minutima koje je potrebno da se peške dođe od izvorišne do odredišne lokacije. Dete želi da stigne od škole (čvor X) do kuće (čvor Y) najbrže moguće. Međutim, postoji opasan deo grada (čvor Z), koji nije bezbedan za decu i koji ona treba da izbegavaju. Napisati funkciju u pseudokodu koja na osnovu zadatog grafa G (nije data reprezentacija, nego treba apstraktno da se piše), zadatih lokacija kuće i škole, Y i X, i opasnog dela grada Z, pronalazi najkraće vreme koje je detetu potrebno od škole do kuće.
=== Rešenje ===
Zadatak se rešava implementacijom Dijkstrinog algortima, tako što kada se u uzimanju čvorova redom po težinskoj udaljenosti od početnog dođe do "opasnog" čvora z, za njega se upise tezina beskonačno i ta petlja preskoči sa continue. Na kraju se samo proveri dostižnost ciljnog čvora.
== 8. zadatak ==
=== Postavka ===
Dat je graf na slici (ima nekih 7-8 čvorova). Za dati graf uraditi topološko sortiranje i prikazati graf dobijen tako.
=== Rešenje ===
== 9. zadatak ==
=== Postavka ===
a) Detaljno opisati postupak za pronalaženje jako povezanih komponenti u grafu.
b) Za graf sa slike (nekih 7-8 čvorova) po koracima primeniti algoritam za pronalaženje jako povezanih komponenti i rezultujući graf.
=== Rešenje ===
== 10. zadatak ==
=== Postavka ===
POtrebnjo je čuvati neki skup brojeva koji će biti u opsegu između 1 i 100.
a) Uporediti sekvencijalnu i ulančanu reprezentaciju skupa i uprediti složenost operacija dodavanja elementa, brisanja elementa i provere pripadnosi elementa skupu za ove dve reprezentacije.
b) Neka je dat skup (npr. 5, 14, 44, 45, 78, 98) prikazati jednu i drugu reprezenatciju nakon operacija (npr. dodavanje 7, dodavanje 46, dodavanje 97, brisanje 78).
=== Rešenje ===
Kod sekvencijalne se alocira vektor S[1:100] i ukoliko je element X u skupu, u polje S[X] se upisuje 1, inače 0. Kod ulančane reprezentacije je najefikasnije čuvati ulančanu listu u rastućem ili opadajućem poretku. Dodavanje/brisanje u sekvencijalnoj se radi u O(1) tako što se samo proveri ili izmeni indeks u nizu. Kod ulančane reprezentacije je potrebno proći kroz listu do lokacije na koju treba umetnuti/obrisati element (po rastućem ili opadajućem poretku).
[[Категорија:АСП1]]
[[Категорија:Рокови]]