Topologické řazení - Historie editací

Acolade: kategorizace

2014-02-20T06:35:40Z

kategorizace

← Starší verze		Verze z 20. 2. 2014, 06:35
Řádka 26:		Řádka 26:

	{{fav-kiv-bzinf}}		{{fav-kiv-bzinf}}
		+	[[Kategorie:fav-kiv-bzinf]]

Tester v 26. 8. 2011, 08:46

2011-08-26T08:46:52Z

← Starší verze		Verze z 26. 8. 2011, 08:46
Řádka 24:		Řádka 24:

	Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je úplně jedno, v jakém vrcholu začneme graf prohledávat, protože díky ukládání do zásobníku se ve výsledku vždyy seřadí tak, jak potřebujeme. (př: když začneme od kalhot, tak se na dno zásobníku uloží boty a nad ně kalhoty. Tady jsme skončili, takže pokračujeme v prohledávání od jiného nenavštíveného uzlu - třeba od spodků. Ty se tedy uloží nad boty a kalhoty, takže když vybíráme ze zásobníku, dostaneme správně spodky->kalhoty->boty. Pokud bychom místo spodků pokračovali třeba ponožkami, nic se nestane, jen bude do této podloupnoosti vložen ještě prvek ponožky: spodky->ponožky->kalhoty->boty, ale posloupnost bude stále zachována taková, aby položky následovaly tak jak mají.)		Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je úplně jedno, v jakém vrcholu začneme graf prohledávat, protože díky ukládání do zásobníku se ve výsledku vždyy seřadí tak, jak potřebujeme. (př: když začneme od kalhot, tak se na dno zásobníku uloží boty a nad ně kalhoty. Tady jsme skončili, takže pokračujeme v prohledávání od jiného nenavštíveného uzlu - třeba od spodků. Ty se tedy uloží nad boty a kalhoty, takže když vybíráme ze zásobníku, dostaneme správně spodky->kalhoty->boty. Pokud bychom místo spodků pokračovali třeba ponožkami, nic se nestane, jen bude do této podloupnoosti vložen ještě prvek ponožky: spodky->ponožky->kalhoty->boty, ale posloupnost bude stále zachována taková, aby položky následovaly tak jak mají.)
		+
		+	{{fav-kiv-bzinf}}

Tester v 26. 8. 2011, 08:45

2011-08-26T08:45:31Z

← Starší verze		Verze z 26. 8. 2011, 08:45
Řádka 23:		Řádka 23:
	[[Soubor:Topologicke-razeni-2.jpg]]		[[Soubor:Topologicke-razeni-2.jpg]]

−	Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je ~~evidentní~~, ~~že je~~ v ~~DFS nutné začínat od~~ vrcholu, ~~který není~~ na ~~ničem závislý~~.	+	Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je úplně jedno, v jakém vrcholu začneme graf prohledávat, protože díky ukládání do zásobníku se ve výsledku vždyy seřadí tak, jak potřebujeme. (př: když začneme od kalhot, tak se na dno zásobníku uloží boty a nad ně kalhoty. Tady jsme skončili, takže pokračujeme v prohledávání od jiného nenavštíveného uzlu - třeba od spodků. Ty se tedy uloží nad boty a kalhoty, takže když vybíráme ze zásobníku, dostaneme správně spodky->kalhoty->boty. Pokud bychom místo spodků pokračovali třeba ponožkami, nic se nestane, jen bude do této podloupnoosti vložen ještě prvek ponožky: spodky->ponožky->kalhoty->boty, ale posloupnost bude stále zachována taková, aby položky následovaly tak jak mají.)

Tester v 26. 8. 2011, 08:36

2011-08-26T08:36:57Z

← Starší verze		Verze z 26. 8. 2011, 08:36
Řádka 6:		Řádka 6:

	Dvojice jsou (musíme obléci):		Dvojice jsou (musíme obléci):
−	Ponožky dříve než boty	+	* Ponožky dříve než boty
−	Spodky dříve než kalhoty	+	* Spodky dříve než kalhoty
−	Kalhoty dříve než boty	+	* Kalhoty dříve než boty
−	Košili dříve než sako	+	* Košili dříve než sako
−	a hodinky nezávisle na zbytku	+	* a hodinky nezávisle na zbytku

	V grafu vidíme, že obsahuje 3 komponenty, a že neobsahuje cykly. Pokud orientovaný graf neobsahuje cykly, nazývá se orientovaný acyklický graf (anglicky DAG, directed acyclyc graph). V takovém grafu lze nalézt uspořádání takové, že prvky budou chronologicky za sebou podle toho, v jakém pořadí je třeba je projít (vykonat jejich akce, obléci daný kus oblečení), např. takto		V grafu vidíme, že obsahuje 3 komponenty, a že neobsahuje cykly. Pokud orientovaný graf neobsahuje cykly, nazývá se orientovaný acyklický graf (anglicky DAG, directed acyclyc graph). V takovém grafu lze nalézt uspořádání takové, že prvky budou chronologicky za sebou podle toho, v jakém pořadí je třeba je projít (vykonat jejich akce, obléci daný kus oblečení), např. takto
