Cộng đồng chia sẻ tri thức Doc24.vn

Chuyên đề thuật toán số học

Gửi bởi: Võ Hoàng vào ngày 2018-01-17 22:27:41 || Kiểu file: DOC

Nội dung tài liệu Tải xuống

Các tài liệu liên quan

Loading...

Thông tin tài liệu

Chuyên đề THU TOÁN CẬ Chuyên đềTHU TOÁN CẬ I. Gi thi chungớ thu toán (Algorithmic number theory) là ngành toán đang phát tri nh, nghiên ạc trên ph ng di thu toán. Ta chú ng là trong nh ng ngành toán ươ ữh nh còn thu toán là khái ni ra đi và phát tri trong th XX. ốh thu toán đc xây ng trên nh ng thành lý thuy thu toán. ượ trong nh ng bài toán ti ng nh đã đoc gi quy trong th XX là bài toán th 10 ức Hilbertủ Có thu toán ng quát cho phép ta tr ph ng trình Diophantine ươcho tr có nghi hay không ?ướ ’. Ph ng trình Diophantine là ph ng trình có ng f(x, y, z, ươ ươ ạ= trong đó f(x, y, z, …) là đa th các bi x, y, z, có các nguyên, và các bi ch ỉnh giá tr nguyên. Bài toán này đã đc Michiakêvích gi quy tr và câu tr là ph ượ ủđnh, là không có thu toán nh y. Bài toán th 10 Hilbert đc gi quy là thành ượ ột quan tr ng cũng nh thu toán. thu toán không ch phát tri trên nh ng thành p, mà nó còn ậd ng nh ng thành hi đi, Đi hi đi, Hình đi Cũng nh các ưngành toán thu toán khác, trong thu toán cũng có nh ng bài toán NP, là không ứcó thu gi trong th gian đa th c, tiêu bi là bài toán phân tích ra các th nguyên ,ậ ốthu toán ki tra nguyên Trong bài vi này, ta ch nh ng nh thu toán, và trên ơs toán p. ấII. Các phép tính nguyênớ Trong máy tính, các đu đc bi di nh phân, vi mô ng nh ượ ướ ịphân làm cho các phép tính tr nên đn gi nhi u. cho ng quát, ta gi hai toán ng đu có đúng bit (trong tr ng các bít có nghĩa ườ ốnh thì ta thêm vào đu cho đ). 1. Phép ng và phép tr Đi phép ng và phép nhân các bít, ta có th th hi gi ng nh phép ng tr trên ệth phân Th hi ng (hay tr ph sang trái (v bít ng mũ nh tr mũ ướ ốl sau). 1. Phép nhân Đi phép nhân, ta có thu toán nhân Nga đc mô nh sau ượ ưFunction Mult(a, Integer): Integer; 1Giáo viên: Võ Tá Hoàng Chuyên đề THU TOÁN CẬ Var Integer; Begin := 0; repeat if Odd(b) then := a; := shl 1; := shr 1; until 0; Mult := c; End; xét cho kĩ thì th ra thu toán nhân Nga có cùng ng thu toán nhân hai ng ằph ng pháp mà bình th ng ta dùng tính tay, ch có đi khác là thao tác trên nh phân. ươ ườ Thu toán nhân Nga ch bít, trong tr ng ng quát ph th hi N/2 phép ườ ầc ng, do đó ph tính toán là Nộ 2. Sau đây, ta gi thi thu toán nhân khác, tuy ph nh ng có ph nh ỏh n. Gi ta ph th hi phép nhân hai có 2N bit và B. Phân tích a1*2 a2 b1*2 b2. AB a1*b1 2N (a1b2 a2b1)*2 a2b2. Ta chú ng phép nhân lu th cũng nh phép ng có th gian N. Nh xét (a1+a2)(b1 b2) a1b1 a2b2 a1b2 a2b1. Do đó bi (a1+a2)(b1 b2), a1b1, a2b2 thì có th tính đc a1b2 a2b1. ượ Qui nhân hai 2N bit nhân bit và phép tính có th gian N. ớN F(n) là th gian nhi nh th hi phép nhân hai có 2ế bit, ta có 2Giáo viên: Võ Tá Hoàng Chuyên đề THU TOÁN CẬ F(n) 3F(n­1) k2 (*) trong đó là ng th hi chi phí các phép tính ng và ch bit ịtrong qui. Chia hai (*) cho 2ỗ ướ ta đc ượ. Do đó, F(n) O( n) O( hay nói cách khác th gian th hi ệphép nhân hai bít có ph O(ố ). 3. Phép chia Trong ph này, ta trình bày thu toán chia hai nh phân có bít (A1A2A3…AN)ầ ị2 (B1B2…BN)2 cho qu th ng Q, R. ươ +B 1:Q ướ 0, 0, +B 2: i+1. ướ thúc thu toán, ng ượ 3. ướ +B 3: ướ (R shl 1) or (A[i]). 4, ng 5. ướ ượ ướ +B 4: ướ B, C[i] 1. Th hi 2. ướ +B 5: C[i] 0. Th hi 2. ướ ướHay ta có th mô ng ch ng trình ươProcedure Divide(A, LongInt; var Q, LongInt); Var Integer; Begin := 0; := 0; For := to do Begin If (A and (1 shl (N­i)) <> 0) then := (R shl 1)+1 else := shl 1; if >= then Begin 3Giáo viên: Võ Tá Hoàng Chuyên đề THU TOÁN CẬ := or (1 shl (N­i)); := B; End; End; End; Đánh giá ph pộ Thu toán chia có ph (Nậ 2). III. Thu toán Euclidậ 1. Thu toán Euclidậ Thu toán Euclid dùng tìm chung nh hai nguyên ng m, n. ướ ươThu toán ti hành nh sau :ậ 0: Đt m, n. ướ 1:ướ ta thay ng ph phép chia cho b, ng thay ng ph ượ ưc phép chia cho a. 2: ho ng 0, thì qu là b, ng th hi 1. ướ ượ ướHay thu toán đc mô ng hàm trong ngôn ng Pascal nh sau ượ ưFunction Euclid(m, Integer) Integer; Var a, Integer; Begin := m; := n; repeat if then := mod else := mod a; until (a 0) or (b 0); Euclid := b; 4Giáo viên: Võ Tá Hoàng Chuyên đề THU TOÁN CẬ End; Ta cũng có cách vi khác nh sau Function Euclid1(m, Integer) Integer; Var a, b, Integer; Begin := m; := n; repeat := mod b; := b; := r; until 0; Euclid := a; End; Trong ta đã bi ng hai nguyên ng m, kì và là chung chúng thì ươ ướ ủluôn hai nguyên u, sao cho u*m v*n d. thu toán Euclid ta cũng có th ch ra ỉđc th (u, v) nh ượ Ta chú ng vòng repeat, và đu (x, y) x, ướ tho ảmãn x*m y*n (= b). Ban đu có ng ng là (1, 0), ng ng nầ ươ ươ là (0, 1) vì 1*m 0*n 0*m 1*n Trong vòng p, ta có phép gán := mod b, phép gán này ng đng := q*b trong đó là ươ ươth ng phép chia cho (q := div b). Khi đó (xươ ặa ya ng ng bi đi ng ng ươ ươ xa := xa q*xb ya := ya q*yb 5Giáo viên: Võ Tá Hoàng Chuyên đề THU TOÁN CẬ Nh y, và luôn có th bi di ng x*m y*n và qu chung ng ướ ướ ẽcó x, ng ng là xặ ươ ứa xb ya yb Nh y, thu toán tìm u, trên thu toán ậEuclid đc vi nh sau ượ ưProcedure Euclid2(m, Integer; var u, Integer); Var a, b, q, Integer; xa, ya, xb, yb, xt, yt Integer; Begin := m; := n; xa := 1; ya := 0; xb := 0; yb := 1; repeat := div b; := mod b; := b; := r; xt := xa; yt := ya; xa := xb; ya := yb; xb := xt q*xb; yb := yt q*yb; until 0; 6Giáo viên: Võ Tá Hoàng Chuyên đề THU TOÁN CẬ := xa; := ya; End; Đánh giá ph thu toán Euclidộ ta (aế ọi bi là a, vòng th i, đánh ốtheo chi ng thúc là (aề ượ ế1 b1 ), tr đó làướ (a2 b2 ), (a3 b3 (as bs )). Ta có th ch ng ứminh ng qui max{aằ ạk bk Fk trong đó Fk là th trong dãy Fibonaci. Ta có công th sau ứFn Fn tăng theo hàm mũ, thu toán Euclid có ph lôgarit max(m, n). ủTa chú ng cách đánh giá này qua th gian th hi phép chia (mod) (trong máy tính đây là ệm nh CPU), tuy nhiên thu toán chia th hi hai bít nói chung kho ng Nộ 2. Do đó xét chi ti t, thu toán Euclid có ph O((log(max{m, n})ế 3). 2. Thu toán Euclid nh phânậ Sau đây, ta trình bày ng Quay 1. ướ 3ướ Ch ng nào khác thu toán Euclid có ph nh n. Ta có nh xét sau ậc chung nh hai a, không ph thu vào các phép bi đi sau ướ Chia (ho b) (ho b) ch n. Thay ng b. Thu toán có th mô nh sau 0ướ m, n, dem 0. 1ướ và đu ch thì ng ướ ượ 3. ướ 2ướ dem dem 1, chia và cho 2,ả còn ch thì chia cho 2, th hi ng ươ ựv b. 4ướ 6, ng ướ ượ 5.; ướ 5ướ := b, ng ượ := a. Th hi 3. ướ 6ướ := dem ch sanh trái bit ng dem Thu toán thúc và là chung ướl nh tìm. ầTa có th môt ng ch ng trình Pascal nh sau ươ ư7Giáo viên: Võ Tá Hoàng Chuyên đề THU TOÁN CẬ Function BinaryEuclid(m, Integer) Integer; Var a, b, dem Integer; Begin := m; := n; dem := 0; while (not Odd(a)) and (not Odd(b)) do begin Inc(dem); := shr 1; := shr 1; end; repeat while not Odd(a) do := shr 1; while not Odd(b) do := shr 1; if then Break; if then := else := a; until b; BinaryEuclid := shl dem; End; Vì các đc mô ng nh phân nên rõ ràng các phép chia có th th hi đn gi ướ ướ ảb ng phép ch ph i. m, có th mô ng bít thì phép ch có chi phí ng N, phép tr ừcũng có chi phí ng (xem ph II). khác, sau phép tr là ít nh phép ch bít và ta ịd th có không quá 2N ch bit. Do đó ph thu toán Nễ hay log(max{m, n}) 2.8Giáo viên: Võ Tá Hoàng Chuyên đề THU TOÁN CẬ Ta cũng chú ng phép mod là nh th ng nên đi các m, không quá ớ(trong ph vi 2ạ 31) thì thu toánậ Euclid ch nhanh thu toán mô đây. Còn ởkhi ta ph làm vi các thì thu toán Euclid nh phân thích n. Thu toán này ậkhông ch có ph nh mà có th khác là ta ch ph th hi phép ch bít và ịphép tr là nh ng phép tính đn gi n, trong khi thu toán Euclidừ ph th hi phép chia vi ếkhá ph p. ạIV. Gi ph ng trình nghi nguyên tuy tínhả ươ 1. Ph ng trình đng ax ươ b(mod c) (*) iớ a, b, đu là các nguyên ng. ươG là chung nh và c. qu cho ta ph ng trình có nghi khi và ướ ươ ệch khi chia và (*) có nghi thì có vô nghi ng xỉ ạ0 Z, và x0 là nghi (*). Nh y, ta có th dàng ki tra ph ng trình có nhi hay ươ ệkhông. còn là tìm nghi xấ ệ0 tho mãn ph ng trình. Ta chú ng thu toán Euclid có ươ ậth chí ra hai u, sao cho *a d, là u*a (mod c) xế0 (b d) (chú ph ng trình có nghi ươ chia cho d) thì a*xế0 (mod c), là xứ0 tho mãn (*). ảCh ng trình Pascal gi ph ng trình (*) nh sau ươ ươ ưProcedure Solve1(a, b, Integer); Var d, e, b1, u, Integer; Begin Euclid2(a, c, u, v); := u*a v*c; if mod <> then Writeln(‘No solution ’) else begin := div d; b1 := div d; Writeln(‘Equation has infinite solution’); 9Giáo viên: Võ Tá Hoàng Chuyên đề THU TOÁN CẬ Write(‘All solutions have form ); Writeln(‘ ’, u*b1 ,‘ k*‘, e); end; End; 2. Ph ng trình Diophantine tuy tính ng a*x b*y cươ (**) a, b, Ta có th th ph ng trình Diophantine này có th đa gi ph ng trình đng tuy ươ ươ ếtính. (**) Vi gi ph ng trình đng tuy tính đã đc trình bày 1. ươ ựơ Chú UCLN(a, b) a1 b1 (**) có nghi khi và ch khiệ (mod d). (**) có nghi thì có vô nghi m, công th nghi (x, y) (x0 y0 (­b1 a1 ). iớ (x0 y0 là nghi nào đó (**). 3. Đnh lý đng Trung Hoaị Đnh lýị Cho nguyên ng aố ươ1 a2 a3 am đôi nguyên cùng nhau, và nguyên bộ ố1 b2 b3 bm tho mãn bi ai i= 1, 2, …, m. Đt aặ1 *a2 *…*am. Khi đó và duy nh nguyên tho mãn và bi (mod ai 1, 2, …, m. 10Giáo viên: Võ Tá Hoàng