Википедија

Topološko uređenje — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Autobot (разговор | доприноси)
1.572.075 измена
м Разне исправке; козметичке измене
Ред 11:
 
{|
|[[ImageДатотека:Directed acyclic graph.png|180px|left]]
| The graph shown to the left has many valid topological sorts, including:
 
Ред 64:
 
== Složenost ==
* [http://en.wikipedia.org/wiki/Computational_complexity Računarska kompleksnost] izračunavanja topološkog uređenja u usmerenom grafu je [http://en.wikipedia.org/wiki/NC_(complexity) '''NC''']<sup>2</sup>; što znači da se može izračunati za ''O''(log<sup>2</sup> ''n'') vremena na [http://en.wikipedia.org/wiki/Parallel_computer paralelnom računaru] pomoću polinomijalnog broja od ''O''(''n<sup>k</sup>'')procesora, za istu konstantu ''k''{{harv|Cook|1985}}.▼
 
▲[http://en.wikipedia.org/wiki/Computational_complexity Računarska kompleksnost] izračunavanja topološkog uređenja u usmerenom grafu je [http://en.wikipedia.org/wiki/NC_(complexity) '''NC''']<sup>2</sup>; što znači da se može izračunati za ''O''(log<sup>2</sup> ''n'') vremena na [http://en.wikipedia.org/wiki/Parallel_computer paralelnom računaru] pomoću polinomijalnog broja od ''O''(''n<sup>k</sup>'')procesora, za istu konstantu ''k''{{harv|Cook|1985}}.
 
== Jedinstvenost ==
Линија 75 ⟶ 74:
Topološka sortiranja su usko povezana sa konceptom [http://en.wikipedia.org/wiki/Linear_extension lineanog istezanja] [http://en.wikipedia.org/wiki/Partial_order#Formal_definition relacije poretka] u matematici.
 
Parcijalno uredjen skup je skup objekata sa definicijom relacije manje ili jednako "≤", zadovoljavajući aksiome refleksivnosti(''x''&nbsp;≤&nbsp;''x''), antisimetričnosti(ako je ''x''&nbsp;≤&nbsp;''y'' i ''y''&nbsp;≤''x'' onda je ''x''&nbsp;=&nbsp;''y''), i [http://en.wikipedia.org/wiki/Transitive_relation tranzitivnosti] (ako je ''x''&nbsp;≤&nbsp;''y'' i ''y''&nbsp;≤&nbsp;''z'', onda je ''x''&nbsp;≤&nbsp;''z'').[http://en.wikipedia.org/wiki/Total_order Relacija totalnog poretka] je relacija poretka u kojoj su svaka dva objekta ''x'' i ''y'' iz skupa uporedivi, ili je ''x''&nbsp;≤&nbsp;''y'' ili je ''y''&nbsp;≤&nbsp;''x''.Totalna uređenja se koriste u informatici kako bi operatori poređenja mogli da izedu upoređivanje kod [http://en.wikipedia.org/wiki/Comparison_sort algoritama za sortiranje].Za konačne skupove, totalna uređenja se mogu identifikovati kao linearan niz objekata gde je "≤" relacija tačna kad god prvi objekat prethodi drugom u redu;algoritmi za sortiranje upoređivanjem se mogu iskoristiti za pretvaranje totalnog uređenja u niz na ovaj način. Linearno istezanje relacije poretka je totalni poredak koji je usaglašen sa njim, u smislu ako je ''x''&nbsp;≤&nbsp;''y'' u relaciji poretka onda je i ''x''&nbsp;≤&nbsp;''y'' u totalnom poretku takođe.
 
Može se definisati relacija poretka iz bilo kog DAL-a tako što ćemo postaviti da skup objekata budu čvorovi DAL-a i definišemo da je ''x''&nbsp;≤&nbsp;''y'' tačno za bilo koja dva čvora ''x'' i ''y', kad god postoji [http://en.wikipedia.org/wiki/Directed_path usmeren put] od ''x'' ka ''y'',tj. kad god iz ''x'' [http://en.wikipedia.org/wiki/Reachability možemo da stignemo do] ''y''. Ovako definisano, topološko uređenje DAL-a je isto što i linearno istezanje ove relacije poretka.Obrnuto, svaka relacija poretka može biti definisana kao relacija domašaja u DAL-u.Jedan način da se ovo izvede je da se definiše DAL koje ima čvor za svaki objekat iz skupa relacije poretka i granu ''xy'' za svaki par objekata za koje važi ''x''&nbsp;≤&nbsp;''y''.Alternativan način da se uradi ovo je da se koristi [http://sr.wikipedia.org/wiki/Tranzitivni_zavr%C5%A1eci tranzitivno zatvorenje] relacije poretka;u celini, ovako dobijamo DAL-ove sa manje grana ali je relacija domašaja i dalje
ista relacija poretka.Ovako se algoritmi za topološko sortiranje mogu koristiti za nalaženje linearnih istezanja relacije poretka.
 
== Pogledati takođe ==
 
* [http://en.wikipedia.org/wiki/Tsort_(Unix) tsort], a Unix program for topological sorting
* [http://sourceforge.net/projects/dep-trace/ dep-trace] Orders basic dependencies and unfolds nested ones. (basic: without 2D graphical presumption)
* [http://en.wikipedia.org/wiki/Feedback_arc_set Feedback arc set], a (possibly empty) set of arcs which, if removed from the graph, make it possible to topologically sort it. Useful for dealing with graphs with cycles.
* [http://en.wikipedia.org/wiki/D._E._Knuth D. E. Knuth], [http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming The Art of Computer Programming], Volume 1, section 2.2.3, which gives an algorithm for topological sorting of a partial ordering, and a brief history.
* [http://en.wikipedia.org/wiki/Dependency_graph Dependency graph]
 
== Reference ==
 
* {{citation
| last = Cook | first = Stephen A. | authorlink = Stephen Cook
| title = A Taxonomy of Problems with Fast Parallel Algorithms
Линија 96 ⟶ 95:
| year = 1985 | pages = 2–22
| doi = 10.1016/S0019-9958(85)80041-3}}.
* {{citation
| last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen
| last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson
Линија 108 ⟶ 107:
| title = [[Introduction to Algorithms]]
| year = 2001}}.
* {{citation
| last = Jarnagin | first = M. P.
| title = Automatic machine methods of testing PERT networks for consistency
Линија 115 ⟶ 114:
| publisher = U. S. Naval Weapons Laboratory
| location = Dahlgren, Virginia}}.
* {{citation
| last = Kahn | first = Arthur B.
| title = Topological sorting of large networks
Линија 121 ⟶ 120:
| volume = 5 | issue = 11 | year = 1962 | pages = 558–562
| doi = 10.1145/368996.369025}}.
* {{citation
| last = Tarjan | first = Robert E. | authorlink = Robert Tarjan
| title = Edge-disjoint spanning trees and depth-first search
| journal = Acta Informatica | volume = 6 | issue = 2 | year = 1976 | pages = 171–185
| doi = 10.1007/BF00268499}}.
* {{citation
| last1 = Vernet | first1 = Oswaldo
| last2 = Markenzon | first2 = Lilian
Преузето из „https://sr.wikipedia.org/wiki/Topološko_uređenje”