Trong quá trình làm việc và tham gia phỏng vấn, mình có nhận xét chung là lập trình viên hiện nay đang thiếu rất nhiều kiến thức về logic học và giải thuật, kiến thức nền tảng để trở thành lập trình viên. Bài viết này mình sẽ đưa ra một số kinh nghiệm học lập trình và cách hiểu về lập trình sao cho đúng.
Vậy lập trình là gì? Lập trình là đưa ra một phương pháp giải quyết cho một lớp các bài toán. Lập trình không phải là cứ phải có máy tính, phải sử dụng một ngôn ngữ lập trình nào đó. Thực tế trong cuộc sống hàng ngày chúng ta đã lập trình và được lập rất nhiều chương trình. Khi bạn lập ra kế hoạch hàng ngày -> bạn đã lập trình và cũng chính bạn là người thực thi chương trình đó. Có điều đa số chúng ta sẽ không bao giờ thực thi nó một cách chính xác cả .
Để giới hạn lại khái niệm lập trình, trong bài viết này mình sẽ chỉ nói về lập trình trên máy tính, sử dụng ngôn ngữ lập trình nào đó. Bạn có thể hiểu lập trình máy tính là đưa ra một phương pháp giải quyết bài toán dựa trên một tập các lệnh logic sử ngôn ngữ lập trình. Chính vì vậy logic học sẽ là kiến thức nền tảng của lập trình, và bạn hãy nhớ học tốt logic trước khi bạn có ý định học lập trình.
Tiếp đến là giải thuật (hay thuật toán), một yếu tố quan trọng và không thể thiếu trong lập trình. Giải thuật chẳng qua cũng chỉ là một tập các logic được sử dụng để giải quyết bài toán, nó có thể là các logic rất đơn giản hoặc phức tạp, nhưng sẽ được sử dụng rất thường xuyên trong lập trình. Người ta đưa ra khái niệm giải thuật để mô tả một tập các logic, cái mà chưa được gọi là chương trình, từ đó chúng ta có thể cài đặt bằng một ngôn ngữ cụ thể để nó trở thành chương trình. Chúng ta có thể coi bất kì một logic giải quyết bài toán nào đều là thuật toán, đơn giản là các thuật toán giải phương trình, sắp xếp… phức tạp hơn là các thuật toán quy hoạch động, tham lam… Thường thì thuật toán sẽ gắn liền với cấu trúc dữ liệu, chính vì vậy người ta thường gọi là “Cấu trúc dữ liệu và giải thuật”.
Khi bạn đã có một kiến thức logic và giải thuật tốt thì việc học một ngôn ngữ lập trình sẽ trở lên rất đơn giản. Đúng như triết học đã chỉ ra “Ngôn ngữ chỉ là vỏ bọc của tư duy” và trong lập trình cũng vậy, ngôn ngữ lập trình chỉ là vỏ bọc của tư duy logic và giải thuật. Ngôn ngữ là công cụ để bạn thể hiện tư duy logic của mình, và bạn có thể sử dụng bất kì ngôn ngữ nào mà không làm thay đổi logic của bạn. Khi đã hiểu được điều này, bạn sẽ nhận ra rằng mọi ngôn ngữ lập trình đều giống nhau.
Trước tiên mình sẽ nói về các ngôn ngữ thủ tục như Pascal hay C. Các ngôn ngữ này đều cho phép ta khai báo cấu trúc dữ liệu và các thuật toán thông qua các kiểu dữ liệu và lệnh. Các kiểu dữ liệu bao gồm các kiểu cơ bản như số nguyên, số thực, kí tự, text, logic (true/false)…, các kiểu cấu trúc, mảng hay hơn nữa là các kiểu dữ liệu do người dùng tự định nghĩa. Tiếp theo là các lệnh điều kiện (if … else…, switch… case…) và các lệnh lặp (loop, for, while). Đây chính là các lệnh cơ bản và quan trọng mà mọi ngôn ngữ phải có, vì nó chính là cú pháp cho phép ta mô tả logic bài toán. Ngoài ra, các ngôn ngữ này còn cho phép chúng ta định nghĩa các thủ tục (procedure) hay hàm (function). Các khái niệm này có được sử dụng hay không tùy vào ngôn ngữ lập trình nhưng nó cũng chẳng qua là một cách cài đặt giúp chúng ta tổ chức và sử dụng lại các tập lệnh mà thôi.
Tiếp theo là lập trình hướng đối tượng. Sự ra đời của lập trình hướng đối tượng đánh dấu một sự phát triển nhảy vọt trong lập trình máy tính. Về ưu điểm của lập trình hướng đối tượng mình sẽ không viết ra ở đây nhưng có 4 tính chất quản trọng của lập trình hướng đối tượng mà mọi lập trình viên sẽ phải nhớ:
1. Tính trừu tượng (abstraction)
2. Tính đóng gói (encapsulation)
3. Tính đa hình (polymorphism)
4. Tính kế thừa (inheritance)
Thông tin chi tiết bạn có thể tham khảo bất kì tài liệu lập trình hương đối tượng nào, cái quan trọng là trước khi học ngôn ngữ lập trình hướng đối tượng bạn phải hiểu rõ các khái niệm và tại sao người ta đưa ra các khái niệm đó trong lập trình hướng đối tượng. Như vậy khi học ngôn ngữ bạn sẽ nắm bắt nhanh và thực sự ngôn ngữ sẽ không còn là vấn đề quan trọng nữa.
Chúc các bạn thành công!
Thứ Ba, 15 tháng 6, 2010
Chuyên đề: THUẬT TOÁN SỐ HỌC
I. Giới thiệu chung
Số học thuật toán (Algorithmic number theory) là một ngành toán học đang phát triển mạnh, nghiên cứu số học trên phương diện thuật toán. Ta cần chú ý rằng Số học là một trong những ngành toán học cổ nhất còn thuật toán lại là một khái niệm mới mẻ ra đời và phát triển từ trong thế kỉ XX. Số học thuật toán được xây dựng trên cơ sở những thành tựu của cả lý thuyết số học lẫn thuật toán.
Một trong những bài toán nổi tiếng nhất đã đựoc giải quyết trong thế kỉ XX là bài toán thứ 10 của Hilbert ‘Có tồn tại một thuật toán tổng quát cho phép ta trả lời một phương trình Diophantine cho trước có nghiệm hay không ?’. Phương trình Diophantine là phương trình có dạng f(x, y, z, … ) = 0 trong đó f(x, y, z, …) là đa thức của các biến x, y, z, … có các hệ số nguyên, và các biến chỉ nhận giá trị nguyên. Bài toán này đã được Michiakêvích giải quyết trọn vẹn và câu trả lời là phủ định, tức là không có thuật toán như vậy. Bài toán thứ 10 của Hilbert được giải quyết là một thành tựu quan trọng của số học cũng như thuật toán.
Số học thuật toán không chỉ phát triển trên những thành tựu của Số học sơ cấp, mà nó còn tận dụng những thành tựu của Số học hiện đại, Đại số hiện đại, Hình học đại số … Cũng như các ngành toán học - thuật toán khác, trong Số học thuật toán cũng có những bài toán NP, tức là không có thuật giải trong thời gian đa thức, tiêu biểu là bài toán phân tích một số ra các thừa số nguyên tố, thuật toán kiểm tra nguyên tố, …
Trong bài viết này, ta chỉ đề cập tới những vấn đề cơ bản nhất của Số học thuật toán, và trên cơ sở của toán học sơ cấp.
II. Các phép tính với số nguyên
Trong máy tính, các số đều được biểu diễn ở hệ nhị phân, hơn nữa việc mô tả dưới dạng nhị phân làm cho các phép tính trở nên đơn giản hơn rất nhiều.
Để cho tổng quát, ta giả sử hai toán hạng đều có đúng N bit (trong trường hợp số các bít có nghĩa nhỏ hơn N thì ta thêm 0 vào đầu cho đủ).
1. Phép cộng và phép trừ
Đối với phép cộng và phép nhân các số N bít, ta có thể thực hiện giống như phép cộng trừ trên hệ thập phân : Thực hiện cộng (hay trừ) từ phải sang trái (với bít ứng với số mũ nhỏ trước rồi số mũ lớn sau).
1. Phép nhân
Đối với phép nhân, ta có thuật toán nhân Nga được mô tả như sau :
Function Mult(a, b : Integer): Integer;
Var
c : Integer;
Begin
c := 0;
repeat
if Odd(b) then c := c + a;
a := a shl 1;
b := b shr 1;
until b = 0;
Mult := c;
End;
Nếu xét cho kĩ thì thực ra thuật toán nhân Nga có cùng một dạng với thuật toán nhân hai số bằng phương pháp mà bình thường ta vẫn dùng để tính tay, chỉ có điều khác là thao tác trên hệ nhị phân.
Thuật toán nhân Nga gồm N lần dịch bít, trong trường hợp tổng quát phải thực hiện N/2 lần phép cộng, do đó độ phức tạp tính toán là N2.
Sau đây, ta sẽ giới thiệu một thuật toán nhân khác, tuy phức tạp hơn nhưng có độ phức tạp nhỏ hơn.
Giả sử ta phải thực hiện phép nhân với hai số có 2N bit A và B. Phân tích :
A = a1*2N + a2
B = b1*2N + b2.
AB = a1*b1 * 22N + (a1b2 + a2b1)*2N + a2b2.
Ta chú ý rằng phép nhân với một luỹ thừa của 2 cũng như phép cộng có thời gian tỉ lệ với N.
Nhận xét : (a1+a2)(b1 + b2) - a1b1 - a2b2 = a1b2 + a2b1.
Do đó nếu biết (a1+a2)(b1 + b2), a1b1, a2b2 thì có thể tính được a1b2 + a2b1.
Qui về nhân hai số 2N bit về 2 lần nhân N bit và một số phép tính có thời gian tỉ lệ với N.
Nếu gọi F(n) là thời gian nhiều nhất để thực hiện phép nhân hai số có 2n bit, ta có
F(n) = 3F(n-1) + k2n (*) trong đó k là một hằng số thể hiện chi phí các phép tính cộng và dịch bit trong mỗi bước gọi đệ qui. Chia cả hai vế của (*) cho 2n ta được
. Do đó, F(n) = O(3n) = O( ) hay nói cách khác thời gian thực hiện phép nhân hai số N bít có độ phức tạp cỡ O( ).
3. Phép chia
Trong phần này, ta sẽ trình bày thuật toán chia hai số nhị phân có N bít A = (A1A2A3…AN)2, B = (B1B2…BN)2 cho kết quả thương Q, dư R.
+Bước 1:Q 0, R 0, i 0
+Bước 2: i = i+1. Nếu i > N kết thúc thuật toán, ngược lại Bước 3.
+Bước 3: R (R shl 1) or (A[i]). Nếu R B Bước 4, ngược lại Bước 5.
+Bước 4: R R - B, C[i] = 1. Thực hiện Bước 2.
+Bước 5: C[i] = 0. Thực hiện Bước 2.
Hay ta có thể mô tả bằng chương trình :
Procedure Divide(A, B : LongInt; var Q, R : LongInt);
Var
i : Integer;
Begin
Q := 0;
R := 0;
For i := 1 to N do
Begin
If (A and (1 shl (N-i)) <> 0) then R := (R shl 1)+1
else R := R shl 1;
if R >= B then
Begin
Q := Q or (1 shl (N-i));
R := R - B;
End;
End;
End;
Đánh giá độ phức tạp: Thuật toán chia có độ phức tạp (N2).
III. Thuật toán Euclid
1. Thuật toán Euclid
Thuật toán Euclid dùng để tìm ước chung lớn nhất của hai số nguyên dương m, n.
Thuật toán tiến hành như sau :
Bước 0: Đặt a = m, b = n.
Bước 1: Nếu a > b ta thay a bằng phần dư của phép chia a cho b, ngược lại thay b bằng phần dư của phép chia b cho a.
Bước 2: Nếu a hoặc b bằng 0, thì kết quả là a + b, ngược lại thực hiện bước 1.
Hay thuật toán được mô tả bằng một hàm trong ngôn ngữ Pascal như sau :
Function Euclid(m, n : Integer) : Integer;
Var
a, b : Integer;
Begin
a := m; b := n;
repeat
if a > b then a := a mod b
else b := b mod a;
until (a = 0) or (b = 0);
Euclid := a + b;
End;
Ta cũng có cách viết khác như sau :
Function Euclid1(m, n : Integer) : Integer;
Var
a, b, r : Integer;
Begin
a := m; b := n;
repeat
r := a mod b;
a := b;
b := r;
until b = 0;
Euclid := a;
End;
Trong số học ta đã biết rằng với hai số nguyên dương m, n bất kì và d là ước chung của chúng thì luôn tồn tại hai số nguyên u, v sao cho u*m + v*n = d. Từ thuật toán Euclid ta cũng có thể chỉ ra được cụ thế một cặp (u, v) như vậy :
Ta chú ý rằng tại mỗi bước của vòng lặp repeat, a và b đều tồn tại cặp (x, y) với x, y Z thoả mãn x*m + y*n = a (= b). Ban đầu a = m có một cặp tương ứng là (1, 0), cặp tương ứng với b = n là (0, 1) vì :
1*m + 0*n = m = a
0*m + 1*n = n = b
Trong vòng lặp, ta có phép gán a := a mod b, phép gán này tương đương a := a - q*b trong đó q là thương của phép chia a cho b (q := a div b). Khi đó cặp (xa, ya) tương ứng với a biến đổi tương ứng
xa := xa - q*xb
ya := ya - q*yb
Như vậy, a và b luôn có thể biểu diễn dưới dạng x*m + y*n và kết quả ước chung bằng a + b sẽ có cặp x, y tương ứng là xa + xb , ya + yb. Như vậy, thuật toán tìm cặp u, v trên cơ sở thuật toán Euclid sẽ được viết như sau :
Procedure Euclid2(m, n : Integer; var u, v : Integer);
Var
a, b, q, r : Integer;
xa, ya, xb, yb, xt, yt : Integer;
Begin
a := m;
b := n;
xa := 1;
ya := 0;
xb := 0;
yb := 1;
repeat
q := a div b;
r := a mod b;
a := b;
b := r;
xt := xa;
yt := ya;
xa := xb;
ya := yb;
xb := xt - q*xb;
yb := yt - q*yb;
until b = 0;
u := xa;
v := ya;
End;
Đánh giá độ phức tạp của thuật toán Euclid : Nếu ta gọi (ai, b¬i) là cặp a, b ở vòng lặp thứ i, đánh số theo chiều ngược lại ( kết thúc là (a1, b1), trước đó là (a2, b2), (a3, b3) … , (as, bs)). Ta có thể chứng minh bằng qui nạp max{ak, bk) Fk trong đó Fk là số thứ k trong dãy Fibonaci. Ta có công thức sau :
Fn =
Fn tăng theo hàm mũ, thuật toán Euclid có độ phức tạp lôgarit của max(m, n).
Ta chú ý rằng cách đánh giá này bỏ qua thời gian thực hiện phép chia (mod) (trong máy tính đây là một lệnh của CPU), tuy nhiên thuật toán chia thực hiện với hai số N bít nói chung mất khoảng N2. Do đó nếu xét chi tiết, thuật toán Euclid có độ phức tạp cỡ O((log(max{m, n})3).
2. Thuật toán Euclid nhị phân
Sau đây, ta sẽ trình bày một dạng Quay về Bước 1.
+ Bước 3 : Chừng nào khác của thuật toán Euclid có độ phức tạp nhỏ hơn. Ta có nhận xét sau : ước chung lẻ lớn nhất của hai số a, b không phụ thuộc vào các phép biến đổi sau :
+ Chia a (hoặc b) nếu a (hoặc b) chẵn.
+ Thay a bằng a - b.
Thuật toán có thể mô tả như sau :
+ Bước 0 : a = m, b = n, dem = 0.
+ Bước 1 : Nếu cả a và b đều chẵn thì Bước 2 ngược lại Bước 3.
+ Bước 2 : dem = dem + 1, chia cả a và b cho 2, a còn chẵn thì chia a cho 2, thực hiện tương tự với b.
+ Bước 4 : Nếu a = b Bước 6, ngược lại Bước 5.;
+ Bước 5 : Nếu a > b a := a - b, ngược lại b := b - a. Thực hiện Bước 3.
+ Bước 6 : c := a * 2dem ( dịch c sanh trái số bit bằng dem ) Thuật toán kết thúc và c là ước chung lớn nhất cần tìm.
Ta có thể môt tả bằng chương trình Pascal như sau :
Function BinaryEuclid(m, n : Integer) : Integer;
Var
a, b, dem : Integer;
Begin
a := m;
b := n;
dem := 0;
while (not Odd(a)) and (not Odd(b)) do
begin
Inc(dem);
a := a shr 1;
b := b shr 1;
end;
repeat
while not Odd(a) do a := a shr 1;
while not Odd(b) do b := b shr 1;
if a = b then Break;
if a > b then a := a - b
else b := b - a;
until a = b;
BinaryEuclid := a shl dem;
End;
Vì các số đước mô tả dưới dạng nhị phân nên rõ ràng các phép chia 2 có thể thực hiện đơn giản bằng phép dịch phải. Nếu m, n có thể mô tả bằng N bít thì phép dịch có chi phí bằng N, phép trừ cũng có chi phí bằng N (xem phần II). Mặt khác, sau mỗi phép trừ là ít nhất một phép dịch bít và ta dễ thấy có không quá 2N lần dịch bit. Do đó độ phức tạp của thuật toán cỡ N2 hay log(max{m, n})2.
Ta cũng cần chú ý rằng phép mod là một lệnh của hệ thống nên đối với các số m, n không quá lớn (trong phạm vi 231) thì thuật toán Euclid nếu ở mục 1 chạy nhanh hơn thuật toán mô tả ở đây. Còn khi ta phải làm việc với các số lớn thì thuật toán Euclid nhị phân thích hợp hơn. Thuật toán này không chỉ có độ phức tạp nhỏ hơn mà có một lợi thế khác là ta chỉ phải thực hiện phép dịch bít và phép trừ là những phép tính rất đơn giản, trong khi thuật toán Euclid phải thực hiện phép chia viết khá phức tạp.
IV. Giải phương trình nghiệm nguyên tuyến tính
1. Phương trình đồng dư ax b(mod c) (*)
Với a, b, c đều là các số nguyên dương.
Gọi d là ước chung lớn nhất của a và c. Kết quả từ số học cho ta phương trình có nghiệm khi và chỉ khi b chia hết d và nếu (*) có nghiệm thì sẽ có vô số nghiệm dạng x = x0 + k * e với k Z, e = c / d và x0 là một nghiệm của (*). Như vậy, ta có thể dễ dàng kiểm tra phương trình có nhiệm hay không.
Vấn đề còn lại là tìm một nghiệm x0 thoả mãn phương trình. Ta chú ý rằng thuật toán Euclid có thể chí ra hai số u, v sao cho u *a + v * c = d, tức là u*a d (mod c) nếu x0 = u * (b / d) (chú ý phương trình có nghiệm b chia hết cho d) thì a*x0 b (mod c), tức là x0 thoả mãn (*).
Chương trình Pascal giải phương trình (*) như sau :
Procedure Solve1(a, b, c : Integer);
Var
d, e, b1, u, v : Integer;
Begin
Euclid2(a, c, u, v);
d := u*a + v*c;
if b mod d <> 0 then Writeln(‘No solution ’)
else
begin
e := c div d;
b1 := b div d;
Writeln(‘Equation has infinite solution’);
Write(‘All solutions have form : );
Writeln(‘ x = ’, u*b1 ,‘ + k*‘, e);
end;
End;
2. Phương trình Diophantine tuyến tính dạng a*x + b*y = c. (**)
với a, b, c Z+
Ta có thể dễ thấy phương trình Diophantine này có thể đưa về giải phương trình đồng dư tuyến tính.
(**)
Việc giải phương trình đồng dư tuyến tính đã đựơc trình bày ở mục 1.
Chú ý :
Gọi d = UCLN(a, b)
a1 = a / d
b1 = b / d
(**) có nghiệm khi và chỉ khi c 0 (mod d).
(**) nếu có nghiệm thì sẽ có vô số nghiệm, công thức nghiệm :
(x, y) = (x0, y0) + k (-b1, a1).
Với (x0, y0) là một nghiệm nào đó của (**).
3. Định lý đồng dư Trung Hoa.
Định lý : Cho m số nguyên dương a1, a2, a3, … am đôi một nguyên tố cùng nhau, và m số nguyên b1, b2, b3, … bm thoả mãn 0 bi ai - 1 i= 1, 2, …, m.
Đặt M = a1*a2*…*am. Khi đó tồn tại và duy nhất số nguyên x thoả mãn :
0 x M - 1 và
x bi (mod ai) i = 1, 2, …, m.
Định lý đồng dư Trung Hoa được trình bày và chứng minh trong hầu hết các giáo trình Số học. Sau đây ta sẽ tìm hiểu thuật toán chỉ ra cụ thể số x như vậy.
Ta chú ý rằng nghiệm tương ứng với k ràng buộc đầu (ứng với các số a1, b1, a2, b2, … ak, bk) sẽ có dạng x = xk + Mk. Trong đó Mk = a1* a2* …* ak và xk là nghiệm thoả mãn định lý đồng dư Trung Hoa tương ứng với a1, b1, a2, b2, … ak, bk.
Dễ thấy khi đó xk+1 là nghiệm không âm nhỏ nhất thoả mãn hệ
x bk+1(mod ak+1)
x xk (mod Mk).
Kết quả cuối cùng, số thỏa mãn bài toán là xm.
Như vậy, ta đưa việc giải m phương trình về m-1 lần giải hệ hai phương trình.
Ta giải hệ hai phương trình như sau :
Vì x xk (mod Mk) nên x = xk + y * Mk, bài toán trở thành tìm nghiệm không âm nhỏ nhất của phương trình đồng dư xk + y * Mk bk+1(mod ¬ak+1). Ở phần 1, ta đã giải phương trình này cho nhiệm có dạng y = y0 + t*ak+1 (vì ak+1 và Mk nguyên tố cùng nhau). Từ công thức nghiệm, dễ thấy y không âm nhỏ nhất = y0 mod ak+1.
V. Thuật toán kiểm tra nguyên tố
Bài toán : Kiểm tra một số n > 1 cho trước có phải là nguyên tố hay không ?
1. Tiếp cận bài toán qua một số thuật toán đơn giản
Theo đúng định nghĩa số nguyên tố: Một số là nguyên tố khi và chỉ khi nó không có các ước không tầm thường. Từ đó ta có thể viết một hàm kiểm tra nguyên tố như sau :
Function Prime(n : Integer) : Boolean;
Var
i : Integer;
Begin
Prime := False;
For i := 2 to n-1 do
if n mod i = 0 then Exit;
Prime := True;
End;
Ta có thể thấy rõ thuật toán trên chi phí trong trường hợp xấu nhất lên tới O(n). Ta có thể thấy nó rất thô dựa vào nhận xét : Nếu n là hợp số thì nó phải có một ước nhỏ hơn , và do đó ta chỉ cần xét các ước không quá của nó. Thuật toán cải tiến sẽ được mô tả như sau :
Function Prime(n : Integer) : Boolean;
Var
i : Integer;
Begin
Prime := False;
For i := 2 to Trunc(Sqrt(n)) do
if n mod i = 0 then Exit;
Prime := True;
End;
Dễ thấy thuật toán cải tiến trong trường hợp tồi nhất mất O( ), tuy nhiên ta cũng cần chú ý rằng thuật toán cải tiến chỉ khác thuật toán ban đầu khi n là số nguyên tố, còn với n là hợp số thì hai thuật toán kết thúc sau cùng một số phép tính.
Ta có thể có một hướng cải tiến nữa nếu nhận xét thêm rằng : Nếu n là hợp số thì phải có một ước nguyên tố , do đó thay vì tìm ước trong tất cả các số trong khoảng từ 2 đến , ta chỉ xét các số nguyên tố trong khoảng đó. Nhưng khi đó một vấn đề dược đặt ra là làm thế nào để có danh sách số nguyên tố không vượt quá , có thể thấy chi phí tạo danh sách số nguyên tố sẽ không dưới . Tuy vậy, trong trường hợp phải kiểm tra rất nhiều số n như thế thì ta có thể áp dụng phương pháp trên. Trong trường hợp không có danh sách các số nguyên tố, ta có thể hạn chế tập tìm kiếm bằng phương pháp sau : Chọn một số k < n, nếu UCLN(n, k) > 1 thì rõ ràng n là hợp số, ngược lại ta hạn chế tập tìm kiểm các số trong khoảng 2 đến mà phải nguyên tố cùng nhau với k. Thuật toán có thể mô tả như sau :
Function Prime(n, k : Integer) : Boolean;
Var
List : array[1..maxk] of Integer;
j, i, l : Integer;
Begin
Prime := False;
if Euclid(n, k) > 1 then Exit; {Hàm Euclid lấy ước chung lớn
nhất của hai số nguyên dương đã được môt tả ở phần III}
l := 0;
for i := 1 to k-1 do
if Euclid(i, k) = 1 then
begin
Inc(l);
List[l] := i;
end;
for i := 2 to l do
if n mod L[i] = 0 then Exit;
j := k;
while Sqr(j) < n do
begin
for i := 1 to l do
if n mod (j+List[i]) = 0 then Exit;
j := j + k;
end;
Prime := True;
End;
Vì k rất nhỏ nên thời gian tính toán chủ yếu ở phép tìm ước. Trong phần tìm ước, cứ trong k số ta chỉ xét l số. Chú ý rằng ở đây l = (k) là số các số tự nhiên không quá k và nguyên tố cùng nhau với k. Độ phức tạp của thuật toán cỡ O( ).
Theo công thức Euler, nếu k có dạng phân tích tiêu chuẩn k = pii
thì (k) = k , tức là = .
Do đó phương pháp chọn k tối ưu nhất là lấy k bằng tích của những số nguyên tố đầu tiên. Nếu chọn k = 6 thì độ phức tạp là O( ), độ phức tạp của thuật toán giảm đáng kể nếu so với O( ). Tuy nhiên, ta sẽ không thu được một sự giảm đáng kể hơn nếu chọn thêm số nguyên tố mới.
K Phân tích tiêu chuẩn
6 2*3
30 2*3*5
210 2*3*5*7
Trong các hướng tiếp cận trên, có một nguyên tắc cơ bản để kiểm tra nguyên tố là tìm một ước không tầm thường của n, và trong trường hợp tồi nhất (khi n là số nguyên tố), thì ta phải xét hết các số nguyên tố không quá .
Nếu gọi (x) là số các số nguyên tố không vượt quá x, người ta đã có kết quả nổi tiếng sau đây :
= 1.
Điều này cho thấy trong trường hợp n là nguyên tố, số phép toán không ít hơn .
Trong thực tế, nếu n lên tới hàng trăm chữ số những thuật toán nêu trên rõ ràng không thể chạy được trong thời gian cho phép. Ta cũng cần chú ý rằng hiện tại chưa có một thuật toán tổng quát cho kết quả chính xác trong thời gian chấp nhận được.
2. Thuật toán xác suất
Thuật toán xác xuất tiếp cận bài toán theo hướng khác, không theo con đường tìm một ước không tầm thường mà dựa vào hai tính chất khác của số nguyên tố. Cho p là một số nguyên tố, a là số nguyên không chia hết cho p, ta có :
ap-1 1 (mod p) (1)
a2 1 (mod p) a 1 (mod p) hoặc a -1 (mod p). (2).
Hai tính chất trên khá quen thuộc trong số nguyên tố, ta có thể chứng minh không mấy khó khăn.
Giả sử p-1 = q2t trong đó q là một số nguyên dương lẻ. Theo (1) và (2), với mọi số a không chia hết cho p ta đều có :
+ 1 (mod p) hoặc
+ -1 (mod p) với một số nguyên r nào đó thoả 0 r < t. (*)
Như vậy, một số n là nguyên tố thì nó phải thoả mãn điều kiện trên với mọi 1 a n-1, ngược lại nếu tồn tại một a không thoả mãn tính chất trên thì chắc chắn n không phải là số nguyên tố. Mặt khác, ta có thể chứng minh được rằng, nếu n là một hợp số lẻ > 3 thì có không quá (n-1) / 4 giá trị a trong khoảng 1 đến n-1 thoả mãn (*). Do đó, với một số a chọn ngẫu nhiên trong khoảng 1 đến n-1, thì xác suất a thoả mãn (*) không quá , và nếu k lần chọn thì xác suất để mọi lần chọn đều thoả mãn là không quá . Từ đó, người ta đã đưa ra một thuật toán xác suất cho phép kiểm tra một số n có phải nguyên tố hay không trong thời gian đa thức với độ chính xác rất cao.
Thuật toán (Rabin - Miller) có thể được mô tả như sau :
Function Prime(n : Integer) : Boolean;
Var
i, a : Integer;
Begin
Prime := False;
Cal(n, q, t) {phân tích n-1 = q2t}
For i := 1 to k do
Begin
a := Random(n-1) + 1;
if MillerTest(n, a, q, t) = False then Exit;
{Kiểm tra với một cơ sở a được chọn ngẫu nhiên}
End;
Prime := True;
End;
Thủ tục Cal(n, q, t) phân tích n-1 = q2t với q là số nguyên lẻ khá đơn giản ta nên ta không trình bày ở đây.
Phần quan trọng nhất là kiểm tra a có thoả mãn tính chất (*) hay không.
Trước hết, ta phải tính aq mod n, nếu ta tính bằng thực hiện tuần tự các phép nhân q lần thì chi phí sẽ rất lớn (q có thể tỉ lệ với n). Vì ta chỉ cần tính luỹ thừa modulo n nên ta có một phương pháp rất hay : Phương pháp bình phương liên tiếp. Ý tưởng cơ bản của nó như sau : phân tích q dạnh nhị phân, q sẽ có dạng tổng của các luỹ thừa của 2.
Ta xây dựng dãy {u} như sau :
u0¬ = a
uk+1 = uk2 mod n k N.
Khi đó, ta dễ dàng chứng minh uk = mod n.
Khi đó, aq mod n sẽ được tính bằng tích theo modulo n của các uk tương ứng với các luỹ thừa của 2 trong phân tích nhị phân của q.
Ta có thể mô tả bằng thủ tục như sau :
Function Power(a, q, n : Integer) : Integer;
Var
c, p2, u : Integer;
Begin
c := 1;
u := a;
p2 := 1;
repeat
if q and p2 <> 0 then c := (c * u) mod n;
p2 := p2 shl 1;
u := (u * u) mod n;
until p2 > q;
Power := c;
End;
Ta có thể dễ dàng chứng minh việc tính aq mod n bằng thủ tục nêu trên phải thực hiện không quá 2log2q lần phép nhân modulo n. Do đó chi phí tính toán ( phép nhân và phép chia mất chi phí O((logn)2) ) cỡ O(logq(logn)2).
Phép kiểm tra điều kiện (*) có thể được viết như sau :
Function MillerTest(n, a, q, t : Integer) : Boolean;
Var
pre, c, i, j : Integer;
Begin
c := Power(a, q, n);
pre := n-1;
for i := 0 to t do
begin
if c = 1 then
begin
MillerTest := (pre = n-1);
Exit;
end;
pre := c;
c := (c * c) mod n;
end;
MillerTest := False;
End;
Thủ tục MillerTest gồm phần tính aq mod n có chi phí O(logq(logn)2) và t lần thực hiện tính bình phương modulo n có chi phí cỡ O(t(logn)2). Ta có n-1 = q2t nên độ phức tạp của một lần kiểm tra cơ sở a có chí phí cỡ O((logn)3).
Thuật toán thực hiện k lần kiểm tra có chi phí O(k(logn)3), xác suất sai không quá . Như vậy, độ phức tạp của thuật toán tăng tuyến tính theo k, xác suất sai lầm giảm theo hàm mũ với k. Chỉ cần chọn k không quá lớn (k 30) thì xác suất sai lầm quá nhỏ, do đó nếu n trải qua phép thử với k cơ sở a chọn ngẫu nhiên thì có thể khẳng định gần như chắc chắn n là số nguyên tố.
3. Thuật toán kiểm tra nguyên tố với số Fecmat và số Mersenne.
Số Fecmat Fn = . Nhà toán học Fecmat đã đưa ra giả thiết Fn là số nguyên tố với mọi n N. Ta có thể dễ dàng kiểm tra điều này đúng với n = 0, 1, 2, 3 và 4. Tuy nhiên Euler đã chỉ ra F5 là hợp số vì nó chia hết cho 641.
Định lý : Fn là số nguyên tố khi và chỉ khi -1 (mod Fn).
Số Mersenne Mp = 2p - 1 . Ta có thể dễ thấy nếu M¬p là số nguyên tố thì p phải là số nguyên tố. Số Mersenne có ý nghĩa quan trọng trong Số học vì nó liên quan tới số hoàn chỉnh. Một số nguyên dương n gọi là số hoàn chỉnh nếu tổng các ước bé hơn n của n bằng n. Euler đã chứng minh n là số hoàn chỉnh chẵn khi và chỉ khi n = Mp2p-1¬ với Mp là số nguyên tố.
Định lý : Cho p là một số nguyên tố, dãy {Ln} xác định như sau :
L0 = 4
Ln+1 = Ln2 - 2 n N.
Mp là số nguyên tố khi và chỉ khi Lp-2 0 (mod Mp) .
Số học thuật toán (Algorithmic number theory) là một ngành toán học đang phát triển mạnh, nghiên cứu số học trên phương diện thuật toán. Ta cần chú ý rằng Số học là một trong những ngành toán học cổ nhất còn thuật toán lại là một khái niệm mới mẻ ra đời và phát triển từ trong thế kỉ XX. Số học thuật toán được xây dựng trên cơ sở những thành tựu của cả lý thuyết số học lẫn thuật toán.
Một trong những bài toán nổi tiếng nhất đã đựoc giải quyết trong thế kỉ XX là bài toán thứ 10 của Hilbert ‘Có tồn tại một thuật toán tổng quát cho phép ta trả lời một phương trình Diophantine cho trước có nghiệm hay không ?’. Phương trình Diophantine là phương trình có dạng f(x, y, z, … ) = 0 trong đó f(x, y, z, …) là đa thức của các biến x, y, z, … có các hệ số nguyên, và các biến chỉ nhận giá trị nguyên. Bài toán này đã được Michiakêvích giải quyết trọn vẹn và câu trả lời là phủ định, tức là không có thuật toán như vậy. Bài toán thứ 10 của Hilbert được giải quyết là một thành tựu quan trọng của số học cũng như thuật toán.
Số học thuật toán không chỉ phát triển trên những thành tựu của Số học sơ cấp, mà nó còn tận dụng những thành tựu của Số học hiện đại, Đại số hiện đại, Hình học đại số … Cũng như các ngành toán học - thuật toán khác, trong Số học thuật toán cũng có những bài toán NP, tức là không có thuật giải trong thời gian đa thức, tiêu biểu là bài toán phân tích một số ra các thừa số nguyên tố, thuật toán kiểm tra nguyên tố, …
Trong bài viết này, ta chỉ đề cập tới những vấn đề cơ bản nhất của Số học thuật toán, và trên cơ sở của toán học sơ cấp.
II. Các phép tính với số nguyên
Trong máy tính, các số đều được biểu diễn ở hệ nhị phân, hơn nữa việc mô tả dưới dạng nhị phân làm cho các phép tính trở nên đơn giản hơn rất nhiều.
Để cho tổng quát, ta giả sử hai toán hạng đều có đúng N bit (trong trường hợp số các bít có nghĩa nhỏ hơn N thì ta thêm 0 vào đầu cho đủ).
1. Phép cộng và phép trừ
Đối với phép cộng và phép nhân các số N bít, ta có thể thực hiện giống như phép cộng trừ trên hệ thập phân : Thực hiện cộng (hay trừ) từ phải sang trái (với bít ứng với số mũ nhỏ trước rồi số mũ lớn sau).
1. Phép nhân
Đối với phép nhân, ta có thuật toán nhân Nga được mô tả như sau :
Function Mult(a, b : Integer): Integer;
Var
c : Integer;
Begin
c := 0;
repeat
if Odd(b) then c := c + a;
a := a shl 1;
b := b shr 1;
until b = 0;
Mult := c;
End;
Nếu xét cho kĩ thì thực ra thuật toán nhân Nga có cùng một dạng với thuật toán nhân hai số bằng phương pháp mà bình thường ta vẫn dùng để tính tay, chỉ có điều khác là thao tác trên hệ nhị phân.
Thuật toán nhân Nga gồm N lần dịch bít, trong trường hợp tổng quát phải thực hiện N/2 lần phép cộng, do đó độ phức tạp tính toán là N2.
Sau đây, ta sẽ giới thiệu một thuật toán nhân khác, tuy phức tạp hơn nhưng có độ phức tạp nhỏ hơn.
Giả sử ta phải thực hiện phép nhân với hai số có 2N bit A và B. Phân tích :
A = a1*2N + a2
B = b1*2N + b2.
AB = a1*b1 * 22N + (a1b2 + a2b1)*2N + a2b2.
Ta chú ý rằng phép nhân với một luỹ thừa của 2 cũng như phép cộng có thời gian tỉ lệ với N.
Nhận xét : (a1+a2)(b1 + b2) - a1b1 - a2b2 = a1b2 + a2b1.
Do đó nếu biết (a1+a2)(b1 + b2), a1b1, a2b2 thì có thể tính được a1b2 + a2b1.
Qui về nhân hai số 2N bit về 2 lần nhân N bit và một số phép tính có thời gian tỉ lệ với N.
Nếu gọi F(n) là thời gian nhiều nhất để thực hiện phép nhân hai số có 2n bit, ta có
F(n) = 3F(n-1) + k2n (*) trong đó k là một hằng số thể hiện chi phí các phép tính cộng và dịch bit trong mỗi bước gọi đệ qui. Chia cả hai vế của (*) cho 2n ta được
. Do đó, F(n) = O(3n) = O( ) hay nói cách khác thời gian thực hiện phép nhân hai số N bít có độ phức tạp cỡ O( ).
3. Phép chia
Trong phần này, ta sẽ trình bày thuật toán chia hai số nhị phân có N bít A = (A1A2A3…AN)2, B = (B1B2…BN)2 cho kết quả thương Q, dư R.
+Bước 1:Q 0, R 0, i 0
+Bước 2: i = i+1. Nếu i > N kết thúc thuật toán, ngược lại Bước 3.
+Bước 3: R (R shl 1) or (A[i]). Nếu R B Bước 4, ngược lại Bước 5.
+Bước 4: R R - B, C[i] = 1. Thực hiện Bước 2.
+Bước 5: C[i] = 0. Thực hiện Bước 2.
Hay ta có thể mô tả bằng chương trình :
Procedure Divide(A, B : LongInt; var Q, R : LongInt);
Var
i : Integer;
Begin
Q := 0;
R := 0;
For i := 1 to N do
Begin
If (A and (1 shl (N-i)) <> 0) then R := (R shl 1)+1
else R := R shl 1;
if R >= B then
Begin
Q := Q or (1 shl (N-i));
R := R - B;
End;
End;
End;
Đánh giá độ phức tạp: Thuật toán chia có độ phức tạp (N2).
III. Thuật toán Euclid
1. Thuật toán Euclid
Thuật toán Euclid dùng để tìm ước chung lớn nhất của hai số nguyên dương m, n.
Thuật toán tiến hành như sau :
Bước 0: Đặt a = m, b = n.
Bước 1: Nếu a > b ta thay a bằng phần dư của phép chia a cho b, ngược lại thay b bằng phần dư của phép chia b cho a.
Bước 2: Nếu a hoặc b bằng 0, thì kết quả là a + b, ngược lại thực hiện bước 1.
Hay thuật toán được mô tả bằng một hàm trong ngôn ngữ Pascal như sau :
Function Euclid(m, n : Integer) : Integer;
Var
a, b : Integer;
Begin
a := m; b := n;
repeat
if a > b then a := a mod b
else b := b mod a;
until (a = 0) or (b = 0);
Euclid := a + b;
End;
Ta cũng có cách viết khác như sau :
Function Euclid1(m, n : Integer) : Integer;
Var
a, b, r : Integer;
Begin
a := m; b := n;
repeat
r := a mod b;
a := b;
b := r;
until b = 0;
Euclid := a;
End;
Trong số học ta đã biết rằng với hai số nguyên dương m, n bất kì và d là ước chung của chúng thì luôn tồn tại hai số nguyên u, v sao cho u*m + v*n = d. Từ thuật toán Euclid ta cũng có thể chỉ ra được cụ thế một cặp (u, v) như vậy :
Ta chú ý rằng tại mỗi bước của vòng lặp repeat, a và b đều tồn tại cặp (x, y) với x, y Z thoả mãn x*m + y*n = a (= b). Ban đầu a = m có một cặp tương ứng là (1, 0), cặp tương ứng với b = n là (0, 1) vì :
1*m + 0*n = m = a
0*m + 1*n = n = b
Trong vòng lặp, ta có phép gán a := a mod b, phép gán này tương đương a := a - q*b trong đó q là thương của phép chia a cho b (q := a div b). Khi đó cặp (xa, ya) tương ứng với a biến đổi tương ứng
xa := xa - q*xb
ya := ya - q*yb
Như vậy, a và b luôn có thể biểu diễn dưới dạng x*m + y*n và kết quả ước chung bằng a + b sẽ có cặp x, y tương ứng là xa + xb , ya + yb. Như vậy, thuật toán tìm cặp u, v trên cơ sở thuật toán Euclid sẽ được viết như sau :
Procedure Euclid2(m, n : Integer; var u, v : Integer);
Var
a, b, q, r : Integer;
xa, ya, xb, yb, xt, yt : Integer;
Begin
a := m;
b := n;
xa := 1;
ya := 0;
xb := 0;
yb := 1;
repeat
q := a div b;
r := a mod b;
a := b;
b := r;
xt := xa;
yt := ya;
xa := xb;
ya := yb;
xb := xt - q*xb;
yb := yt - q*yb;
until b = 0;
u := xa;
v := ya;
End;
Đánh giá độ phức tạp của thuật toán Euclid : Nếu ta gọi (ai, b¬i) là cặp a, b ở vòng lặp thứ i, đánh số theo chiều ngược lại ( kết thúc là (a1, b1), trước đó là (a2, b2), (a3, b3) … , (as, bs)). Ta có thể chứng minh bằng qui nạp max{ak, bk) Fk trong đó Fk là số thứ k trong dãy Fibonaci. Ta có công thức sau :
Fn =
Fn tăng theo hàm mũ, thuật toán Euclid có độ phức tạp lôgarit của max(m, n).
Ta chú ý rằng cách đánh giá này bỏ qua thời gian thực hiện phép chia (mod) (trong máy tính đây là một lệnh của CPU), tuy nhiên thuật toán chia thực hiện với hai số N bít nói chung mất khoảng N2. Do đó nếu xét chi tiết, thuật toán Euclid có độ phức tạp cỡ O((log(max{m, n})3).
2. Thuật toán Euclid nhị phân
Sau đây, ta sẽ trình bày một dạng Quay về Bước 1.
+ Bước 3 : Chừng nào khác của thuật toán Euclid có độ phức tạp nhỏ hơn. Ta có nhận xét sau : ước chung lẻ lớn nhất của hai số a, b không phụ thuộc vào các phép biến đổi sau :
+ Chia a (hoặc b) nếu a (hoặc b) chẵn.
+ Thay a bằng a - b.
Thuật toán có thể mô tả như sau :
+ Bước 0 : a = m, b = n, dem = 0.
+ Bước 1 : Nếu cả a và b đều chẵn thì Bước 2 ngược lại Bước 3.
+ Bước 2 : dem = dem + 1, chia cả a và b cho 2, a còn chẵn thì chia a cho 2, thực hiện tương tự với b.
+ Bước 4 : Nếu a = b Bước 6, ngược lại Bước 5.;
+ Bước 5 : Nếu a > b a := a - b, ngược lại b := b - a. Thực hiện Bước 3.
+ Bước 6 : c := a * 2dem ( dịch c sanh trái số bit bằng dem ) Thuật toán kết thúc và c là ước chung lớn nhất cần tìm.
Ta có thể môt tả bằng chương trình Pascal như sau :
Function BinaryEuclid(m, n : Integer) : Integer;
Var
a, b, dem : Integer;
Begin
a := m;
b := n;
dem := 0;
while (not Odd(a)) and (not Odd(b)) do
begin
Inc(dem);
a := a shr 1;
b := b shr 1;
end;
repeat
while not Odd(a) do a := a shr 1;
while not Odd(b) do b := b shr 1;
if a = b then Break;
if a > b then a := a - b
else b := b - a;
until a = b;
BinaryEuclid := a shl dem;
End;
Vì các số đước mô tả dưới dạng nhị phân nên rõ ràng các phép chia 2 có thể thực hiện đơn giản bằng phép dịch phải. Nếu m, n có thể mô tả bằng N bít thì phép dịch có chi phí bằng N, phép trừ cũng có chi phí bằng N (xem phần II). Mặt khác, sau mỗi phép trừ là ít nhất một phép dịch bít và ta dễ thấy có không quá 2N lần dịch bit. Do đó độ phức tạp của thuật toán cỡ N2 hay log(max{m, n})2.
Ta cũng cần chú ý rằng phép mod là một lệnh của hệ thống nên đối với các số m, n không quá lớn (trong phạm vi 231) thì thuật toán Euclid nếu ở mục 1 chạy nhanh hơn thuật toán mô tả ở đây. Còn khi ta phải làm việc với các số lớn thì thuật toán Euclid nhị phân thích hợp hơn. Thuật toán này không chỉ có độ phức tạp nhỏ hơn mà có một lợi thế khác là ta chỉ phải thực hiện phép dịch bít và phép trừ là những phép tính rất đơn giản, trong khi thuật toán Euclid phải thực hiện phép chia viết khá phức tạp.
IV. Giải phương trình nghiệm nguyên tuyến tính
1. Phương trình đồng dư ax b(mod c) (*)
Với a, b, c đều là các số nguyên dương.
Gọi d là ước chung lớn nhất của a và c. Kết quả từ số học cho ta phương trình có nghiệm khi và chỉ khi b chia hết d và nếu (*) có nghiệm thì sẽ có vô số nghiệm dạng x = x0 + k * e với k Z, e = c / d và x0 là một nghiệm của (*). Như vậy, ta có thể dễ dàng kiểm tra phương trình có nhiệm hay không.
Vấn đề còn lại là tìm một nghiệm x0 thoả mãn phương trình. Ta chú ý rằng thuật toán Euclid có thể chí ra hai số u, v sao cho u *a + v * c = d, tức là u*a d (mod c) nếu x0 = u * (b / d) (chú ý phương trình có nghiệm b chia hết cho d) thì a*x0 b (mod c), tức là x0 thoả mãn (*).
Chương trình Pascal giải phương trình (*) như sau :
Procedure Solve1(a, b, c : Integer);
Var
d, e, b1, u, v : Integer;
Begin
Euclid2(a, c, u, v);
d := u*a + v*c;
if b mod d <> 0 then Writeln(‘No solution ’)
else
begin
e := c div d;
b1 := b div d;
Writeln(‘Equation has infinite solution’);
Write(‘All solutions have form : );
Writeln(‘ x = ’, u*b1 ,‘ + k*‘, e);
end;
End;
2. Phương trình Diophantine tuyến tính dạng a*x + b*y = c. (**)
với a, b, c Z+
Ta có thể dễ thấy phương trình Diophantine này có thể đưa về giải phương trình đồng dư tuyến tính.
(**)
Việc giải phương trình đồng dư tuyến tính đã đựơc trình bày ở mục 1.
Chú ý :
Gọi d = UCLN(a, b)
a1 = a / d
b1 = b / d
(**) có nghiệm khi và chỉ khi c 0 (mod d).
(**) nếu có nghiệm thì sẽ có vô số nghiệm, công thức nghiệm :
(x, y) = (x0, y0) + k (-b1, a1).
Với (x0, y0) là một nghiệm nào đó của (**).
3. Định lý đồng dư Trung Hoa.
Định lý : Cho m số nguyên dương a1, a2, a3, … am đôi một nguyên tố cùng nhau, và m số nguyên b1, b2, b3, … bm thoả mãn 0 bi ai - 1 i= 1, 2, …, m.
Đặt M = a1*a2*…*am. Khi đó tồn tại và duy nhất số nguyên x thoả mãn :
0 x M - 1 và
x bi (mod ai) i = 1, 2, …, m.
Định lý đồng dư Trung Hoa được trình bày và chứng minh trong hầu hết các giáo trình Số học. Sau đây ta sẽ tìm hiểu thuật toán chỉ ra cụ thể số x như vậy.
Ta chú ý rằng nghiệm tương ứng với k ràng buộc đầu (ứng với các số a1, b1, a2, b2, … ak, bk) sẽ có dạng x = xk + Mk. Trong đó Mk = a1* a2* …* ak và xk là nghiệm thoả mãn định lý đồng dư Trung Hoa tương ứng với a1, b1, a2, b2, … ak, bk.
Dễ thấy khi đó xk+1 là nghiệm không âm nhỏ nhất thoả mãn hệ
x bk+1(mod ak+1)
x xk (mod Mk).
Kết quả cuối cùng, số thỏa mãn bài toán là xm.
Như vậy, ta đưa việc giải m phương trình về m-1 lần giải hệ hai phương trình.
Ta giải hệ hai phương trình như sau :
Vì x xk (mod Mk) nên x = xk + y * Mk, bài toán trở thành tìm nghiệm không âm nhỏ nhất của phương trình đồng dư xk + y * Mk bk+1(mod ¬ak+1). Ở phần 1, ta đã giải phương trình này cho nhiệm có dạng y = y0 + t*ak+1 (vì ak+1 và Mk nguyên tố cùng nhau). Từ công thức nghiệm, dễ thấy y không âm nhỏ nhất = y0 mod ak+1.
V. Thuật toán kiểm tra nguyên tố
Bài toán : Kiểm tra một số n > 1 cho trước có phải là nguyên tố hay không ?
1. Tiếp cận bài toán qua một số thuật toán đơn giản
Theo đúng định nghĩa số nguyên tố: Một số là nguyên tố khi và chỉ khi nó không có các ước không tầm thường. Từ đó ta có thể viết một hàm kiểm tra nguyên tố như sau :
Function Prime(n : Integer) : Boolean;
Var
i : Integer;
Begin
Prime := False;
For i := 2 to n-1 do
if n mod i = 0 then Exit;
Prime := True;
End;
Ta có thể thấy rõ thuật toán trên chi phí trong trường hợp xấu nhất lên tới O(n). Ta có thể thấy nó rất thô dựa vào nhận xét : Nếu n là hợp số thì nó phải có một ước nhỏ hơn , và do đó ta chỉ cần xét các ước không quá của nó. Thuật toán cải tiến sẽ được mô tả như sau :
Function Prime(n : Integer) : Boolean;
Var
i : Integer;
Begin
Prime := False;
For i := 2 to Trunc(Sqrt(n)) do
if n mod i = 0 then Exit;
Prime := True;
End;
Dễ thấy thuật toán cải tiến trong trường hợp tồi nhất mất O( ), tuy nhiên ta cũng cần chú ý rằng thuật toán cải tiến chỉ khác thuật toán ban đầu khi n là số nguyên tố, còn với n là hợp số thì hai thuật toán kết thúc sau cùng một số phép tính.
Ta có thể có một hướng cải tiến nữa nếu nhận xét thêm rằng : Nếu n là hợp số thì phải có một ước nguyên tố , do đó thay vì tìm ước trong tất cả các số trong khoảng từ 2 đến , ta chỉ xét các số nguyên tố trong khoảng đó. Nhưng khi đó một vấn đề dược đặt ra là làm thế nào để có danh sách số nguyên tố không vượt quá , có thể thấy chi phí tạo danh sách số nguyên tố sẽ không dưới . Tuy vậy, trong trường hợp phải kiểm tra rất nhiều số n như thế thì ta có thể áp dụng phương pháp trên. Trong trường hợp không có danh sách các số nguyên tố, ta có thể hạn chế tập tìm kiếm bằng phương pháp sau : Chọn một số k < n, nếu UCLN(n, k) > 1 thì rõ ràng n là hợp số, ngược lại ta hạn chế tập tìm kiểm các số trong khoảng 2 đến mà phải nguyên tố cùng nhau với k. Thuật toán có thể mô tả như sau :
Function Prime(n, k : Integer) : Boolean;
Var
List : array[1..maxk] of Integer;
j, i, l : Integer;
Begin
Prime := False;
if Euclid(n, k) > 1 then Exit; {Hàm Euclid lấy ước chung lớn
nhất của hai số nguyên dương đã được môt tả ở phần III}
l := 0;
for i := 1 to k-1 do
if Euclid(i, k) = 1 then
begin
Inc(l);
List[l] := i;
end;
for i := 2 to l do
if n mod L[i] = 0 then Exit;
j := k;
while Sqr(j) < n do
begin
for i := 1 to l do
if n mod (j+List[i]) = 0 then Exit;
j := j + k;
end;
Prime := True;
End;
Vì k rất nhỏ nên thời gian tính toán chủ yếu ở phép tìm ước. Trong phần tìm ước, cứ trong k số ta chỉ xét l số. Chú ý rằng ở đây l = (k) là số các số tự nhiên không quá k và nguyên tố cùng nhau với k. Độ phức tạp của thuật toán cỡ O( ).
Theo công thức Euler, nếu k có dạng phân tích tiêu chuẩn k = pii
thì (k) = k , tức là = .
Do đó phương pháp chọn k tối ưu nhất là lấy k bằng tích của những số nguyên tố đầu tiên. Nếu chọn k = 6 thì độ phức tạp là O( ), độ phức tạp của thuật toán giảm đáng kể nếu so với O( ). Tuy nhiên, ta sẽ không thu được một sự giảm đáng kể hơn nếu chọn thêm số nguyên tố mới.
K Phân tích tiêu chuẩn
6 2*3
30 2*3*5
210 2*3*5*7
Trong các hướng tiếp cận trên, có một nguyên tắc cơ bản để kiểm tra nguyên tố là tìm một ước không tầm thường của n, và trong trường hợp tồi nhất (khi n là số nguyên tố), thì ta phải xét hết các số nguyên tố không quá .
Nếu gọi (x) là số các số nguyên tố không vượt quá x, người ta đã có kết quả nổi tiếng sau đây :
= 1.
Điều này cho thấy trong trường hợp n là nguyên tố, số phép toán không ít hơn .
Trong thực tế, nếu n lên tới hàng trăm chữ số những thuật toán nêu trên rõ ràng không thể chạy được trong thời gian cho phép. Ta cũng cần chú ý rằng hiện tại chưa có một thuật toán tổng quát cho kết quả chính xác trong thời gian chấp nhận được.
2. Thuật toán xác suất
Thuật toán xác xuất tiếp cận bài toán theo hướng khác, không theo con đường tìm một ước không tầm thường mà dựa vào hai tính chất khác của số nguyên tố. Cho p là một số nguyên tố, a là số nguyên không chia hết cho p, ta có :
ap-1 1 (mod p) (1)
a2 1 (mod p) a 1 (mod p) hoặc a -1 (mod p). (2).
Hai tính chất trên khá quen thuộc trong số nguyên tố, ta có thể chứng minh không mấy khó khăn.
Giả sử p-1 = q2t trong đó q là một số nguyên dương lẻ. Theo (1) và (2), với mọi số a không chia hết cho p ta đều có :
+ 1 (mod p) hoặc
+ -1 (mod p) với một số nguyên r nào đó thoả 0 r < t. (*)
Như vậy, một số n là nguyên tố thì nó phải thoả mãn điều kiện trên với mọi 1 a n-1, ngược lại nếu tồn tại một a không thoả mãn tính chất trên thì chắc chắn n không phải là số nguyên tố. Mặt khác, ta có thể chứng minh được rằng, nếu n là một hợp số lẻ > 3 thì có không quá (n-1) / 4 giá trị a trong khoảng 1 đến n-1 thoả mãn (*). Do đó, với một số a chọn ngẫu nhiên trong khoảng 1 đến n-1, thì xác suất a thoả mãn (*) không quá , và nếu k lần chọn thì xác suất để mọi lần chọn đều thoả mãn là không quá . Từ đó, người ta đã đưa ra một thuật toán xác suất cho phép kiểm tra một số n có phải nguyên tố hay không trong thời gian đa thức với độ chính xác rất cao.
Thuật toán (Rabin - Miller) có thể được mô tả như sau :
Function Prime(n : Integer) : Boolean;
Var
i, a : Integer;
Begin
Prime := False;
Cal(n, q, t) {phân tích n-1 = q2t}
For i := 1 to k do
Begin
a := Random(n-1) + 1;
if MillerTest(n, a, q, t) = False then Exit;
{Kiểm tra với một cơ sở a được chọn ngẫu nhiên}
End;
Prime := True;
End;
Thủ tục Cal(n, q, t) phân tích n-1 = q2t với q là số nguyên lẻ khá đơn giản ta nên ta không trình bày ở đây.
Phần quan trọng nhất là kiểm tra a có thoả mãn tính chất (*) hay không.
Trước hết, ta phải tính aq mod n, nếu ta tính bằng thực hiện tuần tự các phép nhân q lần thì chi phí sẽ rất lớn (q có thể tỉ lệ với n). Vì ta chỉ cần tính luỹ thừa modulo n nên ta có một phương pháp rất hay : Phương pháp bình phương liên tiếp. Ý tưởng cơ bản của nó như sau : phân tích q dạnh nhị phân, q sẽ có dạng tổng của các luỹ thừa của 2.
Ta xây dựng dãy {u} như sau :
u0¬ = a
uk+1 = uk2 mod n k N.
Khi đó, ta dễ dàng chứng minh uk = mod n.
Khi đó, aq mod n sẽ được tính bằng tích theo modulo n của các uk tương ứng với các luỹ thừa của 2 trong phân tích nhị phân của q.
Ta có thể mô tả bằng thủ tục như sau :
Function Power(a, q, n : Integer) : Integer;
Var
c, p2, u : Integer;
Begin
c := 1;
u := a;
p2 := 1;
repeat
if q and p2 <> 0 then c := (c * u) mod n;
p2 := p2 shl 1;
u := (u * u) mod n;
until p2 > q;
Power := c;
End;
Ta có thể dễ dàng chứng minh việc tính aq mod n bằng thủ tục nêu trên phải thực hiện không quá 2log2q lần phép nhân modulo n. Do đó chi phí tính toán ( phép nhân và phép chia mất chi phí O((logn)2) ) cỡ O(logq(logn)2).
Phép kiểm tra điều kiện (*) có thể được viết như sau :
Function MillerTest(n, a, q, t : Integer) : Boolean;
Var
pre, c, i, j : Integer;
Begin
c := Power(a, q, n);
pre := n-1;
for i := 0 to t do
begin
if c = 1 then
begin
MillerTest := (pre = n-1);
Exit;
end;
pre := c;
c := (c * c) mod n;
end;
MillerTest := False;
End;
Thủ tục MillerTest gồm phần tính aq mod n có chi phí O(logq(logn)2) và t lần thực hiện tính bình phương modulo n có chi phí cỡ O(t(logn)2). Ta có n-1 = q2t nên độ phức tạp của một lần kiểm tra cơ sở a có chí phí cỡ O((logn)3).
Thuật toán thực hiện k lần kiểm tra có chi phí O(k(logn)3), xác suất sai không quá . Như vậy, độ phức tạp của thuật toán tăng tuyến tính theo k, xác suất sai lầm giảm theo hàm mũ với k. Chỉ cần chọn k không quá lớn (k 30) thì xác suất sai lầm quá nhỏ, do đó nếu n trải qua phép thử với k cơ sở a chọn ngẫu nhiên thì có thể khẳng định gần như chắc chắn n là số nguyên tố.
3. Thuật toán kiểm tra nguyên tố với số Fecmat và số Mersenne.
Số Fecmat Fn = . Nhà toán học Fecmat đã đưa ra giả thiết Fn là số nguyên tố với mọi n N. Ta có thể dễ dàng kiểm tra điều này đúng với n = 0, 1, 2, 3 và 4. Tuy nhiên Euler đã chỉ ra F5 là hợp số vì nó chia hết cho 641.
Định lý : Fn là số nguyên tố khi và chỉ khi -1 (mod Fn).
Số Mersenne Mp = 2p - 1 . Ta có thể dễ thấy nếu M¬p là số nguyên tố thì p phải là số nguyên tố. Số Mersenne có ý nghĩa quan trọng trong Số học vì nó liên quan tới số hoàn chỉnh. Một số nguyên dương n gọi là số hoàn chỉnh nếu tổng các ước bé hơn n của n bằng n. Euler đã chứng minh n là số hoàn chỉnh chẵn khi và chỉ khi n = Mp2p-1¬ với Mp là số nguyên tố.
Định lý : Cho p là một số nguyên tố, dãy {Ln} xác định như sau :
L0 = 4
Ln+1 = Ln2 - 2 n N.
Mp là số nguyên tố khi và chỉ khi Lp-2 0 (mod Mp) .
eXe – Công cụ tạo bài giảng dạng web
E-Learning XHTML editor (eXe) là một công cụ xây dựng nội dung đào tạo được thiết kế chạy trên môi trường web và có thể xuất ra các trang web độc lập hay theo các chuẩn elearning để giúp đỡ các giáo viên và các học sinh trong việc thiết kế, phát triển và xuất bản các tài liệu dạy và học trên web mà không cần phải thành thạo về HTML, XML hay các ứng dụng xuất bản web rắc rối khác. Đây là phần mềm miễn phí và dự án eXe được điều hành bởi một nhóm các nhà giáo dục ở New Zealand.
Đặc điểm vượt trội của chương trình là nội dung bài dạy có thể đưa trực tiếp lên mạng để học sinh tự kiểm tra kiến thức không cần có sự can thiệp của giáo viên (dưới hình thức trắc nghiệm khách quan, điền từ, đúng sai, hỏi và trả lời, kể cả giáo án đã soạn của giáo viên ). Bài dạy có thể kèm theo hình ảnh (jpg) , phim (swf, flv), âm thanh (mp3, wma), liên kết với website khác lúc online để minh họa cho nội dung bài dạy. Học sinh, giáo viên có thể thao tác trực tiếp với bài dạy trên mạng hoặc tải các bài dạy, tư liệu kèm theo để học tại nhà trên máy tính.
Để cài đặt eXe trên Windows, ta làm theo các bước sau:
Bước 1: Tải phiên bản eXe mới nhất tại địa chỉ: http://www.exelearning.org. Phiên bản mới nhất tại thời điểm này là eXe 1.04. Tuy nhiên, trong khuôn khổ bài viết tôi minh họa với phiên bản eXe 0.96.0. Các bạn có thể download phần mềm và bài tập minh họa tại:
Bước 2: Chạy chương trình cài đặt eXe vừa download (trong trường hợp nay là file eXe 0.96.0.exe):
Giao diện màn hình chính của eXe
Mục chọn Outline và iDevice trong các phiên bản trước đã trở thành menu biên cho phép người dùng linh động hơn với các công cụ thường sử dụng để có thể biến đổi đề cương và lựa chọn iDevice.
Outline
Mục chọn Outline cho phép người dùng thiết kế một đề cương phản chiếu cấu trúc theo thứ tự và phân loại ưu tiên. Ví dụ: topics-sections-units, hoặc books-chapters-verses, v.v.. Chúng ta có thể tự thiết lập được chúng.
iDeviece
Mục chọn iDevice (instructional device) bao gồm một tập các phần tử có cấu trúc để mô tả nội dung học tập như: objectives, pre-knownledge, case studies, free text. Nội dung học tập (learning content) được biên soạn bằng cách lựa chọn các iDeviece từ menu iDeviece và nhập nội dung học tập của chúng ta vào. Một tài nguyên học tập có thể bao gồm một số hoặc nhiều các iDeviece tùy theo yêu cầu thực tế của nội dung bài giảng. Các iDeviece hiện đang được phát triển, tùy theo từng phiên bản cụ thể sẽ có thể có những iDeviece khác nhau. Bộ soạn thảo iDeviece cho phép người dùng thiết kế các mẫu và các iDeviece của riêng mình.
Authoring
Đây là vùng soạn thảo nội dung chính của eXe. Nội dung tài liệu được đưa vào thông qua các iDeviece tương ứng.
Xây dựng nội dung cho khóa học
Trong môi trường E-Learning, một khoá học được phân thành nhiều mô đun khác nhau. Trong mỗi mô đun, có thể tách thành các mô đun nhỏ hơn... (chúng ta có thể hình dung một cấu trúc cây các mô đun). Như vậy, chúng ta có thể coi một khóa học như là một mô đun chính, chứa các mô đun nhỏ hơn. Để xây dựng đề cương cho tài liệu, chúng ta sử dụng ô Outline và các nút xung quanh ô này:
• Thêm một nhánh trên cây đề cương
Để thêm một nhánh của cây đề cương, ta làm như sau:
Bấm chọn vị trí cần đưa vào cây đề cương
Bấm chọn nút Add page
Sau khi bấm nút Add Page, cây đề cương sẽ xuất hiện một trang mới.
• Đổi tên một nhánh trên cây đề cương:
Để đổi tên một nhánh trên cây đề cương, ta làm như sau:
Kích đúp chuột vào nhánh cần đổi tên. Hộp thoại sẽ hiển thị như hình sau:
Nhập tên mới cho nhánh (trang) vào ô Enter the new name.
Bấm OK để hoàn thành việc đổi tên.
• Xóa một nhánh trên cây đề cương:
Để xóa một nhánh trên cây đề cương, ta làm như sau:
Kích chọn nhánh cần xóa
Kích chọn nút Delete
Bấm chọn OK để xác nhận xóa trang.
• Thay đổi vị trí các trang
Để thay đổi vị trí của một trang, ta có thể sử dụng các nút điều khiển ở ngay phía duới ô Outline:
Để thay đổi cấp độ sâu của một nhánh, ta sử dụng các phím
Để thay đổi vị trí của các nhánh trong cùng một cấp, ta có thể sử dụng các nút ▲ (lên trên một nấc) hay ▼ (xuống dưới một nấc).
Xây dựng nội dung cho các nút thông qua các iDevice
Một trang tài liệu trong eXe được cấu thành bởi một hoặc nhiều thành phần riêng biệc gọi là các iDevice nằm xen kẽ lẫn nhau. Mỗi iDevice sẽ xác định một nội dung cụ thể, chẳng hạn có iDevice để hiển thị một hình ảnh, có iDevice để xây dựng một thư viện ảnh, có iDevice cho phép nhập nội dung xác định mục tiêu của bài học...
Danh sách một số iDevice trong eXe
Activity Các hoạt động xảy ra trong quá trình học
Attachment Đính kèm một file vào nội dung học tập
Case Study Một câu chuyện liên quan đến nội dung học tập, qua đó có thể đưa vào các câu hỏi thảo luận và rút ra kết luận
Cloze Activity Các câu hỏi điền khuyết hỗ trợ học sinh nắm được nội dung bài học
External Website Đưa một trang web vào nội dung học tập, qua đó học sinh có thể duyệt nội dung của website ngay trong bài học mà không cần mở cửa sổ khác.
Flash Movie Đưa một đoạn film flash (*.flv) vào nội dung tài liệu
Flash with text Đưa một file hoạt hình flash (*.swf) và văn bản mô tả (nếu cần) vào nội dung tài liệu
Free Text Nhập văn bản đơn thuần vào nội dung tài liệu
Image Gallery Nhập một thư viện ảnh vào nội dung tài liệu
Image Magnifier Cho phép xem phóng đại một ảnh được chèn vào
Image with text Chèn một ảnh và văn bản (nếu cần) vào tài liệu
Multi choice question Câu hỏi đa lựa chọn
Objective Mục tiêu, mục đích của quá trình học
Preknowlege Các kiến thức cần có để có thể tham gia khóa học
Reading Activity Một thu gọn của Case study với một hoạt động
Reflection Cho phép đưa vào các câu hỏi phản chiếu
Scorm Quiz Câu hỏi đa lựa chọn theo chuẩn SCORM
True-False Question Các câu hỏi đúng sai
Wikipedia Article Đưa vào các nội dung của bộ từ điển bách khoa trực tuyến Wikipedia
Cách thức điều khiển các iDevice
Để đưa một iDevice vào trang tài liệu, ta kích chuột vào iDevice tương ứng. Khi đó, khung làm việc bên phải sẽ hiển thị mẫu biểu nhập thông tin cho iDevice.
Trong quá trình nhập thông tin cho iDevice, phía dưới mỗi iDevice sẽ có một thanh điều khiển với các nút như sau:
Nút có dấu check màu xanh được sử dụng để lưu lại nội dung của iDevice
Nút Thùng rác được dùng để xóa iDevice
Nút tam giác hướng lên: Chuyển vị trí của iDevice trong trang nội dung lên phía trên
Nút tam giác hướng xuống: Chuyển vị trí của iDevice trong trang nội dung xuống phía dưới
Ô sổ xuống Move To sẽ cho phép chuyển iDevice từ trang nội dung hiện thời sang trang nội dung khác.
Để thay đổi nội dung chứa trong một ô iDevice, chúng ta kích đúp chuột vào iDevice đó. Khi đó, màn hình soạn thảo iDevice tương ứng sẽ hiển thị cho phép chúng ta soạn thảo hoặc xóa iDevice.
MINH HỌA SỬ DỤNG TRÊN CÁC iDEVICE CỦA PHẦN MỀM eXe
(anh có thể đăng kỳ 2)
Minh họa: iDevice xác định mục tiêu của bài học (iDevice Objective)
Để đưa phần nội dung xác định mục tiêu vào bài học, ta sử dụng iDevice Objective. Thao tác cụ thể như sau:
Bước 1: Kích chọn iDevice Objective trong danh sách iDevice. Khi đó, phần nội dung bên phải sẽ hiển thị ra mẫu có dạng như hình sau:
Bước 2: Ta có thể thay đổi tiêu đề Objective bởi một tiêu đề khác bằng tiếng Việt, ví dụ như: “Mục tiêu” hay “Mục đích”...
Bước 3: Trong ô soạn thảo ở dưới, ta có thể nhập nội dung của mục tiêu. Ta cũng có thể sử dụng các thanh công cụ để soạn thảo, trình bày nội dung cho đẹp (giống như trên Word).
Bước 4: Kích chuột vào nút dấu check màu xanh ở góc dưới bên trái của iDevice để lưu lại nội dung của iDevice đó.
Minh họa: iDevice Cloze Activity (câu hỏi điền khuyết)
Câu hỏi điền khuyết (điền vào chỗ trống) cho phép giáo viên nhập vào một đoạn văn bản, sau đó ẩn một số từ và yêu cầu học sinh điền đúng từ đã ẩn vào chỗ trống.
Để thực hiện điều này, ta làm như sau:
Bước 1: Kích chọn iDevice Cloze Activity. iDevice này sẽ hiển thị như hình sau:
Bước 2: Nhập dòng tiêu đề hướng dẫn vào ô Instructions, chẳng hạn như: “Đọc đoạn văn bản sau đây và điền từ vào chỗ trống”:
Bước 3: Trong ô Cloze Text, nhập đoạn văn bản mẫu.
Bước 4: Đánh đấu từ cần ẩn, sau đó bấm chọn Hide/Show Word. Khi đó từ bị ẩn sẽ được đánh dấu gạch dưới để phân biệt với các từ thông thường.
Ta có thể lặp lại bước 4 nhiều lần để ẩn nhiều từ khác.
Bước 5: Kích chọn dấu check màu xanh để lưu nội dung trong iDevice.
Sau khi hoàn thành việc soạn thảo câu hỏi, trên trang soạn thảo sẽ hiển thị câu hỏi điền từ có dạng:
Học sinh sẽ nhập các từ còn thiếu vào các ô trống trên đoạn tài liệu và bấm Submit, khi đó hệ thống sẽ hiển thị các câu trả lời đúng với màu xanh, câu trả lời sai với màu đỏ, và số điểm của học viên:
Nếu học sinh muốn làm lại, học sinh có thể bấm nút Restart, còn trong trường hợp muốn xem đáp án, học sinh có thể bấm nút Show Answers.
Xuất bản nội dung
Hiện tại eXe sử dụng 3 loại định dạng file chính như sau:
.elp Các gói nội dung eXe content packages được lưu lại dưới các file có đuôi .elp (elearning packages); định dạng này chủ yếu được sử dụng ở bên trong của eXe, chỉ có thể được sử dụng để trao đổi nội dung giữa những người dùng cần cộng tác với nhau.
SCORM export Gói nội dung được lưu lại dưới dạng một file nén zip, cho phép gói tất cả các trang được tạo ra cùng với một file IMSmanifest.xml để sử dụng với các hệ LMS tương thích vói SCORM. Tài liệu này cung cấp cho LMS những chỉ dẫn hiển thị và cấu trúc gói nội dung.
IMS export Định dạng này đóng gói nội dung theo cách tương tự như việc xuất ra chuẩn SCORM
HTML export Tạo ra một thư mục chứa các trang HTML,hình ảnh và các style sheet cần thiết để xuất bản gói nội dung lên web.
Nếu sử dụng môi trường Windows, các file eXe sẽ được lưu vào thư mục My Documents. Đây là thư mục mặc định và có thể được thay đổi bằng cách nhập đường dẫn tới thư mục mà chúng ta cần lưu các file.
Các nội dung được tạo ra trong eXe có thể được export thành các gói web để xuất bản lên web server, cũng như gói SCORM 1.2 để phân phát tới các hệ LMS tương thích với SCORM, một IMS Content Package, hoặc như là một trang web đơn để tiện in ấn.
Hướng dẫn xuất bản gói nội dung dưới dạng web
Để xuất bản nội dung dưới dạng một website, ta làm như sau:
Bước 1: Vào menu File, chọn Export
Bước 2: Chọn tiếp Website. Khi đó có hai lựa chọn:
Sefl Contained folder: Lựa chọn này để xuất bản nội dung ra một thư mục
Zip file: Lựa chọn này để xuất bản nội dung dưới dạng một file nén.
Bước 3: Sau khi lựa chọn một trong hai hình thức trên, hệ thống sẽ mở hộp thoại để chọn thư mục lưu trữ. Bấm OK.
Hướng dẫn xuất bản gói nội dung dưới dạng các gói nội dung SCORM/IMS
Như đã đề cập đến ở trên, các gói SCORM/IMS là các gói tài liệu được đóng gói theo chuẩn đặc tả SCORM hoặc IMS. Việc đóng gói theo các định chuẩn này sẽ cho phép nội dung có thể được sử dụng ở các hệ thống LMS khác nhau hỗ trợ SCORM.
Bước 1: Vào menu File, chọn Export
Bước 2: Lựa chọn SCORM 1.2 hoặc IMS Content Package. Cửa sổ sẽ được hiển thị và chúng ta sẽ được nhắc để nhập tiêu đề cho gói.
Bước 3: Nhập tiêu đề cho gói và kích chọn Save.
Ta có thể làm tương tự với việc export sang gói IMS.
Các gói được export theo cách này sẽ được lưu dưới dạng các file nén .zip. Chúng ta không cần phải giải nén các file này để import và một LMS.
Mỗi phần mềm đều có một thế mạnh riêng, để việc ứng dụng CNTT vào giảng dạy có hiệu quả, giáo viên cần phải xác định mục đích bài dạy rõ ràng để chọn phần mềm thích hợp cho bài giảng. Ngoài ra, giáo viên cũng có thể tích hợp các phần mềm với nhau để bài giảng thêm phong phú, dạy học đạt hiệu quả cao.
Tải bài viết chi tiết tại: http://www.mediafire.com/download.php?ynd0oqmwzty
Đặc điểm vượt trội của chương trình là nội dung bài dạy có thể đưa trực tiếp lên mạng để học sinh tự kiểm tra kiến thức không cần có sự can thiệp của giáo viên (dưới hình thức trắc nghiệm khách quan, điền từ, đúng sai, hỏi và trả lời, kể cả giáo án đã soạn của giáo viên ). Bài dạy có thể kèm theo hình ảnh (jpg) , phim (swf, flv), âm thanh (mp3, wma), liên kết với website khác lúc online để minh họa cho nội dung bài dạy. Học sinh, giáo viên có thể thao tác trực tiếp với bài dạy trên mạng hoặc tải các bài dạy, tư liệu kèm theo để học tại nhà trên máy tính.
Để cài đặt eXe trên Windows, ta làm theo các bước sau:
Bước 1: Tải phiên bản eXe mới nhất tại địa chỉ: http://www.exelearning.org. Phiên bản mới nhất tại thời điểm này là eXe 1.04. Tuy nhiên, trong khuôn khổ bài viết tôi minh họa với phiên bản eXe 0.96.0. Các bạn có thể download phần mềm và bài tập minh họa tại:
Bước 2: Chạy chương trình cài đặt eXe vừa download (trong trường hợp nay là file eXe 0.96.0.exe):
Giao diện màn hình chính của eXe
Mục chọn Outline và iDevice trong các phiên bản trước đã trở thành menu biên cho phép người dùng linh động hơn với các công cụ thường sử dụng để có thể biến đổi đề cương và lựa chọn iDevice.
Outline
Mục chọn Outline cho phép người dùng thiết kế một đề cương phản chiếu cấu trúc theo thứ tự và phân loại ưu tiên. Ví dụ: topics-sections-units, hoặc books-chapters-verses, v.v.. Chúng ta có thể tự thiết lập được chúng.
iDeviece
Mục chọn iDevice (instructional device) bao gồm một tập các phần tử có cấu trúc để mô tả nội dung học tập như: objectives, pre-knownledge, case studies, free text. Nội dung học tập (learning content) được biên soạn bằng cách lựa chọn các iDeviece từ menu iDeviece và nhập nội dung học tập của chúng ta vào. Một tài nguyên học tập có thể bao gồm một số hoặc nhiều các iDeviece tùy theo yêu cầu thực tế của nội dung bài giảng. Các iDeviece hiện đang được phát triển, tùy theo từng phiên bản cụ thể sẽ có thể có những iDeviece khác nhau. Bộ soạn thảo iDeviece cho phép người dùng thiết kế các mẫu và các iDeviece của riêng mình.
Authoring
Đây là vùng soạn thảo nội dung chính của eXe. Nội dung tài liệu được đưa vào thông qua các iDeviece tương ứng.
Xây dựng nội dung cho khóa học
Trong môi trường E-Learning, một khoá học được phân thành nhiều mô đun khác nhau. Trong mỗi mô đun, có thể tách thành các mô đun nhỏ hơn... (chúng ta có thể hình dung một cấu trúc cây các mô đun). Như vậy, chúng ta có thể coi một khóa học như là một mô đun chính, chứa các mô đun nhỏ hơn. Để xây dựng đề cương cho tài liệu, chúng ta sử dụng ô Outline và các nút xung quanh ô này:
• Thêm một nhánh trên cây đề cương
Để thêm một nhánh của cây đề cương, ta làm như sau:
Bấm chọn vị trí cần đưa vào cây đề cương
Bấm chọn nút Add page
Sau khi bấm nút Add Page, cây đề cương sẽ xuất hiện một trang mới.
• Đổi tên một nhánh trên cây đề cương:
Để đổi tên một nhánh trên cây đề cương, ta làm như sau:
Kích đúp chuột vào nhánh cần đổi tên. Hộp thoại sẽ hiển thị như hình sau:
Nhập tên mới cho nhánh (trang) vào ô Enter the new name.
Bấm OK để hoàn thành việc đổi tên.
• Xóa một nhánh trên cây đề cương:
Để xóa một nhánh trên cây đề cương, ta làm như sau:
Kích chọn nhánh cần xóa
Kích chọn nút Delete
Bấm chọn OK để xác nhận xóa trang.
• Thay đổi vị trí các trang
Để thay đổi vị trí của một trang, ta có thể sử dụng các nút điều khiển ở ngay phía duới ô Outline:
Để thay đổi cấp độ sâu của một nhánh, ta sử dụng các phím
Để thay đổi vị trí của các nhánh trong cùng một cấp, ta có thể sử dụng các nút ▲ (lên trên một nấc) hay ▼ (xuống dưới một nấc).
Xây dựng nội dung cho các nút thông qua các iDevice
Một trang tài liệu trong eXe được cấu thành bởi một hoặc nhiều thành phần riêng biệc gọi là các iDevice nằm xen kẽ lẫn nhau. Mỗi iDevice sẽ xác định một nội dung cụ thể, chẳng hạn có iDevice để hiển thị một hình ảnh, có iDevice để xây dựng một thư viện ảnh, có iDevice cho phép nhập nội dung xác định mục tiêu của bài học...
Danh sách một số iDevice trong eXe
Activity Các hoạt động xảy ra trong quá trình học
Attachment Đính kèm một file vào nội dung học tập
Case Study Một câu chuyện liên quan đến nội dung học tập, qua đó có thể đưa vào các câu hỏi thảo luận và rút ra kết luận
Cloze Activity Các câu hỏi điền khuyết hỗ trợ học sinh nắm được nội dung bài học
External Website Đưa một trang web vào nội dung học tập, qua đó học sinh có thể duyệt nội dung của website ngay trong bài học mà không cần mở cửa sổ khác.
Flash Movie Đưa một đoạn film flash (*.flv) vào nội dung tài liệu
Flash with text Đưa một file hoạt hình flash (*.swf) và văn bản mô tả (nếu cần) vào nội dung tài liệu
Free Text Nhập văn bản đơn thuần vào nội dung tài liệu
Image Gallery Nhập một thư viện ảnh vào nội dung tài liệu
Image Magnifier Cho phép xem phóng đại một ảnh được chèn vào
Image with text Chèn một ảnh và văn bản (nếu cần) vào tài liệu
Multi choice question Câu hỏi đa lựa chọn
Objective Mục tiêu, mục đích của quá trình học
Preknowlege Các kiến thức cần có để có thể tham gia khóa học
Reading Activity Một thu gọn của Case study với một hoạt động
Reflection Cho phép đưa vào các câu hỏi phản chiếu
Scorm Quiz Câu hỏi đa lựa chọn theo chuẩn SCORM
True-False Question Các câu hỏi đúng sai
Wikipedia Article Đưa vào các nội dung của bộ từ điển bách khoa trực tuyến Wikipedia
Cách thức điều khiển các iDevice
Để đưa một iDevice vào trang tài liệu, ta kích chuột vào iDevice tương ứng. Khi đó, khung làm việc bên phải sẽ hiển thị mẫu biểu nhập thông tin cho iDevice.
Trong quá trình nhập thông tin cho iDevice, phía dưới mỗi iDevice sẽ có một thanh điều khiển với các nút như sau:
Nút có dấu check màu xanh được sử dụng để lưu lại nội dung của iDevice
Nút Thùng rác được dùng để xóa iDevice
Nút tam giác hướng lên: Chuyển vị trí của iDevice trong trang nội dung lên phía trên
Nút tam giác hướng xuống: Chuyển vị trí của iDevice trong trang nội dung xuống phía dưới
Ô sổ xuống Move To sẽ cho phép chuyển iDevice từ trang nội dung hiện thời sang trang nội dung khác.
Để thay đổi nội dung chứa trong một ô iDevice, chúng ta kích đúp chuột vào iDevice đó. Khi đó, màn hình soạn thảo iDevice tương ứng sẽ hiển thị cho phép chúng ta soạn thảo hoặc xóa iDevice.
MINH HỌA SỬ DỤNG TRÊN CÁC iDEVICE CỦA PHẦN MỀM eXe
(anh có thể đăng kỳ 2)
Minh họa: iDevice xác định mục tiêu của bài học (iDevice Objective)
Để đưa phần nội dung xác định mục tiêu vào bài học, ta sử dụng iDevice Objective. Thao tác cụ thể như sau:
Bước 1: Kích chọn iDevice Objective trong danh sách iDevice. Khi đó, phần nội dung bên phải sẽ hiển thị ra mẫu có dạng như hình sau:
Bước 2: Ta có thể thay đổi tiêu đề Objective bởi một tiêu đề khác bằng tiếng Việt, ví dụ như: “Mục tiêu” hay “Mục đích”...
Bước 3: Trong ô soạn thảo ở dưới, ta có thể nhập nội dung của mục tiêu. Ta cũng có thể sử dụng các thanh công cụ để soạn thảo, trình bày nội dung cho đẹp (giống như trên Word).
Bước 4: Kích chuột vào nút dấu check màu xanh ở góc dưới bên trái của iDevice để lưu lại nội dung của iDevice đó.
Minh họa: iDevice Cloze Activity (câu hỏi điền khuyết)
Câu hỏi điền khuyết (điền vào chỗ trống) cho phép giáo viên nhập vào một đoạn văn bản, sau đó ẩn một số từ và yêu cầu học sinh điền đúng từ đã ẩn vào chỗ trống.
Để thực hiện điều này, ta làm như sau:
Bước 1: Kích chọn iDevice Cloze Activity. iDevice này sẽ hiển thị như hình sau:
Bước 2: Nhập dòng tiêu đề hướng dẫn vào ô Instructions, chẳng hạn như: “Đọc đoạn văn bản sau đây và điền từ vào chỗ trống”:
Bước 3: Trong ô Cloze Text, nhập đoạn văn bản mẫu.
Bước 4: Đánh đấu từ cần ẩn, sau đó bấm chọn Hide/Show Word. Khi đó từ bị ẩn sẽ được đánh dấu gạch dưới để phân biệt với các từ thông thường.
Ta có thể lặp lại bước 4 nhiều lần để ẩn nhiều từ khác.
Bước 5: Kích chọn dấu check màu xanh để lưu nội dung trong iDevice.
Sau khi hoàn thành việc soạn thảo câu hỏi, trên trang soạn thảo sẽ hiển thị câu hỏi điền từ có dạng:
Học sinh sẽ nhập các từ còn thiếu vào các ô trống trên đoạn tài liệu và bấm Submit, khi đó hệ thống sẽ hiển thị các câu trả lời đúng với màu xanh, câu trả lời sai với màu đỏ, và số điểm của học viên:
Nếu học sinh muốn làm lại, học sinh có thể bấm nút Restart, còn trong trường hợp muốn xem đáp án, học sinh có thể bấm nút Show Answers.
Xuất bản nội dung
Hiện tại eXe sử dụng 3 loại định dạng file chính như sau:
.elp Các gói nội dung eXe content packages được lưu lại dưới các file có đuôi .elp (elearning packages); định dạng này chủ yếu được sử dụng ở bên trong của eXe, chỉ có thể được sử dụng để trao đổi nội dung giữa những người dùng cần cộng tác với nhau.
SCORM export Gói nội dung được lưu lại dưới dạng một file nén zip, cho phép gói tất cả các trang được tạo ra cùng với một file IMSmanifest.xml để sử dụng với các hệ LMS tương thích vói SCORM. Tài liệu này cung cấp cho LMS những chỉ dẫn hiển thị và cấu trúc gói nội dung.
IMS export Định dạng này đóng gói nội dung theo cách tương tự như việc xuất ra chuẩn SCORM
HTML export Tạo ra một thư mục chứa các trang HTML,hình ảnh và các style sheet cần thiết để xuất bản gói nội dung lên web.
Nếu sử dụng môi trường Windows, các file eXe sẽ được lưu vào thư mục My Documents. Đây là thư mục mặc định và có thể được thay đổi bằng cách nhập đường dẫn tới thư mục mà chúng ta cần lưu các file.
Các nội dung được tạo ra trong eXe có thể được export thành các gói web để xuất bản lên web server, cũng như gói SCORM 1.2 để phân phát tới các hệ LMS tương thích với SCORM, một IMS Content Package, hoặc như là một trang web đơn để tiện in ấn.
Hướng dẫn xuất bản gói nội dung dưới dạng web
Để xuất bản nội dung dưới dạng một website, ta làm như sau:
Bước 1: Vào menu File, chọn Export
Bước 2: Chọn tiếp Website. Khi đó có hai lựa chọn:
Sefl Contained folder: Lựa chọn này để xuất bản nội dung ra một thư mục
Zip file: Lựa chọn này để xuất bản nội dung dưới dạng một file nén.
Bước 3: Sau khi lựa chọn một trong hai hình thức trên, hệ thống sẽ mở hộp thoại để chọn thư mục lưu trữ. Bấm OK.
Hướng dẫn xuất bản gói nội dung dưới dạng các gói nội dung SCORM/IMS
Như đã đề cập đến ở trên, các gói SCORM/IMS là các gói tài liệu được đóng gói theo chuẩn đặc tả SCORM hoặc IMS. Việc đóng gói theo các định chuẩn này sẽ cho phép nội dung có thể được sử dụng ở các hệ thống LMS khác nhau hỗ trợ SCORM.
Bước 1: Vào menu File, chọn Export
Bước 2: Lựa chọn SCORM 1.2 hoặc IMS Content Package. Cửa sổ
Bước 3: Nhập tiêu đề cho gói và kích chọn Save.
Ta có thể làm tương tự với việc export sang gói IMS.
Các gói được export theo cách này sẽ được lưu dưới dạng các file nén .zip. Chúng ta không cần phải giải nén các file này để import và một LMS.
Mỗi phần mềm đều có một thế mạnh riêng, để việc ứng dụng CNTT vào giảng dạy có hiệu quả, giáo viên cần phải xác định mục đích bài dạy rõ ràng để chọn phần mềm thích hợp cho bài giảng. Ngoài ra, giáo viên cũng có thể tích hợp các phần mềm với nhau để bài giảng thêm phong phú, dạy học đạt hiệu quả cao.
Tải bài viết chi tiết tại: http://www.mediafire.com/download.php?ynd0oqmwzty
Học thuật toán và đánh giá độ phức tạp của thuật toán trong chương trình Tin học THPT
Chương trình Tin học 11 dạy lập trình của trung học phổ thông nhằm trang bị cho học sinh một số kiến thức, kỹ năng cơ bản về lập trình, biết vận dụng chúng để giải một số bài tập cơ bản, đồng thời bước đầu chuẩn bị hành trang cho học sinh có thể đi tiếp vào lĩnh vực Tin học ở các giai đoạn tiếp theo. Tuy nhiên, học lập trình học sinh cần một loại hình tư duy quan trọng - đó là tư duy thuật toán. Để hình thành và phát triển loại hình tư duy này học sinh cần trú trọng rèn luyện các khả năng sau:
1. Thực hiện những thao tác theo một trình tự nhất định phù hợp với một thuật toán cho trước
2. Phân tích một hoạt động thành những thao tác thành phần được thực hiện theo một trình tự nhất định.
3. Mô tả chính xác quá trình tiến hành một hoạt động.
4. Khái quát hoá một hoạt động trên những đối tượng riêng lẻ thành một hoạt động trên một lớp đối tượng.
5. So sánh những thuật toán khác nhau cùng thực hiện một công việc và phát hiện thuật toán tối ưu.
Tuy nhiên, một điều cần cũng rất quan trọng là học sinh cần chú trọng đến một khái niệm "Độ phức tạp của một thuật toán" và đánh giá độ phức tạp của một thuật toán…Để làm được điều này, học sinh có thể từng bước hình thành, rèn luyện khả năng đánh giá độ phức tạp của thuật toán ở mức độ đơn giản dưới các góc độ sau:
- Độ phức tạp về thời gian tính của thuật toán
- Độ phức tạp về dung lượng nhớ dùng cho thuật toán.
Chúng ta có thể đi vào chi tiết một vài ví dụ đơn giản trong SGK Tin học lớp 11.
Ví dụ 1: Lập trình giải bài toán cổ "vừa gà vừa chó"
Cách 1: Gọi số gà là i (khi đó số chó là 36-i)
Từ giả thiết suy ra i là một số nguyên và có thể nhận giá trị từ 0 đến 36.
Ta có thuật toán :
For i:= 0 To 36 Do
If 2*i + (36-i)*4 =100 Then
Thông báo kết quả.
Với mỗi bước lặp về hình thức máy phải thực hiện 5 phép toán, nếu gọi thời gian để thực hiện một lượt 5 phép toán đó là t thì thời gian thực hiện thuật toán là 36t.
Cách 2: Gọi số chó là i (số gà là 36-i). Vậy i là một số nguyên có thể nhận giá trị từ 0 đến 25 (vì tổng số chân chỉ có 100 nên số chó tối đa là 25), ta có thuật toán
For i:= 0 to 25 do
If 4*i + (36-i)*2 = 100 then
Thông báo kết quả.
Vậy thời gian để thực hiện thuật toán 2 là 25t. So với thuật toán ban đầu thì lượng thời gian rút ngắn được là 11t.
Ví dụ 2: Viết chương trình nhập vào 20 số thực, sau đó sắp lại dãy theo chiều tăng dần và cho biết một số thực x có thuộc mảng không?
Khi giải quyết công đoạn sắp xếp lại dãy số, chúng thường sử dụng thuật toán sắp xếp tuần tự hoặc sắp xếp "nổi bọt".
Cách 1: Ta lần lượt so sánh số x với từng số trong dãy
i:=1; ok:=true
While (i<=20) and ok do
If x=a[i] then
begin
Thông báo đã tìm thấy ở vị trí i;
ok:=False;
end
else i:=i+1;
Vậy tối đa thuật toán thực hiện 20 lần phép toán so sánh.
Cách 2: Lần lượt so sánh x với số nằm ở vị trí giữa của dãy
dau:=1; cuoi:=20;ok:=true;
While (dau<= cuoi) and ok do
Begin
k:=Trunc((daưcuoi)/2);
If a[k]=x then
Begin
Thông báo tìm thấy ở vị trí i;
ok:=False;
end
else If a[k]>x then cuoi:=k-1
else dau:=k+1
Vậy sau mỗi bước lặp hoặc ta tìm được số x hoặc chỉ còn phải so sánh x với một nửa các phần tử của dãy.
Bằng các ví dụ cụ thể với số phần tử n càng lớn, chúng ta có thể chỉ ra được tính tối ưu của cách 2 so với cách 1 (độ phức tạp của phương án 2 là O(log2n) trong khi đó độ phức tạp của thuật toán trong phương án 1 là O(n)).
Ví dụ 3: Cho một dãy số a có n phần tử a1, a2, ...an. Hãy xây dựng thuật toán để tìm con số lớn nhất trong dãy a.
Khi giải quyết bài toán này, chúng ta nhận thấy:
- Nếu dãy chỉ có 1 phần tử thì phần tử đó là số lớn nhất.
- Giả sử dãy có n phần tử và ta đã xác định được phần tử lớn nhất là amax . Nếu bổ sung thêm phần tử thứ an+1 vào dãy mà an+1 > amax thì an+1 chính là phần tử lớn nhất của dãy có n+1 phần tử. Trường hợp ngược lại, nghĩa là an+1 < amax thì amax vẫn là phần tử lớn nhất của dãy có n+1 phần tử.
Ta có thuật toán như sau:
Bước 1: Ghi nhớ amax = a1.
Bước 2: i = 2.
Bước 3: Nếu (i £ n) thì thực hiện các bước sau, ngược lại sang bước 5.
Bước 3.1: Nếu (ai > amax ) thì
Bước 3.1.1: Ghi nhớ amax = ai .
Bước 3.2: Tăng i lên 1.
Bước 4: Trở lại bước 3.
Bước 5: Phần tử lớn nhất dãy a chính là amax .Kết thúc.
Trong thuật toán trên, để đơn giản, ta chỉ xem chi phí là số lần so sánh ở bước 3.1 và số lần "ghi nhớ" trong bước 3.1.1. Trường hợp tốt nhất của thuật toán này xảy ra khi con số lớn nhất nằm đầu dãy (amax= a1); trường hợp xấu nhất xảy ra khi con số lớn nhất nằm ở cuối dãy (amax=an) và dãy được sắp xếp theo thứ tự tăng dần.
Dựa theo sơ đồ khối của thuật toán, ta nhận thấy rằng, trong mọi trường hợp của bài toán, phép "ghi nhớ" ở bước 3.1 luôn được thực hiện và số lần thực hiện là n-1 (ứng với việc xét từ phần tử a2 đến an). Ta gọi đây là chi phí cố định hoặc bất biến của thuật toán.
- Trường hợp tốt nhất : do amax = a1 suy ra, với mọi i >= 2, ai< amax. Do đó, điều kiện ai>amax ở bước 3.1 luôn không thỏa nên bước 3.1.1 không bao giờ được thực hiện. Như vậy, chi phí chung cho trường hợp này chính là chi phí cố định của bài toán.
T = f(n) = n-1
- Trường hợp xấu nhất : với mọi i>1, ai-1< ai (do định nghĩa dãy được sắp xếp tăng dần) nên điều kiện ai>amax ở bước 3.1 luôn thỏa, bước 3.1.1 luôn được thực hiện. Như vậy, ngoài chi phí chung là n-1 phép so sánh, ta cần phải dùng thêm n-1 phép "ghi nhớ" ở bước 3.1.1. Như vậy, tổng chi phí của trường hợp này là
T = f(n) = 2(n-1)=2n-2
Tóm lại, một điều quan trọng cần phải biết là máy tính phải cần bao lâu để giải xong một bài toán. Thí dụ, nếu một thuật toán đòi hỏi 10 giờ, thì chúng ta có thể chấp nhận chi phí thời gian máy tính đòi hỏi để giải bài toán đó. Nhưng nếu một thuật toán đòi hỏi 10 tỉ năm để giải một bài toán, thì thực hiện thuật toán đó sẽ là một điều phi lý. Một trong những hiện tượng lý thú nhất của công nghệ hiện đại là sự tăng ghê gớm của tốc độ và lượng bộ nhớ trong máy tính. Một nhân tố quan trọng khác làm giảm thời gian cần thiết để giải một bài toán là sự xử lý song song - đây là kỹ thuật thực hiện đồng thời các dãy phép tính. Do sự tăng tốc độ tính toán và dung lượng bộ nhớ của máy tính, cũng như nhờ việc dùng các thuật toán lợi dụng được ưu thế của kỹ thuật xử lý song song, các bài toán vài năm trước đây được xem là không thể giải được, thì bây giờ có thể giải bình thường.
1. Thực hiện những thao tác theo một trình tự nhất định phù hợp với một thuật toán cho trước
2. Phân tích một hoạt động thành những thao tác thành phần được thực hiện theo một trình tự nhất định.
3. Mô tả chính xác quá trình tiến hành một hoạt động.
4. Khái quát hoá một hoạt động trên những đối tượng riêng lẻ thành một hoạt động trên một lớp đối tượng.
5. So sánh những thuật toán khác nhau cùng thực hiện một công việc và phát hiện thuật toán tối ưu.
Tuy nhiên, một điều cần cũng rất quan trọng là học sinh cần chú trọng đến một khái niệm "Độ phức tạp của một thuật toán" và đánh giá độ phức tạp của một thuật toán…Để làm được điều này, học sinh có thể từng bước hình thành, rèn luyện khả năng đánh giá độ phức tạp của thuật toán ở mức độ đơn giản dưới các góc độ sau:
- Độ phức tạp về thời gian tính của thuật toán
- Độ phức tạp về dung lượng nhớ dùng cho thuật toán.
Chúng ta có thể đi vào chi tiết một vài ví dụ đơn giản trong SGK Tin học lớp 11.
Ví dụ 1: Lập trình giải bài toán cổ "vừa gà vừa chó"
Cách 1: Gọi số gà là i (khi đó số chó là 36-i)
Từ giả thiết suy ra i là một số nguyên và có thể nhận giá trị từ 0 đến 36.
Ta có thuật toán :
For i:= 0 To 36 Do
If 2*i + (36-i)*4 =100 Then
Thông báo kết quả.
Với mỗi bước lặp về hình thức máy phải thực hiện 5 phép toán, nếu gọi thời gian để thực hiện một lượt 5 phép toán đó là t thì thời gian thực hiện thuật toán là 36t.
Cách 2: Gọi số chó là i (số gà là 36-i). Vậy i là một số nguyên có thể nhận giá trị từ 0 đến 25 (vì tổng số chân chỉ có 100 nên số chó tối đa là 25), ta có thuật toán
For i:= 0 to 25 do
If 4*i + (36-i)*2 = 100 then
Thông báo kết quả.
Vậy thời gian để thực hiện thuật toán 2 là 25t. So với thuật toán ban đầu thì lượng thời gian rút ngắn được là 11t.
Ví dụ 2: Viết chương trình nhập vào 20 số thực, sau đó sắp lại dãy theo chiều tăng dần và cho biết một số thực x có thuộc mảng không?
Khi giải quyết công đoạn sắp xếp lại dãy số, chúng thường sử dụng thuật toán sắp xếp tuần tự hoặc sắp xếp "nổi bọt".
Cách 1: Ta lần lượt so sánh số x với từng số trong dãy
i:=1; ok:=true
While (i<=20) and ok do
If x=a[i] then
begin
Thông báo đã tìm thấy ở vị trí i;
ok:=False;
end
else i:=i+1;
Vậy tối đa thuật toán thực hiện 20 lần phép toán so sánh.
Cách 2: Lần lượt so sánh x với số nằm ở vị trí giữa của dãy
dau:=1; cuoi:=20;ok:=true;
While (dau<= cuoi) and ok do
Begin
k:=Trunc((daưcuoi)/2);
If a[k]=x then
Begin
Thông báo tìm thấy ở vị trí i;
ok:=False;
end
else If a[k]>x then cuoi:=k-1
else dau:=k+1
Vậy sau mỗi bước lặp hoặc ta tìm được số x hoặc chỉ còn phải so sánh x với một nửa các phần tử của dãy.
Bằng các ví dụ cụ thể với số phần tử n càng lớn, chúng ta có thể chỉ ra được tính tối ưu của cách 2 so với cách 1 (độ phức tạp của phương án 2 là O(log2n) trong khi đó độ phức tạp của thuật toán trong phương án 1 là O(n)).
Ví dụ 3: Cho một dãy số a có n phần tử a1, a2, ...an. Hãy xây dựng thuật toán để tìm con số lớn nhất trong dãy a.
Khi giải quyết bài toán này, chúng ta nhận thấy:
- Nếu dãy chỉ có 1 phần tử thì phần tử đó là số lớn nhất.
- Giả sử dãy có n phần tử và ta đã xác định được phần tử lớn nhất là amax . Nếu bổ sung thêm phần tử thứ an+1 vào dãy mà an+1 > amax thì an+1 chính là phần tử lớn nhất của dãy có n+1 phần tử. Trường hợp ngược lại, nghĩa là an+1 < amax thì amax vẫn là phần tử lớn nhất của dãy có n+1 phần tử.
Ta có thuật toán như sau:
Bước 1: Ghi nhớ amax = a1.
Bước 2: i = 2.
Bước 3: Nếu (i £ n) thì thực hiện các bước sau, ngược lại sang bước 5.
Bước 3.1: Nếu (ai > amax ) thì
Bước 3.1.1: Ghi nhớ amax = ai .
Bước 3.2: Tăng i lên 1.
Bước 4: Trở lại bước 3.
Bước 5: Phần tử lớn nhất dãy a chính là amax .Kết thúc.
Trong thuật toán trên, để đơn giản, ta chỉ xem chi phí là số lần so sánh ở bước 3.1 và số lần "ghi nhớ" trong bước 3.1.1. Trường hợp tốt nhất của thuật toán này xảy ra khi con số lớn nhất nằm đầu dãy (amax= a1); trường hợp xấu nhất xảy ra khi con số lớn nhất nằm ở cuối dãy (amax=an) và dãy được sắp xếp theo thứ tự tăng dần.
Dựa theo sơ đồ khối của thuật toán, ta nhận thấy rằng, trong mọi trường hợp của bài toán, phép "ghi nhớ" ở bước 3.1 luôn được thực hiện và số lần thực hiện là n-1 (ứng với việc xét từ phần tử a2 đến an). Ta gọi đây là chi phí cố định hoặc bất biến của thuật toán.
- Trường hợp tốt nhất : do amax = a1 suy ra, với mọi i >= 2, ai< amax. Do đó, điều kiện ai>amax ở bước 3.1 luôn không thỏa nên bước 3.1.1 không bao giờ được thực hiện. Như vậy, chi phí chung cho trường hợp này chính là chi phí cố định của bài toán.
T = f(n) = n-1
- Trường hợp xấu nhất : với mọi i>1, ai-1< ai (do định nghĩa dãy được sắp xếp tăng dần) nên điều kiện ai>amax ở bước 3.1 luôn thỏa, bước 3.1.1 luôn được thực hiện. Như vậy, ngoài chi phí chung là n-1 phép so sánh, ta cần phải dùng thêm n-1 phép "ghi nhớ" ở bước 3.1.1. Như vậy, tổng chi phí của trường hợp này là
T = f(n) = 2(n-1)=2n-2
Tóm lại, một điều quan trọng cần phải biết là máy tính phải cần bao lâu để giải xong một bài toán. Thí dụ, nếu một thuật toán đòi hỏi 10 giờ, thì chúng ta có thể chấp nhận chi phí thời gian máy tính đòi hỏi để giải bài toán đó. Nhưng nếu một thuật toán đòi hỏi 10 tỉ năm để giải một bài toán, thì thực hiện thuật toán đó sẽ là một điều phi lý. Một trong những hiện tượng lý thú nhất của công nghệ hiện đại là sự tăng ghê gớm của tốc độ và lượng bộ nhớ trong máy tính. Một nhân tố quan trọng khác làm giảm thời gian cần thiết để giải một bài toán là sự xử lý song song - đây là kỹ thuật thực hiện đồng thời các dãy phép tính. Do sự tăng tốc độ tính toán và dung lượng bộ nhớ của máy tính, cũng như nhờ việc dùng các thuật toán lợi dụng được ưu thế của kỹ thuật xử lý song song, các bài toán vài năm trước đây được xem là không thể giải được, thì bây giờ có thể giải bình thường.
Ứng dụng phương pháp quy nạp toán học
Trong toán học, quy nạp là một phương pháp đơn giản nhưng hiệu quả để chứng minh các bài toán. Ở bài viết này tôi xin đưa ra một ứng dụng nhỏ của nó trong việc giải các bài toán tin học:
1. Thuật toán quy nạp quy nạp(nhắc lại):
Giả sử có bài toán F cần chứng minh đúng với mọi n N. Ta chứng minh bài toán đúng bằng cách quy nạp, cần tiến hành các bước sau:
- n = 1: mệnh đề cần chứng minh đúng.
- Giả sử n = k: mệnh đề cần chứng minh đúng.
- n = k + 1: ta cần chứng nó cũng đúng. Vậy theo nguyên lý quy nạp bài toán đúng với mọi N.
Trong tin học, thuật toán nay cũng được áp dụng. Tuy thuật toán đơn giản nhưng nó lại được áp dụng một cách rất linh động và khéo léo trong các bài toán tin.
2. Phát biểu bài toán tổng quát giải bằng quy nạp:
Thông thường bài toán giải bằng quy nạp không phải là một bài toán tối ưu hoá. Nó chỉ đơn giản là bài toán cần chỉ ra cách biến đổi theo quy luật cho trước để thu được kết quả mong đợi. Và bài toán đó thường được phát biểu như sau:Cho N đối tượng và một số thao tác biến đổi. Yêu cầu sử dụng các thao tác biến đổi để thu được kết mong đợi.
Cách làm thông thường:
- Nếu n = 0; 1: ta luôn có cách biến đổi đúng.
- Nếu có n > 1 mà ta luôn chỉ ra một cách biến đổi sao cho giản bớt được số đối tượng mà điều kiện bài toán vẫn không thay đổi.
- Như vậy vì số đối tượng trong một bài toán tin học luôn là hữu hạn nên sau một số hữu hạn bước thì số lượng đối tương bằng 1 hoặc 0. Suy ra bài toán được giải quyết một cách hoàn toàn.
3. Các ví dụ cụ thể:
P1. Cho N vecto v1, v2, …, vn độ dài nhỏ hơn L cho trước. Cần đặt trước các vecto một dấu cộng hoặc trừ sao cho vecto tổng thu được có độ dài nhỏ hơn căn 2 nhân L.Input: Segment.In
- Dòng đầu ghi số N ( 1 < N ≤ 10000) và L (0 < L ≤ 15000.00)
- N dòng tiếp theo mỗi dòng ghi một cặp số xi, yi là toạ độ của vecto thứ i. (|xi|, |yi| ≤ 10000).
Ouput: Segment.out
- Dòng thứ nhất ghi YES nó có thể đặt các dấu cộng trừ thoả mãn yêu cầu bài toán, NO trong trường hợp ngược lại.
- Nếu là YES dòng thứ hai ghi N kí tự cộng hoặc trừ cần đặt trước các vecto sao cho tổng vecto nhỏ hơn sprt(2)*L.
Ví dụ:
Thuật giải:
- n = 1 bài toán đã đúng.
- n = 2 có trường hợp xảy ra với hai vecto:
+ góc giữa hai vecto nhỏ hơn 90 độ, lấy vecto 1 trừ cho vecto 2 lúc đó ta thu được 1 vecto co độ dài nhỏ hơn sqrt(2) * L.
+ góc giữa hai vecto lớn hơn hoặc bài một 90 độ, lấy vecto 1 cộng cho vecto 2 lúc đó ta thu được 1 vecto có độ dài nhỏ hơn sqrt(2) * L.
- n ≥ 3 suy ra luôn có 2 vecto mà góc giữa hai phương của vecto nhỏ hơn hoặc 60 bằng độ có hai trường xảy ra:
+ góc giữa hai vecto đó nhỏ hơn hoặc bằng 60 độ, trừ vecto 1 cho vecto 2 thay hai vecto bằng vecto mới nhận được.
+ góc giữa hai vecto đó lớn hơn hoặc bằng 120 độ, cộng vecto 1 cho vecto 2 thay hai vecto bằng vecto mới nhận được. Lưu ý sau này nếu trừ vecto mới nhận được phải trừ (đổi dấu) toàn vecto bộ hình thành lên nó, vecto mới nhận được có độ dài nhỏ hơn L, số đoạn thẳng giảm 1.
Như vậy đây là bài toán luôn có lời giải, độ phức tạp O(N^2) nếu xử lý khéo có thể giản xuống O(n*log(n)). Chương trình mô tả thuật giải:
Procedure Xuly (n: integer //* số đối tượng *//);
Begin
If n <= 1 then exit else
If n = 2 then
Begin
If goc (v1, v2) <= 90 độ Then đổi dấu (v2);
//* đổi dấu tức là đổi dấu toàn bộ vecto thành phần *//
Thay hai vecto bằng 1 vecto (v1 + v2);
//* vecto mới gồm các thành phần của v1 và v2 *//
//* lúc này v2 nếu cần thiết đã đổi dấu rồi *//
Exit;
End else
Begin
lấy 3 vecto bất kỳ;
chọn ra được 2 vecto v1, v2 sao cho
góc nhỏ giữa phương 2 vec to nhỏ 60;
if goc (v1, v2) <= 60 then đổi dấu (v2);
Thay hai vecto này bằng (v1 + v2);
End;
End;
P2: Utopia (IOI 2002)
Đất nước Utopia tươi đẹp bị chiến tranh tàn phá. Khi chiến tranh tạm ngừng, đất nước bị chia cắt thành bốn miền bởi một đường kinh tuyến (đường theo hướng Bắc-Nam) và một đường vĩ tuyến (đường theo hướng Đông-Tây). Giao điểm của hai đường này xem như điểm (0, 0). Tất cả các miền này đều muốn mang tên Utopia, theo thời gian các miền này được gọi là Utopia 1 (phía Đông Bắc), Utopia 2 (phía Tây Bắc), Utopia 3 (phía Tây Nam), Utopia 4 (phía Đông Nam). Một điểm trong bất kỳ miền nào cũng được xác định bởi khoảng cách theo hướng Đông và khoảng cách theo hướng Bắc của nó so với điểm (0, 0). Bộ hai khoảng cách này được gọi là toạ độ của điểm. Các thành phần của toạ độ có thể là số âm; do đó một điểm miền Utopia 2 có toạ độ (âm, dương), một điểm miền Utopia 3 có toạ độ (âm, âm), một điểm miền Utopia 4 có toạ độ (dương, âm), một điểm miền Utopia 1 có toạ độ (dương, dương) (Giống như các góc phần tư trong hệ toạ độ đề các).
Một vấn đề là các công dân không được phép đi qua biên giới giữa các miền. May thay, một số thí sinh tham dự IOI của Utopia sáng chế ra một loại máy an toàn để vận chuyển từ xa. Máy này cần các số mã, mỗi số mã chỉ có thể được dùng một lần. Bây giờ, nhóm thí sinh tham dự và bạn phải hướng dẫn máy vận chuyển từ xa xuất phát từ vị trí ban đầu (0, 0) đến các miền của Utopia theo một trình tự cho trước. Khi bạn nhận được một dãy N số hiệu miền mà theo trình tự đó máy vận chuyển từ xa phải hạ cánh, với mỗi miền, bạn không cần phải quan tâm đến việc hạ cánh tại điểm nào của miền đó miễn là điểm đó thuộc miền yêu cầu. Người ta có thể yêu cầu máy hạ cánh liên tiếp hai lần hay nhiều lần hơn ở cùng một miền. Sau khi rời khỏi điểm ban đầu (0, 0), bạn không được hạ cánh trên các đường biên giới.
Bạn sẽ nhận được input là một dãy 2N số mã và phải viết chúng thành một dãy gồm N cặp mã, sau khi đặt một dấu + hoặc một dấu - thích hợp trước mỗi số. Nếu hiện tại bạn ở điểm (x,y) và sử dụng cặp mã số (+u,-v), bạn sẽ được chuyển tới điểm (x+u,y-v). Bạn có 2N số và bạn có thể sử dụng các số này theo thứ tự bạn muốn, mỗi số kèm theo một dấu + hoặc một dấu -.
Giả sử bạn có các số mã 7, 5, 6, 1, 3, 2, 4, 8 và phải hướng dẫn máy vận chuyển từ xa lần lượt đến các miền thuộc dãy miền 4, 1, 2, 1. Dãy các cặp mã (+7, -1), (-5, +2), (-4, +3), (+8, +6) đáp ứng yêu cầu này vì nó đưa bạn từ (0,0) lần lượt đến các vị trí (7, -1), (2, 1), (-2, 4) và (6, 10). Những điểm này nằm tương ứng ở Utopia 4, Utopia 1, Utopia 2 và Utopia 1.
Nhiệm vụ:
Cho 2N số mã khác nhau và một dãy N số hiệu miền là dãy các miền mà máy vận chuyển từ xa phải lần lượt hạ cánh. Hãy xây dựng một dãy các cặp mã từ các số đã cho để hướng dẫn máy vận chuyển từ xa lần lượt đi đến các miền thuộc dãy đã cho.
Input
Chương trình của bạn phải đọc từ input chuẩn. Dòng đầu gồm một số nguyên dương N (1 ≤ N ≤ 10000). Dòng thứ hai gồm 2N số mã nguyên khác nhau, tất cả đều là các số nguyên dương không lớn hơn 100000. Dòng cuối cùng gồm một dãy N số hiệu miền, mỗi một trong các số đó là 1, 2, 3 hoặc 4. Hai số liên tiếp trên một dòng cách nhau đúng một dấu trống.
Output
Chương trình của bạn phải viết ra output chuẩn. Ouput gồm N dòng, mỗi dòng chứa một cặp số mã mà trước mỗi số có dấu + hoặc dấu -. Đó là các cặp mã sẽ hướng dẫn cho máy vận chuyển đến dãy miền đã cho. Chú ý rằng không được có dấu trống sau dấu + hoặc dấu - nhưng phải có một dấu trống sau số mã thứ nhất.Nếu có nhiều lời giải, chương trình của bạn có thể đưa ra một lời giải bất kỳ trong số đó. Nếu không có lời giải, chương trình của bạn phải đưa ra một số 0 duy nhất.
Ví dụ:
Thuật giải:
Đây cũng là bài toàn luôn giải được để giải bài toán trên ta cần giải bài toán nhỏ sau:Cho một gồm N số nguyên dương khác nhau a1 < a2 < … < an. Cần sắp xếp lại và thêm các dấu vào các số ai sao cho tổng các số từ 1 đến vị trí i là dương hoặc âm biết trước:
Ví dụ:
Dãy 3 số: 1 2 3
Dấu cần xây dựng: +-+
Một cách thêm dấu và sắp xếp: +1 -2 + 3
Bổ đề:
Nếu dãy có dãy {ai} dương tăng và một chuỗi dấu cần biến đổi thì ta luôn có cách thêm dấu và thay đổi vị trí sao cho tổng cách số từ 1 đến i mang đấu của chuỗi dấu biết trước.
Chứng minh:
- số an mang dấu cuối cùng của chuỗi trên, các số còn lại đan dấu. (điều kiện về dấu để luôn xây được dãy) Ví dụ: {ai} = {1, 5, 10}; S = ‘++-‘; suy ra dãy {ai} được đánh dấu như sau: -1, +5, -10;
- nhận xét rằng: tổng của n số trên cuối cùng sẽ mang dấu của S[n]
- với n = 1 ta nhận được dãy cần tìm.
- Giả sử n =k ta xây dựng được chuỗi như trên.
- n = k + 1 chia hai trường hợp:
+ s[n-1] cùng dấu s[n]: đặt a[1] vào vị trí cuối cùng và lấy phần tử a[1] và s[n] ra khỏi dãy, nhưng còn là (n - 1) số và (n-1) dấu và dấu cuối cùng với số cuối, dãy đan dấu (vẫn thoả mãn điều kiện về dấu)
+ s[n - 1] và s[n] khác dấu: đặt a[n] vào vị trí cuối cùng và lấy phần tử a[n] và s[n] ra khỏi dãy, nhưng còn là (n - 1) số và (n-1) dấu và dấu cuối cùng với số cuối, dãy đan dấu. Theo giả thiết quy nạp thì dãy còn lại luôn xây dựng được.
Chương trình:
Procedure Xuly (Var a, dau, q: array [1…10000] of integer; n, cd, ct : integer);
//*ta đang xử lý dãy các số từ a[cd] đến a[ct] có dấu từ dấu[1] đến dấu[n] *//
Begin
If n <= 1 then exit;
If dau[n - 1] = dau[n] then
Begin
q[n] := a[cd];
Xuly (a, dau, q, n - 1, cd + 1, ct);
End else
Begin
q[n] := a[ct];
Xuly (a, dau, q, n - 1, cd, ct - 1);
End;
End;
//* mảng q thu được là kết quả cần tìm*//
Ở bài toán trên các dấu tọa độ x, y là đã xác định: Chia dãy 2N phần tử khác nhau thành hai gồm N phần tử làm hoành độ và tung độ, sau đó sắp tăng. Tiến hành thuật giải trên ta thu được hai dãy toạ độ thoả mãn điều kiện về dấu, đó cũng chính là dãy toạ độ cần tìm.
P3: (Bài tập tự giải) 2N point (POI)
Cho 2N diểm trên mặt phẳng gồm N diểm màu xanh và N điểm màu trắng sao cho không có ba điểm nào thẳng hàng. Hãy tìm N đoạn thẳng mà mỗi đoạn thẳng nối giữa một điểm màu xanh và một điểm màu trắng và các doạn nay không cắt nhau.
Input: 2Npoint.Int
- Dòng dầu ghi số N. (1 ≤ N ≤ 5000)
- N dòng tiếp theo mỗi dòng ghi toạ độ xi, yi của điểm màu xanh (|xi|, |yi| ≤ 10000).
- N dòng tiếp theo mỗi dòng ghi toạ độ xi, yi của điểm màu trắng (|xi|, |yi| ≤ 10000).
Output: 2Npoint.Out
- Gồm N dòng mỗi dòng ghi hai số a, b để chỉ điểm màu xanh thứ a, nối với điểm màu trắng thứ b.
4. Lời kết:
.Mọi tư duy toán học đều có thể vận dụng một cách linh động trong tin học. Tôi hy vọng sau bài viết này, ngoài việc học thêm được một hướng giải mới, các bạn sẽ tìm tòi thêm các ứng dụng toán học khác vào tin học.
1. Thuật toán quy nạp quy nạp(nhắc lại):
Giả sử có bài toán F cần chứng minh đúng với mọi n N. Ta chứng minh bài toán đúng bằng cách quy nạp, cần tiến hành các bước sau:
- n = 1: mệnh đề cần chứng minh đúng.
- Giả sử n = k: mệnh đề cần chứng minh đúng.
- n = k + 1: ta cần chứng nó cũng đúng. Vậy theo nguyên lý quy nạp bài toán đúng với mọi N.
Trong tin học, thuật toán nay cũng được áp dụng. Tuy thuật toán đơn giản nhưng nó lại được áp dụng một cách rất linh động và khéo léo trong các bài toán tin.
2. Phát biểu bài toán tổng quát giải bằng quy nạp:
Thông thường bài toán giải bằng quy nạp không phải là một bài toán tối ưu hoá. Nó chỉ đơn giản là bài toán cần chỉ ra cách biến đổi theo quy luật cho trước để thu được kết quả mong đợi. Và bài toán đó thường được phát biểu như sau:Cho N đối tượng và một số thao tác biến đổi. Yêu cầu sử dụng các thao tác biến đổi để thu được kết mong đợi.
Cách làm thông thường:
- Nếu n = 0; 1: ta luôn có cách biến đổi đúng.
- Nếu có n > 1 mà ta luôn chỉ ra một cách biến đổi sao cho giản bớt được số đối tượng mà điều kiện bài toán vẫn không thay đổi.
- Như vậy vì số đối tượng trong một bài toán tin học luôn là hữu hạn nên sau một số hữu hạn bước thì số lượng đối tương bằng 1 hoặc 0. Suy ra bài toán được giải quyết một cách hoàn toàn.
3. Các ví dụ cụ thể:
P1. Cho N vecto v1, v2, …, vn độ dài nhỏ hơn L cho trước. Cần đặt trước các vecto một dấu cộng hoặc trừ sao cho vecto tổng thu được có độ dài nhỏ hơn căn 2 nhân L.Input: Segment.In
- Dòng đầu ghi số N ( 1 < N ≤ 10000) và L (0 < L ≤ 15000.00)
- N dòng tiếp theo mỗi dòng ghi một cặp số xi, yi là toạ độ của vecto thứ i. (|xi|, |yi| ≤ 10000).
Ouput: Segment.out
- Dòng thứ nhất ghi YES nó có thể đặt các dấu cộng trừ thoả mãn yêu cầu bài toán, NO trong trường hợp ngược lại.
- Nếu là YES dòng thứ hai ghi N kí tự cộng hoặc trừ cần đặt trước các vecto sao cho tổng vecto nhỏ hơn sprt(2)*L.
Ví dụ:
Thuật giải:
- n = 1 bài toán đã đúng.
- n = 2 có trường hợp xảy ra với hai vecto:
+ góc giữa hai vecto nhỏ hơn 90 độ, lấy vecto 1 trừ cho vecto 2 lúc đó ta thu được 1 vecto co độ dài nhỏ hơn sqrt(2) * L.
+ góc giữa hai vecto lớn hơn hoặc bài một 90 độ, lấy vecto 1 cộng cho vecto 2 lúc đó ta thu được 1 vecto có độ dài nhỏ hơn sqrt(2) * L.
- n ≥ 3 suy ra luôn có 2 vecto mà góc giữa hai phương của vecto nhỏ hơn hoặc 60 bằng độ có hai trường xảy ra:
+ góc giữa hai vecto đó nhỏ hơn hoặc bằng 60 độ, trừ vecto 1 cho vecto 2 thay hai vecto bằng vecto mới nhận được.
+ góc giữa hai vecto đó lớn hơn hoặc bằng 120 độ, cộng vecto 1 cho vecto 2 thay hai vecto bằng vecto mới nhận được. Lưu ý sau này nếu trừ vecto mới nhận được phải trừ (đổi dấu) toàn vecto bộ hình thành lên nó, vecto mới nhận được có độ dài nhỏ hơn L, số đoạn thẳng giảm 1.
Như vậy đây là bài toán luôn có lời giải, độ phức tạp O(N^2) nếu xử lý khéo có thể giản xuống O(n*log(n)). Chương trình mô tả thuật giải:
Procedure Xuly (n: integer //* số đối tượng *//);
Begin
If n <= 1 then exit else
If n = 2 then
Begin
If goc (v1, v2) <= 90 độ Then đổi dấu (v2);
//* đổi dấu tức là đổi dấu toàn bộ vecto thành phần *//
Thay hai vecto bằng 1 vecto (v1 + v2);
//* vecto mới gồm các thành phần của v1 và v2 *//
//* lúc này v2 nếu cần thiết đã đổi dấu rồi *//
Exit;
End else
Begin
lấy 3 vecto bất kỳ;
chọn ra được 2 vecto v1, v2 sao cho
góc nhỏ giữa phương 2 vec to nhỏ 60;
if goc (v1, v2) <= 60 then đổi dấu (v2);
Thay hai vecto này bằng (v1 + v2);
End;
End;
P2: Utopia (IOI 2002)
Đất nước Utopia tươi đẹp bị chiến tranh tàn phá. Khi chiến tranh tạm ngừng, đất nước bị chia cắt thành bốn miền bởi một đường kinh tuyến (đường theo hướng Bắc-Nam) và một đường vĩ tuyến (đường theo hướng Đông-Tây). Giao điểm của hai đường này xem như điểm (0, 0). Tất cả các miền này đều muốn mang tên Utopia, theo thời gian các miền này được gọi là Utopia 1 (phía Đông Bắc), Utopia 2 (phía Tây Bắc), Utopia 3 (phía Tây Nam), Utopia 4 (phía Đông Nam). Một điểm trong bất kỳ miền nào cũng được xác định bởi khoảng cách theo hướng Đông và khoảng cách theo hướng Bắc của nó so với điểm (0, 0). Bộ hai khoảng cách này được gọi là toạ độ của điểm. Các thành phần của toạ độ có thể là số âm; do đó một điểm miền Utopia 2 có toạ độ (âm, dương), một điểm miền Utopia 3 có toạ độ (âm, âm), một điểm miền Utopia 4 có toạ độ (dương, âm), một điểm miền Utopia 1 có toạ độ (dương, dương) (Giống như các góc phần tư trong hệ toạ độ đề các).
Một vấn đề là các công dân không được phép đi qua biên giới giữa các miền. May thay, một số thí sinh tham dự IOI của Utopia sáng chế ra một loại máy an toàn để vận chuyển từ xa. Máy này cần các số mã, mỗi số mã chỉ có thể được dùng một lần. Bây giờ, nhóm thí sinh tham dự và bạn phải hướng dẫn máy vận chuyển từ xa xuất phát từ vị trí ban đầu (0, 0) đến các miền của Utopia theo một trình tự cho trước. Khi bạn nhận được một dãy N số hiệu miền mà theo trình tự đó máy vận chuyển từ xa phải hạ cánh, với mỗi miền, bạn không cần phải quan tâm đến việc hạ cánh tại điểm nào của miền đó miễn là điểm đó thuộc miền yêu cầu. Người ta có thể yêu cầu máy hạ cánh liên tiếp hai lần hay nhiều lần hơn ở cùng một miền. Sau khi rời khỏi điểm ban đầu (0, 0), bạn không được hạ cánh trên các đường biên giới.
Bạn sẽ nhận được input là một dãy 2N số mã và phải viết chúng thành một dãy gồm N cặp mã, sau khi đặt một dấu + hoặc một dấu - thích hợp trước mỗi số. Nếu hiện tại bạn ở điểm (x,y) và sử dụng cặp mã số (+u,-v), bạn sẽ được chuyển tới điểm (x+u,y-v). Bạn có 2N số và bạn có thể sử dụng các số này theo thứ tự bạn muốn, mỗi số kèm theo một dấu + hoặc một dấu -.
Giả sử bạn có các số mã 7, 5, 6, 1, 3, 2, 4, 8 và phải hướng dẫn máy vận chuyển từ xa lần lượt đến các miền thuộc dãy miền 4, 1, 2, 1. Dãy các cặp mã (+7, -1), (-5, +2), (-4, +3), (+8, +6) đáp ứng yêu cầu này vì nó đưa bạn từ (0,0) lần lượt đến các vị trí (7, -1), (2, 1), (-2, 4) và (6, 10). Những điểm này nằm tương ứng ở Utopia 4, Utopia 1, Utopia 2 và Utopia 1.
Nhiệm vụ:
Cho 2N số mã khác nhau và một dãy N số hiệu miền là dãy các miền mà máy vận chuyển từ xa phải lần lượt hạ cánh. Hãy xây dựng một dãy các cặp mã từ các số đã cho để hướng dẫn máy vận chuyển từ xa lần lượt đi đến các miền thuộc dãy đã cho.
Input
Chương trình của bạn phải đọc từ input chuẩn. Dòng đầu gồm một số nguyên dương N (1 ≤ N ≤ 10000). Dòng thứ hai gồm 2N số mã nguyên khác nhau, tất cả đều là các số nguyên dương không lớn hơn 100000. Dòng cuối cùng gồm một dãy N số hiệu miền, mỗi một trong các số đó là 1, 2, 3 hoặc 4. Hai số liên tiếp trên một dòng cách nhau đúng một dấu trống.
Output
Chương trình của bạn phải viết ra output chuẩn. Ouput gồm N dòng, mỗi dòng chứa một cặp số mã mà trước mỗi số có dấu + hoặc dấu -. Đó là các cặp mã sẽ hướng dẫn cho máy vận chuyển đến dãy miền đã cho. Chú ý rằng không được có dấu trống sau dấu + hoặc dấu - nhưng phải có một dấu trống sau số mã thứ nhất.Nếu có nhiều lời giải, chương trình của bạn có thể đưa ra một lời giải bất kỳ trong số đó. Nếu không có lời giải, chương trình của bạn phải đưa ra một số 0 duy nhất.
Ví dụ:
Thuật giải:
Đây cũng là bài toàn luôn giải được để giải bài toán trên ta cần giải bài toán nhỏ sau:Cho một gồm N số nguyên dương khác nhau a1 < a2 < … < an. Cần sắp xếp lại và thêm các dấu vào các số ai sao cho tổng các số từ 1 đến vị trí i là dương hoặc âm biết trước:
Ví dụ:
Dãy 3 số: 1 2 3
Dấu cần xây dựng: +-+
Một cách thêm dấu và sắp xếp: +1 -2 + 3
Bổ đề:
Nếu dãy có dãy {ai} dương tăng và một chuỗi dấu cần biến đổi thì ta luôn có cách thêm dấu và thay đổi vị trí sao cho tổng cách số từ 1 đến i mang đấu của chuỗi dấu biết trước.
Chứng minh:
- số an mang dấu cuối cùng của chuỗi trên, các số còn lại đan dấu. (điều kiện về dấu để luôn xây được dãy) Ví dụ: {ai} = {1, 5, 10}; S = ‘++-‘; suy ra dãy {ai} được đánh dấu như sau: -1, +5, -10;
- nhận xét rằng: tổng của n số trên cuối cùng sẽ mang dấu của S[n]
- với n = 1 ta nhận được dãy cần tìm.
- Giả sử n =k ta xây dựng được chuỗi như trên.
- n = k + 1 chia hai trường hợp:
+ s[n-1] cùng dấu s[n]: đặt a[1] vào vị trí cuối cùng và lấy phần tử a[1] và s[n] ra khỏi dãy, nhưng còn là (n - 1) số và (n-1) dấu và dấu cuối cùng với số cuối, dãy đan dấu (vẫn thoả mãn điều kiện về dấu)
+ s[n - 1] và s[n] khác dấu: đặt a[n] vào vị trí cuối cùng và lấy phần tử a[n] và s[n] ra khỏi dãy, nhưng còn là (n - 1) số và (n-1) dấu và dấu cuối cùng với số cuối, dãy đan dấu. Theo giả thiết quy nạp thì dãy còn lại luôn xây dựng được.
Chương trình:
Procedure Xuly (Var a, dau, q: array [1…10000] of integer; n, cd, ct : integer);
//*ta đang xử lý dãy các số từ a[cd] đến a[ct] có dấu từ dấu[1] đến dấu[n] *//
Begin
If n <= 1 then exit;
If dau[n - 1] = dau[n] then
Begin
q[n] := a[cd];
Xuly (a, dau, q, n - 1, cd + 1, ct);
End else
Begin
q[n] := a[ct];
Xuly (a, dau, q, n - 1, cd, ct - 1);
End;
End;
//* mảng q thu được là kết quả cần tìm*//
Ở bài toán trên các dấu tọa độ x, y là đã xác định: Chia dãy 2N phần tử khác nhau thành hai gồm N phần tử làm hoành độ và tung độ, sau đó sắp tăng. Tiến hành thuật giải trên ta thu được hai dãy toạ độ thoả mãn điều kiện về dấu, đó cũng chính là dãy toạ độ cần tìm.
P3: (Bài tập tự giải) 2N point (POI)
Cho 2N diểm trên mặt phẳng gồm N diểm màu xanh và N điểm màu trắng sao cho không có ba điểm nào thẳng hàng. Hãy tìm N đoạn thẳng mà mỗi đoạn thẳng nối giữa một điểm màu xanh và một điểm màu trắng và các doạn nay không cắt nhau.
Input: 2Npoint.Int
- Dòng dầu ghi số N. (1 ≤ N ≤ 5000)
- N dòng tiếp theo mỗi dòng ghi toạ độ xi, yi của điểm màu xanh (|xi|, |yi| ≤ 10000).
- N dòng tiếp theo mỗi dòng ghi toạ độ xi, yi của điểm màu trắng (|xi|, |yi| ≤ 10000).
Output: 2Npoint.Out
- Gồm N dòng mỗi dòng ghi hai số a, b để chỉ điểm màu xanh thứ a, nối với điểm màu trắng thứ b.
4. Lời kết:
.Mọi tư duy toán học đều có thể vận dụng một cách linh động trong tin học. Tôi hy vọng sau bài viết này, ngoài việc học thêm được một hướng giải mới, các bạn sẽ tìm tòi thêm các ứng dụng toán học khác vào tin học.
Đăng ký:
Bài đăng (Atom)