Luận văn Áp dụng các mẫu thiết kế hướng đối tượng trong việc thiết lập các thuật toán tổ hợp

10 Chương 1 Tổng quan Nội dung của Chương 1 trình bày tổng quan về bài toán vận dụng các mẫu thiết kế hướng đối tượng vào việc thiết lập các thuật giải tổ hợp; một số khái niệm và các nghiên cứu liên quan; đồng thời nêu lên mục đích, nội dung và ý nghĩa của đề tài. 1.1 Giới thiệu Mẫu thiết kế hướng đối tượng [10] là một trong những thuật ngữ được nhắc đến nhiều nhất hiện nay trong việc thiết kế phần mềm. Việc sử dụng những mẫu thiết kế này giúp ta có được những hệ thống phần mềm mạnh mẽ, có tính tương thích và khả năng tái sử dụng cao. Do đó, áp dụng mẫu thiết kế hướng đối tượng vào một số lĩnh vực trong công nghệ phần mềm cũng là đề tài đang được các nhà nghiên cứu trong và ngoài nước thực hiện. 11 Bên cạnh đó, các thuật giải tổ hợp1 cơ bản [28,29,31] như các thuật giải tìm kiếm, sắp xếp, các thuật giải trên đồ thị … lại là những vấn đề kinh điển, mà hầu hết các sinh viên chuyên ngành Tin học đều phải nắm vững trong những năm đầu tiên của chương trình học. Tuy nhiên, hầu hết các tài liệu giảng dạy của các môn học này hiện nay đều hướng dẫn sinh viên tiếp cận theo phương pháp truyền thống, giải từng bài toán cụ thể bằng những đoạn chương trình riêng lẻ. Với mong muốn đem lại một góc nhìn khác đối với các bài toán này, luận văn đề cập đến việc áp dụng các mẫu thiết kế hướng đối tượng vào việc tái thiết lập các thuật giải tổ hợp, góp phần vào việc nghiên cứu và giảng dạy một số môn cơ sở ngành Tin học. Trong đó, những thuật giải này sẽ là những trường hợp đặc biệt hóa từ một thuật giải tổng quát chứa những điểm chung nhất về mặt bản chất của chúng được gọi là khung thuật giải. Từ khung thuật giải này, chúng ta có thể thiết lập lại các thuật giải cụ thể với sự cài đặt tối thiểu mà vẫn giữ được độ chính xác và tính tối ưu của chúng. 1.2 Một số khái niệm và nghiên cứu liên quan 1.2.1 Một số khái niệm 1.2.1.1 Lập trình tổng quát Lập trình tổng quát [6] hiện nay đang là một mô hình được lựa chọn cho việc phát triển và xây dựng những bộ thư viện mạnh mẽ, linh hoạt và dễ bảo trì, nâng cấp. Đây cũng là một hình thức của phương pháp lập trình nhấn mạnh việc thiết kế và hiện thực chương trình máy tính bằng cách tổng quát hóa, trừu tượng hóa từ các đối 1 Hiện nay thuật ngữ “thuật toán tổ hợp” bao gồm các thuật toán như tìm kiếm, sắp xếp, các thuật toán tối ưu hóa rời rạc, các thuật toán trên đồ thị nói chung, thuật toán quy hoạch động, các thuật toán trên siêu đồ thị (hypergraph), các thuật toán biến đổi đồ thị (graph transformation),… Nói chung đó là các thuật toán thao tác trên các cấu trúc rời rạc mà không gian tìm kiếm có khả năng bùng nổ tổ hợp. Đối với cộng đồng nghiên cứu đây là một thuật ngữ quen thuộc, được dùng thông dụng, mặc dù người ta không định nghĩa một cách hình thức. 12 tượng dữ liệu hoặc thuật giải cụ thể. Lập trình tổng quát phụ thuộc chủ yếu vào phương pháp tổng quát hóa thuật giải, được phân thành hai loại như sau [23]: · Loại 1: Tổng quát hóa thuật giải dựa trên dữ liệu. Ví dụ: thuật giải tổng quát trên cấu trúc dãy tuần tự, thuật giải tổng quát trên cấu trúc cây, thuật giải tổng quát trên cấu trúc đồ thị… · Loại 2: Tổng quát hóa thuật giải dựa trên chiến lược giải quyết bài toán. Ví dụ: thuật giải chia để trị tổng quát, thuật giải quy hoạch động tổng quát, thuật giải tham lam tổng quát … Trong loại 1 của lập trình tổng quát, nguyên lý cơ bản là sẽ tách biệt thuật giải ra khỏi các cấu trúc dữ liệu cụ thể và hoạt động trên những cấu trúc dữ liệu trừu tượng. Có nghĩa là trong các chương trình xây dựng theo nguyên lý này, các thuật giải sẽ không thao tác trên các cấu trúc dữ liệu cụ thể một cách trực tiếp mà thay vào đó, nó sẽ thao tác trên các lớp trừu tượng được định nghĩa tương đương Nhờ vậy, thuật giải tổng quát có thể được áp dụng với bất kì cấu trúc dữ liệu nào phù hợp với đặc tả chung trên. Ví dụ: thuật giải sắp xếp tổng quát áp dụng với bất kì cấu trúc dữ liệu truy xuất ngẫu nhiên và các đối tượng so sánh được nào, hoặc một đối tượng đồ thị trừu tượng có thể được cụ thể hóa thành đối tượng đồ thị cài đặt theo ma trận kề, danh sách cạnh, danh sách kề … hoặc ngược lại. Còn ở loại 2, thuật giải tổng quát xây dựng bằng việc xác định những chiến thuật cơ bản của một họ thuật giải. Những chiến lược này sẽ được trừu tượng hóa từ các chiến lược cụ thể của các thuật giải trong họ. Những trường hợp đặc biệt hóa của thuật giải tổng quát sẽ trở thành những thuật giải cụ thể hoặc trở thành những thuật giải tổng quát khác. Mỗi khác nhau trong quá trình đặc biệt hóa sẽ đem lại những thuật giải khác nhau. Ví dụ: thuật giải sắp xếp nhanh, thuật giải sắp xếp trộn hay thuật giải tìm kiếm nhị phân về mặt bản chất đều được giải quyết theo phương pháp chia để trị, đều chia bài toán thành những bài toán con nhỏ hơn và lần lượt giải quyết nó. Do vậy, chúng ta có thể xây dựng một thuật giải chia để trị tổng quát mà 13 trong đó ứng với mỗi trường hợp chia nhỏ bài toán hay giải quyết bài toán con sẽ trở thành các thuật giải cụ thể này. 1.2.1.2 Mẫu thiết kế hướng đối tượng Thiết kế phần mềm là một vấn đề rất khó khăn, nhất là đối với các phần mềm lớn có nhiều mối quan hệ giữa các phần tử. Trong trường hợp này, các bản thiết kế thường không hiệu quả dẫn đến phải trả giá cao khi phát sinh lỗi. Phương pháp lập trình hướng đối tượng cung cấp cơ chế để có thể xây dựng được phần mềm linh hoạt, dễ nâng cấp và bảo trì. Tuy nhiên việc xây dựng những phần mềm như thế phụ thuộc nhiều vào khả năng người thiết kế. Một trong những biện pháp để có được những thiết kế tốt là tận dụng lại những thiết kế của các chuyên gia đã kiểm nghiệm qua thực tế, gọi là “mẫu thiết kế” (design pattern). Những mẫu thiết kế thường đã được sử dụng và được đánh giá tốt, giúp giải quyết những vấn đề thiết kế thường gặp. Ngoài ra, nó không chỉ giúp cho bản thiết kế đáp ứng yêu cầu mà còn chú trọng việc giúp cho bản thiết kế có tính uyển chuyển, dễ nâng cấp, thay đổi, trở thành một giải pháp tin cậy, tiết kiệm nguồn lực cho các chuyên gia phát triển phần mềm. Khái niệm về mẫu thiết kế được Christopher Alexander đưa ra vào những năm 1970 trong xuất bản A Pattern Language và A Timeless Way of Building, và trở nên phổ biến khi Gang of Four – GoF tổng hợp và xuất bản vào năm 1995 [10]. Mẫu thiết kế có thể được phân loại như sau: · Mẫu thiết kế hướng đối tượng o Kiến tạo – Khắc phục các vấn đề khởi tạo đối tượng, hạn chế sự phụ thuộc platform. o Cấu trúc – Cung cấp cơ chế xử lý những lớp không thể thay đổi (lớp thư viện của third party…), ràng buộc muộn (lower coupling) và cung cấp các cơ chế khác để thừa kế. 14 o Hành vi – Che dấu hiện thực của đối tượng, che dấu thuật giải, hỗ trợ việc thay đổi cấu hình đối tượng một cách linh động. · Mẫu thiết kế phân tích · Mẫu thiết kế tổ chức · Mẫu thiết kế quy trình GoF đã tổng hợp và đưa ra 23 mẫu thiết kế hướng đối tượng. Một mẫu GoF thường bao gồm những thuộc tính sau: tên/phân loại, mục đích sử dụng, tình huống cụ thể và khả năng ứng dụng, cấu trúc bằng UML và mã nguồn minh họa ... Trong khuôn khổ của luận văn, chúng tôi tập trung chủ yếu vào một số mẫu thiết kế kinh điển như sau: · Mẫu thiết kế ℎ [10] được sử dụng để xác định khung của một thuật giải thành nhiều bước, nhượng lại việc thực hiện một số bước ở lớp con và cho phép các lớp con tái định nghĩa một số bước trong thuật giải mà không làm thay đổi cấu trúc tổng quát. · Mẫu thiết kế [10] được sử dụng để xác định một họ các thuật giải, đóng gói mỗi thuật giải thành một đối tượng có thể thay thế lẫn nhau và cho phép biến đổi thuật giải một cách độc lập. Hình 1-1 Mẫu thiết kế Strategy và mẫu Template Method [20] 15 · Mẫu thiết kế [10] là một mẫu thiết kế cho phép thêm các thao tác mới vào một thao tác có sẵn một cách linh động. Mẫu này làm việc bằng cách đóng gói đối tượng gốc vào trong một đối tượng "trang trí" bằng cách truyền đối tượng gốc như một tham số tới hàm khởi tạo của đối tượng “trang trí”, và chính đối tượng “trang trí” này sẽ thực thi các hàm của nó trước khi gọi lại đối tượng gốc. Mẫu này thường được vận dụng trong việc minh họa trực quan các thuật giải. · Mẫu thiết kế [10] là mẫu thiết kế cho phép truy xuất các phần tử của đối tượng dạng tập hợp tuần tự (list, array, …) mà không phụ thuộc vào biểu diễn bên trong của các phần tử Hình 1-2 Mẫu Iterator [10] · Mẫu thiết kế [10] là mẫu thiết kế cho phép định nghĩa thêm phép toán mới tác động lên các phần tử của một cấu trúc đối tượng mà không cần thay đổi các lớp định nghĩa cấu trúc đó Hình 1-3 Mẫu Visitor[10] 16 Những mẫu thiết kế còn lại có thể tham khảo trong sơ đồ 2-4 sau: Hình 1-4 23 mẫu thiết kế GoF và sự liên hệ giữa chúng [10] Ngoài ra, ngày nay các nhà lập trình viên cũng đã đóng góp thêm nhiều mẫu thiết kế hướng đối tượng ngoài 23 mẫu mà GoF đã đưa ra. Đa số những mẫu này đều có nguồn gốc từ mẫu GoF, có thể là dạng biến thể của một mẫu GoF hay là sự phối hợp một cách hợp lý các mẫu GoF để giải quyết các vấn đề trong thiết kế hướng đối tượng. 17 · Mẫu thiết kế [34] là mẫu dưa trên ý tưởng chủ đạo vẫn từ mẫu của GoF. Mẫu này chia ứng dụng ra làm ba thành phần: , và . Các thành phần của kiến trúc MVC một trách nhiệm duy nhất và không phụ thuộc vào các thành phần khác. Những sự thay đổi trong một thành phần sẽ không có hoặc là có rất ít ảnh hưởng đến các thành phần khác. có nhiệm vụ lưu trữ và thực hiện các nghiệp vụ liên quan đến dữ liệu; có nhiệm vụ hiển thị thông tin và là tầng trung gian giữa và : nhận yêu cầu từ client, gọi thực hiện yêu cầu ở , sinh ra kết quả và được hiển thị ở . Hình 1-5 Mẫu Observer [10] và mẫu MVC [34] · Mẫu thiết kế và [32] là hai mẫu thiết kế dùng để trừu tượng hóa vị trí của những phần tử trong các lớp chứa. 18 Hình 1-6 Mẫu Positions [32] và mẫu Locators [32] 1.2.1.3 Khung thuật giải Khung thuật giải là bản thu hẹp của khung phần mềm [4] dành riêng cho mô hình các bài toán và thuật giải. Khung thuật giải được xây dựng từ việc kết hợp những ý tưởng cơ bản của lập trình tổng quát và các mẫu thiết kế hướng đối tượng, bao gồm những đoạn mã nguồn có thể được dễ dàng tái sử dụng và những giao diện lập trình ứng dụng ( ) được định nghĩa tốt. Khung thuật giải thường đưa ra một thuật giải tổng quát theo phương pháp lập trình tổng quát loại 2 (xem mục 2.1.1) và từ đó, các thuật giải cụ thể được xây dựng tương ứng, kế thừa từ thuật giải tổng quát này. Hình 2-7 minh họa một khung thuật giải cho các thuật giải duyệt cây nhị phân sử dụng mẫu thiết kế . Trong đó, lớp được xem là lớp khung biểu diễn thuật giải tổng quát duyệt cây nhị phân. Các thuật giải , , , ℎ … là những thuật giải cụ thể tương ứng với mỗi cách duyệt cây nhị phân, kế thừa từ thuật giải tổng quát 19 Hình 1-7 Khung thuật giải duyệt cây nhị phân [4] 1.2.2 Một số công trình nghiên cứu liên quan 1.2.2.1 Một số nghiên cứu về tổng quát hóa dữ liệu Các ngôn ngữ lập trình hiện đại hiện nay như C++, Java, C# … hoặc một số ngôn ngữ lập trình tổng quát đặc thù như ML, Haskell … đều hầu như hỗ trợ rất mạnh việc tổng quát hóa dữ liệu bằng việc tích hợp sẵn các khuôn mẫu, các lớp dữ liệu trừu tượng vào trong bộ thư viện của mình. Sự hỗ trợ này có thể xem trong bảng 2-1. Bảng 1-1 So sánh mức hỗ trợ lập trình tổng quát giữa các ngôn ngữ [11] 20 Một trong những bộ thư viện điển hình có thể kể đến là thư viện khuôn mẫu chuẩn của + + ( – [17]). Trong bộ thư viện này, các cấu trúc dữ liệu được trừu tượng hóa thành các lớp chứa ( ) như và và giao tiếp xử lí với các thuật giải thông qua các giao diện . Mỗi thuật giải trong sẽ được viết lại theo các này và do đó tất cả các thuật giải đều có thể thao tác với bất kì lớp chứa nào của . Thêm vào đó, nhiều thuật giải được trừu tượng hóa không chỉ trên các kiểu và còn trên cả các toán tử qua các hàm đối tượng ( ). Các biến hàm này giúp chúng ta dễ dàng thay đổi các hàm thành phần của đối tượng, ví dụ như khi phải thay đổi các kiểu so sánh phần tử trong các thuật giải sắp xếp chẳng hạn … hiện tại có sẵn trong bộ thư viện chuẩn của ngôn ngữ + + và đang được sử dụng rộng rãi. Do chỉ cung cấp những cấu trúc dữ liệu và thuật giải cơ bản, nên việc mở rộng nó cũng là đề tài rất được quan tâm của các chuyên gia lập trình. Những mở rộng nổi bật của STL có thể được kể ra như sau: [19] cho các thuật giải tổ hợp và hình học phức tạp, [16] cho cấu trúc dữ liệu đồ thị và thuật giải trên đó, [18] cho các bài toán đại số tuyến tính. Hình 1-8 So sánh kiến trúc giữa STL và GGCL [27] Ngoài ra, các ngôn ngữ lập trình tổng quát khác như Java cũng cung cấp một số thư viện hỗ trợ như − (bộ thư viện lập trình tổng quả của dựa trên ) hoặc ℎ − ) của alphaWork (thư viện lập trình cho các bài toán trên đồ thị), 21 – (thư viện cấu trúc dữ liệu cho Java )… Trong đó, 2.0 [32] được xem là bộ thư viện khá đầy đủ co các cấu trúc dữ liệu và thuật giải dành cho ngôn ngữ này. Những cấu trúc hỗ trợ bao gồm: Dãy (Danh sách, Vector), Cây, Hàng đợi ưu tiên, Từ điển (Bảng hash, Cây đỏ - đen), Đồ thị … Để duyệt các cấu trúc này cung cấp hai công cụ là Iterators và Accessors (dựa theo hai khái niệm đồng tên của STL và LEDA). Các thuật giải cơ bản trong các cấu trúc này cũng được hỗ trợ: sắp xếp, tìm kiếm, đường đi ngắn nhất và cây bao trùm ngắn nhất trong đồ thị … Ta có thể so sánh mức độ hỗ trợ hỗ trợ lập trình tổng quát cho các bài toán cấu trúc dữ liệu và thuật giải giữa các thư viện trong Bảng 2-2 sau: STL LEDA GGCL GFC JGL JDSL Sequences (lists, vectors) ü ü ü ü ü ü General-purpose trees ü ü ü ü ü Priority queues (heaps) ü ü ü ü ü Dictionaries ü ü ü ü Sets ü ü Graphs ü ü ü ü Templated algorithms ü ü ü Sorting algorithms ü ü ü ü Data permutation algorithms ü ü ü Graph traversals ü ü ü ü Shortest path, Minimum spanning tree ü ü ü Graph drawing algorithms ü ü ü Iterators ü ü ü ü ü Accessors (positions and locators) ü Decorations ü ü ü Bảng 1-2 So sánh mức độ hỗ trợ lập trình tổng quát thuật giải của các thư viện 22 1.2.2.2 Một số nghiên cứu về tổng quát hóa thuật giải Khác với các nghiên cứu ở mục 2.2.1, các nghiên cứu được trình bày ở phần này tập trung về phần tổng quát hóa các thuật giải dựa trên những sự tương đồng về mặt bản chất của nó (lập trình tổng quát loại 3). Đầu tiên, có thể kể đến những công trình của S. Merritt, K. K. Lau và các cộng sự [14-15, 20-21]. Trong những loạt bài báo này, các tác giả đã đưa ra cách phân loại “nghịch” của các thuật giải sắp xếp khác với phân loại “thuận” kinh điển của Knuth [28,29]. Hình 1-9 Phân loại "thuận" [27] và "nghịch" [20] các thuật giải sắp xếp Ở cách phân loại này, các tác giả đã chỉ ra rằng đa phần các thuật giải sắp xếp đều có thể viết lại theo hai thuật giải chính là và . Trong đó, là một trường hợp “đơn” của và là một trường hợp đơn của với sự phân chia hai dãy con theo tỉ lệ [1, − 1]. Hơn nữa, và sẽ là trường hợp in-place (sắp xếp trực tiếp) của và . Việc minh họa bằng ngôn ngữ lập trình cụ thể của sự phân loại này được thể hiện rõ trong công trình của N. Dzung và S. Wong [17]. Các tác giả đã sử dụng mẫu thiết kế ℎ để cài đặt ý tưởng đã đưa ra S. Merritt và K. K. Lau. Các lớp thuật giải sắp xếp được kế thừa từ lớp thuật giải sắp xếp trừu tượng đã cài đặt sẵn phương thức (). Phương thức này sẽ lặp việc chia đôi dãy thông qua phương thức ảo (), thực hiện việc sắp xếp trên hai dãy con này và ghép lại 23 thông qua phương thức ảo (). Mỗi thuật giải sắp xếp cụ thể kế thừa từ ASorter sẽ phải cài đặt lại hai phương thức này tương ứng theo chiến lược sắp xếp của mình, Hình 1-10 Cài đặt phân loại "nghịch" các thuật giải sắp xếp [17] Cũng với bài toán tổng quát hóa các thuật giải sắp xếp, nhưng nhóm tác giả S. Rajsbaum và E. Viso [27] lại theo hướng tiếp cập khác. Các tác giả này cho rằng một số thuật giải sắp xếp như , và có thể là một trường hợp đặc biệt của , chỉ khác ở cách chọn phần tử và đưa vào danh sách được sắp. Cách cài đặt này của các tác giả cũng sử dụng mẫu thiết kế ℎ (xem hình 2-11), trong đó lớp biểu diễn thuật giải sắp xếp tổng quát là với hai phương thức ảo nhượng quyền xử lý cho lớp con là () và (). 24 Hình 1-11 Tổng quát hóa một số thuật giải sắp xếp dựa SelectionSort [26] Một bài toán khác trong lĩnh vực này là tổng quát hóa các thuật giải trên đồ thị. Đối với bài toán tìm cây bao trùm tối tiểu của đồ thị, nhóm tác giả [22] đã đưa ra ba điều kiện để đồ thị con = ( , ) trở thành cây bao trùm tối tiểu của đồ thị = ( , ): (1) là cây, (2) phủ nghĩa là = và (3) tối tiểu. Đồng thời nhóm tác giả cũng chỉ ra rằng các thuật giải tìm kiếm cây bao trùm nổi tiếng sử dụng 2 trong 3 điều kiện này để làm điều kiện bất biến trong bước lặp. Cụ thể, trong mỗi bước lặp của mình, thuật giải Kruskal sẽ đảm bảo trên đồ thị con chứa các đỉnh của (2) và chọn lựa các cạnh để được tối tiểu (3) (dĩ nhiên là cách chọn này sẽ không đảm bảo được điều kiện (1)). Còn với thuật giải Prim, điều kiện (1), (3) là điều kiện bất biến trong bước lặp và không thỏa điều kiện (2). 25 Cũng với bài toán duyệt đồ thị, S. Rajsbaum và E. Viso [27] đã chỉ ra rằng các thuật giải như , , , hay đều có thể là một trường hợp cụ thể của thuật giải duyệt đồ thị tổng quát . Trong đó ở mỗi bước lặp các thuật giải sẽ chọn một cạnh trong (danh sách cạnh được khởi tạo ban đầu) và kết thúc khi rỗng. Tùy vào cách chọn mỗi cạnh và cập nhật lại sau khi đã chọn sẽ cho chúng ta một thuật giải cụ thể. Hình 1-12 Tổng quát hóa thuật giải tìm kiếm trên đồ thị [26] Trong khi các tác giả trên tập trung vào từng nhóm thuật giải giải quyết một bài toán, thì nhóm Cunningham, Liu & Zhang trong [2-3] tập trung vào một phương pháp giải toán cụ thể là phương pháp chia để trị. Nhóm tác giả này đã vận dụng mẫu thiết kế để xây dựng thành một khung thuật giải chia để trị tổng quát, áp dụng cho các thuật giải liên quan như tìm kiếm nhị phân, sắp xếp nhanh, sắp xếp trộn. 1.2.2.3 Một số nhận xét Đối với bài toán tổng quát hóa các thuật giải sắp xếp, N. Dzung và S. Wong [8] đã trừu tượng hóa thành công các thuật giải sắp xếp bằng cách sử dụng mẫu thiết kế ℎ dựa trên ý tưởng của S. Merritt và K. K. Lau [13,19]. Tuy nhiên cách trừu tượng hóa này tương đối “phẳng” không thể hiện được sự kế thừa rõ nét giữa các thuật giải với nhau, chẳng hạn thuật giải nên được kế thừa từ thay vì kế thừa trực tiếp từ lớp tổng quát … Điều này dẫn đến việc vẫn tồn tại sự trùng lắp mã nguồn khi cài đặt của các tác giả. Còn 26 trong các công trình của S. Rajsbaum và E. Viso [27] thì số lượng thuật giải được tổng quát chưa được nhiều và chỉ nằm trong một chiến lược sắp xếp là chọn và chèn phần tử được chọn vào dãy được sắp. Đối với bài toán tổng quát hóa thuật giải tìm kiếm trên đồ thị, S. Rajsbaum và E. Viso [27] tuy đã tổng quát hóa một số thuật giải như , , , … Tuy nhiên, theo ý chúng tôi, phương pháp tổng quát hóa này chưa được tự nhiên gây nhiều khó khăn việc sử dụng. Những thuật giải này có thể được trừu tượng hóa một cách đơn giản hơn dựa trên những ý tưởng về đã trình bày trong những cuốn sách kinh điển về đồ thị của D. Knuth hay R. Sedgewick [27, 28]. Khái niệm về khung thuật giải được nhóm tác giả H. C. Cunningham, Y. Liu và C. Zhang [2-4] tuy không là ý tưởng mới nhưng lại trở nên khá thú vị khi áp dụng vào các thuật giải kinh điển. Trong loạt bài báo này, các tác giả đã vận dụng những phương pháp xây dựng khung phần mềm kết hợp với một số mẫu thiết kế để đưa ra khung thuật giải tổng quát. Sinh viên khi đã được tiếp cận với khái niệm này sẽ trở nên dễ dàng hơn với các bài toán kinh điển cũng như các khái niệm về khung phần mềm hiện đại. Tổng kết các công trình nghiên cứu quan trọng trong hướng tổng quát hóa thuật giải này được liệt kê ở bảng 2-3 sau: Mức độ tổng quát hóa thuật giải Các mẫu thiết kế được vận dụng Merritt & Lau [14,20] Các thuật giải sắp xếp: MergeSort, InsertionSort, SinkingSort, QuickSort, SelectionSort, BubbleSort theo phưong pháp chia để trị Không Dzung & Wong [8] Cài đặt ý tưởng tổng quát hóa của Merritt & Lau [13,19] Template Method State Rajsbaum & Viso [26] Các thuật giải sắp xếp: SelectionSort, BubbleSort, HeapSort, InsertionSort theo Template Method 27 phương pháp chọn và chèn. Rajsbaum & Viso [26] Các thuật giải duyệt đồ thị: DFS, BFS, Dijkstra và Prim theo phương pháp chọn cạnh trong border và lan cạnh ra sau mỗi bước chọn Template Method Cunningham, Liu & Zhang [2] Khung thuật giải chia để trị: BinarySearch, QuickSort và MergeSort Strategy Cunningham, Liu & Zhang [4] Khung thuật giải duyệt cây nhị phân: Euler, BreathFirst, DepthFirst Visitor Bảng 1-3 Bảng tổng kết một số kết quả nghiên cứu về tổng quát hóa thuật giải 1.3 Phạm vi nghiên cứu Do danh mục các thuật giải tổ hợp rất rộng, nên trong khuôn khổ của luận văn, chúng tôi tập trung vào hai vấn đề chính: thứ nhất, luận văn xây dựng khung thuật giải cho một số các thuật giải kinh điển như chia để trị, quay lui, tham lam, quy hoạch động … và áp dụng cụ thể vào việc tổng quát hóa thuật giải tìm kiếm, sắp xếp trên mảng; thứ hai, luận văn đề xuất phương pháp tái thiết lập các thuật giải tổ hợp như thuật giải tìm kiếm tổng quát và thuật giải duyệt đồ thị tổng quát. 1.4 Ý nghĩa khoa học của luận văn Việc thiết lập các thuật giải tổ hợp bằng cách áp dụng các mẫu thiết kế hướng đối tượng, xây dựng thành các khung thuật giải mang lại một số ý nghĩa sau: · Nhằm có một thiết kế trừu tượng và tổng quát hóa các thuật toán tổ hợp bằng cách dựa vào các mẫu thiết kế. Sự trừu tượng hóa này sẽ giúp chúng ta nhận ra được những điểm chung (khía cạnh tổng quát hóa) và đặc điểm riêng (khía cạnh đặc biệt hóa) của các thuật toán thông dụng. Nhờ vậy, có thể dễ dàng hơn trong việc cài đặt mã nguồn hướng đối tượng, tái sử dụng hay đánh giá độ phức tạp các thuật toán. · Nhờ vào những kết quả nói trên, nghiên cứu này sẽ nhằm hướng đến những kết quả lý thuyết về những “định lý khung” tức là những định lý chung cho 28 những thuật toán mà trước đây được phát triển riêng lẻ cho từng thuật toán. Nhờ những định lý khung này, có thể hiểu thêm bản chất và phát triển được những thuật toán mới. Hiện tại, đây chỉ là hướng phát triển của luận văn. 1.5 Nội dung của luận văn Chương đầu tiên của luận văn trình bày về một số khái niệm và các công trình liên quan đến việc lập trình tổng quát, mẫu thiết kế hướng đối tượng và khung thuật giải. Chương thứ hai của luận văn sẽ trình bày về mô hình hướng đối tượng để giải quyết cái bài toán một cách tổng quát, được gọi là khung thuật giải. Việc xây dựng khung thuật giải sẽ chủ yếu dựa vào các mẫu thiết kế hướng đối tượng ℎ và . Chương này cũng đưa ra một số khung thuật giải cho các thuật giải tổ hợp kinh điển như thuật giải chia để trị, thuật giải quay lui, thuật giải quy hoạch động … Trong chương tiếp theo, luận văn đưa ra một khung thuật giải tìm kiếm và sắp xếp dựa trên nguyên lý chia để trị đã trình bày ở chương hai. Các thuật giải tìm kiếm sẽ trở thành các trường hợp đặc biệt của một thuật giải tìm kiếm tổng quát. Tương tự, các thuật giải sắp xếp cũng được tổng quát hóa thành một thuật giải sắp xếp tổng quát, và chúng được tạo nên bởi việc cụ thể hóa hai phương thức trừu tượng “tách” và “ghép” danh sách của thuật giải tổng quát. Luận văn cũng đưa ra một mô hình phân cấp hơn, khi chia các thuật giải sắp xếp thành 3 nhóm: tách danh sách dựa trên giá trị, tách danh sách dựa trên chỉ số và tách danh sách dựa trên giá trị từng phần. Trong đó, các thuật giải , và sẽ thuộc một nhóm, và sẽ thuộc một nhóm. Nhóm còn lại gồm các thuật giải sắp xếp theo cơ số như và . Chương 4 của luận văn trình bày về khung thuật giải cho các thuật giải tổ hợp. Hai khung thuật giải được trình bày là thuật giải tìm kiếm tổng quát và thuật giải duyệt đồ thị tổng quát. Khung thuật giải tìm kiếm được trừu tượng hóa từ các thuật giải tìm kiếm tuần tự tuyến tính đến các thuật giải tìm kiếm heurictisc như thuật giải leo đồi hay thuật giải A*. Chương này cũng đồng thời đưa ra một thuật giải duyệt đồ thị tổng quát có thể duyệt qua tất cả các đỉnh của đồ thị và kết quả trả về là một cây bao 29 trùm của đồ thị đó. Từ đó, chỉ ra rằng các thuật giải tìm kiếm đồ thị như tìm kiếm ưu tiên chiều sâu, tìm kiếm ưu tiên chiều rộng, thuật giải và thuật giải là một trong những trường hợp đặc biệt của thuật giải tổng quát này. Cuối cùng là một số tổng kết và đánh giá kết quả đạt được.