復(fù)習(xí)思考題11設(shè)f1、

f2RR，R為實(shí)數(shù)集，且定義R上的等價(jià)關(guān)系T1、T2，使得：則T1對(duì)應(yīng)的劃分是__________則T2對(duì)應(yīng)的劃分是__________{{x}|xR}{Z,R-Z}復(fù)習(xí)思考題11設(shè)f1、

f2RR，R為實(shí)數(shù)集，且定義R上的等價(jià)關(guān)系T1、T2，使得：設(shè)g1,g2為自然映射，gi:RR/Ti,gi(x)=[x]

g1為單射、滿射、雙射？__________

g2為單射、滿射、雙射？__________

g2(0)=______,g2(0.9)=______ZR-Z滿射、非單射滿射、單射、雙射第4章二元關(guān)系與函數(shù)4.1集合的笛卡兒積與二元關(guān)系4.2關(guān)系的運(yùn)算4.3關(guān)系的性質(zhì)4.4關(guān)系的閉包4.5等價(jià)關(guān)系和偏序關(guān)系4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復(fù)合和反函數(shù)

集合論在計(jì)算機(jī)科學(xué)中的應(yīng)用集合論在計(jì)算機(jī)科學(xué)中的應(yīng)用關(guān)系在關(guān)系數(shù)據(jù)庫(kù)中的應(yīng)用數(shù)據(jù)的插入相當(dāng)于集合的并運(yùn)算數(shù)據(jù)的刪除相當(dāng)于集合的差運(yùn)算數(shù)據(jù)的自然聯(lián)接相當(dāng)于集合的笛卡爾積運(yùn)算數(shù)據(jù)的投影相當(dāng)于集合的子集運(yùn)算(行)數(shù)據(jù)的選擇相當(dāng)于集合的子集運(yùn)算(列)單機(jī)調(diào)度問(wèn)題：設(shè)有1臺(tái)機(jī)器,任務(wù)集T={t1,t2,t3,t4,t5,t6}

每項(xiàng)任務(wù)的加工時(shí)間為:

l(t1)=l(t3)=l(t5)=l(t6)=1,l(t2)=l(t4)=2任務(wù)之間的順序約束是：t3只有在t5和t6完成之后才可加工；t2只有在t6、t5和t4都完成之后才可加工；t1只有在t3和t2完成之后才可加工。調(diào)度：任務(wù)安排在機(jī)器上加工的方案截止時(shí)間：開(kāi)始時(shí)刻0，最后停止加工機(jī)器的停機(jī)時(shí)刻單機(jī)調(diào)度問(wèn)題：設(shè)有1臺(tái)機(jī)器,任務(wù)集T={t1,t2,t3,t4,t5,t6}

每項(xiàng)任務(wù)的加工時(shí)間為:

l(t1)=l(t3)=l(t5)=l(t6)=1,l(t2)=l(t4)=2任務(wù)之間的順序約束是：t3只有在t5和t6完成之后才可加工；t2只有在t6、t5和t4都完成之后才可加工；t1只有在t3和t2完成之后才可加工。順序約束R是T上的偏序關(guān)系，定義為

R={<ti,tj>|ti,tj

T,i=j

或ti完成后tj才可開(kāi)始加工}6項(xiàng)任務(wù)的哈斯圖如上圖t4

t5

t6

t2t3

t1單機(jī)調(diào)度----拓?fù)渑判蛲負(fù)渑判驑?gòu)造一個(gè)包含某個(gè)給定部分序的全序的過(guò)程。拓?fù)渑判蛩惴?---對(duì)有限集T上給定的部分序R，產(chǎn)生一個(gè)全序SStep1:(初始化)令k=1，T‘=T(T‘存放剩下未排序元素)Step2:(取下一個(gè)元素)WhileT’≠{對(duì)R在T’上誘導(dǎo)出來(lái)的部分序，選取任一個(gè)極小元TkT’=T’-Tkk=k+1}Step3:(定義S)定義T上的全序S：<Ti,Tj>S當(dāng)且僅當(dāng)i≤jt4

t5

t6

t2t3

t1雙機(jī)調(diào)度問(wèn)題：有2臺(tái)機(jī)器c1,c2,任務(wù)集T={t1,t2,t3,t4,t5,t6}每項(xiàng)任務(wù)的加工時(shí)間為:l(t1)=l(t3)=l(t5)=l(t6)=1,l(t2)=l(t4)=2任務(wù)之間的順序約束是：t3只有在t5和t6完成之后才可加工；t2只有在t6、t5和t4都完成之后才可加工；t1只有在t3和t2完成之后才可加工。調(diào)度：任務(wù)安排在機(jī)器上加工的方案截止時(shí)間：開(kāi)始時(shí)刻0，最后停止加工機(jī)器的停機(jī)時(shí)刻兩個(gè)調(diào)度方案

D=6D=5t1t2t3t4t5t6t1t3t5t2t6t4t4

t5

t6

t2t3

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

l(t2)=l(t4)=2多機(jī)調(diào)度問(wèn)題描述有n項(xiàng)任務(wù)要分配到m臺(tái)相同的機(jī)器上加工，對(duì)每項(xiàng)任務(wù)i有加工時(shí)間l(i),i=1,2,…,n，已知在某些任務(wù)之間有著加工順序的約束，設(shè)所有機(jī)器都可以從0時(shí)刻開(kāi)始工作；在同一時(shí)刻每臺(tái)機(jī)器只能加工一項(xiàng)任務(wù)；在同一臺(tái)機(jī)器上兩個(gè)連續(xù)任務(wù)之間無(wú)等待時(shí)間；整個(gè)任務(wù)的截止時(shí)間為最后一臺(tái)機(jī)器的停機(jī)的時(shí)間.問(wèn)如何安排任務(wù)的加工次序，使截止時(shí)間D最小？——可行調(diào)度問(wèn)題集合任務(wù)集T={t1,t2,...,tn},nZ+機(jī)器集M={c1,c2,...,cm}，mZ+時(shí)間集

N函數(shù)和關(guān)系R加工時(shí)間——函數(shù)l:TZ+.順序約束

R——T上的偏序關(guān)系，定義為：

R={<ti,tj>|ti,tjT,i=j或ti完成后tj才可開(kāi)始加工}多機(jī)調(diào)度——問(wèn)題描述多機(jī)調(diào)度——問(wèn)題描述（續(xù)）

可行調(diào)度

分配到機(jī)器：T的劃分

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

劃分塊Tj是T的非空子集，由安排在機(jī)器cj上加工的所有任務(wù)組成.

多機(jī)調(diào)度——問(wèn)題描述（續(xù)）

可行調(diào)度每個(gè)機(jī)器上的任務(wù)開(kāi)始時(shí)間Tj，存在調(diào)度函數(shù)

j:TjN，滿足以下條件：(1)任意時(shí)刻i，每臺(tái)機(jī)器上正在加工至多1個(gè)任務(wù)i,0

i<D,

|{tk

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

1,

j=1,2,…,m(2)任務(wù)的安排滿足偏序約束tiTi,tjTj,

<ti,tj>R

i(ti)+l(ti)j(tj)i,j=1,2,…,m多機(jī)調(diào)度——問(wèn)題描述（續(xù)）機(jī)器j的停止時(shí)間

Dj=max{j(tk)|tkTj}+l(tk)所有任務(wù)的截止時(shí)間

D=max{