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

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

2024-09-13T00:09:04Z

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

← Старија измена		Верзија на датум 13. септембар 2024. у 02:09
Ред 88:		Ред 88:
	=== Rešenje ===		=== Rešenje ===
	Pošto se ne kaže da mora iterativno rešenje, ovde nam je najlakše rekurzivno rešenje.		Pošto se ne kaže da mora iterativno rešenje, ovde nam je najlakše rekurzivno rešenje.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	FIND PATHS NUM(G, src, dst, k)		FIND PATHS NUM(G, src, dst, k)
	if k < 1 then		if k < 1 then
Ред 101:		Ред 101:
	end_for		end_for
	return paths		return paths
	</~~syntaxhighlight~~>		</nowiki>}}

	== 4. zadatak ==		== 4. zadatak ==
Ред 108:		Ред 108:

	=== Rešenje ===		=== Rešenje ===
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	TELECOM(G, n, k)		TELECOM(G, n, k)
	S = {1}		S = {1}
Ред 119:		Ред 119:
	end_for		end_for
	return true		return true
	</~~syntaxhighlight~~>		</nowiki>}}

	== 5. zadatak ==		== 5. zadatak ==
Ред 127:		Ред 127:
	=== Rešenje ===		=== Rešenje ===
	Osnovna detekcija povezanih komponenti funkcioniše tako što jedna petlja prolazi kroz svaki čvor i ako nije posećen računa ga kao odvojenu komponentu i radi DFS nad njim kako bi se ostali čvorovi u komponenti označili kao posećeni. Sa listom susednosti spoljašnja petlja prolazi tačno ''n'' puta kroz niz a od svakog čvora prilikom DFS-a se moraju posetiti sve grane, pa to čini ukupnu složenost od <math>\mathcal{O(e + n)}</math>. Pošto, nažalost, koristimo matricu susednosti umesto liste susednosti, pri obilaženju svakog čvora DFS-om moraćemo da prođemo kroz ceo red matrice kako bismo odredili koje su u njoj grane, i to ćemo morati da učinimo za svaki čvor (jer ćemo svaki čvor morati da posetimo), što bez obzira na spoljašnju petlju čini složenost od <math>\mathcal{O(n^2)}</math>.		Osnovna detekcija povezanih komponenti funkcioniše tako što jedna petlja prolazi kroz svaki čvor i ako nije posećen računa ga kao odvojenu komponentu i radi DFS nad njim kako bi se ostali čvorovi u komponenti označili kao posećeni. Sa listom susednosti spoljašnja petlja prolazi tačno ''n'' puta kroz niz a od svakog čvora prilikom DFS-a se moraju posetiti sve grane, pa to čini ukupnu složenost od <math>\mathcal{O(e + n)}</math>. Pošto, nažalost, koristimo matricu susednosti umesto liste susednosti, pri obilaženju svakog čvora DFS-om moraćemo da prođemo kroz ceo red matrice kako bismo odredili koje su u njoj grane, i to ćemo morati da učinimo za svaki čvor (jer ćemo svaki čvor morati da posetimo), što bez obzira na spoljašnju petlju čini složenost od <math>\mathcal{O(n^2)}</math>.
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	CONN COMP MAT(G)		CONN COMP MAT(G)
	curr_comp = 0		curr_comp = 0
Ред 166:		Ред 166:
	end_for		end_for
	return res		return res
	</~~syntaxhighlight~~>		</nowiki>}}

	== 6. zadatak ==		== 6. zadatak ==
Ред 231:		Ред 231:
	Rezidualni graf može maksimalno da ima duplo više grana od protočnog grafa, u slučaju da se nakon zamene grana ne dobiju grane težine 0. Protočni graf ima maksimalan broj grana <math>\frac{n(n-1)}{2}</math> jer između svaka dva čvora može da postoji grana, pa zato rezidualni graf može da ima maksimalno <math>n(n-1)</math> grana.		Rezidualni graf može maksimalno da ima duplo više grana od protočnog grafa, u slučaju da se nakon zamene grana ne dobiju grane težine 0. Protočni graf ima maksimalan broj grana <math>\frac{n(n-1)}{2}</math> jer između svaka dva čvora može da postoji grana, pa zato rezidualni graf može da ima maksimalno <math>n(n-1)</math> grana.

	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	GtoGf(G)		GtoGf(G)
	ALLOCATE(E', n)		ALLOCATE(E', n)