Řádka 19:		Řádka 19:
	Projdeme graf pomocí DFS, a při každé operaci (každém obarvení: nalezení/přesun na vrchol (šedá) a dokončení vyhledávání okolních vrcholů (černá)) pamatujeme čas, ve kterém jsme operaci provedli. První číslo udává "čas" nalezení vrcholu, druhé "čas" zpracování vrcholu.		Projdeme graf pomocí DFS, a při každé operaci (každém obarvení: nalezení/přesun na vrchol (šedá) a dokončení vyhledávání okolních vrcholů (černá)) pamatujeme čas, ve kterém jsme operaci provedli. První číslo udává "čas" nalezení vrcholu, druhé "čas" zpracování vrcholu.
	Pokud je vrchol dokončen, vložíme jeho prvek jej do zásobníku		Pokud je vrchol dokončen, vložíme jeho prvek jej do zásobníku
−	Výběrem všech prvků zásobníku získáme ~~poředí~~, ve kterém lze prvky [vykonat, použít, vypsat] tak, že jsou splněny jejich závislosti na poředí vykonání	+	Výběrem všech prvků zásobníku získáme pořadí, ve kterém lze prvky [vykonat, použít, vypsat] tak, že jsou splněny jejich závislosti na poředí vykonání

	[[Soubor:Topologicke-razeni-2.jpg]]		[[Soubor:Topologicke-razeni-2.jpg]]

	Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je evidentní, že je v DFS nutné začínat od vrcholu, který není na ničem závislý.		Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je evidentní, že je v DFS nutné začínat od vrcholu, který není na ničem závislý.

Tester v 10. 8. 2011, 09:25

2011-08-10T09:25:27Z

← Starší verze		Verze z 10. 8. 2011, 09:25
Řádka 21:		Řádka 21:
	Výběrem všech prvků zásobníku získáme poředí, ve kterém lze prvky [vykonat, použít, vypsat] tak, že jsou splněny jejich závislosti na poředí vykonání		Výběrem všech prvků zásobníku získáme poředí, ve kterém lze prvky [vykonat, použít, vypsat] tak, že jsou splněny jejich závislosti na poředí vykonání

−	Topologicke-razeni-2.jpg	+	[[Soubor:Topologicke-razeni-2.jpg]]

	Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je evidentní, že je v DFS nutné začínat od vrcholu, který není na ničem závislý.		Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je evidentní, že je v DFS nutné začínat od vrcholu, který není na ničem závislý.

Tester v 10. 8. 2011, 09:25

2011-08-10T09:25:11Z

← Starší verze		Verze z 10. 8. 2011, 09:25
Řádka 3:		Řádka 3:
	Jako příklad může posloužit proces oblékání.		Jako příklad může posloužit proces oblékání.

−		+	[[Soubor:Topologicke-razeni-1.jpg]]

	Dvojice jsou (musíme obléci):		Dvojice jsou (musíme obléci):
Řádka 20:		Řádka 20:
	Pokud je vrchol dokončen, vložíme jeho prvek jej do zásobníku		Pokud je vrchol dokončen, vložíme jeho prvek jej do zásobníku
	Výběrem všech prvků zásobníku získáme poředí, ve kterém lze prvky [vykonat, použít, vypsat] tak, že jsou splněny jejich závislosti na poředí vykonání		Výběrem všech prvků zásobníku získáme poředí, ve kterém lze prvky [vykonat, použít, vypsat] tak, že jsou splněny jejich závislosti na poředí vykonání
		+
		+	Topologicke-razeni-2.jpg

	Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je evidentní, že je v DFS nutné začínat od vrcholu, který není na ničem závislý.		Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je evidentní, že je v DFS nutné začínat od vrcholu, který není na ničem závislý.

Tester: Založena nová stránka: Máme množinu prvků, ve které je definována množina dvojic, které jsou uspořádánvy v určitém pořadí. Tuto množinu lze zakreslit jako orientovaný graf, kdy ka...

2011-08-08T15:02:03Z

Založena nová stránka: Máme množinu prvků, ve které je definována množina dvojic, které jsou uspořádánvy v určitém pořadí. Tuto množinu lze zakreslit jako orientovaný graf, kdy ka...

Nová stránka

Máme množinu prvků, ve které je definována množina dvojic, které jsou uspořádánvy v určitém pořadí. Tuto množinu lze zakreslit jako orientovaný graf, kdy každá hrana reprezentuje pořadí prvků.

Jako příklad může posloužit proces oblékání.

Dvojice jsou (musíme obléci):
Ponožky dříve než boty
Spodky dříve než kalhoty
Kalhoty dříve než boty
Košili dříve než sako
a hodinky nezávisle na zbytku

V grafu vidíme, že obsahuje 3 komponenty, a že neobsahuje cykly. Pokud orientovaný graf neobsahuje cykly, nazývá se orientovaný acyklický graf (anglicky DAG, directed acyclyc graph). V takovém grafu lze nalézt uspořádání takové, že prvky budou chronologicky za sebou podle toho, v jakém pořadí je třeba je projít (vykonat jejich akce, obléci daný kus oblečení), např. takto

Jedním z algoritmů je Topologické řazení pomocí DSF:

Projdeme graf pomocí DFS, a při každé operaci (každém obarvení: nalezení/přesun na vrchol (šedá) a dokončení vyhledávání okolních vrcholů (černá)) pamatujeme čas, ve kterém jsme operaci provedli. První číslo udává "čas" nalezení vrcholu, druhé "čas" zpracování vrcholu.
Pokud je vrchol dokončen, vložíme jeho prvek jej do zásobníku
Výběrem všech prvků zásobníku získáme poředí, ve kterém lze prvky [vykonat, použít, vypsat] tak, že jsou splněny jejich závislosti na poředí vykonání

Na obrázku je vidět, že seřazení může být různé pro různé výchozí body hledání (v našem případě spodky, košile, sako). Je evidentní, že je v DFS nutné začínat od vrcholu, který není na ničem závislý.