The art of calculating by means of nine figures and zero. - Nghệ thuật tính toán bởi chín chữ số và số không.

Trở lại quá khứ xa hơn trong từ điển toán học Vollstandiges Mathematiesches Lexikon, Leipzig, 1747 có giải thích rằng algorithm là "tổ hợp của bốn phép toán số học bao gồm cộng, trừ, nhân, chia".

Các nhà nghiên cứu lịch sử toán học đã tìm ra chính xác nguồn gốc của từ "algorism". Algorism là tên của một nhà bác học nổi tiếng người Arập là Abu Jafar Mohammed ibn Musâ al Khowârizmi. Phiên âm của từ al Khowârizmi chính là Algorism. Ông là người đã viết hai quyển sách nổi tiếng là "Sơ lược về các phép tính trên al jafar và al mukabal" và "Về hệ đếm ấn độ" vào khoảng năm 850. Đây là những quyển sách giáo khoa nổi tiếng về toán, đặt nền móng cho sự phát triển độc lập ngành đại số. Nguồn gốc các từ Algorithm (thuật toán) và Algebra (đại số) đều xuất phát từ những tác phẩm này.

Ngày nay, algorithm được hiểu như thế nào? Ta hãy xem lời giải thích trong Oxford Advanced Learner's Dictionary:

Set of rules and procedures that must be followed in solving a problem. - Tập hợp các qui tắc và thủ tục theo trật tự nhất định để giải quyết một vấn đề.

Như vậy khái niệm và ý nghĩa của từ "Algorithm" đã được nêu rõ. Chúng ta hãy cùng nhau tìm hiểu sâu hơn những đặc trưng, tính chất cơ bản của khái niệm này. Trước khi đi tiếp cuộc hành trình, chúng ta hãy cùng nhau kiểm tra lại kiến thức và hiểu biết của chính mình.

Bài tập 1: Các bạn học sinh khối Tiểu học khi học đến các phép toán (cộng, trừ, nhân, chia) thường hay gặp các bài toán yêu cầu tính nhanh. Theo bạn tính "nhanh" ở đây phải hiểu theo nghĩa gì? Tính chính xác hơn, tính nhanh hơn theo thời gian hay tối ưu hơn theo số các bước thực hiện. Em hãy cho một vài ví dụ về tính bình thường và tính nhanh.

2. Đặc trưng của Algorithm

Algorithm - Thuật giải. ý nghĩa của từ này giờ đây ai cũng hiểu. Trong tiếng Anh có một loạt các từ có ý nghĩa tương tự như vậy: instruction, receipt, process, method, procedure, program... Tuy nhiên từ Algorithm vẫn mang một số đặc trưng nhất định tiêu biểu cho một thuật toán phải có. Các đặc trưng cơ bản của một thuật toán bao gồm:

A. Tính hữu hạn

Một thuật toán bao giờ cũng phải kết thúc sau hữu hạn bước mặc dù số bước này có thể rất lớn.

B. Tính xác định

Mọi bước của một thuật giải bao giờ cũng được xác định rõ ràng, chính xác và do đó luôn thực hiện được.

C. Giá trị vào

Mỗi thuật toán đều có một số giá trị nhập vào, chúng được gọi là Input values.

D. Giá trị ra

Mỗi thuật toán có một số giá trị đưa ra, chúng được gọi là Output values.

E. Tính hiệu quả

Tính hiệu quả được thể hiện bởi khả năng thực thi các bước của thuật toán để đạt được kết quả mong muốn và tổng thời gian thực hiện thuật toán phải đủ nhỏ. Chú ý: Trên thực tế để đánh giá tính hiệu quả của các thuật toán, người ta thường qui về các đơn vị tính sơ cấp. Tính hiệu quả của một thuật giải được đo bởi số lượng các đơn vị tính sơ cấp mà thuật toán này yêu cần thực hiện. Ví dụ cho các phép tính sơ cấp đó là phép +, -, *, : các số tự nhiên nhỏ hơn 10.

