Download miễn phí 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
Mụclục
Danhmục cácbảng biểu . . . . . . . . . . . . . . .6
Danhmục các hìnhvẽ . . . . . . . . . . . . . . . .8
Chương1 Tổng quan . . . . . . . . . . . . . . . 10
1.1 Giới thiệu. . . . . . . . . . . . . . . . 10
1.2 Mộtsố khái niệm và nghiêncứu liên quan . . . . . . . . 11
1.2.1 Mộtsố khái niệm. . . . . . . . . . . . . 11
1.2.1.1 Lập trìnhtổng quát . . . . . . . . . . . . 11
1.2.1.2 Mẫu thiếtkếhướng đốitượng . . . . . . . . . 13
1.2.1.3 Khung thuật giải . . . . . . . . . . . . . 18
1.2.2 Mộtsố công trình nghiêncứu liên quan . . . . . . . . 19
1.2.2.1 Mộtsố nghiêncứuvềtổng quát hóadữ liệu . . . . . . 19
1.2.2.2 Mộtsố nghiêncứuvềtổng quát hóa thuật giải . . . . . 22
1.2.2.3 Mộtsố nhận xét . . . . . . . . . . . . . 25
1.3 Phạm vi nghiêncứu . . . . . . . . . . . . . . 27
1.4 Ý nghĩa khoahọccủa luậnvăn . . . . . . . . . . . 27
1.5 Nội dungcủa luậnvăn . . . . . . . . . . . . . 28
Chương2 Xâydựng khung thuật giải . . . . . . . . . . . 30
2.1 Xây dựng khung thuật giảitổng quát . . . . . . . . . . 30
2.2 Mộtsố khung thuật giảicụ thể . . . . . . . . . . . 32
2.2.1 Khung thuật giải chia để trị . . . . . . . . . . . 32
2.2.2 Khung thuật giải quay lui . . . . . . . . . . . . 36
2.2.3 Khung thuật giải quy hoạch động . . . . . . . . . . 39
4
2.2.4 Khung thuật giải tham lam . . . . . . . . . . . 41
Chương3 Thiếtlậpmộtsố thuật giảisắpxếp . . . . . . . . . 44
3.1 Họ thuật giảisắpxếp . . . . . . . . . . . . . . 44
3.2 Thuật giảisắpxếp và phương pháp chia để trị . . . . . . . . 45
3.3 Thuật giảisắpxếptổng quát . . . . . . . . . . . . 47
3.3.1 Xâydựng khung thuật giảisắpxếp . . . . . . . . . 47
3.3.2 Các thuật giảisắpxếpcụ thể . . . . . . . . . . . 49
3.4 Một khung thuật giảisắpxếp phâncấphơn . . . . . . . . 51
Chương4 Thiếtlậpmộtsố thuật giải tìm kiếm . . . . . . . . . 53
4.1 Họ thuật giải tìm kiếm . . . . . . . . . . . . . 53
4.2 Xây dựng thuật giải tìm kiếmtổng quát . . . . . . . . . 56
4.3 Các thuật giải tìm kiếm cụ thể . . . . . . . . . . . . 59
4.3.1 Thuật giải tìm kiếm ưu tiên chiều sâu . . . . . . . . . 59
4.3.2 Thuật giải tìm kiếm ưu tiên chiềurộng . . . . . . . . 60
4.3.3 Thuật giải tìm kiếm ưu tiênlựa chọntốt nhất . . . . . . . 61
4.3.3.1 Thuật giải tìm kiếm ưu tiênlựa chọntốt nhấttổng quát . . . 61
4.3.3.2 Thuật giải A* . . . . . . . . . . . . . 63
4.3.4 Thuật giải tìm kiếmcụcbộ . . . . . . . . . . . 63
4.3.4.1 Thuật giải tìm kiếm cụcbộtổng quát . . . . . . . . 63
4.3.4.2 Thuật giải leo đồi . . . . . . . . . . . . 64
4.4 Tổngkết . . . . . . . . . . . . . . . . . 66
Chương5 Thiếtlậpmộtsố thuật giải tìm kiếm trên đồ thị . . . . . . 67
5.1 ồ thị và bài toán tìm kiếm trên đồ th ị . . . . . . . . . 67
5.2 Thuật giải tìm kiếm trên đồ th ịtổng quát . . . . . . . . . 68
5.3 Các thuật giải tìm kiếm đồ th ịcụ th ể . . . . . . . . . . 71
5.3.1 Thuật giải tìm kiếm ưu tiên chiều sâu . . . . . . . . . 71
5.3.2 Thuật giải tìm kiếm ưu tiên chiềurộng . . . . . . . . 72
5.3.3 Thuật giải tìm đường đi ngắn nhấtDijkstra . . . . . . . 72
5.3.4 Thuật giải tìm cây khung ngắn nhất Prim . . . . . . . . 73
5.4 Kết lu ận . . . . . . . . . . . . . . . . . 73
Chương6 Kết luận . . . . . . . . . . . . . . . . 74
6.1 Kết quả đạt được . . . . . . . . . . . . . . . 74
6.2 Hạn chế vàhướng phát triển . . . . . . . . . . . . 75
Tài liệu tham khảo . . . . . . . . . . . . . . . . 76
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-10-26-luan_van_ap_dung_cac_mau_thiet_ke_huong_doi_tuong.EqC7Tn7WUD.swf /tai-lieu/de-tai-ung-dung-tren-liketly-42507/Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung:
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 hay 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, hay 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ề … hay 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ể hay 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
