Mathematics for Computer Science MIT 6.042J/18.062J DAGs, Partial Orders, Scheduling Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.1 Normal Person’s Graph y x y = f(x) Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.2 Computer Scientist’s Graph b a c d f e Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.3 Relations and Graphs b a set of vertices V set of edges E, E ⊆ V × V dc (Formally the same as a binary relation on V.) V={a,b,c,d} E = {(a,b), (a,c), (c,b)} Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.4 Graphical Properties of Relations Reflexive Symmetric Transitive Antisymmetric NO Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.5 Paths A R Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.6 12 L4-2.7 September 28, 2005 Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. A R= paths of length 1 R2 from A to A R2 = paths of length 2 R≤2 = paths of length ≤2 L4-2.11 September 28, 2005 Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. Some Course 6 Prerequisites • 18.01 → 6.042 • 18.01 → 18.02 • 18.01 → 18.03 • 8.01 → 8.02 • 6.001 → 6.034 • 6.042 → 6.046 • 18.03, 8.02 → 6.002 • 6.001, 6.002 → 6.004 • 6.001, 6.002 → 6.003 • 6.004 → 6.033 • 6.033 → 6.857 • 6.046 → 6.840 L4-2.12 September 28, 2005 Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. Indirect Prerequisites 18.01 is indirect prereq. of 6.840 © a1 and a2 are by path of length in the graph of R a1Rka2 a1R≤ka2 iff a1 and a2 are by path of length R L4-2.8 September 28, 2005 Copyright Albert R. Meyer and Ronitt Rubinfeld 2005. Path Relations connected exactly k iff connected at most k in the graph of © Reflexive Transitive Closure a1R* a2 iff a1 and a2 are by path © class c is a prerequisite for class d c→d L4-2.9 September 28, 2005 Copyright Albert R. Meyer and Ronitt Rubinfeld 2005. connected L4-2.10 September 28, 2005 Copyright Albert R. Meyer and Ronitt Rubinfeld 2005. Prerequisite Relation on Classes 18.01 → → 6.046 → 6.8406.042© "Freshman classes" 18.01 6.0018.01 d nothing → d © d is minimal for → there is no c s.t. c→d Minimal elements L4-2.13 September 28, 2005 Copyright Albert R. Meyer and Ronitt Rubinfeld 2005. Classes with no prereqs is a Freshman class iff L4-2.14 September 28, 2005 Copyright Albert R. Meyer and Ronitt Rubinfeld 2005. Prerequisite graph 18.02 18.01 6.046 6.840 18.03 6.001 6.034 6.003 8.01 8.02 6.002 6.004 6.033 6.857 6.042 Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.15 minimal not minimum minimum means "smallest" -- a prereq. for every class no minimum in this example Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.16 Team Problem Problem 1,2 Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.17 Prerequisite graph What if there is a cycle in this graph? -- a path from class c to class d and back to class c? No one can graduate! Comm. on Curricula & Registrar are supposed to prevent cycles. Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.18 3Directed Acyclic Graph (DAG) 18.02 18.01 6.046 6.840 18.03 6.001 6.034 6.003 8.01 8.02 6.002 6.004 6.033 6.857 6.042 Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.19 Constructing the DAG • 18.01 → 6.042 • 18.03, 8.02 → 6.002 • 18.01 → 18.02 • 6.001, 6.002 → 6.004 • 18.01 → 18.03 • 6.001, 6.002 → 6.003 • 8.01 → 8.02 • 6.004 → 6.033 • 6.033 → 6.857 • 6.001 → 6.034 • 6.046 → 6.840 • 6.042 → 6.046 Identify Minimal Elements Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.21 Constructing the DAG • 18.01 → 6.042 • 18.03, 8.02 → 6.002 • 18.01 → 18.02 • 6.001, 6.002 → 6.004 • 18.01 → 18.03 • 6.001, 6.002 → 6.003 • 8.01 → 8.02 • 6.004 → 6.033 • 6.033 → 6.857 • 6.001 → 6.034 • 6.046 → 6.840 • 6.042 → 6.046 Remove minimal elements Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.23 DAG's = Partial Orders Theorem: • The path relation of a DAG is a partial order. • The graph of a partial order is a DAG. Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.20 Directed Acyclic Graph (DAG) 18.01 6.0018.01 Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.22 Constructing the DAG • 6.042 • 18.03, 8.02 → 6.002 • 18.02 • 6.002 → 6.004 • 18.03 • 6.002 → 6.003 • 8.02 • 6.004 → 6.033 • 6.033 → 6.857 • 6.034 • 6.046 → 6.840 • 6.042 → 6.046 Remove minimal elements Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.24 4Constructing the DAG 6.042 18.02 18.03 8.02 6.034 • 18.03, 8.02 → 6.002 • • • 6.002 → 6.004 • 6.002 → 6.003 • • 6.004 → 6.033 • • 6.033 → 6.857 • • 6.046 → 6.840 • 6.042 → 6.046 Identify new minimal elements Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.25 Directed Acyclic Graph (DAG) 18.02 18.01 6.046 18.03 6.001 6.034 8.01 8.02 6.002 6.042 Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.27 Topological sort • Is there a way of graduating? (in any number of semesters?) • Yes - take a minimal remaining course each semester Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.29 Directed Acyclic Graph (DAG) 18.02 18.01 18.03 6.001 6.034 8.01 8.026.042 continue in this way… Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.26 Prerequisite graph 18.02 18.01 6.046 6.840 18.03 6.001 6.034 6.003 8.01 8.02 6.002 6.004 6.033 6.857 6.042 Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.28 How many terms to graduate? 18.02 18.01 6.046 6.840 18.03 6.001 6.034 6.003 8.01 8.02 6.002 6.004 6.033 6.857 6.042 maximum chain Copyright © Albert R. Meyer and Ronitt Rubinfeld 2005. September 28, 2005 L4-2.30 5Parallel Task Scheduling • 6 terms are necessary to complete the curriculum • and sufficient (if you can take unlimited courses per term...)
View Full Document
Unlocking...