Ред 247:		Ред 247:
	end_for		end_for
	return (V, E')		return (V, E')
	</~~syntaxhighlight~~>		</nowiki>}}
	<~~syntaxhighlight lang="milo"~~>		{{Милокод\|<nowiki>
	BRANCH INSERT(E', from, to, w)		BRANCH INSERT(E', from, to, w)
	if w = 0 then		if w = 0 then
Ред 258:		Ред 258:
	next(e'[from]) = t		next(e'[from]) = t
	w(e'[from]) = w		w(e'[from]) = w
	</~~syntaxhighlight~~>		</nowiki>}}

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

KockaAdmiralac: PNG u SVG

2022-02-13T21:16:39Z

PNG u SVG

← Старија измена		Верзија на датум 13. фебруар 2022. у 23:16
Ред 38:		Ред 38:

	=== Rešenje ===		=== Rešenje ===
	[[{{ns:6}}:ASP1 K3 2018 zadatak 2 graf.~~png~~\|thumb\|Graf koji se dobija iz matrice susednosti.]]		[[{{ns:6}}:ASP1 K3 2018 zadatak 2 graf.svg\|thumb\|Graf koji se dobija iz matrice susednosti.]]
	Naša tabela već sadrži informacije o svim putevima dužine 1, a to su:		Naša tabela već sadrži informacije o svim putevima dužine 1, a to su:
	* AB		* AB
Ред 181:		Ред 181:
	\|		\|
	H		H
	<gallery>		<gallery class="transparent-svg">
	ASP1 K3 2018 zadatak 6 graf.~~png~~ \| Graf iz postavke zadatka.		ASP1 K3 2018 zadatak 6 graf.svg \| Graf iz postavke zadatka.
	ASP1 K3 2018 zadatak 6 rešenje.~~png~~ \| Rešenje zadatka.		ASP1 K3 2018 zadatak 6 rešenje.svg \| Rešenje zadatka.
	</gallery>		</gallery>

	== 7. zadatak ==		== 7. zadatak ==
	=== Postavka ===		=== Postavka ===
	[[{{ns:6}}:ASP1 K3 2018 zadatak 7 graf.~~png~~\|thumb\|Pojednostavljen graf iz postavke zadatka.]]		[[{{ns:6}}:ASP1 K3 2018 zadatak 7 graf.svg\|thumb\|Pojednostavljen graf iz postavke zadatka.]]
	Za graf sa slike, odrediti najkraća rastojanja od čvora C do svih ostalih čvorova. Kada algoritam završava svoj rad u ovom slučaju?		Za graf sa slike, odrediti najkraća rastojanja od čvora C do svih ostalih čvorova. Kada algoritam završava svoj rad u ovom slučaju?

KockaAdmiralac: Formatiranje

2021-09-02T16:20:01Z

Formatiranje

