387
个编辑
更改
→Data processing networks 数据处理网络
计划评审技术是一种基于有向无环图的计划排定技术，通常用于组织大型的人工项目。在计划评审技术中，每个顶点表示项目的一个里程碑（英语：Milestone (project management)），每条有向边表示任务或者活动，连接着表示任务开始或结束的两个节点。每条边则被标注上预估需时。图中的最长路径即为项目的关键路径。关键路径决定了项目所需的总时间，里程碑的完成时间取决于结束于本顶点的最长路径。[33]
计划评审技术是一种基于有向无环图的计划排定技术，通常用于组织大型的人工项目。在计划评审技术中，每个顶点表示项目的一个里程碑（英语：Milestone (project management)），每条有向边表示任务或者活动，连接着表示任务开始或结束的两个节点。每条边则被标注上预估需时。图中的最长路径即为项目的关键路径。关键路径决定了项目所需的总时间，里程碑的完成时间取决于结束于本顶点的最长路径。[33]
=== Data processing networks 数据处理网络 ===
=== Data processing networks 数据处理网络===
the length of the longest path, from the n-th node added to the network to the first node in the network, scales as <math>\ln(n)</math>.
最长路径的长度，从添加到网络的第 n 个节点到网络中的第一个节点，缩放为 < math > ln (n) </math > 。
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.
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 gate]]s that computes a function of an input, where the input and output of the function are represented as individual [[bit]]s. 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.<ref>{{citation|title=Timing|first=Sachin|last=Sapatnekar|publisher=Springer|year=2004|isbn=978-1-4020-7671-8|page=133|url=https://books.google.com/books?id=fL9k-VkZVr0C&pg=PA133}}.</ref> 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]纸上或数据库中的电子电路原理图是一种有向无环图的形式，它使用实例或元件来形成对低级元件的有向引用。电子电路本身不一定是非循环的或定向的。
Directed acyclic graphs may also be used as a compact representation of a collection of sequences. In this type of application, one finds a DAG in which the paths form the given sequences. When many of the sequences share the same subsequences, these shared subsequences can be represented by a shared part of the DAG, allowing the representation to use less space than it would take to list out all of the sequences separately. For example, the directed acyclic word graph is a data structure in computer science formed by a directed acyclic graph with a single source and with edges labeled by letters or symbols; the paths from the source to the sinks in this graph represent a set of strings, such as English words. Any set of sequences can be represented as paths in a tree, by forming a tree vertex for every prefix of a sequence and making the parent of one of these vertices represent the sequence with one fewer element; the tree formed in this way for a set of strings is called a trie. A directed acyclic word graph saves space over a trie by allowing paths to diverge and rejoin, so that a set of words with the same possible suffixes can be represented by a single tree vertex.
有向无环图也可用作序列集合的紧凑表示。在这种类型的应用程序中，人们会找到一个 DAG，其中的路径形成给定的序列。当许多序列共享相同的子序列时，这些共享子序列可以由 DAG 的一个共享部分来表示，这使得这种表示比单独列出所有序列所需要的空间更少。例如，有向无环词图是计算机科学中的一种数据结构，由一个单源的有向无环图构成，其边缘用字母或符号标记; 在这个图中，从源到汇的路径表示一组字符串，例如英语单词。任何一组序列都可以表示为树中的路径，方法是为序列的每个前缀形成一个树顶点，并使其中一个顶点的父顶点表示只有一个元素的序列; 对于一组字符串以这种方式形成的树称为 trie。有向无环词图允许路径发散和重新连接，从而在一个三元图上节省空间，这样一组可能具有相同后缀的词可以由一个树顶点表示。
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]] languages describe systems of operations on [[data stream]]s, 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.<ref>{{citation|title=Programming Symposium|series=Lecture Notes in Computer Science|volume=19|year=1974|pages=362–376|contribution=First version of a data flow procedure language|first=Jack B.|last=Dennis|doi=10.1007/3-540-06859-7_145|isbn=978-3-540-06859-4}}.</ref>
数据式编程（英语：Dataflow programming）语言描述针对数据流（英语：data stream）的操作，以及操作的输出和其他操作的输入之间的关系。这类型的语言使得描绘高重复率数据处理任务的变得更加简单，因为同样的数据操作可以应用于许多数据项。数据操作可以用有向无环图来表示。这些数据操作可以被并发执行，其中每一个操作都是在另一组输入可用时由一个并行进程来执行的，从而高效利用多核心处理器。[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]
The same idea of using a DAG to represent a family of paths occurs in the binary decision diagram, a DAG-based data structure for representing binary functions. In a binary decision diagram, each non-sink vertex is labeled by the name of a binary variable, and each sink and each edge is labeled by a 0 or 1. The function value for any truth assignment to the variables is the value at the sink found by following a path, starting from the single source vertex, that at each non-sink vertex follows the outgoing edge labeled with the value of that vertex's variable. Just as directed acyclic word graphs can be viewed as a compressed form of , binary decision diagrams can be viewed as compressed forms of decision trees that save space by allowing paths to rejoin when they agree on the results of all remaining decisions.
使用 DAG 表示一系列路径的同样想法也出现在二元决策图中，这是一个基于 dags 的数据结构，用于表示二进制函数。在二元决策图中，每个无汇点都用一个二进制变量的名称标记，每个汇点和每条边都用一个0或1标记。任何对变量进行真值赋值的函数值，都是指从单个源顶点开始，沿着一条路径，在每个非汇顶点上沿着标有该顶点变量值的外向边缘，在汇处找到的值。正如有向无环字图可以看作是一种压缩形式，二叉决策图可以看作是一种压缩形式的决策树，通过允许路径在所有剩余决策的结果一致时重新连接来节省空间。
In [[compiler]]s, 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.<ref>{{citation|title=Advanced Backend Optimization|first1=Sid|last1=Touati|first2=Benoit|last2=de Dinechin|publisher=John Wiley & Sons|year=2014|isbn=978-1-118-64894-0|page=123|url=https://books.google.com/books?id=nO2-AwAAQBAJ&pg=PA123}}.</ref> 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.<ref>{{citation|title=Large-Scale Software Architecture: A Practical Guide using UML|first1=Jeff|last1=Garland|first2=Richard|last2=Anthony|publisher=John Wiley & Sons|year=2003|isbn=9780470856383|page=215|url=https://books.google.com/books?id=_2oQLLSqZ88C&pg=PA215}}.</ref>
在编译器中，直线码（不含条件分支和循环的代码段）可以使用有向无环图表示。图标示出每个算术运算的输入和输出。这种表示法让编译器能执行通用子表达式删除（英语：common subexpression elimination），使得代码更高效。在更高级别的代码组织中，非循环依赖性原则指出，大型软件系统的模块或组件之间的依赖关系应形成一个有向非循环图。[37]
在编译器中，直线码（不含条件分支和循环的代码段）可以使用有向无环图表示。图标示出每个算术运算的输入和输出。这种表示法让编译器能执行通用子表达式删除（英语：common subexpression elimination），使得代码更高效。在更高级别的代码组织中，非循环依赖性原则指出，大型软件系统的模块或组件之间的依赖关系应形成一个有向非循环图。[37]
[[Feedforward neural network]]s are another example.
=== Causal structures 因果结构 ===
=== Causal structures 因果结构 ===