Link tải luận văn miễn phí cho ae Kết nối
Nghiên cứu tổng quan về phương pháp lập trình ràng buộc. Tìm hiểu và đánh giá các hệ thống lập trình ràng buộc. Xây dựng ứng dụng lập lịch giảng dạy đại học sử dụng hệ thống lập trình ràng buộc Comet
Đăng 01 bài báo trên tạp chí Khoa học và Công nghệ. Giúp đỡ 01 khóa luận tốt nghiệp
GIẢI THÍCH CÁC CHŨ VIÉT T Ắ T .......................................................................................................... 3
DANH SÁCH NHỮNG NGƯỜI THAM G IA .......................................................................................... 4
THỰC HIỆN ĐẺ T À I.....................................................................................................................................4
TÓM TẮT NHỪNG KẾT QUÀ CHÍNH CỬA ĐỀ T À I......................................................................... 6
BÁO CÁ O TÓ N G K ẾT..................................................................................................................................7
1. Đặt vấn đề...............................................................................................................................................7
2. Lập trình ràng buộc và hệ thống lập trình ràng buộc Com et........................................................7
2.1 Lập trinh ràng b u ộ c.................................................................................................................... 7
2.2 Hệ thống lập trình ràng buộc C om et.....................................................................................10
3. Áp dụng hệ lập trình ràng buộc Comet vào bài toán lập lịch giảng d ạ y ...........................11
4. Kết luận............................................................................................................................................. 17
5. Địa điềm, thời gian và phương pháp nghiên c ứ u .....................................................................17
6. Kết quả nghiên c ứ u .........................................................................................................................17
6.1 Ket quả khoa học....................................................................................................................17
6.2 Kết quả đào tạo.......................................................................................................................17
7. Tài liệu tham khảo...........................................................................................................................19
PHỤ LỤ C......................................................................................................................................................... 21BÁO CÁO TỎNG KÉT
1. Đ ặt vấn đề
Lập trình ràng buộc (CP) đang nổi iên như một công nghệ giải quyết hiệu quà các bài toán tồ
họp. Lập trình ràng buộc mô tả các ràng buộc cúa bài toán cần thỏa mãn thay vi xác định tuân tự
các bước cần thực hiện như trong lập trình truyền thống. Điều đó mang đến tính linh động trong
việc diễn đạt và giải quyết hiệu quà các bài toán, đặc biệt trong các bài toán gồm nhiều ràng buộc
đa dạng, biến đổi.
Xu hướng hiện nay, các ngành công nghiệp, các lĩnh vực hoạt động sản xuất ứng dụng công
nghệ CP ngày càng tăng lên nhanh chóng, số lượng các công ty ứng dụng thành công công nghệ
này tăng lên hàng năm, có thể kể tên một số còng ty, tồ chức điển hình: sân bay Quốc tế Hong
Kong, British Airway, SAS, Swissair, cảng Quốc tế Hong Kong, Michelin, Dassault, Ericsson
[17] ... Đoi với lĩnh vực hàng không, CP được ứng dụng để lập lịch các chuyến bay, hoạt động
chuyền phát nhanh...Trong công nghiệp sản xuất, CP ứng dụng trong việc quản lý chuỗi cung
ứng sàn xuất, lập lịch, phẩn bồ tài nguyên, nguồn lực. Lĩnh vực sinh học: phân tích phân tử sinh
học (chuồi DNA-protein) [16].
Lập lịch giảng dạy là bài toán không mới, đã được giãi quyết theo nhiều phương pháp
khác nhau như giài thuật di truyền, tìm kiếm cục bộ như leo lúi, luyện thép, Tabu [1, 2, 3], Các
phương pháp này được sử dụng rộng rãi và cho các kết quà tốt. Tuy nhiên các phương pháp này
thường viết cho các đơn vị cụ thể và không dỗ sửa đổi thích nghi (thay đổi dữ liệu hay yêu cầu trong
bài toán có thể yêu cầu phải xem xét lại toàn bộ chương trinh). Lập trình ràng buộc cũng được áp dụng
thành công trong bài toán lập lịch giàng dạy tại các trường đại học [10,11].
Nội dung đề tài sỗ tập trung vào tìm hiểu phương pháp lập trinh ràng buộc, và áp dụng hệ thống lập
trình ràng buộc mới hiện nay là Comet vào bài toán ỉập lịch giảng dạy tại Trường Đại học Công nghệ.
Cấu trúc báo cáo như sau: Phần 2 sẽ mô tả về lập trinh ràng buộc và hệ thống lập trình ràng buộc
Comet. Phần 3 sẽ mô tà áp dụng hệ thống Comet vào giải quyết bài toán lập lịch giảng dạy tại Trường
Đại học Công nghệ.
2. L ậ p trìn h ràn g buộc và hệ thống lập trình ràng buộc Com et
2.1 L ậ p trình ràn g buộc
Trước khi đi vào phương pháp lập trình ràng buộc, chúng ta đề cập tới phương pháp lập trình
truyên thống qua ví dụ minh họa.
Ví dụ: xem xét bài toán 4-queens (4 hậu): vêu cầu đặt 4 quân hậu trên bàn cờ vua kích
thước 4*4 sao cho không có quân hậu nào có thề “ăn" được quân hậu khác. Ta xét bài toán này
trong m ôi trường lập trinh truyền thống (bủng ngôn ngữ lập trình C/C++ hay Java...) với giải
thuật vét cạn, quay lui (backtracking). Tư tướng cơ bàn cùa giải thuật vét cạn, quay lui là ta thừ
đặt một quân cờ vào một ô trong bàn cơ, sau đó lần lượt đặt từng quân cơ tiếp theo vào các ô cờ
khác. Trong trường hợp không thỏa mãn điều kiện ràng buộc cùa bài toán (Không có hai quân cờ
nào “ăn” dược nhau) thì quay lui trớ lại bước trước đó và đặt lại quân cờ sao cho thỏa mãn điều kiện bài toán. Giải thuật này được mô tà trực quan hơn trong một nhánh cùa cây tìm kiếm bài
toán 4-Queens trong Hình ì .
H ình 1. M ột nhánh trong cây tìm kiếm của bài toán 4-Hậu
Trong lập trình truyền thống không hỗ trợ tự động thù tục quay lui, người lập trình phải tự
viết chức năng thực hiện quay lui để tìm kiếm tất cả các lời giải thỏa mãn điều kiện bài toán.
Ý tường cùa lập trình ràng buộc là giải quyêt bài toán bằng cách khai báo các ràng buộc (các
yêu cẩu) cùa bài toán. Lập trình ràng buộc không xác định tuần tự các bước cần thực hiện như
trong lập trình truyền thống. Lập trình ràng buộc bắt đầu từ những năm 90 bằng việc tich họp xừ
lý ràng buộc vào ngôn ngữ logic. Hai mô hình này chia sẽ nhiều đặc điểm quan trọng như biến
logic và thù tục tự động quay lui. Ngày nay hầu hết các cài đặt Prolog phổ biến như Sisctus
Prolog, Eclipse đều tích hợp các thư viện cho lập trinh ràng buộc [4, 5]. Ngoài tích hợp vào ngôn
ngữ logic, lập trình ràng buộc sử dụng cách tiếp cận khác như tích họp với lập trình thủ tục, với
các hệ thống lập trình ràng buộc phổ biến như Gecode [6], Comet [7].
Mô hình lập trình ràng buộc có thể mô tả như sau: Lập trình ràng buộc = M ô hình ràng buộc
+ Tìm kiếm
Ví dụ sau minh họa một bài toán giải bằng phương pháp lập trình ràng buộc, chúng ta
hãy xét m ột bài toán chơi chừ cồ điển
Phưcmg trình cùa bài toán:
s E N D
+ M O R E
= M 0 N E Y
M ồi ký tự thay mặt cho một con sổ khác sau. cần tìm ra giá trị số tương ứng cho từng ký
tự và thòa mãn phương trình trê
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Nghiên cứu tổng quan về phương pháp lập trình ràng buộc. Tìm hiểu và đánh giá các hệ thống lập trình ràng buộc. Xây dựng ứng dụng lập lịch giảng dạy đại học sử dụng hệ thống lập trình ràng buộc Comet
Đăng 01 bài báo trên tạp chí Khoa học và Công nghệ. Giúp đỡ 01 khóa luận tốt nghiệp
GIẢI THÍCH CÁC CHŨ VIÉT T Ắ T .......................................................................................................... 3
DANH SÁCH NHỮNG NGƯỜI THAM G IA .......................................................................................... 4
THỰC HIỆN ĐẺ T À I.....................................................................................................................................4
TÓM TẮT NHỪNG KẾT QUÀ CHÍNH CỬA ĐỀ T À I......................................................................... 6
BÁO CÁ O TÓ N G K ẾT..................................................................................................................................7
1. Đặt vấn đề...............................................................................................................................................7
2. Lập trình ràng buộc và hệ thống lập trình ràng buộc Com et........................................................7
2.1 Lập trinh ràng b u ộ c.................................................................................................................... 7
2.2 Hệ thống lập trình ràng buộc C om et.....................................................................................10
3. Áp dụng hệ lập trình ràng buộc Comet vào bài toán lập lịch giảng d ạ y ...........................11
4. Kết luận............................................................................................................................................. 17
5. Địa điềm, thời gian và phương pháp nghiên c ứ u .....................................................................17
6. Kết quả nghiên c ứ u .........................................................................................................................17
6.1 Ket quả khoa học....................................................................................................................17
6.2 Kết quả đào tạo.......................................................................................................................17
7. Tài liệu tham khảo...........................................................................................................................19
PHỤ LỤ C......................................................................................................................................................... 21BÁO CÁO TỎNG KÉT
1. Đ ặt vấn đề
Lập trình ràng buộc (CP) đang nổi iên như một công nghệ giải quyết hiệu quà các bài toán tồ
họp. Lập trình ràng buộc mô tả các ràng buộc cúa bài toán cần thỏa mãn thay vi xác định tuân tự
các bước cần thực hiện như trong lập trình truyền thống. Điều đó mang đến tính linh động trong
việc diễn đạt và giải quyết hiệu quà các bài toán, đặc biệt trong các bài toán gồm nhiều ràng buộc
đa dạng, biến đổi.
Xu hướng hiện nay, các ngành công nghiệp, các lĩnh vực hoạt động sản xuất ứng dụng công
nghệ CP ngày càng tăng lên nhanh chóng, số lượng các công ty ứng dụng thành công công nghệ
này tăng lên hàng năm, có thể kể tên một số còng ty, tồ chức điển hình: sân bay Quốc tế Hong
Kong, British Airway, SAS, Swissair, cảng Quốc tế Hong Kong, Michelin, Dassault, Ericsson
[17] ... Đoi với lĩnh vực hàng không, CP được ứng dụng để lập lịch các chuyến bay, hoạt động
chuyền phát nhanh...Trong công nghiệp sản xuất, CP ứng dụng trong việc quản lý chuỗi cung
ứng sàn xuất, lập lịch, phẩn bồ tài nguyên, nguồn lực. Lĩnh vực sinh học: phân tích phân tử sinh
học (chuồi DNA-protein) [16].
Lập lịch giảng dạy là bài toán không mới, đã được giãi quyết theo nhiều phương pháp
khác nhau như giài thuật di truyền, tìm kiếm cục bộ như leo lúi, luyện thép, Tabu [1, 2, 3], Các
phương pháp này được sử dụng rộng rãi và cho các kết quà tốt. Tuy nhiên các phương pháp này
thường viết cho các đơn vị cụ thể và không dỗ sửa đổi thích nghi (thay đổi dữ liệu hay yêu cầu trong
bài toán có thể yêu cầu phải xem xét lại toàn bộ chương trinh). Lập trình ràng buộc cũng được áp dụng
thành công trong bài toán lập lịch giàng dạy tại các trường đại học [10,11].
Nội dung đề tài sỗ tập trung vào tìm hiểu phương pháp lập trinh ràng buộc, và áp dụng hệ thống lập
trình ràng buộc mới hiện nay là Comet vào bài toán ỉập lịch giảng dạy tại Trường Đại học Công nghệ.
Cấu trúc báo cáo như sau: Phần 2 sẽ mô tả về lập trinh ràng buộc và hệ thống lập trình ràng buộc
Comet. Phần 3 sẽ mô tà áp dụng hệ thống Comet vào giải quyết bài toán lập lịch giảng dạy tại Trường
Đại học Công nghệ.
2. L ậ p trìn h ràn g buộc và hệ thống lập trình ràng buộc Com et
2.1 L ậ p trình ràn g buộc
Trước khi đi vào phương pháp lập trình ràng buộc, chúng ta đề cập tới phương pháp lập trình
truyên thống qua ví dụ minh họa.
Ví dụ: xem xét bài toán 4-queens (4 hậu): vêu cầu đặt 4 quân hậu trên bàn cờ vua kích
thước 4*4 sao cho không có quân hậu nào có thề “ăn" được quân hậu khác. Ta xét bài toán này
trong m ôi trường lập trinh truyền thống (bủng ngôn ngữ lập trình C/C++ hay Java...) với giải
thuật vét cạn, quay lui (backtracking). Tư tướng cơ bàn cùa giải thuật vét cạn, quay lui là ta thừ
đặt một quân cờ vào một ô trong bàn cơ, sau đó lần lượt đặt từng quân cơ tiếp theo vào các ô cờ
khác. Trong trường hợp không thỏa mãn điều kiện ràng buộc cùa bài toán (Không có hai quân cờ
nào “ăn” dược nhau) thì quay lui trớ lại bước trước đó và đặt lại quân cờ sao cho thỏa mãn điều kiện bài toán. Giải thuật này được mô tà trực quan hơn trong một nhánh cùa cây tìm kiếm bài
toán 4-Queens trong Hình ì .
H ình 1. M ột nhánh trong cây tìm kiếm của bài toán 4-Hậu
Trong lập trình truyền thống không hỗ trợ tự động thù tục quay lui, người lập trình phải tự
viết chức năng thực hiện quay lui để tìm kiếm tất cả các lời giải thỏa mãn điều kiện bài toán.
Ý tường cùa lập trình ràng buộc là giải quyêt bài toán bằng cách khai báo các ràng buộc (các
yêu cẩu) cùa bài toán. Lập trình ràng buộc không xác định tuần tự các bước cần thực hiện như
trong lập trình truyền thống. Lập trình ràng buộc bắt đầu từ những năm 90 bằng việc tich họp xừ
lý ràng buộc vào ngôn ngữ logic. Hai mô hình này chia sẽ nhiều đặc điểm quan trọng như biến
logic và thù tục tự động quay lui. Ngày nay hầu hết các cài đặt Prolog phổ biến như Sisctus
Prolog, Eclipse đều tích hợp các thư viện cho lập trinh ràng buộc [4, 5]. Ngoài tích hợp vào ngôn
ngữ logic, lập trình ràng buộc sử dụng cách tiếp cận khác như tích họp với lập trình thủ tục, với
các hệ thống lập trình ràng buộc phổ biến như Gecode [6], Comet [7].
Mô hình lập trình ràng buộc có thể mô tả như sau: Lập trình ràng buộc = M ô hình ràng buộc
+ Tìm kiếm
Ví dụ sau minh họa một bài toán giải bằng phương pháp lập trình ràng buộc, chúng ta
hãy xét m ột bài toán chơi chừ cồ điển
Phưcmg trình cùa bài toán:
s E N D
+ M O R E
= M 0 N E Y
M ồi ký tự thay mặt cho một con sổ khác sau. cần tìm ra giá trị số tương ứng cho từng ký
tự và thòa mãn phương trình trê
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links