387
个编辑
更改
跳到导航
跳到搜索
第238行：
第238行： + 第244行：
第245行： + + + + + + + + + + + + + + + + + + + + + + + + + + + 第271行：
第299行： − A somewhat different DAG-based formulation of scheduling constraints is used by the [[program evaluation and review technique]] (PERT), a method for management of large human projects that was one of the first applications of DAGs. In this method, the vertices of a DAG represent [[Milestone (project management)|milestones]] of a project rather than specific tasks to be performed. Instead, a task or activity is represented by an edge of a DAG, connecting two milestones that mark the beginning and completion of the task. Each such edge is labeled with an estimate for the amount of time that it will take a team of workers to perform the task. The [[Longest path problem|longest path]] in this DAG represents the [[Critical path method|critical path]] of the project, the one that controls the total time for the project. Individual milestones can be scheduled according to the lengths of the longest paths ending at their vertices.<ref>{{citation |title=What Every Engineer Should Know About Decision Making Under Uncertainty |first=John X. |last=Wang |publisher=CRC Press |year=2002 |isbn=978-0-8247-4373-4 |page=160 |url=https://books.google.com/books?id=C3yKML0dUVIC&pg=PA160}}.</ref>
→Scheduling 调度
Directed acyclic graphs representations of partial orderings have many applications in scheduling for systems of tasks with ordering constraints.[29] An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a spreadsheet after one of the cells has been changed, or the object files of a piece of computer software after its source code has been changed. In this context, a dependency graph is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a circular dependency, and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle. Dependency graphs without circular dependencies form DAGs.[30]
Directed acyclic graphs representations of partial orderings have many applications in scheduling for systems of tasks with ordering constraints.[29] An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a spreadsheet after one of the cells has been changed, or the object files of a piece of computer software after its source code has been changed. In this context, a dependency graph is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a circular dependency, and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle. Dependency graphs without circular dependencies form DAGs.[30]
有向无环图的偏序关系可以在调度有着先后顺序限制的系统任务中发挥作用。[29]调度问题的一个重要种类是串联需要更新的对象，如電子試算表中某个单元格的计算公式依赖于其他单元格，或在程序的源代码被修改后重新编译目标文件。依赖图（英语：dependency graph）则记录了这种更新依赖关系。其每个顶点对应一个需要被更新的对象，边则表示更新的关系。依赖图中的环被称为环状依赖（英语：circular dependency）。环状依赖通常是不被允许出现的，因为不能保证圈内任务排定顺序的一致性。无环的依赖图即为有向无环图。[31]
有向无环图的偏序关系可以在调度有着先后顺序限制的系统任务中发挥作用。[29]调度问题的一个重要种类是串联需要更新的对象，如電子試算表中某个单元格的计算公式依赖于其他单元格，或在程序的源代码被修改后重新编译目标文件。依赖图（英语：dependency graph）则记录了这种更新依赖关系。其每个顶点对应一个需要被更新的对象，边则表示更新的关系。依赖图中的环被称为环状依赖（英语：circular dependency）。环状依赖通常是不被允许出现的，因为不能保证圈内任务排定顺序的一致性。无环的依赖图即为有向无环图。[31]
举例来说，当电子表格中一个单元格的数值发生改变，其他直接或间接依赖于该单元格的所有单元格的值都需要被重新计算。被调度的任务为重新计算某个特定单元格的值。当一个单元格的值取决于另外一个单元格时，两个单元格之间则有依赖关系。每个被依赖单元格的值的计算过程都必须先于使用它的表达式执行。使用依赖图的拓扑排序来调度任务使得在每个单元格的值都仅被重新计算一次的情况下，整个工作表都能被更新。[31]相似的任务调度场景出现在程序源代码编译的makefile，[31]和优化计算机程序底层执行的指令调度中。[32]
举例来说，当电子表格中一个单元格的数值发生改变，其他直接或间接依赖于该单元格的所有单元格的值都需要被重新计算。被调度的任务为重新计算某个特定单元格的值。当一个单元格的值取决于另外一个单元格时，两个单元格之间则有依赖关系。每个被依赖单元格的值的计算过程都必须先于使用它的表达式执行。使用依赖图的拓扑排序来调度任务使得在每个单元格的值都仅被重新计算一次的情况下，整个工作表都能被更新。[31]相似的任务调度场景出现在程序源代码编译的makefile，[31]和优化计算机程序底层执行的指令调度中。[32]
A somewhat different DAG-based formulation of scheduling constraints is used by the [[program evaluation and review technique]] (PERT), a method for management of large human projects that was one of the first applications of DAGs. In this method, the vertices of a DAG represent [[Milestone (project management)|milestones]] of a project rather than specific tasks to be performed. Instead, a task or activity is represented by an edge of a DAG, connecting two milestones that mark the beginning and completion of the task. Each such edge is labeled with an estimate for the amount of time that it will take a team of workers to perform the task. The [[Longest path problem|longest path]] in this DAG represents the [[Critical path method|critical path]] of the project, the one that controls the total time for the project. Individual milestones can be scheduled according to the lengths of the longest paths ending at their vertices.<ref>{{citation |title=What Every Engineer Should Know About Decision Making Under Uncertainty |first=John X. |last=Wang |publisher=CRC Press |year=2002 |isbn=978-0-8247-4373-4 |page=160 |url=https://books.google.com/books?id=C3yKML0dUVIC&pg=PA160}}.</ref>
计划评审技术是一种基于有向无环图的计划排定技术，通常用于组织大型的人工项目。在计划评审技术中，每个顶点表示项目的一个里程碑（英语：Milestone (project management)），每条有向边表示任务或者活动，连接着表示任务开始或结束的两个节点。每条边则被标注上预估需时。图中的最长路径即为项目的关键路径。关键路径决定了项目所需的总时间，里程碑的完成时间取决于结束于本顶点的最长路径。[33]
=== Data processing networks 数据处理网络 ===
A directed acyclic graph may be used to represent a network of processing elements. In this representation, data enters a processing element through its incoming edges and leaves the element through its outgoing edges.
有向无环图可以用于表示处理数据的元素网络。在网络中，数据从一个元素顶点的入边进入，处理后从出边离开。
For instance, in electronic circuit design, static combinational logic blocks can be represented as an acyclic system of logic gates that computes a function of an input, where the input and output of the function are represented as individual bits. In general, the output of these blocks cannot be used as the input unless it is captured by a register or state element which maintains its acyclic properties.[34] Electronic circuit schematics either on paper or in a database are a form of directed acyclic graphs using instances or components to form a directed reference to a lower level component. Electronic circuits themselves are not necessarily acyclic or directed.
在电子电路设计中，静态组合逻辑电路块可以被表示为由逻辑门组成的有向无环系统。每个逻辑门对输入做一次函数处理，输入和输出均为一个位元组。通常，这些电路块的输出不能够再作为输入，除非它们被存储在寄存器或者状态单元中，以保证图不出现环。[35]纸上或数据库中的电子电路原理图是一种有向无环图的形式，它使用实例或元件来形成对低级元件的有向引用。电子电路本身不一定是非循环的或定向的。
Dataflow programming languages describe systems of operations on data streams, and the connections between the outputs of some operations and the inputs of others. These languages can be convenient for describing repetitive data processing tasks, in which the same acyclically-connected collection of operations is applied to many data items. They can be executed as a parallel algorithm in which each operation is performed by a parallel process as soon as another set of inputs becomes available to it.[35]
数据式编程（英语：Dataflow programming）语言描述针对数据流（英语：data stream）的操作，以及操作的输出和其他操作的输入之间的关系。这类型的语言使得描绘高重复率数据处理任务的变得更加简单，因为同样的数据操作可以应用于许多数据项。数据操作可以用有向无环图来表示。这些数据操作可以被并发执行，其中每一个操作都是在另一组输入可用时由一个并行进程来执行的，从而高效利用多核心处理器。[35]
In compilers, straight line code (that is, sequences of statements without loops or conditional branches) may be represented by a DAG describing the inputs and outputs of each of the arithmetic operations performed within the code. This representation allows the compiler to perform common subexpression elimination efficiently.[36] At a higher level of code organization, the acyclic dependencies principle states that the dependencies between modules or components of a large software system should form a directed acyclic graph.[37]
在编译器中，直线码（不含条件分支和循环的代码段）可以使用有向无环图表示。图标示出每个算术运算的输入和输出。这种表示法让编译器能执行通用子表达式删除（英语：common subexpression elimination），使得代码更高效。在更高级别的代码组织中，非循环依赖性原则指出，大型软件系统的模块或组件之间的依赖关系应形成一个有向非循环图。[37]
=== Causal structures 因果结构 ===
An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a [[spreadsheet]] after one of the cells has been changed, or the [[object file]]s of a piece of computer software after its [[source code]] has been changed.
An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a [[spreadsheet]] after one of the cells has been changed, or the [[object file]]s of a piece of computer software after its [[source code]] has been changed.
在引用图中，顶点是只有一个出版日期的文档。边代表从一个文档的参考书目到其他必要的早期文档的引用。经典的例子来自于学术论文之间的引用，正如1965年德瑞克·约翰·德索拉·普莱斯在《科学论文网络》一文中指出的那样，他继续创造了引用网络的第一个模型---- 价格模型。在这种情况下，一篇论文的引文数量就是引文网络相应顶点的度数。这是21引文分析的一项重要措施。法院判决提供了另一个例子，因为法官通过回顾以前案件中作出的其他判决来支持他们在一个案件中的结论。最后一个例子是专利，必须提到先前的技术，先前的专利，这是有关当前的专利权利主张。通过考虑有向无环图的特殊性质，可以利用网络分析方法分析引文网络。例如，传递减法对不同应用中的引用分布提供了新的见解，突出了不同上下文中引用网络形成机制的明显差异。另一种技术是主路径分析，它跟踪引文链接，并提出给定引文图中最重要的引文链。
在引用图中，顶点是只有一个出版日期的文档。边代表从一个文档的参考书目到其他必要的早期文档的引用。经典的例子来自于学术论文之间的引用，正如1965年德瑞克·约翰·德索拉·普莱斯在《科学论文网络》一文中指出的那样，他继续创造了引用网络的第一个模型---- 价格模型。在这种情况下，一篇论文的引文数量就是引文网络相应顶点的度数。这是21引文分析的一项重要措施。法院判决提供了另一个例子，因为法官通过回顾以前案件中作出的其他判决来支持他们在一个案件中的结论。最后一个例子是专利，必须提到先前的技术，先前的专利，这是有关当前的专利权利主张。通过考虑有向无环图的特殊性质，可以利用网络分析方法分析引文网络。例如，传递减法对不同应用中的引用分布提供了新的见解，突出了不同上下文中引用网络形成机制的明显差异。另一种技术是主路径分析，它跟踪引文链接，并提出给定引文图中最重要的引文链。