← Старија измена		Верзија на датум 2. септембар 2021. у 18:20
Ред 7:		Ред 7:

	=== Rešenje ===		=== Rešenje ===
	Pošto se radi o topološkom sortiranju u inverznom poretku, to znači da se uvek traži naredni čvor koji nema izlaznih grana. ~~<br><br>~~U ovom slučaju je najpovoljnije koristiti inverzne liste susednosti. Na početku se prođe kroz sve grane i formira vektor koji za svaki čvor pamti broj sledbenika (kad god se naiđe na određeni čvor u granama inkrementira mu se broj sledbenika jer nailaskom na njega znamo da je on prethodnik čvora iz tog zaglavlja). U toku izvršavanja TOP_SORT algoritma uvek se traži u vektoru čvor koji nema sledbenike, direktno mu se pristupa u nizu zaglavlja, i onda se samo uklone svi čvorovi iz njegove ulančane liste prethodnika. Nakon ovog postupka se ažurira uvek i vektor tako što se za svaki uklonjeni čvor dekrementira broj njegovih sledbenika. Na ovaj način TOP_SORT algoritam ima složenost <math>O(n+e)</math> jer se postupak ponavlja za svih n čvorova u grafu, a ukupno se prolazi kroz ~~e grana.~~ <br><br>		Pošto se radi o topološkom sortiranju u inverznom poretku, to znači da se uvek traži naredni čvor koji nema izlaznih grana.
	Sa druge strane, korišćenje regularnih lista susednosti bi bilo znatno složenije jer uprkos tome što lako nalazimo čvor bez izlaznih grana i ne treba nam dodatan vektor za to, prilikom uklanjanja svih ulaznih grana za taj čvor bismo uvek morali da prođemo sve grane u grafu kako bismo ~~nalazili~~ kojim čvorovima je on sve sledbenik.
			U ovom slučaju je najpovoljnije koristiti inverzne liste susednosti. Na početku se prođe kroz sve grane i formira vektor koji za svaki čvor pamti broj sledbenika (kad god se naiđe na određeni čvor u granama inkrementira mu se broj sledbenika jer nailaskom na njega znamo da je on prethodnik čvora iz tog zaglavlja). U toku izvršavanja <code>TOP_SORT</code> algoritma uvek se traži u vektoru čvor koji nema sledbenike, direktno mu se pristupa u nizu zaglavlja, i onda se samo uklone svi čvorovi iz njegove ulančane liste prethodnika. Nakon ovog postupka se ažurira uvek i vektor tako što se za svaki uklonjeni čvor dekrementira broj njegovih sledbenika. Na ovaj način <code>TOP_SORT</code> algoritam ima složenost <math>O(n+e)</math> jer se postupak ponavlja za svih <math>n</math> čvorova u grafu, a ukupno se prolazi kroz <math>e</math> grana.

			Sa druge strane, korišćenje regularnih lista susednosti bi bilo znatno složenije jer uprkos tome što lako nalazimo čvor bez izlaznih grana i ne treba nam dodatan vektor za to, prilikom uklanjanja svih ulaznih grana za taj čvor bismo uvek morali da prođemo sve grane u grafu kako bismo našli kojim čvorovima je on sve sledbenik.

	== 2. zadatak ==		== 2. zadatak ==

Etfsibg: /* 1. zadatak */

2021-09-02T11:19:04Z

1. zadatak

← Старија измена		Верзија на датум 2. септембар 2021. у 13:19
Ред 3:		Ред 3:

	== 1. zadatak ==		== 1. zadatak ==
	~~{{delimično rešeno}}~~
	=== Postavka ===		=== Postavka ===
	Diskutovati implementaciju algoritma za topološko sortiranje grafa u '''inverznom poretku''', ukoliko se za memorijsku reprezentaciju grafa usvoje liste susednosti. Da li je za ovu operaciju pogodnije koristiti inverzne liste susednosti? Obrazložiti odgovor uz precizno navođenje razlika u implementaciji.		Diskutovati implementaciju algoritma za topološko sortiranje grafa u '''inverznom poretku''', ukoliko se za memorijsku reprezentaciju grafa usvoje liste susednosti. Da li je za ovu operaciju pogodnije koristiti inverzne liste susednosti? Obrazložiti odgovor uz precizno navođenje razlika u implementaciji.

Etfsibg: /* Rešenje */

2021-09-02T11:16:33Z

Rešenje

