第4章 二元关系与函数 离散数学技术方案.pptVIP

第4章 二元关系与函数 4.1 集合的笛卡儿积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数 集合论在计算机科学中的应用 集合论在计算机科学中的应用 关系在关系数据库中的应用 数据的插入相当于集合的并运算 数据的删除相当于集合的差运算 数据的自然联接相当于集合的笛卡尔积运算 数据的投影 相当于集合的子集运算(行) 数据的选择 相当于集合的子集运算(列) 集合论在计算机科学中的应用----多机调度 问题描述 有n项任务要分配到m台机同的机器加工，对每项任务i有加工时间L(i),i=1,2,…,n，已知在某些任务之间有着加工顺序的约束，设 所有机器都可以从0时刻开始工作， 在同一时刻每台机器只能加工一项任务 在同一台机器上两个连续任务之间无等待时间 整个任务的截止时间为最后一台机器的停机的时间 问如何安排任务的加工次序，使截止时间D最小？——最优调度问题 单机调度 设有1台机器,6项任务t1,t2,…t6.加工时间为 L(t1)=L(t3)=L(t5)=L(t6)=1, L(t2)=L(t4)=2 顺序约束： t3只有在t5和t6完成之后才可加工， t2只有在t6、t5和t4都完成之后才可加工； t1只有在t3和t2完成之后才可加工 问如何安排任务的加工次序？ 单机调度 设有1台机器,6项任务t1,t2,…t6.加工时间为 L(t1)=L(t3)=L(t5)=L(t6)=1, L(t2)=L(t4)=2 顺序约束： t3只有在t5和t6完成之后才可加工， t2只有在t6、t5和t4都完成之后才可加工； t1只有在t3和t2完成之后才可加工 顺序约束R是T上的偏序关系，定义为 R={ti,tj|ti, tj∈T,i=j 或ti完成后tj才可开始加工} 6项任务的哈斯图如上图 4 5 6 2 3 1 多机调度 用集合、关系、函数的概念来描述这个问题 任务集T={t1,t2,…tn}, n∈Z+ 机器集M={c1,c2,…,cm}，m∈Z+ 时间集N， 加工时间L: T ?Z+, 顺序约束R是T上的偏序关系，定义为 R={ti,tj|t1, tj∈T,i=j 或ti完成后tj才可开始加工} 一个可行调度是T的划分{T1,T2,…Tm}, Ti≠?,由安排在机器cj上加工的所有任务组成， *