Học thuật toán qua các bài toán – Phần 2
Tiếp theo bài viết “Học thuật toán qua các bài toán”, trong bài viết này tôi xin tiếp tục giới thiệu với các bạn độc giả yêu thích thuật toán và lập trình một số ví dụ khá thú vị về thuật toán qua các bài toán. Trước hết chúng ta hãy bắt đầu bằng bài toán “Nhân hai ma trận”.
Bài toán 1: Bài toán nhân hai ma trận
Hầu như bất kỳ ai học qua toán đại cương ở trường đại học hay mới học lập trình đều đã từng biết về bài toán nhân ma trận. Một ma trận kích thước NxM là một bảng (mảng) hai chiều gồm N hàng, mỗi hàng gồm M cột, tại mỗi ô (i, j), tương ứng với hàng i và cột j, của bảng là một số nguyên (hoặc số thực). Khi số hàng N bằng với số cột M, ta sẽ có một ma trận vuông. Hai ma trận vuông NxN nhân với nhau sẽ cho ma trận tích kích thước NxN. Giả sử ma trận thứ nhất là a, ma trận thứ hai là b thì công thức để nhân a với b được cho như sau:


Cài đặt cho thuật toán nhân hai ma trận theo công thức trên như sau:


Quan sát một chút chúng ta sẽ thấy rằng đoạn chương trình thực hiện chức năng chính của việc nhân ma trận chính là 3 vòng lặp với các biến chỉ số i, j, k và việc thay đổi thứ tự của ba vòng lặp này không ảnh hưởng gì tới kết quả cuối cùng. Ở đây chúng ta có 3 vòng lặp với 3 chỉ số nên sẽ có 3! = 6 cách khác nhau để tiến hành nhân hai ma trận tương ứng với việc thay đổi thứ tự của ba vòng lặp. Các bạn có thể cho rằng 6 cách để nhân hai ma trận này có thời gian chạy giống nhau nhưng thực tế lại không phải như vậy. Chúng ta hãy phân tích xem tại sao lại có kết quả khác nhau và cách nào là tốt nhất cho bài toán nhân ma trận theo thuật toán trên.
Nếu nhân hai ma trận theo thứ tự chỉ số ijk như ở trên, các phần tử của ma trận a, c sẽ được truy cập theo từng hàng, còn ma trận b sẽ có các phần tử truy cập theo các cột. Còn nếu nhân hai ma trận theo thứ tự ikj thì cả ba ma trận đều có các phần tử được truy cập tới theo từng hàng. Các phần tử của một ma trận được tổ chức trong bộ nhớ thực chất là một dãy các ô nhớ liên tiếp trong đó các phần tử ở cùng một hàng sẽ nằm kế tiếp nhau, hết hàng này lại đến hàng khác của ma trận. Vì thế nếu các phần tử được truy cập tới theo hàng, kết quả sẽ nhanh hơn so với truy cập tới theo cột. Điều này là do nguyên tắc làm việc của máy tính: khi truy cập tới một phần tử bộ nhớ nào đó, các phần tử liền kề với nó cũng sẽ được đọc vào bộ nhớ trong của máy tính để tối ưu thời gian truy cập bộ nhớ theo nguyên lý: nếu một địa chỉ bộ nhớ nào đó được truy cập tới thì rất có thể trong tương lai các ô nhớ lân cận với nó cũng sẽ được sử dụng (truy cập tới). Chính vì vậy việc thực hiện thuật toán nhân hai ma trận theo thứ tự ikj sẽ nhanh hơn so với 5 cách còn lại của thuật toán nhân hai ma trận. Các bạn có thể sinh ngẫu nhiên các ma trận có N xấp xỉ 1000 để kiểm chứng kết quả này.
Bài toán 2: Bài toán trộn các dãy con
Bài toán trộn các dãy con được phát biểu như sau: cho hai dãy số (nguyên) đã được sắp xếp tăng dần là dãy a (có N phần tử) và dãy b (có M phần tử), hãy trộn hai dãy a và b thành một dãy kết quả c sao cho dãy c gồm tất cả các phần tử của a, b và cũng được sắp xếp tăng dần.
Thật ra có khá nhiều cách để cài đặt thuật toán cho bài toán trên, sau đây tôi sẽ đưa ra một cài đặt khá đơn giản và hiệu quả cho bài toán trộn 2 Run này (1 dãy sắp xếp được gọi là 1 Run). Trước hết cần để ý rằng dù có tiến hành theo cách nào thì Run kết quả c cũng sẽ có đủ N+M phần tử của cả Run a và Run b. Nếu ta gọi i, j, k lần lượt là chỉ số tương ứng của các Run a, b, c thì các chỉ số này sẽ lần lượt nhận các giá trị:
• Từ 0 tới N-1 cho biến i
• Từ 0 tới M-1 cho biến j
• Từ 0 tới (N+M)-1 cho biến k
Hơn nữa mỗi phần tử của Run c chỉ có thể nhận giá trị là 1 phần tử của Run a hoặc Run c, có nghĩa là c[k] = a[i] hoặc b