Ví dụ để tính 5 + 7 = 12, các em cần 1 đơn vị tính. Nhưng nếu tính 15 + 7 = 22, các em phải dùng 2 đơn vị tính: 5 + 7 = 12 (ghi 2 cho vay 1) và 1 + 1 = 2. Bài tập 2: Các phép tính sau sử dụng hết bao nhiêu đơn vị tính:

45 + 12

202 + 89

1102 + 6723

3. Ví dụ 1: Thuật toán Euclid

Thuật toán Euclid được phát biểu vào những năm đầu thế kỷ này và được coi là mẫu mực về thuật giải. Ta sẽ xét một vài thuật toán này:

A. Thuật toán tìm ước số chung lớn nhất của 2 số cho trước m, n.

1. Chia m cho n được số dư là r (0 <= r < n)

2. Nếu r=0 thì n là số phải tìm, kết thúc.

3. Đặt m=n, n=r và quay lại bước 1.

Ví dụ với cặp số m=18, n=12 các bước của thuật toán trên như sau:.

1. m=18, n=12, r = 6

2. m=12, n = 6

3. m=12, n=6, r=0

4. Kết thúc. Kết quả 6.

B. Thuật toán tìm ước số chung lớn nhất của d của 2 số tự nhiên n, m và tìm cặp số nguyên a, b sao cho d=am+bn (thuật toán Euclid tổng quát).

1. Đặt á=b=1, a=b'=0, c=m, d=n.

2. Chia c cho d được thương là q và số dư là r.

c= qd + r (0 <= r< d).

3. Nếu r=0, thuật toán kết thúc, đáp số là d=am+bn.

4. Đặt c=d, d=r

t=á, á=a

a=t-qa

t=b', b'=b

b=t-qb

và quay lại bước 2.

Bài tập 3: Hãy thực hiện các bước của thuật toán trên với m=30, n=27.

4. Ví dụ 2: Thuật toán nhân các số nguyên ,

Trong mỗi chúng ta có lẽ không một ai lại không nhiều lần trong đời thực hiện các phép nhân tay số nguyên. Những bài học vỡ lòng về phép nhân tay các số nguyên là những ví dụ rất điển hình về thuật toán.

Chúng ta hãy bắt đầu bằng các phép nhân "đơn giản": nhân một số nguyên với một số có một chữ số. Ví dụ 254 x 3. Ta có các bước thực hiện sau:

- Lấy 4 x 3 = 12, viêt 2 "nhớ" 1

- Lấy 5 x 3 = 15 viết 5 + 1 = 6 "nhớ" 1

- Lấy 2 x 3 = 6 viết 6 + 1 = 7

- Kết quả phép nhân: 762.

Có thể mô tả "thuật toán" nhân đơn giản trên như sau:

1. Đưa hạng tử đầu tiên vào mảng a[i] với i=1..n+1. Đặt thêm a[n+1]=0. Biến "nhớ" đặt là mem=0. Mảng kết quả là kq[i]. Hạng tử thứ hai là biến b.

2. Biến chạy i=1.

3. Nếu i>n thì đặt kq[i]=mem và dừng chương trình.

4. Lấy tích a[i] x b. Gọi phần đơn vị của giá trị này là DV và phần chục là CH. Hay nói cách khác CH = a[i] x b div 10, DV = a[i] x b mod 10. Giá trị CH được bổ sung vào biến mem.

5. Lấy tổng DV + mem. Phần đơn vị của số này đưa vào kq[i], phần chục gán cho biến mem. Hay nói cách khác ta thực hiện các phép toán sau: kq[i] = (mem + DV) mod 10, mem = (mem + DV) div 10.

6. Tăng i = i+1. Quay lại bước 3.

Bài tập 4: Nếu định nghĩa một đơn vị tính là một trong các phép toán +, -, mod, div, x hai số < 10 thì nếu thực hiện phép tính nhân 254 x 3 hết bao nhiêu đơn vị tính?

Số các đơn vị tính được nêu trong bài tập 4 chính là một trong các thước đo độ hiệu quả của thuật toán. Chúng ta sẽ còn quay lại vấn đề này nhiều lần.