← Старија измена		Верзија на датум 2. септембар 2021. у 13:16
Ред 8:		Ред 8:

	=== Rešenje ===		=== Rešenje ===
	Pošto se radi o topološkom sortiranju u inverznom poretku, to znači da se uvek traži naredni čvor koji nema izlaznih grana. <br><br>U ovom slučaju je najpovoljnije koristiti ~~inevrzne~~ liste susednosti. Na početku se prođe kroz sve grane i formira vektor koji za svaki čvor pamti broj sledbenika (kad god se naiđe na određeni čvor u granama inkrementira mu se broj sledbenika jer nailaskom na njega znamo da je on prethodnik čvora iz tog zaglavlja). U toku izvršavanja TOP_SORT algoritma uvek se traži u vektoru čvor koji nema sledbenike, direktno mu se pristupa u nizu zaglavlja, i onda se samo uklone svi čvorovi iz njegove ulančane liste prethodnika. Nakon ovog postupka se ažurira uvek i vektor tako što se za svaki uklonjeni čvor dekrementira broj njegovih sledbenika. Na ovaj način TOP_SORT algoritam ima složenost <math>O(n+e)</math> jer se postupak ponavlja za svih n čvorova u grafu, a ukupno se prolazi kroz e grana. <br><br>		Pošto se radi o topološkom sortiranju u inverznom poretku, to znači da se uvek traži naredni čvor koji nema izlaznih grana. <br><br>U ovom slučaju je najpovoljnije koristiti inverzne liste susednosti. Na početku se prođe kroz sve grane i formira vektor koji za svaki čvor pamti broj sledbenika (kad god se naiđe na određeni čvor u granama inkrementira mu se broj sledbenika jer nailaskom na njega znamo da je on prethodnik čvora iz tog zaglavlja). U toku izvršavanja TOP_SORT algoritma uvek se traži u vektoru čvor koji nema sledbenike, direktno mu se pristupa u nizu zaglavlja, i onda se samo uklone svi čvorovi iz njegove ulančane liste prethodnika. Nakon ovog postupka se ažurira uvek i vektor tako što se za svaki uklonjeni čvor dekrementira broj njegovih sledbenika. Na ovaj način TOP_SORT algoritam ima složenost <math>O(n+e)</math> jer se postupak ponavlja za svih n čvorova u grafu, a ukupno se prolazi kroz e grana. <br><br>
	Sa druge strane, korišćenje regularnih lista susednosti bi bilo znatno složenije jer uprkos tome što lako nalazimo čvor bez izlaznih grana i ne treba nam dodatan vektor za to, prilikom uklanjanja svih ulaznih grana za taj čvor bismo uvek morali da prođemo sve grane u grafu kako bismo nalazili kojim čvorovima je on sve sledbenik.		Sa druge strane, korišćenje regularnih lista susednosti bi bilo znatno složenije jer uprkos tome što lako nalazimo čvor bez izlaznih grana i ne treba nam dodatan vektor za to, prilikom uklanjanja svih ulaznih grana za taj čvor bismo uvek morali da prođemo sve grane u grafu kako bismo nalazili kojim čvorovima je on sve sledbenik.

Etfsibg: /* Rešenje */

2021-09-02T11:15:54Z

Rešenje

