計(jì)算機(jī)問題求解 - 算法在計(jì)算機(jī)科學(xué)中的地位

計(jì)算機(jī)問題求解

–

論題1-8

-集合及其運(yùn)算2016年11月06日PartI集合與集合代數(shù)問題1：什么是集合？你聽說過集合的數(shù)學(xué)定義嗎？問題2:兩個(gè)集合“相等”究竟是什么意思？問題3：如何將“preciselythesame”用精確的數(shù)學(xué)語言表達(dá)？A=B,ifABandBA,orA=B,ifforallx,xAifandonlyifxB問題4：結(jié)合我們前面討論的邏輯推理方法，你能理解要證明兩個(gè)集合相等，如何給出proofplan嗎？證明：方法1thePlan證明：方法2thePlan問題5：你理解集合相等在描述集合運(yùn)算性質(zhì)(定理7.4)中的作用嗎？問題6：你是否覺得有關(guān)集合運(yùn)算的性質(zhì)都“似曾相識”，你想到過為什么嗎？邏輯表達(dá)式與集合表達(dá)式如何“對應(yīng)”？等式替換：證明集合相等證明：A

B=A

當(dāng)且僅當(dāng)

A\B=

A

B=A

A\B=

:

A\B=A

Bc

=(A

Bc)(A

Ac)=A(Bc

Ac)=A(A

B)c=A

Ac=

A\B=AB=A:AB=(AB)(ABc)=A(BBc)=AE=A你能明確說出每一步演算的根據(jù)嗎？現(xiàn)在你能理解為什么我們有“集合代數(shù)”、“邏輯代數(shù)”、…這樣的名詞了吧？問題7：文氏圖是否可以用于關(guān)于集合的數(shù)學(xué)證明？文氏圖與數(shù)學(xué)證明文氏圖不能代替數(shù)學(xué)證明,但可以幫助推測結(jié)論例子：給出(A\B)

(A\C)=A的

一個(gè)盡量簡明的充要條件：A

B

C=

證明從文氏圖得到的猜想(A\B)

(A\C)=A當(dāng)且僅當(dāng)A

B

C=

（反證）假設(shè)A

B

C

，即：存在xA

B

C,

則x(A\B),x(A\C),x

(A\B)

(A\C),但由已知：(A\B)

(A\C)=A，矛盾。

A

B

C=

根據(jù)相對補(bǔ)運(yùn)算定義，A\BA,A\CA;（反證）假設(shè)(A\B)

(A\C)

A，則(A-B)

(A-C)

A;則存在x

A,但x(A\B)(A\C),即x(A\B)且x(A\C),由相對補(bǔ)運(yùn)算定義，xA

B

C,與已知條件矛盾，

(A-B)

(A-C)=A有時(shí)，證明集合相等也大不易！前4個(gè)perfect數(shù)是：6=1+2+3；28=1+2+4+7+14；496；8128我們已經(jīng)知道：1，A是P的子集2，只要是偶的perfect數(shù)，全部在A中但是……沒人知道：是否有奇的perfect數(shù)！PartII

集合模型與算法一個(gè)關(guān)于冪集的子集的例子美國的總統(tǒng)大選采用一種非常特別的“選舉人”制度。每個(gè)州的選舉人數(shù)是事先確定的。問題：有“平局”的可能嗎？問題8：你能給出這個(gè)問題基于集合的數(shù)學(xué)模型嗎？問題9：如果一個(gè)問題的解可以通過枚舉有限多個(gè)子集的集合來得到，這個(gè)問題“難”嗎？一個(gè)著名的“難”問題–背包問題優(yōu)化問題簡化版本一個(gè)“最直觀”的算法可以幫我們得到一個(gè)“不算特別差”的近似解，但近似解對我們回答前面提到的與美國總統(tǒng)選舉有關(guān)的問題沒有用。另一個(gè)關(guān)于子集的問題：精確覆蓋問題問題的描述:GivenasetAandafinitenumberofsubsetsofA:A1,A2,…Ak,aexactcoverofAwithrespecttotheAi’sisasetS

{A1,A2,…Ak},satisfying:AnytwosetsinSaredisjoint,and

S=AMathematically,wecallSapartitionofA.一個(gè)例子:A={a,b,c,d,e,f,g,h,i,j};A1={a,c,d},A2={a,b,e,f},

A3={b,f,g},A4={d,h,i},A5={a,h,j},A6={e,h},A7={c,i,j},A8={i,j}解是：{A1,A3,A6,A8

}精確覆蓋問題的矩陣表示Let|A|=n,andtherearemsubsetsforAi’s,wecanrepresenttheinputofexactcoverproblemasam

nmatrix,witheachrowforaAi.Solution:FindacollectionofrowsofM:r1,r2,…rk,satisfying:ri

rj=0for1i,jk,andr1

r2…rk=1where0=[0000000000]

1=[1111111111]and,isbooleanproduct,is booleansum Knuth給出的算法（概要）輸入：矩陣表示A（如果有一列全0，顯然無解）初始化：每行給個(gè)固定標(biāo)號；建立行的子集L（開始為空）;找出當(dāng)前矩陣中1最少的一列（比如c);從c列中選一個(gè)1，將其所在行r加入L，并執(zhí)行以下操作：Eliminateanyrowrihavingtheproperty:r

ri

0;

Eliminateallcolumnsinwhichrhasa1;Eliminaterowr;如果已經(jīng)沒有剩下任何行列，則輸出L,否則，如果有一列全0，則回溯：刪除L中的r,重新選c列中另一個(gè)1，重復(fù)以上操作。問題10：為什么可能“回溯”？什么時(shí)候沒法回溯了？“刪除”的理由是什么？為什么找最少的列？結(jié)果是:

{A1,A3,A6,A8}問題11:你知道“數(shù)獨(dú)”(Sudoku)嗎？你覺得它與“精確”、“覆蓋”有什么聯(lián)系？簡單一點(diǎn)，且考慮3

3的。精確覆蓋問題與“數(shù)獨(dú)”我們?nèi)绾巍案采w”用“動(dòng)作”覆蓋33的矩陣，每個(gè)動(dòng)作用1個(gè)特定數(shù)字“覆蓋”1個(gè)特定“位置”如何實(shí)現(xiàn)“精確”每個(gè)動(dòng)作對其它動(dòng)作產(chǎn)生“限制”位置限制：唯一行與列的限制：同一數(shù)字不重復(fù)構(gòu)造集合覆蓋矩陣每個(gè)動(dòng)作對應(yīng)于1行：共27個(gè)動(dòng)作，所以總共應(yīng)該有27行。每個(gè)動(dòng)作產(chǎn)生3個(gè)限制：1行中應(yīng)該有3個(gè)“1”（位置、行、列）位置有9個(gè)；（數(shù)字，行），（數(shù)字，列）組合也各有9個(gè)。所以總共應(yīng)該有27列填入1填入2填入3k填在(i,j)中k在第i行k在第i列2放在(1,3)問題12：流行的數(shù)獨(dú)是99的，用的數(shù)字是1-9，除了關(guān)于行與列的限制外，還有關(guān)于“宮”的限制，即81個(gè)位置劃分為9個(gè)33的“宮”，每個(gè)宮中沒有重復(fù)數(shù)字。你能說說應(yīng)該用什么樣的集合精確覆蓋矩陣嗎？順便問一下，為了答案唯一，給的格