数学与资讯工程.ppt

Sep. 20, 2001 演講綱要 1. 簡介資料結構 2. Hashing (赫序) 模式 3. 如何存取小群的文字資料 4. 如何存取大群的文字資料 5. 結論與有趣問題大公開 1.簡介資料結構 ■ 資料結構─為方便資料存取的組織型態 (i) Linear Organization (線型結構) 　 (甲) 非序列結構 (sequential list) 35,18,24,12,27,44,33 (乙)序列結構(ordered list) 12,18,24,27,33,35,44 (丙)串列結構(linked list) (ii) Non-linear Organization (非線型結構) 如： binary tree 2.Hashing (赫序模式) The set of keys ■ Hashing Function ■ Collision ■ Perfect Hashing ■ Minimal Perfect Hashing 給了一組關鍵字 k={k1,k2, …, kn} H(Ki) = 餘數 (C/P(Ki)) 條件： P(Ki) 與 P(Kj) 兩兩互質 幾個疑問？ (1) 為什麼 h(ki) = 餘數(C/P(Ki))，可以為“1-1”且“onto” (2) 有沒有很有效的方法可以讓 k={k1,k2, …, kn} ? P(k1), P(k2 ), …, P(kn ) 而且兩兩互質？ (3) 如何求C？ 回答(1)：中國餘式定理 Let r1,r2, …, rn be integers an integer C s.t. 回答(2)： 利用Prime Number Functions 甲：P(x) = x2 – x + 17 for 1 x 16 乙：P(x) = x2 – x + 41 for 1 x 40 丙：P(x) = x2 – 81x + 1681 for 41 x 80 丁：P(x) = x2 +x + 41 for 1 x 39 戍：P(x) = x2 – 79x + 1601 for 40 x 79 回答(3)： 其中 且 例：m1=4, m2=5, m3=7, m4=9 M1=5*7*9=315 M2=4*7*9=252 M3=4*5*9=180 M4=4*5*7=140 假設 有沒有很有效的方法求 “b” 此為聯考常考題 Mx+My=1 求 (x,y)? 「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何」 (孫武 孫子算經) 亦即求正整數 C，使得 兩個疑問？ C 是否存在 如何求得 C 回答 (1)： 孫子定理(又稱中國餘數定理) Let r1,r2, …, rn be integers an integer C s.t. 回答(2)： 「三人同行七十稀， 五樹梅花廿一枝， 七子團圓正半月， 除百零五便得知。」 ~(程大位 算法統宗(1593)) 亦即 70*2 + 21*3 + 15*2 = 140+63+30 = 233 233 / 105 = ■ 餘 23 3. 如何存取小群文字資料 12個月份的英文名稱 選取 (第二字元，第三字元) 36 個 Pascal 保留字 Pairs AA, AD, BI, CE, CS, DN, DO, DV, ED, EE, FC, FE, FR, GO, IF, IN, LE, MD, NL, NT, OE, OF, OR, PC, PG, PK , RE, RO, ST, TE, TN, TO, UI, VR, WH, WL 4. 如何存取大群文字資料 選取 (第一字元， ) Hj (ki1, ki2) = dj(ki1)+ ( c(ki1) mod