計(jì)算機(jī)問題求解：函數(shù)

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

–

論題1-10

函數(shù)問題1:“函數(shù)”與“關(guān)系”有什么異同？問題2：這里的function與你中學(xué)時(shí)熟悉的函數(shù)有什么異同？問題3：你是否能解釋一下？(SeeFigureabove)問題4：關(guān)于函數(shù)自變量的集合只有一個(gè)(domain)，關(guān)于函數(shù)值的集合卻有兩個(gè)(codomain和range)，為什么？問題5:書中提出了什么問題?你想出了什么“自己”的問題嗎？幾種特殊的函數(shù)滿射

:A

B是滿射的：ran

=B,iff.

y

B,

x

A,使得

(x)=y單射（一對一的）

:A

B是單射的：

y

ran

,

!x

A,使得

(x)=yiff.

x1,x2

A,若x1

x2，則

(x1)

(x2)iff.

x1,x2

A,若

(x1)=

(x2)，則x1=x2。雙射（一一對應(yīng)的）滿射+單射幾種特殊的函數(shù)：例子

:R

R,

(x)=-x2+2x-1

:Z+

R,

(x)=lnx,單射

:R

Z,

(x)=

x

,滿射

:R

R,

(x)=2x-1，雙射

:R+

R+,

(x)=(x2+1)/x注意：f(x)2,而對任意正實(shí)數(shù)x，f(x)=f(1/x)

:R

R

R

R,

(<x,y>)=<x+y,x-y>,雙射。

:N

N

N,

(<x,y>)=|x2-y2|問題6:為什么?有限集合上一一對應(yīng)的函數(shù)的例子S={1,2,3},可以在S上定義6個(gè)不同的一一對應(yīng)的函數(shù)(每一個(gè)稱為一個(gè)“置換”):問題7:這兩個(gè)定義有什么關(guān)聯(lián)?問題8:

和(

)(x)

有什么不同?={(1,2),(2,3),(3,1)};={(1,3),(2,2),(3,1)};

={(1,2),(2,1),(3,3)}=問題9:你能否討論一下函數(shù)復(fù)合與函數(shù)性質(zhì)之間的關(guān)聯(lián)?復(fù)合運(yùn)算保持

函數(shù)性質(zhì)：單射單射的復(fù)合是單射

定理：如果f:A

B,g:B

C均是單射，則g

f:A

C也是單射。證明要點(diǎn)：若不然，即存在x1,x2A,且x1

x2，使得g

f（x1)=g

f(x2)

，設(shè)f(x1)=t1,f(x2)=t2， 如果t1=t2，與f是單射矛盾。 如果t1

t2，與g是單射矛盾。但是…若g

f是單射，能推出f和g是單射嗎？顯然，f一定是單射。

若存在t1,t2

B,t1

t2，但g(t1)=g(t2),(即：g不是單射！)只要t1或者t2不在f值域內(nèi)，則g

f仍然可能是單射。fgABC關(guān)于反函數(shù)問題10:這些函數(shù)是否都有反函數(shù),各自的反函數(shù)是什么?123順時(shí)針旋轉(zhuǎn)：0度：e120度：

240度：

繞軸翻轉(zhuǎn)

問題11:為什么函數(shù)存在反函數(shù)的充分必要條件是該函數(shù)是bijection?換一個(gè)角度看“undo”。Hashing:計(jì)算機(jī)科學(xué)中的多對一函數(shù)KeySpaceHashFunctionE[0]E[1]E[m-1]ValueofaspecifickeyAcalculatedarrayindexforthekeyVerylarge,butonlyasmallpartisusedinanapplicationInfeasiblesize

IndexdistributionCollisionhandlingE[k]xH(x)=k問題12:你認(rèn)為一個(gè)好的Hash函數(shù)應(yīng)該滿足什么樣的條件?課外作業(yè)UD13.3-13.5,

13.11,

13.13;UD14.8,

14