計算理論與算法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 有序對有序對 (a, b)n 笛卡兒積笛卡兒積n 函數函數f：AB n BA = f | f：AB n函數函數 f：AB, AAnfA：值域、定義域的像：值域、定義域的像 3函數與關系:NNN,( , )( , )ffm nmnf m nmn2021-12-144 of 158n 一對一一對一n 滿射滿射n 雙射雙射n 逆函數

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

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

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

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