Phương pháp phát triển tư duy thuật toán cho học sinh phổ thông trên con đường từ ý tưởng đến mô tả thuật toán

JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 157-168 This paper is available online at PHƯƠNG PHÁP PHÁT TRIỂN TƯ DUY THUẬT TOÁN CHO HỌC SINH PHỔ THÔNG TRÊN CON ĐƯỜNG TỪ Ý TƯỞNG ĐẾNMÔ TẢ THUẬT TOÁN Nguyễn Chí Trung Khoa Công nghệ thông tin, Trường Đại học Sư Phạm Hà Nội E-mail: trungnc@hnue.edu.vn Tóm tắt. Hình thành và phát triển khả năng tư duy thuật toán là một trong các mục tiêu của môn Tin học ở phổ thông. Có một khoảng trống về mặt thể hiện tri thức, ngầm diễn ra trong tư duy, giữa phần nêu ý tưởng thuật toán và phần mô tả thuật toán. Bài báo đề xuất một phương pháp tiếp cận mô tả thuật toán mà dựa vào đó, giáo viên có thể dẫn dắt học sinh phân tích, tìm tòi các thao tác quan trọng để hiểu và mô tả được thuật toán. Từ khóa: Tư duy thuật toán, môn Tin học, thuật toán. 1. Mở đầu Xét bài toán đơn giản sau: Bài toán 1. Hãy tính S là tổng các bình phương của n số tự nhiên đầu tiên. Cách trình bày thuật toán giải quyết bài toán này, cũng giống như cách trình bày thuật toán trong hầu hết các tài liệu khác về thuật toán, kể cả trong sách giáo khoa Tin học lớp 10 [1], gồm 3 phần sau đây: Phần 1: Xác định bài toán Input: số tự nhiên n. Output: S là giá trị của biểu thức 12 + 22 + ... + n2. Phần 2: Tìm ý tưởng thuật toán Khởi tạo S←− 0. Lần lượt với i từ 1 đến n, cộng dần giá trị của i2 vào cho S. Phần 3: Mô tả thuật toán Bước 1. Nhập số n; Bước 2. S←− 0; i←− 0; Bước 3. i←− i + 1; Bước 4. Nếu i > n thì đưa ra tổng S rồi kết thúc; Bước 5. S←− S + i2; Quay về bước 3; Rõ ràng ý tưởng thuật toán là dễ hiểu, nhưng mô tả thuật toán thường làm học sinh khó hiểu với những câu hỏi như: Tại sao lại có thể gán được i bằng i + 1?, Tại sao gán 157 Nguyễn Chí Trung được S bằng S + i2?, Tại sao phải lần lượt tăng i lên một đơn vị để cộng dần i2 vào S? Liệu có thể thay dãy các bước từ 2 đến 5 chỉ bằng một bước với cách viết dễ hiểu sau đây được không? Bước 3: S = 12 + 22 + ... + n2 = n∑ i=1 i2 (*) Những thắc mắc của học sinh khi cố gắng hiểu một mô tả thuật toán đã cho thấy có một khoảng trống khá lớn về mặt thể hiện tri thức, ngầm diễn ra trong tư duy, khi chuyển từ phần nêu ý tưởng thuật toán sang phần mô tả thuật toán. Khoảng trống này cần được lấp đầy bằng tư duy thuật toán ở góc độ tin học. Với nhiệm vụ biến tri thức giáo khoa thành tri thức dạy học, người thầy phải dạy cho học sinh một con đường tư duy để từ ý tưởng thuật toán, học sinh có thể hiểu và xây dựng được mô tả thuật toán giải bài toán đã cho. Nguyễn Bá Kim khi bàn về “Dạy học qui tắc, phương pháp” đã chỉ ra 5 dạng hoạt động để phát triển tư duy cho học sinh, nhưng không đề cập đến việc vận dụng 5 dạng hoạt động này để hướng dẫn học sinh cách tư duy trong “khoảng trống” nói trên [2]. Lê Khắc Thành đã chú ý đến việc rèn luyện cho học sinh các hoạt động trí tuệ, nhưng chưa chỉ rõ một phương cách cụ thể để rèn luyện cho học sinh tư duy thuật toán [3]. Knuth, D. E. đã so sánh mối quan hệ giữa tư duy thuật toán và tư duy toán học, nhưng không đề cập đến việc hướng dẫn người học tư duy như thế nào khi xây dựng thuật toán [4]. Theo Gerald Futschek trong [5], tư duy thuật toán là sự kết nối các năng lực của tư duy theo cách nào đó để hiểu và xây dựng được thuật toán, bao gồm: - Năng lực phân tích bài toán đã cho; - Năng lực xác định chính xác bài toán; - Năng lực tìm ra các thao tác cơ bản tương ứng với bài toán đã cho; - Năng lực xây dựng một thuật toán chính xác để giải bài toán đã cho bằng cách sử dụng các thao tác cơ bản; - Năng lực tư duy về tất cả các trường hợp bình thường và đặc biệt có thể xảy ra của một bài toán; - Năng lực nâng cao hiệu quả của một thuật toán. Hai năng lực đầu tiên giúp học sinh thực hiện tốt nhiệm vụ “Xác định bài toán”. Các năng lực còn lại giúp học sinh hiểu và làm tốt nhiệm vụ “Mô tả thuật toán”. Trong đó, năng lực 5 và 6 được xem là những năng lực tư duy giúp học sinh xây dựng được một thuật toán đảm bảo tính đúng đắn và tính hiệu quả; năng lực 3 và 4 được xem là những năng lực tìm ra các thao tác cơ bản để mô tả thuật toán giải bài toán. Gerald đề nghị nên dùng các bài toán khó nhưng phát biểu bài toán là dễ hiểu để rèn luyện tư duy thuật toán cho người học, và chọn bài toán “Tìm đường trong mê cung” để phân tích quá trình tìm ra thuật toán đúng đắn thông qua quá trình tối ưu hóa “cách đi” (thao tác cơ bản) để thoát khỏi mê cung. Bài báo tập trung vào các năng lực 3 và 4 và đề nghị một hướng khác: Thứ nhất là xem xét được tất cả các bài toán từ dễ đến khó để phù hợp cho tất cả các trình độ của người học; Thứ hai là không chọn cách tối ưu dần các thao tác cơ bản mà đề xuất một số thao tác cố định mới (khái niệm mới) và tìm cách dùng chúng để mô tả thuật toán dựa 158 Phương pháp phát triển tư duy thuật toán cho học sinh phổ thông... trên ý tưởng thuật toán. Hướng tiếp cận này sẽ hình thành một con đường cho học sinh tư duy để hiểu và xây dựng được thuật toán, nhằm lấp đầy khoảng trống giữa phần nêu ý tưởng thuật toán và phần mô tả thuật toán. 2. Nội dung nghiên cứu 2.1. Dạy cho học sinh cảm nhận được cách “tư duy” của máy tính Không thể dạy cho học sinh phổ thông kiến thức Kiến trúc tập lệnh (Instruction set architecture), là hình ảnh trừu tượng của một hệ thống tính toán được nhìn từ góc độ của một lập trình viên sử dụng ngôn ngữ máy (hay hợp ngữ) [6]. Nhưng nếu hiểu được những vấn đề này thì mới có thể hiểu rõ cách mà máy tính “tư duy” để thực hiện thuật toán giải một bài toán, và do đó biết cách diễn tả đúng thuật toán. Mâu thuẫn này dẫn đến sự khó hiểu về cách viết các thao tác trong một mô tả thuật toán và nó dường như bị áp đặt lên học sinh. Bởi vậy, trong những cơ hội có thể được, giáo viên cần dạy cho học sinh cảm nhận được cách tư duy của máy tính. Cơ hội đầu tiên là trả lời các câu hỏi dạng “Tại sao có thể gán được x bằng x + 1?”. Thao tác gán là một thao tác đặc trưng, gặp thường xuyên trong các thuật toán của tin học, và nó không thể giải thích dựa vào các phép toán thông thường của toán học. Học sinh phải hiểu rằng thao tác gán x ←− x + 1 được thực hiện theo thứ tự: giá trị của biểu thức ở bên phải phép gán được tính toán trước, rồi sau đó giá trị này mới được gán cho biến ở bên trái phép gán. Như vậy giá trị của x ở vế phải khác với giá trị của x ở vế trái (các giá trị này tương ứng là giá trị của x trước và sau khi thực hiện thao tác gán). Trong ngôn ngữ lập trình Pascal, kí hiệu←− được thay bằng kí pháp :=, và máy tính thực hiện thao tác gán x := x + 1 theo thuật toán sau: Bước 1. Tìm địa chỉ biến x ở biểu thức bên phải và lấy giá trị của x; Bước 2. Tính giá trị của biểu thức ở bên phải; Bước 3. Tìm lại địa chỉ của biến x ở bên trái để lưu kết quả vừa tính. Ta gọi các thao tác ở 3 bước trên đây là các thao tác nguyên tố, nghĩa là các thao tác nhỏ nhất (không thể phân chia thành các thao tác khác) mà các phần tử vật lí thực hiện chức năng tính toán trong máy tính có thể “hiểu” và thực hiện được. Phép gán x←− x + 1 trong ngôn ngữ C/C++ được viết là x++ và máy tính thực hiện thao tác gán này thông qua các thao tác nguyên tố sau đây: Bước 1. Tìm địa chỉ của biến duy nhất trong phép gán để lấy giá trị; Bước 2. Tăng giá trị đó lên 1 đơn vị; Bước 3. Đặt giá trị mới vào địa chỉ đã biết. Trở lại Bài toán 1, cách viết trong (*) phản ánh đúng cách tư duy quen thuộc của toán học, vì S được biểu diễn toán học của một tổng các bình phương của các phần tử từ 1 đến n. Cách viết từ bước 2 đến bước 5 phản ánh đúng cách tư duy trong tin học, vì chúng phù hợp với kiến trúc vật lí thực hiện chức năng tính toán trong máy tính, và do đó chúng là dãy các thao tác dễ chuyển đổi thành chương trình được viết dưới dạng một ngôn ngữ lập trình nào đó. Đây là cơ hội thứ hai để giáo viên giải thích cho học sinh biết “Tại sao phải lần lượt tăng i lên một đơn vị để cộng dần i2 vào S?”. Máy tính có thể hiểu được một 159 Nguyễn Chí Trung tổng có các số hạng hoàn toàn xác định, ví dụ 12 + 22 + 32 + 42 + 52, nhưng nó không thể hiểu được một tổng có các số hạng biểu thị một cách trừu tượng như trong dạng 12 + 22 + ... + n2 . Vì thế biểu thức tổng trong dạng (*) phải được phân tích thành n tổng có các số hạng xác định, nghĩa là: Bước 3: S←− S + i2, i = 1, 2, ..., n; (**) Cách viết trong (**) cũng phản ánh gần giống cách tư duy trong tin học và nó là cách viết tóm tắt của dãy các bước từ 2 đến 5. 2.2. Dạy cho học sinh biết sử dụng các “thao tác cơ sở” để mô tả thuật toán Để ý thấy các thuật toán giải một bài toán đều xuất hiện một số thao tác sau đây: - Thao tác nhập: nhập giá trị cho biến. - Thao tác xuất: đưa ra ra giá trị của biến. - Thao tác gán: gán giá trị của biểu thức cho một biến, có dạng: ←− ; - Thao tác chuyển: chuyển đến một bước nào đó phía trước hoặc phía sau bước hiện tại. - Thao tác kiểm tra: thực hiện một thao tác dạng "Nếu P thì Q"; trong đó P là một mệnh đề có một và chỉ một trong hai giá trị đúng hoặc sai, Q là một trong các thao tác đã chỉ ra (có thể là một thao tác kiểm tra khác). Ta gọi 5 thao tác trên đây là các thao tác cơ sở chung. Ví dụ, đối với Bài toán 1, giáo viên có thể yêu cầu học sinh chỉ sử dụng 5 thao tác cơ sở chung để mô tả thuật toán giải bài toán này. Ngoài các thao tác cơ sở chung, mỗi bài toán còn có thao tác cơ sở của riêng nó, ta gọi chúng là các thao tác cơ sở riêng. Cả hai loại thao tác này được gọi chung là các thao tác cơ sở, và được định nghĩa như sau: Định nghĩa 1. Thao tác cơ sở là thao tác nhỏ nhất, được dùng để diễn tả từng bước của thuật toán và biểu thị một khả năng hiểu và thực hiện được bởi một tác nhân tương ứng. Trong định nghĩa trên, từ nhỏ nhất được hiểu là một thao tác cơ sở thì không thể phân chia thành các thao tác cơ sở khác (nhưng có thể phân chia thành các thao tác nguyên tố). Tác nhân ở đây là một đối tượng, ví dụ như con người, máy tính hay một “máy” nào đó có khả năng hiểu và thực hiện được thuật toán đã mô tả. Cụm từ tác nhân tương ứng nhằm nhấn mạnh rằng các thao tác cơ sở được chỉ ra trong thuật toán phải không vượt quá “năng lực và trình độ” của tác nhân, nghĩa là tác nhân đó có thể hiểu và thực hiện được chúng. Bài toán 2 sau đây minh họa một bài toán có thao tác cơ sở riêng và cách sử dụng các thao tác cơ sở để mô tả thuật toán. Bài toán 2. Giả sử máy tính chỉ thực hiện được thao tác cộng hai số nguyên dương, không thực hiện được thao tác trừ. Hãy chỉ ra các bước hướng dẫn máy tính tính giá trị biểu thức a – b với a và b là hai số nguyên dương được nhập vào, và a > b? Ý tưởng thuật toán: gọi c là hiệu của a trừ b, ta có c = a – b←→ a = b + c. Khi đó, 160 Phương pháp phát triển tư duy thuật toán cho học sinh phổ thông... nếu đặt s = b + c thì s = a. Vậy ta bắt đầu với c = 0, s = b, rồi lần lượt tăng từng đơn vị cho c để tính lại s = b + c, (hoặc s và c đồng thời cùng tăng dần 1 đơn vị) đến khi s bằng a thì đương nhiên giá trị thu được của c là hiệu cần tìm. Tìm cách mô tả thuật toán: Ta thấy lời giải bài toán (hay thuật toán) được trình bày bằng một phương tiện và cách thức duy nhất. Phương tiện là 5 thao tác cơ sở chung và 1 thao tác cơ sở riêng của bài toán (thao tác cộng). Cách thức là phán đoán, suy luận để lựa chọn các thao tác cơ sở, rồi tìm cách viết chúng theo một thứ tự thích hợp để diễn tả lời giải bài toán. Nói cách khác, chỉ có một con đường duy nhất để mô tả thuật toán, đó là sử dụng các thao tác cơ sở để diễn tả từng bước của thuật toán. Một mô tả thuật toán giải bài toán 2 được trình bày như Bảng 1 dưới đây: Bảng 1. Mô tả thuật toán giải bài toán 2 Bước Thao tác được chọn Sử dụng thao tác 1 Nhập Nhập a và b; 2 Gán c←− 0; s←− b; 3 Kiểm tra và xuất Nếu s = a thì đưa ra giá trị của c và kếtthúc; 4 Cộng, gán và chuyển c←− c + 1; s←− b + c; Quay về bước 3; 2.3. Dạy cho học sinh biết xây dựng các “thao tác cơ bản” để mô tả thuật toán Trong nhiều bài toán, nếu chỉ dùng các thao tác cơ sở để mô tả thuật toán thì thuật toán sẽ dài dòng và khó hiểu. Bài toán 3 dưới đây là một minh họa nhu cầu phải xây dựng thêm một thao tác mới để mô tả thuật toán ngắn gọn, dễ hiểu hơn. Bài toán 3. Biết rằng máy tính chỉ thực hiện được thao tác cộng. Hãy chỉ ra các bước hướng dẫn máy tính tính giá trị biểu thức s = (a - b) + (b - c) + (c - d) + (d - e), với a, b, c, d, e là các số nguyên dương cho trước và a > b > c > d > e. Ý tưởng thuật toán: Dựa vào thuật toán giải bài toán 2, ta khởi tạo s bằng 0, rồi lần lượt mô tả thuật toán tính các hiệu và cộng dần các kết quả này vào cho biến s. Tìm cách mô tả thuật toán: Theo ý tưởng thuật toán đã nêu, rõ ràng ta phải lặp lại việc mô tả thuật toán tính các hiệu. Để tránh phải viết mô tả thuật toán dài dòng, trước hết ta hướng dẫn máy tính cách sử dụng các thao tác cơ sở để thực hiện thao tác trừ đối với hai số nguyên dương bất kì. Ta gọi các số nguyên dương này là các tham số. Hướng dẫn này được "đóng gói" trong một mô tả thuật toán độc lập, giải quyết một bài toán con độc lập (bài toán thực hiện phép trừ). Ta có thể xem gói này như một thao tác cơ sở mới để có thể sử dụng lại nhiều lần trong mô tả thuật toán giải quyết yêu cầu bài toán đã nêu. Ta gọi gói này là một thao tác cơ bản. Có thể định nghĩa thao tác cơ bản như sau: Định nghĩa 2. Một thao tác cơ bản là thao tác được xây dựng từ các thao tác cơ sở, và mô tả thuật toán giải quyết một bài toán độc lập, được đóng gói thành một thao tác mới để sử dụng như một thao tác cơ sở. 161 Nguyễn Chí Trung Một thao tác cơ bản có thể được “đóng gói” theo dạng như Hình 1 dưới đây: Định nghĩa thao tác : Input: các tham số; Output: thông tin cần đưa ra; Thuật toán: Các thao tác cơ sở để tìm output từ input. Hình 1. Đóng gói một thao tác cơ bản Mô tả thuật toán tính biểu thức s như Bảng 2 sau đây: Bảng 2. Mô tả thuật toán giải bài toán 3 Bước Thao tác được chọn Sử dụng thao tác I Xây dựng thao tác cơ bản Định nghĩa thao tác trừ: x - y Input: x, y; Output: z là hiệu của x - y; Thuật toán: 1 Gán z←− 0; h←− y; 2 Kiểm tra và xuất Nếu h = x thì đưa ra z và kết thúc; 3 Cộng, gán và chuyển z←− z + 1; h←− y + z; quay về bước 3; II Thuật toán chính 1 Nhập Nhập a, b, c, d, e; 2 Gán s←− a - b; 3 Trừ, cộng và gán h←− b - c; s←− s + h; 4 Trừ, cộng và gán h←− c - d; s←− s + h; 5 Trừ, cộng và gán h←− d - e; s←− s + h; 6 Xuất Đưa ra giá trị của s. Nhận xét 1: Ta thấy phép nhân có thể qui về một dãy các phép cộng, ví dụ 4 × 5 = 5 + 5 + 5 + 5. Phép chia nguyên có thể qui về một dãy các phép cộng, một phép trừ và hai phép kiểm tra, ví dụ xét phép chia 7 : 3, ta có 3 + 3 = 6 7, do đó 7 bằng 6 (tổng của 2 số 3) cộng với 1 (hiệu của 7 - 6). Vậy 7 : 3 bằng 2 dư 1. Từ các nhận xét này, tương tự như bài toán 3, học sinh có thể xây dựng được ba thao tác cơ bản là trừ, nhân và chia, sau đó vận dụng các thao tác cơ sở và các thao tác cơ bản này để có thể tính được giá trị của một biểu thức bất kì theo thứ tự ưu tiên của các phép toán trong toán học. 2.4. Dạy cho học sinh biết hình thành các “thao tác tổng hợp” để mô tả thuật toán Trên đây là các bài toán đơn giản. Đối với các bài toán khó như Bài toán 4 dưới đây, học sinh cần xây dựng thêm các thao tác mới, khó hơn trong quá trình hình thành mô tả thuật toán. 162 Phương pháp phát triển tư duy thuật toán cho học sinh phổ thông... Bài toán 4: Xét trò chơi "Xoay vòng" có cấu hình như Hình 2a dưới đây, trong đó có hai vòng xoay X và Y hình chữ nhật, chung dây MN. Mỗi vòng có thể xoay cùng chiều hoặc ngược chiều kim đồng hồ một số vị trí (nấc). Ví dụ, nếu vòng X được xoay 2 vị trí theo chiều kim đồng hồ thì ta thu được trạng thái như Hình 2b. Hãy hướng dẫn máy tính cách xoay các vòng sao cho thỏa mãn các yêu cầu: (1) đưa được 5 kí tự "*" vào dây MN, (2) đưa được các chữ số vào vòng X, các chữ cái vào vòng Y, và (3) các kí tự chữ số và các chữ cái được sắp thứ tự như trong Hình 2c. * Giải quyết yêu cầu 1 Ý tưởng thuật toán: Lần lượt đưa từng kí tự “*” trong Y (tính cả dây MN) về vị trí 1 của Y, đổi chỗ nó với vị trí 1 của X, rồi quay X theo chiều kim đồng hồ một vị trí để chuyển kí tự “*” đến vị trí 2 của X. Cứ làm như vậy, đến khi X quay được 5 vòng thì tất cả các kí tự “*” chuyển sang X một cách liên tục ở các vị trí 2, 3, 4, 5, 6. Bây giờ ta chỉ việc quay ngược chiều kim đồng đồ vòng X 6 vị trí để chuyển dãy “*” này sang dây MN. Tìm cách mô tả thuật toán giải quyết yêu cầu 1: Trước hết ta cần xác định các thao tác cơ sở riêng của bài toán. Từ cách xoay hình đã cho, ta thấy có 2 thao tác cơ sở được kí hiệu và giải thích như sau: thao tác X(k): xoay vòng X đi k vị trí theo chiều kim đồng hồ (nếu k > 0) và ngược chiều kim đồng hồ (nếu k < 0); và Y(k): xoay vòng Y đi k vị trí, cùng chiều hay ngược chiều kim đồng hồ tương ứng với k > 0 hay k < 0. Theo ý tưởng thuật toán trên đây, để thuận lợi cho việc mô tả thuật toán, ta cần xây dựng thêm hai thao tác cơ bản sau đây: - SW11: là thao tác đổi chỗ hai kí tự ở vị trí 1 tương ứng trên hai vòng X và Y. Có thể suy ra SW11 = X(-1); Y(1); X(1), Y(-1). - Tìm vị trí kí tự “*” trên Y: là thao tác cho biết vị trí của kí tự "*" đầu tiên trên vòng Y, và qui ước vị trí này bằng 0 nếu không tìm thấy kí tự “*” trong Y. Thao tác cơ bản này được xây dựng từ các thao tác cơ sở chung. Thuật toán biểu thị thao tác này là thuật toán tìm kiếm tuần tự - một thuật toán cơ bản trong sách giáo khoa tin học lớp 10. Có thể trình bày sơ lược các thao tác cơ bản mô tả thuật toán để giải quyết yêu cầu 1 như sau: i) Lặp quá trình sau đây khi còn kí tự “*” trên vòng Y: - Tìm vị trí kí tự “*” trên Y và gán cho k; - Nếu k = 1 thì thực hiện hai thao tác SW11 và X(1) để chuyển kí tự “*” sang vị trí 163 Nguyễn Chí Trung 1, rồi sang vị trí 2 của vòng X; - Nếu k ≤ 7 (tức là kí tự * không thuộc dây MN) thì thực hiện dãy các thao tác Y(k-1); SW11; X(1) để lần lượt chuyển kí tự “*” đến vị trí 1 của vòng Y, rồi vị trí 1, rồi vị trí 2 trên vòng X; - Nếu 8 ≤ k ≤ 12 (tức là kí tự “*” nằm trên dây MN) thì thực hiện dãy các thao tác Y(-(k-7)); SW11; X(1) để chuyển được kí tự “*” đến các vị trí như bước 1.3; ii) Thực hiện thao tác X(-6) để chuyển dãy kí “*” sang dây MN. * Giải quyết yêu cầu 2 Ý tưởng thuật toán: Tiến hành đổi chỗ tất cả các cặp kí tự (chữ cái trên X, chữ số trên Y) sao cho giữ nguyên dây MN. Liệu ý tưởng này có thực hiện được không? Câu hỏi này chỉ có thể trả lời nhờ việc phân tích sâu hơn khi tìm cách mô tả thuật toán thể hiện ý tưởng đã nêu. Tìm cách mô tả thuật toán giải quyết yêu cầu 2: Sau khi đã đưa được các kí tự “*” vào dây MN, ta có thể suy nghĩ cách chuyển các chữ số sang vòng X và các chữ cái sang vòng Y. Chỉ có một chỗ “bế tắc” trong hướng giải quyết, đó là khi xoay các vòng X và Y để đưa được một kí tự đến vị trí mong muốn nào đó, thì các kí tự khác bị thay đổi vị trí so với vị trí mà trước đó ta đã chuyển nó đến, và ta mong đợi nó sẽ đứng cố định ở đấy. Vậy ta phải tìm ra được các thao tác mới mà nó có khả năng đổi chỗ được một số vị trí nào đó trong cấu hình sao cho một phần được chú trọng trong cấu hình phải được giữ nguyên. Phần không cần chú trọng trong cấu hình là dây MN vì sự đổi chỗ các kí tự “*” trên dây MN vẫn giữ nguyên tính chất “dây MN chỉ bao gồm các kí tự ‘*’ ”. Theo ý tưởng thuật toán, ta mong muốn có một thao tác, kí hiệu là XY(i,j), có khả năng đổi chỗ được kí tự ở vị trí i trên vòng X với kí tự ở vị trí j trên vòng Y, sao cho, trừ đoạn chung MN, các kí tự còn lại trên vòng X và Y giữ nguyên. Các thao tác X(k), Y(k) và SW11 không đủ để xây dựng XY(i,j). Bằng con đường suy diễn lùi, ta có thể suy ra được dãy các thao tác cần xây dựng sau đây: - Thao tác đổi chỗ kí tự thứ i trên vòng X với kí tự ở vị trí 1 trên vòng Y, sao cho trừ đoạn chung MN, các kí tự còn lại trên X và Y được giữ nguyên: PX(i) = X(-i+1); SW11; X(i-1) - Thao tác đổi chỗ kí tự thứ j trên vòng Y với kí tự ở vị trí 1 trên vòng X, sao cho trừ đoạn chung MN, các kí tự còn lại trên X và Y được giữ nguyên: PY(j) = Y(-j+1); SW11; Y(j-1) - Thao tác đổi chỗ kí tự thứ i trên vòng X với kí tự thứ j trên vòng Y, sao cho trừ đoạn chung MN, các kí tự còn lại trên X và Y được g