← Старија измена		Верзија на датум 2. септембар 2021. у 13:15
Ред 8:		Ред 8:

	=== Rešenje ===		=== Rešenje ===
	Pošto se radi o topološkom sortiranju u inverznom poretku, to znači da se uvek traži naredni čvor koji nema izlaznih grana. U ovom slučaju je najpovoljnije koristiti inevrzne liste susednosti. Na početku se prođe kroz sve grane i formira vektor koji za svaki čvor pamti broj sledbenika (kad god se naiđe na određeni čvor u granama inkrementira mu se broj sledbenika jer nailaskom na njega znamo da je on prethodnik čvora iz tog zaglavlja). U toku izvršavanja TOP_SORT algoritma uvek se traži u vektoru čvor koji nema sledbenike, direktno mu se pristupa u nizu zaglavlja, i onda se samo uklone svi čvorovi iz njegove ulančane liste prethodnika. Nakon ovog postupka se ažurira uvek i vektor tako što se za svaki uklonjeni čvor dekrementira broj njegovih sledbenika. Na ovaj način TOP_SORT algoritam ima složenost <math>O(n+e)</math> jer se postupak ponavlja za svih n čvorova u grafu, a ukupno se prolazi kroz e grana. <br><br>		Pošto se radi o topološkom sortiranju u inverznom poretku, to znači da se uvek traži naredni čvor koji nema izlaznih grana. <br><br>U ovom slučaju je najpovoljnije koristiti inevrzne liste susednosti. Na početku se prođe kroz sve grane i formira vektor koji za svaki čvor pamti broj sledbenika (kad god se naiđe na određeni čvor u granama inkrementira mu se broj sledbenika jer nailaskom na njega znamo da je on prethodnik čvora iz tog zaglavlja). U toku izvršavanja TOP_SORT algoritma uvek se traži u vektoru čvor koji nema sledbenike, direktno mu se pristupa u nizu zaglavlja, i onda se samo uklone svi čvorovi iz njegove ulančane liste prethodnika. Nakon ovog postupka se ažurira uvek i vektor tako što se za svaki uklonjeni čvor dekrementira broj njegovih sledbenika. Na ovaj način TOP_SORT algoritam ima složenost <math>O(n+e)</math> jer se postupak ponavlja za svih n čvorova u grafu, a ukupno se prolazi kroz e grana. <br><br>
	Sa druge strane, korišćenje regularnih lista susednosti bi bilo znatno složenije jer uprkos tome što lako nalazimo čvor bez izlaznih grana i ne treba nam dodatan vektor za to, prilikom uklanjanja svih ulaznih grana za taj čvor bismo uvek morali da prođemo sve grane u grafu kako bismo nalazili kojim čvorovima je on sve sledbenik.		Sa druge strane, korišćenje regularnih lista susednosti bi bilo znatno složenije jer uprkos tome što lako nalazimo čvor bez izlaznih grana i ne treba nam dodatan vektor za to, prilikom uklanjanja svih ulaznih grana za taj čvor bismo uvek morali da prođemo sve grane u grafu kako bismo nalazili kojim čvorovima je on sve sledbenik.

Etfsibg: /* Rešenje */

2021-09-02T11:14:12Z

Rešenje

← Старија измена		Верзија на датум 2. септембар 2021. у 13:14
Ред 8:		Ред 8:

	=== Rešenje ===		=== Rešenje ===
	Pošto se radi o topološkom sortiranju u inverznom poretku, to znači da se uvek traži naredni čvor koji nema izlaznih grana. U ovom slučaju je najpovoljnije koristiti inevrzne liste susednosti. Na početku se prođe kroz sve grane i formira vektor koji za svaki čvor pamti broj sledbenika(kad god se naiđe na određeni čvor u granama inkrementira mu se broj sledbenika jer nailaskom na njega znamo da je on prethodnik čvora iz tog zaglavlja). U toku izvršavanja TOP_SORT algoritma uvek se traži u vektoru čvor koji nema sledbenike, direktno mu se pristupa u nizu zaglavlja, i onda se samo uklone svi čvorovi iz njegove ulančane liste prethodnika. Nakon ovog postupka se ažurira uvek i vektor tako što se za svaki uklonjeni čvor dekrementira broj njegovih sledbenika. Na ovaj način TOP_SORT algoritam ima složenost <math>O(n+e)</math> jer se postupak ponavlja za svih n čvorova u grafu, a ukupno se prolazi kroz e grana. <br><br>		Pošto se radi o topološkom sortiranju u inverznom poretku, to znači da se uvek traži naredni čvor koji nema izlaznih grana. U ovom slučaju je najpovoljnije koristiti inevrzne liste susednosti. Na početku se prođe kroz sve grane i formira vektor koji za svaki čvor pamti broj sledbenika (kad god se naiđe na određeni čvor u granama inkrementira mu se broj sledbenika jer nailaskom na njega znamo da je on prethodnik čvora iz tog zaglavlja). U toku izvršavanja TOP_SORT algoritma uvek se traži u vektoru čvor koji nema sledbenike, direktno mu se pristupa u nizu zaglavlja, i onda se samo uklone svi čvorovi iz njegove ulančane liste prethodnika. Nakon ovog postupka se ažurira uvek i vektor tako što se za svaki uklonjeni čvor dekrementira broj njegovih sledbenika. Na ovaj način TOP_SORT algoritam ima složenost <math>O(n+e)</math> jer se postupak ponavlja za svih n čvorova u grafu, a ukupno se prolazi kroz e grana. <br><br>
	Sa druge strane, korišćenje regularnih lista susednosti bi bilo znatno složenije jer uprkos tome što lako nalazimo čvor bez izlaznih grana i ne treba nam dodatan vektor za to, prilikom uklanjanja svih ulaznih grana za taj čvor bismo uvek morali da prođemo sve grane u grafu kako bismo nalazili kojim čvorovima je on sve sledbenik.		Sa druge strane, korišćenje regularnih lista susednosti bi bilo znatno složenije jer uprkos tome što lako nalazimo čvor bez izlaznih grana i ne treba nam dodatan vektor za to, prilikom uklanjanja svih ulaznih grana za taj čvor bismo uvek morali da prođemo sve grane u grafu kako bismo nalazili kojim čvorovima je on sve sledbenik.