Ta sẽ xét trường hợp tổng quát: nhân hai số tự nhiên bất kỳ.

Ví dụ cần tính 254 x 123:

"Algorithm" nhân tay trên có thể mô tả một cách tường minh như sau:

1. Viết hai số cần tính phép nhân theo hàng dọc, căn thẳng hàng bên phải.

2. Lần lượt lấy nhân tử thứ nhất (số ở hàng trên), nhân tay với chữ số thứ k (k=1, 2,...) tính từ bên phải sang, của hạng tử thứ hai (số ở hàng dưới), lấy kết quả thu được nhân với 10k-1.

3. Lấy tổng tất cả các kết quả tính toán được ở bước 2.

Chú ý: Trong thuật toán trên, cách nhân một số nguyên với một số có một chữ số

Cách nhân hay "Thuật toán nhân" trên chỉ là một trong nhiều cách nhân mà con người sử dụng. Ví dụ người Anh lại sử dụng cách nhân hai số nguyên như sau:

Cách nhân của người Anh có hơi "ngược" so với chúng ta nhưng kết quả tất nhiên vẫn thu được tích đúng của hai số.

Bài tập 5: Các bạn hãy miêu tả thuật toán nhân hai số nguyên của người Anh.

Người Nga cổ lại có một phương pháp nhân hai số nguyên rất độc đáo như sau:

Hai số hạng cần lấy tích được xếp vào hai cột. Lần lượt thực hiện việc chia đôi số trên cột 1 (chỉ lấy phần nguyên) và nhân đôi các trên cột 2 và xếp chúng vào một hàng phía dưới. Nếu số hạng của cột 1 là lẻ thì số tương ứng của cột 2 được lấy ra và xếp riêng trên một cột (trích tổng). Công việc trên dừng lại khi cột bên trái thu được số 1. Kết quả của phép nhân chính là tổng của các số trong cột Trích Tổng.

Bài tập 6: Em hãy kiểm nghiệm tích đúng đắn của thuật toán trên và mô phỏng tường minh các bước của chúng.

Trở lại phép nhân hai số nguyên, chúng ta hãy cùng nhau tìm hiểu một thuật toán nữa (mà hiện tại trong chúng ta ít người biết đến) có tên gọi thuật giải divide-and-conquer.

Trong thuật toán này các hạng tử nhân phải có số chữ số là lũy thừa của 2, ví dụ là 1, 2, 4, 8. Với ví dụ trên, 254 x 123 ta có thể viết cho phù hợp với yêu cầu này: 0254 x 0123.

Các bước thực hiện thuật toán divide-and-conquer như sau:

Ta tách các hạng tử với 4 chữ số thành những phần nhỏ hơn gồm 2 chữ số và lấy lần lượt tích của chúng: 02 x 01, 02 x 23, 54 x 01, 54 x 23. Biến nhớ Shift ghi lại tổng số các vị trí của các thành phần này. Khi lấy kết quả ta thêm vào bên phải của các tích số các số 0 tương ứng bằng giá trị Shift.

Chú ý: khi thực hiện các tích của các thành phần, ví dụ 23 x 46, ta lại có thể áp dụng thuật toán divide-and-conquer cho các cặp số này vì theo giả thiết các số này đều có số chữ số là lũy thừa của 2. Chẳng hạn với 23 x 46 ta lại phân tích thành các tích 2x4, 2x6, 3x4, 3x6. (Kỹ thuật này gọi là đệ qui, sẽ được trình bày kỹ hơn trong phần sau của bài viết này).

Bài tập 7: Bạn hãy mô tả thuật toán divide-and-conquer dưới dạng tường minh.

Bài tập 8: Theo em, trong 4 cách nhân đã mô tả ở trên của Việt nam, người Anh, người Nga và phương pháp divide-and-conquer, thuật toán nào có tốc độ nhanh hơn cả. Em hãy phân tích và chứng minh lập luận của mình.

School@net