Author: Gã coder si tình
Máy tính vốn được sinh ra để tính toán các phép tính phức tạp với độ chính xác có thể nói là tuyệt đối mà con người có siêu việt đến cỡ nào cũng không làm được. Thế nhưng, ta vẫn có thể sử dụng những cỗ máy nổi tiếng vì sự chính xác ấy để tạo ra số ngẫu nhiên. Chúng có thể sinh hàng tỉ số (thậm chí hơn) chỉ trong vài giây với khả năng đoán trước cực thấp và sự phân bố của mẫu số cũng rất đều.
Vậy làm thế nào mà máy tính có thể sinh ra số ngẫu nhiên? Và việc sinh ngẫu nhiên có ứng dụng gì trong Tin học nói chung và lập trình thi đấu nói riêng?
Chúng ta sẽ cùng tìm hiểu trong bài viết này nhé.
In common usage, randomness is the apparent or actual lack of pattern or predictability in information.
– Wikipedia
Tạm dịch theo định nghĩa của Wikipedia, sự ngẫu nhiên là một sự kiện thiếu đi quy luật hoặc khả năng dự đoán trước được.
Thật ra theo mình thì không có gì là hoàn toàn ngẫu nhiên, không có quy luật. Ví dụ như việc tung xúc sắc, theo lý thuyết, nếu đó là viên xúc sắc bình thường thì cả mặt của nó đều có xác suất là . Tuy nhiên, giá trị nhận được từ việc tung xúc sắc thực chất không phải ngẫu nhiên mà nó phụ thuộc vào các yếu tố: trạng thái của nó trước khi được tung, trọng lượng của xúc sắc, vận tốc đầu, bề mặt mà nó rơi xuống,… rất nhiều yếu tố khác. Có thể thấy, nó cũng có quy luật, nhưng có rất nhiều yếu tố khác nhau quyết định đến kết quả cuối cùng. Nếu viết ra thành công thức thì cực kỳ phức tạp, do đó, người ta coi như xúc sắc sẽ cho ra giá trị "ngẫu nhiên".
Tương tự, với máy tính, những "yếu tố" đó sẽ là tham số truyền vào hàm sinh ngẫu nhiên hoặc những biến số khác. Máy tính tuy là một thứ được sinh ra để đảm bảo độ chính xác nhưng nó vẫn có thể sinh ra "số ngẫu nhiên", nếu ta có thể tạo ra một thuật toán biến đổi các tham số đưa vào một cách đủ phức tạp để cho ra đáp án có thể coi là ngẫu nhiên.
Pseudo-random Number Generator (PRNG) hoạt động như ý tưởng được trình bày ở trên, máy tính sẽ biến đổi các tham số đưa vào (gọi là seed) một cách đủ phức tạp, để khả năng dự đoán trước được gần như là con số . Đây là loại randomizer rất phổ biến trong Tin học và cũng sẽ là chủ đề chính của bài viết này. Một số ví dụ của PRNG là hàm rand()
, mt19937
trong C++
, thư viện random
trong Python
, hay randomizer của trang CalculatorSoup.
True Random Number Generator (TRNG) sinh ra số ngẫu nhiên dựa trên một sự kiện không liên quan gì đến máy tính, ví dụ như tiếng ồn trong khí quyển, các thông số liên quan đến chất phóng xạ,… Ví dụ của TRNG là trang RANDOM.ORG.
Cách sinh số ngẫu nhiên đơn giản nhất trong ngôn ngữ lập trình C++
đó là sử dụng hàm rand()
[1]. Hàm này sẽ sinh số nguyên ngẫu nhiên từ đến RAND_MAX
, với RAND_MAX
là một giá trị tùy thuộc vào máy, tối thiểu là .
Ưu điểm của hàm rand()
là cú pháp dễ nhớ và dễ sử dụng. Tuy nhiên, khuyết điểm của nó là rất lớn, mà neal (một Codeforces International Grandmaster) đã viết hẳn một bài blog để nói về điều này [2]. Mình sẽ tóm tắt 2 vấn đề chính mà neal đã đề cập:
RAND_MAX
của hàm này, tùy thuộc vào máy, trên Codeforces thì là đúng . Nếu ta cần sinh một dãy số với các giá trị trong đoạn thì các giá trị được hàm sinh ra sẽ bị lệch giá trị kỳ vọng rất nhiều.rand()
được cài đặt bằng một thuật toán khá đơn giản, chỉ dựa trên một hàm tuyến tính [3] nên khả năng dự đoán trước khá cao.Randomizer thứ 2 có sẵn trong STL
của C++
đó là mt19937
. Đây là cài đặt của thuật toán Mersenne Twister [4] – thuật toán sinh ngẫu nhiên mạnh nhất trong Tin học tính đến thời điểm hiện tại, được phát triển dựa trên số nguyên tố Mersenne . Hai người phát minh ra Mersenne Twister tên là Makoto Matsumoto và Takuji Nishimura.
Để sử dụng thuật toán này, ta khai báo một hàm rng()
như sau:
Các bạn có thể chọn seed tùy ý, trong bài viết này mình sẽ sử dụng thời gian. Ở đây, có thể gọi hàm time(0)
, nhưng với seed như thế thì khi tham gia Codeforces sẽ dễ bị hack. Do đó, mình sẽ dùng đến thư viện chrono
.
Thư viện chrono
cung cấp loại đồng hồ chính đó là system_clock
, steady_clock
và high_resolution_clock
với độ chia nhỏ nhất khác nhau và đều có điểm bắt đầu (epoch) là giờ, ngày (UTC). Mình sẽ sử dụng thời gian từ epoch đến khoảnh khắc mà hàm được khai báo, tính bằng high_resolution_clock
làm seed như sau:
Sau khi khai báo dòng này thì hàm rng()
sẽ trả về một số nguyên ngẫu nhiên trong khoảng . Nếu muốn tăng giới hạn lên -bit thì ta sử dụng mt19937_64
.
Để sinh 1 số ngẫu nhiên trong khoảng , ta dùng uniform_int_distribution
. Để tiện thì mình sẽ khai báo thêm một hàm khác như sau:
Để kiểm tra chất lượng của mt19937
, mình đã sinh thử một mẫu dữ liệu số trong khoảng và tính toán vài con số trong thống kê để thấy được distribution của mẫu dữ liệu này. Kết quả của lần chạy đầu tiên như sau:
Có thể thấy thuật toán này sinh ra số với distribution khá đều. Bên cạnh đó, mt19937
có thể sinh số ngẫu nhiên nhanh hơn hàm rand()
.
Ngôn ngữ lập trình Python cũng có randomizer tương tự với thư viện random
và hàm randrange
sử dụng thuật toán Mersenne Twister. Cách truyền tham số vào hàm randrange
khá giống hàm range
, cụ thể như sau:
randrange(R)
trả về một số ngẫu nhiên trong đoạn .randrange(L, R)
trả về một số ngẫu nhiên trong đoạn .randrange(L, R, x)
trả về một số ngẫu nhiên trong đoạn với bậc là .Ví dụ đoạn code sau in ra số ngẫu nhiên được chọn từ tập .
Khi đã có thể sinh số ngẫu nhiên với xác suất đều, bây giờ ta sẽ tính đến bài toán sinh số ngẫu nhiên với xác suất không đều. Đây cũng là bài tập xuất hiện trên Leetcode [5] có tên Random pick with weights.
Việc sinh số ngẫu nhiên với xác suất không đều không có quá nhiều ứng dụng trong lập trình thi đấu, tuy nhiên ta có thể cần đến nó trong một số bài toán heuristic, hoặc các lĩnh vực Tin học khác như Machine Learning,…
Trong bài viết này, mình sẽ trình bày nhanh thuật toán sử dụng binary search, cách giải này cũng đã được đề cập đến trong bài viết của page Code cùng RR [6].
Viết hàm sinh ngẫu nhiên với distribution không đều, cụ thể giá trị (với ) sẽ có xác suất xuất hiện là .
Constraints:
Ví dụ cho mảng , , ta cần viết một hàm sinh ngẫu nhiên với kết quả là:
Ý tưởng của bài toán này đó là ta sẽ tạo ra "slots" cho các giá trị, rồi cho giá trị thứ chiếm slots. Với ví dụ ở trên thì giá trị sẽ chiếm các slots từ , giá trị chiếm các slots từ , giá trị chiếm các slots từ ,…
Sau đó, ta sẽ sinh ra một số ngẫu nhiên trong khoảng rồi tính xem slot tương ứng là slot của giá trị nào. Để làm điều đó ta binary search trên mảng prefix sum của .
Như vậy, độ phức tạp thời gian và bộ nhớ của phần tiền xử lý là , một lần gọi hàm tốn thời gian xử lý là .
Mình sẽ cài đặt trong class Solution
, giống với yêu cầu trên Leetcode.
XOR Hash là một trong những hàm Hash được sử dụng phổ biến trong lập trình thi đấu. Các bạn có thể đọc thêm về hàm này cũng như một số hàm Hash khác trong bài viết của page Page này được lập ra để Dế Mèn được gáy [7].
XOR Hash yêu cầu một hàm sinh ngẫu nhiên đủ chất lượng để có thể giảm thiểu sai số và cũng như khả năng bị hack khi tham gia các contests có open hack như trên Codeforces hoặc các dạng tương tự.
Ý tưởng chính của XOR Hash đó là để so sánh hai dãy và gồm các phần tử phân biệt và có cùng độ dài mà không quan tâm thứ tự, ta sẽ tính tổng XOR các giá trị hash của các phần tử trong dãy. Tức là, ta sẽ kiểm tra:
Với là bitwise XOR và là một dãy số (-bit) được sinh ngẫu nhiên.
Dễ dàng thấy được, nếu hai dãy và giống nhau (không cần đúng thứ tự) thì biểu thức trên sẽ luôn đúng. Ngược lại, biểu thức trên có thể vẫn đúng (trường hợp xảy ra sai số) với tỉ lệ , nếu đủ lớn, ta có thể coi như xác suất xảy ra sai số là .
Ở phần này, mình sẽ sử dụng bài tập minh họa là bài Perfect [8] (Bedao Grand Contest 10).
Cho hoán vị độ dài và truy vấn có dạng , ở mỗi truy vấn, hãy cho biết khi sắp xếp dãy con theo thứ tự tăng dần thì dãy con này có tạo thành dãy số nguyên liên tiếp hay không?
Constraints:
Nhiệm vụ của chúng ta là so sánh dãy với dãy với và lần lượt là phần tử bé nhất và độ dài của dãy con.
Do là hoán vị nên ta có thể áp dụng XOR Hash, ta sẽ tính:
rồi đem so sánh với:
Giá trị có thể được tính bằng Sparse table, và các giá trị Hash cũng có thể tính trong với prefix XOR. Ngoài ra, để giảm thiểu khả năng sai số, ta sẽ tạo ra dãy là các số ngẫu nhiên -bit, khi đó, xác suất xảy ra sai số là cực thấp (một số có số ngay sau dấu chấm thập phân).
Monte Carlo là tên gọi chung của những thuật toán hoạt động dựa trên việc sinh nghẫu nhiên, có khả năng đưa ra kết quả sai với tỉ lệ sai số khá thấp (lưu ý Hash không phải là thuật toán Monte Carlo).
Cái tên Monte Carlo cũng chính là tên của một casino nổi tiếng ở Monaco, xuất phát từ việc rủi ro của những thuật toán này khá giống với rủi ro của đặt cược trong cờ bạc. Tuy nhiên, trong Tin học, ta có cách để giảm khả năng sai số của chúng xuống nhiều lần để đảm bảo độ chính xác của chương trình.
Trong bài viết này, chúng ta sẽ cùng tìm hiểu thuật toán Monte Carlo có tính ứng dụng khá cao trong lập trình thi đấu.
Freivalds' algorithm là thuật toán kiểm tra phép nhân ma trận có bằng một ma trận cho trước hay không một cách hiệu quả mà không cần phải tính trực tiếp .
Khi nhân ma trận có kích thước cho ma trận có kích thước , ta sẽ được ma trận có kích thước sao cho:
Để tính toàn bộ ma trận ta cần phép toán.
Do công thức trên hơi khó tưởng tượng nên các bạn có thể xem ảnh động dưới đây để dễ hình dung cách hoạt động của phép nhân ma trận:
Một tính chất quan trọng của phép nhân ma trận là tính chất kết hợp, tức là:
Tùy vào cách kết hợp mà phép nhân ma trận sẽ tốn độ phức tạp thời gian khác nhau.
Cho ma trận , , và có cùng kích thước . Nhiệm vụ là kiểm tra xem có bằng hay không. Dĩ nhiên, ta sẽ không tính trực tiếp trong .
Thuật toán này sẽ sinh ngẫu nhiên một ma trận có kích thước . Mỗi phần tử của có giá trị là hoặc (để tránh tràn số).
Bây giờ ta kiểm tra:
Để kiểm tra , ta chỉ cần thực hiện phép nhân ma trận, cả đều có độ phức tạp thời gian . Hai ma trận nhận được sau khi tính toán có kích thước và chỉ tốn thời gian để so sánh.
Sẽ có trường hợp xảy ra:
Nếu chỉ dừng lại ở đây với xác suất sai số lên đến thì thuật toán này chẳng còn tính ứng dụng gì cả. Do đó ta chạy thuật toán lần, mỗi lần sinh một ma trận mới.
Ta kết luận nếu cả lần chạy đều cho ra đúng. Ngược lại, nếu có ít nhất lần chạy cho ra sai thì ta kết luận .
Lúc này, vẫn sẽ có trường hợp xảy ra sai số, là khi nhưng cả lần chạy đều cho ra đúng. Dễ thấy, xác suất để trường hợp này xảy ra là . Nếu ta chọn đủ lớn thì con số này sẽ trở nên rất nhỏ. Ví dụ, với , xác suất sai số giảm xuống còn:
Như vậy, ta đã có một thuật toán chạy trong thay vì mà còn đạt độ chính xác rất cao.
Mình sẽ áp dụng thuật toán Freivalds vào bài Ma trận (vòng sơ khảo bảng C1, Hội thi Tin học trẻ toàn quốc năm 2022) [10]. Sau đây là phần cài đặt:
Miller–Rabin primality test (primality test tạm dịch là kiểm tra tính nguyên tố) là thuật toán kiểm tra số nguyên tố được phát triển bởi Garry L. Miller và hoàn thiện bởi Michael O. Rabin vào năm 1980. Miller đã phát triển ý tưởng cho thuật toán này dựa trên định lý Fermat nhỏ và những tính chất toán học khác.
Thông thường, để kiểm tra xem một số nguyên dương có phải số nguyên tố hay không, ta cần thời gian , hoặc sau khi chạy sàng nguyên tố trong . Với thuật toán của Miller–Rabin thì ta chỉ tốn độ phức tạp mà không cần tiền xử lý (mình sẽ giải thích biến sau).
Tuy nhiên, là một thuật toán Monte Carlo, Miller–Rabin primality test có thể xảy ra sai số. Song, như đã nói, ta có thể giảm xác suất đó xuống mức cực thấp.
Trước khi nói đến ý tưởng của thuật Miller–Rabin thì mình sẽ nói một chút về định lý Fermat nhỏ [11] và một thuật toán kiểm tra số nguyên tố được phát triển trực tiếp trên định lý này [12].
Theo định lý Fermat nhỏ, ta có:
Với là một số nguyên tố và là một số nguyên không phải bội của .
Dựa vào định lý này, nếu ta chọn một cơ số không phải bội của mà khi thế vào lại không thỏa, tức là , thì ta có thể kết luận ngay là một hợp số (không phải số nguyên tố). Khi đó, cơ số đã được chọn để kiểm tra gọi là Fermat witness (tạm dịch là minh chứng Fermat cho việc là hợp số).
Tuy nhiên, với một số hợp số , tồn tại không phải bội của mà vẫn thỏa. Khi đó ta gọi là Fermat liar (tạm dịch lời nói dối của Fermat cho việc là hợp số?). Đây là lúc mà Fermat primality test xảy ra sai số.
Để khắc phục điều này, ta sẽ thử với nhiều cơ số khác nhau bằng cách chọn ngẫu nhiên. Nếu không tìm được cơ số nào làm Fermat witness thì ta kết luận có khả năng rất cao là số nguyên tố.
Để dễ hình dung hơn, các bạn có thể xem decision tree cho Fermat primality test với số lần thử là . Mũi tên hồng biểu diễn trường hợp không thỏa (đồng nghĩa với việc tìm được Fermat witness cho ), mũi tên xanh biểu diễn trường hợp thỏa.
Hợp số Carmichael [13] có thể được coi là "khắc tinh" của Fermat primality test bởi tính chất đặc biệt của nó. Với một hợp số Carmichael , mọi cơ số nguyên tố cùng nhau với đều là Fermat liar. Tức là luôn đúng với là hợp số Carmichael và .
Một ví dụ cho hợp số Carmichael là . Các bạn có thể xem thêm dãy số Carmichael trên OEIS có mã A002997 [14].
Để Fermat primality test phát hiện được một số Carmichael là hợp số, nó phải sinh ngẫu nhiên ra một cơ số thỏa , mà khả năng điều này xảy ra là rất thấp.
Tuy nhiên, hợp số Carmichael khá hiếm (số càng lớn lại càng hiếm). Người ta đã tính được rằng có số Carmichael không quá , và khoảng số Carmichael không quá . Bên cạnh đó ta có thể tính và lưu vài số Carmichael đầu tiên vào mảng hằng. Vì vậy, Fermat primality test vẫn được ứng dụng vào thực tế với độ chính xác khá cao.
Miller–Rabin primality test cũng được phát triển dựa trên định lý Fermat nhỏ ( là số nguyên tố, không phải bội của ). Nhưng thay vì sử dụng trực tiếp định lý này, Miller–Rabin đưa ra nhận xét là ta chỉ quan tâm lẻ (vì chỉ có là số chẵn nguyên tố) chẵn. Từ đó, ta có thể biểu diễn dưới dạng (với và là số nguyên ). Nếu biểu diễn dưới dạng nhị phân thì là số bit liên tiếp bên phải và là sau khi right shift lần.
Thay và chuyển số sang vế trái:
Ta thấy có dạng hằng đẳng thức với và . Sau khi phân tích xong, ta lại áp dụng hằng đẳng thức vào , cứ như vậy, ta có:
Cộng với một số phân tích toán học, Miller–Rabin kết luận một số có khả năng cao là số nguyên tố khi trong điều kiện này đúng:
Nếu cả điều này đều không đúng thì ta kết luận ngay là hợp số và cơ số vừa được dùng để kiểm tra là minh chứng cho việc là hợp số.
Lưu ý, trong điều này đúng đúng đúng. Điều ngược lại không xảy ra vì vẫn có trường hợp các thừa số đều không chia hết cho nhưng tích lại chia hết cho . Điều này khiến Miller–Rabin mạnh hơn Fermat primality test.
Với một số hợp số , vẫn tồn tại cơ số sao cho trong điều kiện nêu trên đúng. Lúc này, ta gọi là strong liar.
Khác với Fermat, thuật toán của Miller–Rabin không có bất kỳ "khắc tinh" nào. Hơn nữa, người ta chứng minh được, với một cơ số ngẫu nhiên (), khả năng là một strong liar là [15]. Đây là một xác suất không quá thấp nhưng tốt hơn rất nhiều so với Fermat primality test khi gặp số Carmichael.
Tương tự các thuật toán Monte Carlo khác, ta có thể chạy Miller–Rabin primality test lần, mỗi lần với một cơ số ngẫu nhiên khác nhau. Có thể thấy, xác suất sai số lúc này – chính là xác suất cả lần cho ra cơ số là strong liar – giảm xuống còn . Ta chỉ cần chọn thì xác suất sai số sẽ còn là một con số không đáng kể.
Để cài đặt Miller–Rabin primality test, mình cần cài đặt sẵn hàm sinh ngẫu nhiên trong đoạn với xác suất đều và hàm tính mũ nhanh bằng chia để trị. Lưu ý, nếu muốn nhân số -bit với nhau thì cần lưu vào biến -bit để tránh tràn số.
Tiếp đến, mình sẽ cài hàm kiểm tra điều kiện Miller–Rabin, chỉ cần điều kiện thỏa thì hàm sẽ trả về true
ngay:
Ở đây, mình dùng biến val
ban đầu lưu giá trị để kiểm tra điều kiện thứ nhất. Sau đó, mình sẽ chạy vòng lặp, cứ mỗi lần kiểm tra xong, val
sẽ lưu giá trị , để tăng lên, ta chỉ việc bình phương biến val
lên là xong, vì .
Cuối cùng, mình sẽ cài hàm kiểm tra số nguyên tố, trước khi dùng đến hàm MillerRabin
, mình sẽ loại hết các edge cases (, có thể loại luôn trường hợp chẵn luôn để tối ưu), tính và bằng cách tận dùng hàm __builtin_ctzll(x)
và right shift. Mình sẽ chọn , đủ để xác suất sai số gần như là không có.
Dễ thấy, nên Miller–Rabin primality test có độ phức tạp thời gian với là số lần thử và là số cần kiểm tra.
Nếu tự cài đặt, các bạn có thể kiểm tra code trên SPOJ [16].
Song song với Monte Carlo, ta có Las Vegas algorithm, đây là tên gọi chung của những thuật toán hoạt động dựa trên việc sinh ngẫu nhiên, luôn đưa ra kết quả đúng, nhưng có lúc sẽ rơi vào độ phức tạp xấu nhất với xác suất khá thấp.
Trong phần này, ta sẽ tìm hiểu thuật toán Las Vegas khá hay mà mình biết.
QuickSelect là thuật toán tìm kiếm được phát triển bởi C. A. R. Hoare và xuất bản năm 1961 [17], thuật toán "anh em" của QuickSort – một thuật toán Las Vegas khác rất nổi tiếng thông dụng (được sử dụng cho hàm sort
trong C++
) cũng do Hoare tạo ra.
Thuật toán này được sinh ra để giải bài toán -th order statistic, tức là tìm phần tử lớn thứ trong một dãy số có phần tử chưa được sắp xếp, được đánh số từ . Ta có thể giả sử .
Thông thường, ta sẽ chạy một thuật toán sắp xếp nào đó trong rồi tìm phần tử thứ trong . Tuy nhiên, liệu ta có cần sắp xếp cả dãy số chỉ để tìm phần tử?
Ý tưởng chính của QuickSelect cũng khá giống QuickSort, là một thuật toán chia để trị như sau:
Đây là hình ảnh minh họa quá trình tìm phần tử lớn thứ (đếm từ ) trong mảng ngẫu nhiên có phần tử:
Với việc chọn pivot ngẫu nhiên, khả năng cao dãy con được tạo ra sẽ tương đối bằng nhau. Khi đó, không gian tìm kiếm sẽ được chia đôi sau mỗi bước, dẫn đến độ phức tạp thời gian là:
Độ phức tạp tệ nhất của QuickSelect là , tuy nhiên xác suất là rất thấp, trong thực tế, chuyện này gần như không thể xảy ra.
Mình sẽ cài hàm quickSelect
tìm phần tử lớn thứ trong không gian tìm kiếm là vector<int> vec
theo kiểu đệ quy.
Mình đã chạy thử đoạn code này với vector<int>
có phần tử, kết quả là Quickselect chạy nhanh hơn thuật toán sắp xếp khoảng - lần.
Eight Queens [18] là một bài toán kinh điển và rất phổ biến trong Tin học, thường được dùng làm ví dụ minh họa cho backtracking. Nhắc lại, bài toán yêu cầu tìm cách đặt quân Hậu vào một bàn cờ sao cho không có quân Hậu nào tấn công nhau (theo luật cờ vua). Dưới đây là ảnh minh họa cho một cách đặt hợp lệ:
Với cách làm backtrack cổ điển, ta sẽ viết hàm với , tức là đã có quân Hậu, bây giờ ta sẽ thử các phương án đặt con Hậu thứ vào dòng thứ rồi gọi đệ quy tiếp . Nếu tất cả các phương án đều không thành công thì quay lui lại và cứ tiếp tục thử. Đến khi gọi thành công nghĩa là ta đã đặt đủ quân Hậu và tìm được đáp án hợp lệ.
Người ta đã tìm ra cách tối ưu thuật toán này như sau: thay vì lần lượt thử các phương án để đặt quân Hậu vào dòng thứ , ta chọn ngẫu nhiên một phương án để thử, nếu không thành công, loại phương án này rồi chọn ngẫu nhiên và thử tiếp. Trên thực tế, cách này có thể tìm ra đáp án hợp lệ nhanh hơn thuật toán backtrack thông thường.