Etfsibg: /* Rešenje */

2021-09-02T11:13:38Z

Rešenje

← Старија измена		Верзија на датум 2. септембар 2021. у 13:13
Ред 8:		Ред 8:

	=== Rešenje ===		=== Rešenje ===
			Pošto se radi o topološkom sortiranju u inverznom poretku, to znači da se uvek traži naredni čvor koji nema izlaznih grana. U ovom slučaju je najpovoljnije koristiti inevrzne liste susednosti. Na početku se prođe kroz sve grane i formira vektor koji za svaki čvor pamti broj sledbenika(kad god se naiđe na određeni čvor u granama inkrementira mu se broj sledbenika jer nailaskom na njega znamo da je on prethodnik čvora iz tog zaglavlja). U toku izvršavanja TOP_SORT algoritma uvek se traži u vektoru čvor koji nema sledbenike, direktno mu se pristupa u nizu zaglavlja, i onda se samo uklone svi čvorovi iz njegove ulančane liste prethodnika. Nakon ovog postupka se ažurira uvek i vektor tako što se za svaki uklonjeni čvor dekrementira broj njegovih sledbenika. Na ovaj način TOP_SORT algoritam ima složenost <math>O(n+e)</math> jer se postupak ponavlja za svih n čvorova u grafu, a ukupno se prolazi kroz e grana. <br><br>
			Sa druge strane, korišćenje regularnih lista susednosti bi bilo znatno složenije jer uprkos tome što lako nalazimo čvor bez izlaznih grana i ne treba nam dodatan vektor za to, prilikom uklanjanja svih ulaznih grana za taj čvor bismo uvek morali da prođemo sve grane u grafu kako bismo nalazili kojim čvorovima je on sve sledbenik.

	== 2. zadatak ==		== 2. zadatak ==

KockaAdmiralac: Delimično rešeno

2021-06-27T17:58:55Z

Delimično rešeno

← Старија измена		Верзија на датум 27. јун 2021. у 19:58
Ред 3:		Ред 3:

	== 1. zadatak ==		== 1. zadatak ==
			{{delimično rešeno}}
	=== Postavka ===		=== Postavka ===
	Diskutovati implementaciju algoritma za topološko sortiranje grafa u '''inverznom poretku''', ukoliko se za memorijsku reprezentaciju grafa usvoje liste susednosti. Da li je za ovu operaciju pogodnije koristiti inverzne liste susednosti? Obrazložiti odgovor uz precizno navođenje razlika u implementaciji.		Diskutovati implementaciju algoritma za topološko sortiranje grafa u '''inverznom poretku''', ukoliko se za memorijsku reprezentaciju grafa usvoje liste susednosti. Da li je za ovu operaciju pogodnije koristiti inverzne liste susednosti? Obrazložiti odgovor uz precizno navođenje razlika u implementaciji.

KockaAdmiralac: Prebacivanje na jednostavno isticanje sintakse

2020-08-28T09:41:09Z

Prebacivanje na jednostavno isticanje sintakse

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