CHUYÊN ĐỀ TIN HỌC LỚP 10 NĂM 2021 - 2022: chuyên đề bài toán và thuật toán 10

[Yopovn]

CHUYÊN ĐỀ TIN HỌC LỚP 10 NĂM 2021 - 2022: chuyên đề bài toán và thuật toán 10

Chuyên đề

THUẬT TOÁN SỐ HỌC

I. Gớ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 là thời gian nhiều nhất để thực hiện phép nhân hai số có 2n bit, ta có

F = 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 = 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