离散数学：4-7-1 二元关系与函数

复习思考题11设f1、

f2RR，R为实数集，且定义R上的等价关系T1、T2，使得：则T1对应的划分是__________则T2对应的划分是__________{{x}|xR}{Z,R-Z}复习思考题11设f1、

f2RR，R为实数集，且定义R上的等价关系T1、T2，使得：设g1,g2为自然映射，gi:RR/Ti,gi(x)=[x]

g1为单射、满射、双射？__________

g2为单射、满射、双射？__________

g2(0)=______,g2(0.9)=______ZR-Z满射、非单射满射、单射、双射第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数

集合论在计算机科学中的应用集合论在计算机科学中的应用关系在关系数据库中的应用数据的插入相当于集合的并运算数据的删除相当于集合的差运算数据的自然联接相当于集合的笛卡尔积运算数据的投影相当于集合的子集运算(行)数据的选择相当于集合的子集运算(列)单机调度问题：设有1台机器,任务集T={t1,t2,t3,t4,t5,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完成之后才可加工。调度：任务安排在机器上加工的方案截止时间：开始时刻0，最后停止加工机器的停机时刻单机调度问题：设有1台机器,任务集T={t1,t2,t3,t4,t5,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项任务的哈斯图如上图t4

t5

t6

t2t3

t1单机调度----拓扑排序拓扑排序构造一个包含某个给定部分序的全序的过程。拓扑排序算法----对有限集T上给定的部分序R，产生一个全序SStep1:(初始化)令k=1，T‘=T(T‘存放剩下未排序元素)Step2:(取下一个元素)WhileT’≠{对R在T’上诱导出来的部分序，选取任一个极小元TkT’=T’-Tkk=k+1}Step3:(定义S)定义T上的全序S：<Ti,Tj>S当且仅当i≤jt4

t5

t6

t2t3

t1双机调度问题：有2台机器c1,c2,任务集T={t1,t2,t3,t4,t5,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完成之后才可加工。调度：任务安排在机器上加工的方案截止时间：开始时刻0，最后停止加工机器的停机时刻两个调度方案

D=6D=5t1t2t3t4t5t6t1t3t5t2t6t4t4

t5

t6

t2t3

t1l(t1)=l(t3)=l(t5)=l(t6)=1,

l(t2)=l(t4)=2多机调度问题描述有n项任务要分配到m台相同的机器上加工，对每项任务i有加工时间l(i),i=1,2,…,n，已知在某些任务之间有着加工顺序的约束，设所有机器都可以从0时刻开始工作；在同一时刻每台机器只能加工一项任务；在同一台机器上两个连续任务之间无等待时间；整个任务的截止时间为最后一台机器的停机的时间.问如何安排任务的加工次序，使截止时间D最小？——可行调度问题集合任务集T={t1,t2,...,tn},nZ+机器集M={c1,c2,...,cm}，mZ+时间集

N函数和关系R加工时间——函数l:TZ+.顺序约束

R——T上的偏序关系，定义为：

R={<ti,tj>|ti,tjT,i=j或ti完成后tj才可开始加工}多机调度——问题描述多机调度——问题描述（续）

可行调度

分配到机器：T的划分

={T1,T2,...,Tm}，

划分块Tj是T的非空子集，由安排在机器cj上加工的所有任务组成.

多机调度——问题描述（续）

可行调度每个机器上的任务开始时间Tj，存在调度函数

j:TjN，满足以下条件：(1)任意时刻i，每台机器上正在加工至多1个任务i,0

i<D,

|{tk

|tkTj,j(tk)i<j(tk)+l(tk)}|

1,

j=1,2,…,m(2)任务的安排满足偏序约束tiTi,tjTj,

<ti,tj>R

i(ti)+l(ti)j(tj)i,j=1,2,…,m多机调度——问题描述（续）机器j的停止时间

Dj=max{j(tk)|tkTj}+l(tk)所有任务的截止时间

D=max{