Thiết kế và phân tích thuật toán

Cấu trúc dữ liệu và Giải thuật của Đỗ Xuân Lôi:

• Chương 2. Thiết kế và phân tích giải thuật;
• Mã giả được sử dụng trong bài học này và các bài học kế tiếp gọi là ngôn ngữ giả mã tựa PASCAL mục 1.3, chương 1.

1. Từ bài toán đến chương trình

Mô-đun hóa và việc giải quyết bài toán

Các bài toán giải được trên máy tính ngày càng phức tạp và đa dạng. Các thuật toán và chương trình để giải quyết chúng cũng ngày càng có quy mô lớn và càng khó khi thiết lập cũng như khi muốn tìm hiểu.

Một giải pháp là chia nhỏ bài toán lớn thành các bài toán nhỏ hơn. Điều đó có nghĩa là nếu xem bài toán cần giải quyết là một mô-đun lớn thì các bài toán nhỏ hơn có thể xem là mô-đun con và cứ tiếp tục phân chia cho đến khi một bài toán hay mô-đun không thể chia nhỏ được nữa. Ví dụ bài toán A có thể phân chia thành các bài toán B, C, D; bài toán B phân chia thành E, F,…

Phương pháp giải quyết bài toán kiểu này được gọi là phương pháp chia để trị (divide and conquer) và được thiết kế từ đỉnh xuống (top-down design). Đó là cách phân tích tổng quát toàn bộ vấn đề, xuất phát từ dữ kiện và các mục tiêu đặt ra, rồi sau đó mới đi dần vào giải quyết các phần cụ thể một cách chi tiết hơn (vì vậy mà người ta còn gọi là cách thiết kế từ khái quát đến chi tiết).

Ví dụ một chương trình xử lý tệp (hay tập tin)

Phương pháp tinh chỉnh từng bước (Stepwise refinement)

Tinh chỉnh từng bước là phương pháp thiết kế thuật toán gắn liền với lập trình. Nó phản ánh tinh thần của quá trình mô-đun hóa bài toán kiểu và thiết kế kiểu top-down.

Thoạt đầu chương trình thể hiện thuật toán được trình bày bằng ngôn ngữ tự nhiên phản ánh ý chính của công việc cần làm sau đó được thể hiện bằng mã giả (pseudo code) rồi đến ngôn ngữ lập trình. Hay nói cách khác, phương pháp tinh chỉnh từng bước sẽ đi từ mức “làm cái gì” đến mức “làm thế nào”, ngày càng sát với các chức năng ứng với các câu lệnh của ngôn ngữ lập trình đã chọn.

Bài toán ví dụ: Sắp xếp một dãy n số nguyên khác nhau theo thứ tự tăng dần.

* Có thể phác thảo thuật toán như sau:

Từ dãy các số nguyên chưa được sắp xếp, chọn ra số nhỏ nhất, đặt nó vào cuối dãy đã được sắp xếp.

Cứ lặp lại quy trình đó cho tới khi dãy chưa được sắp xếp trở thành rỗng.

Hình dung cụ thể hơn một chút ta thấy, thoạt đầu dãy số chưa được sắp xếp chính là dãy số đã cho. Dãy số đã được sắp xếp còn rỗng, chưa có phần tử nào. Vậy thì nếu chọn được số nhỏ nhất đầu tiên và đặt vào cuối dãy đã được sắp thì cũng chính là đặt vào vị trí đầu tiên của dãy này. Nhưng dãy này đặt ở đâu?

Thế thì phải hiểu dãy số mà ta sẽ sắp xếp được đặt tại chỗ cũ hay đặt chỗ khác? Điều đó đòi hỏi phải chi tiết hơn về cấu trúc dữ liệu và cấu trúc lưu trữ của dãy số đã cho.

Trước hết ta ấn định: dãy số cho ở đây được coi như dãy các phần tử của một vectơ (sau này ta nói: nó có cấu trúc mảng một chiều) và dãy này cần được lưu trữ bởi một vectơ lưu trữ gồm n từ máy kế tiếp ở bộ nhớ trong (a₁, a₂,…,a_n) mỗi từ a_i lưu trữ một phần tử thứ i (1 <= i <= n) của dãy số.

Ta cũng quy ước: dãy số được sắp xếp rồi vẫn để tại chỗ cũ như đã cho.

Vậy thì việc đặt “số nhỏ nhất” vừa được chọn, ở một lượt nào đó, vào cuối dãy đã được sắp xếp phải thực hiện bằng cách đổi chỗ với số hiện đang ở vị trí đó (nếu như nó khác số này). Ta có bước tinh chỉnh đầu tiên.

Bước tinh chỉnh 1

For i := 1 to n do begin
– Xét từ a_i đến a_n để tìm số nhỏ nhất a_j
– Đổi chỗ giữa a_i và a_j
End

Tới đây ta thấy có hai nhiệm vụ con cần làm rõ thêm:

• NV1: Tìm số nguyên nhỏ nhất a_j trong các số từ a_i đến a_n
• NV2: Đổi chỗ giữa a_j và a_i

NV1 có thể thực hiện bằng cách: Thoạt tiên coi a_i là số nhỏ nhất tạm thời; lần lượt so sánh a_i với a_i+1, a_i+2, v.v… Khi thấy số nào nhỏ hơn thì lại coi đó là số nhỏ nhất mới. Khi đã so sánh với a_n rồi thì số nhỏ nhất sẽ được xác định.

Nhưng xác định bằng cách nào? Có thể chỉ ra chỗ của nó, nghĩa là nắm được chỉ số của phần tử ấy. Ta có bước tinh chỉnh tiếp theo.

Bước tinh chỉnh 2.1

j := i

For k := j + 1 to n do

                If a_k < a_j then j := k;

Với nhiệm vụ thứ hai (NV2) thì có thể giải quyết tương tự như khi ta muốn chuyển hai thứ rượu trong hai ly, từ ly nọ sang ly kia: ta sẽ phải dùng ly thứ ba (không đựng gì) B để làm ly trung chuyển. Ta có bước tinh chỉnh cuối cùng.

Bước tinh chỉnh 2.2

B := a_i; a_i := a_j; a_j := B;

Sau các bước tinh chỉnh, thuật toán sắp xếp được viết lại như sau:

Procedure SORT (A, n)

For i := 1 to n do begin
{Chọn số nhỏ nhất}  j := i;
	For k := j + 1 to n do
		If A[k] < A[j] then j := k;
{Đổi chỗ}  B := A[i]; A[i] := A[k]; A[j] := B;
	end
Return

Bạn có vấn đề gì về bài học này không?