計(jì)算理論與算法16年CH0

1、CH0 緒論 2021-12-142 of 158n 元素、成員元素、成員n 單元集單元集n 不相交不相交n A1, A2, , An=A1 A2 An A1, A2, , An=A1 A2 Ann 冪集冪集2An 劃分劃分1 集合2021-12-143 of 158n 有序?qū)τ行驅(qū)?(a, b)n 笛卡兒積笛卡兒積n 函數(shù)函數(shù)f：AB n BA = f | f：AB n函數(shù)函數(shù) f：AB, AAnfA：值域、定義域的像：值域、定義域的像 3函數(shù)與關(guān)系:NNN,( , )( , )ffm nmnf m nmn2021-12-144 of 158n 一對一一對一n 滿射滿射n 雙射雙射n 逆函數(shù)

2、逆函數(shù) 3 關(guān)系與函數(shù)2021-12-145 of 158n合成合成Q R 3 函數(shù)與關(guān)系Q R = | c ( Q R) f g(a) = h(a) = g(f(a) 2021-12-146 of 158n自反、對稱、反對稱、傳遞自反、對稱、反對稱、傳遞3 特殊的二元關(guān)系自反自反對稱對稱反對稱反對稱傳遞性傳遞性關(guān)關(guān)系系圖圖各點(diǎn)各點(diǎn)都有都有環(huán)環(huán)無單無單向邊向邊無雙向邊無雙向邊xi到到xj有邊有邊, xj 到到xk有有邊邊, 則則xi到到xk也有邊也有邊 2021-12-147 of 158n 無向圖（簡稱圖）無向圖（簡稱圖）n 等價關(guān)系等價關(guān)系n 等價類等價類n 偏序偏序n 全序全序n 極小元

3、極小元3 特殊的二元關(guān)系2021-12-148 of 158n 等勢等勢n 有窮的、無窮的有窮的、無窮的 若有一個從集合 1, , n 到A 的雙射函數(shù),則稱A 是有窮的; 若A 不是有窮的,則它是無窮的.n 無窮可數(shù)的：與無窮可數(shù)的：與N等勢的等勢的 n 可數(shù)的：有窮的或可數(shù)無窮的可數(shù)的：有窮的或可數(shù)無窮的n 不可數(shù)的不可數(shù)的3 有窮集合與無窮集合2021-12-149 of 158n 3 有窮集合與無窮集合2021-12-1410 of 158n 數(shù)學(xué)歸納法數(shù)學(xué)歸納法n 反證法反證法n 鴿巢原理鴿巢原理4 三個基本的證明技術(shù)2021-12-1411 of 158n由特定的符號組成的有限集合

4、稱為由特定的符號組成的有限集合稱為字母字母表表。常見的字母表是由。常見的字母表是由26個英文字母、個英文字母、10個阿拉伯?dāng)?shù)字、運(yùn)算符號等組成的集個阿拉伯?dāng)?shù)字、運(yùn)算符號等組成的集合。合。0和和1兩個數(shù)字也可以組成字母表。兩個數(shù)字也可以組成字母表。n設(shè)設(shè)是一個字母表，由是一個字母表，由上的符號組成的上的符號組成的有窮序列稱為有窮序列稱為上的上的字符串字符串。n空串空串: e或者或者.5 字母表與語言2021-12-1412 of 158n連接連接: x y 或者或者xy n前綴前綴.n后綴后綴.n子串子串.n反轉(zhuǎn)反轉(zhuǎn). xR (wx)R= xRwR5 字母表與語言2021-12-1413 of

5、158n字母表字母表上滿足一定條件的字符串的上滿足一定條件的字符串的集合集合L，稱為，稱為上的一種上的一種語言語言。n例例 全體全體3位二進(jìn)制數(shù)組成的字母表位二進(jìn)制數(shù)組成的字母表0，1上的語言可用列舉法表示出來：上的語言可用列舉法表示出來：L000，001，010，011，100，101，110，111。5 字母表與語言2021-12-1414 of 158n正則運(yùn)算正則運(yùn)算:定義正則運(yùn)算并定義正則運(yùn)算并,連接連接,星號如下星號如下: 并并: A B=x|x A或或x B 連接連接: A B=xy|x A且且y B 星號星號: A*=x1x2xk|k 0且每個且每個xi A設(shè)字母表設(shè)字母表 由由標(biāo)準(zhǔn)的標(biāo)準(zhǔn)的2626個字母組成個字母組成A=good,bad, B=boy,gi