Đề tài Ứng dụng ngôn ngữ lập trình ràng buộc comet vào bài toán lập thời khóa biểu

i ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thùy ỨNG DỤNG NGÔN NGỮ LẬP TRÌNH RÀNG BUỘC COMET VÀO BÀI TOÁN LẬP THỜI KHÓA BIỂU KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Hà Nội – 2010 ii ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thùy ỨNG DỤNG NGÔN NGỮ LẬP TRÌNH RÀNG BUỘC COMET VÀO BÀI TOÁN LẬP THỜI KHÓA BIỂU KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hƣớng dẫn: Th.S Lê Hồng Hải Hà Nội - 2010 1 LỜI CẢM ƠN Trước hết, em xin chân thành cảm ơn đến quý thày cô trường Đại học Công Nghệ đã tận tình dạy bảo em trong suốt thời gian học tập tại trường. Em xin gửi lời biết ơn sâu sắc đến Thạc sĩ Lê Hồng Hải đã dành nhiều thời gian và tâm huyết hướng dẫn nghiên cứu, giúp em hoàn thành khóa luận tốt nghiệp. Em cũng xin chân thành cảm ơn Ban Giám hiệu trường Đại học Công nghệ cùng quí thày cô trong Khoa công nghệ thông tin đã tạo điều kiện để em học tập và hoàn thành tốt khóa học. Trong khóa luận không thể tránh khỏi những thiếu sót. Em rất mong nhận được được những đóng góp quí báu của thày cô và các bạn để khóa luận được hoàn thiện hơn. Hà Nội, tháng 5 năm 2010 Sinh viên Nguyễn Thị Thùy 2 TÓM TẮT KHÓA LUẬN Lập Thời khóa biểu là công việc cần thiết và quan trọng mà tất cả các tổ chức giáo dục phải thực hiện nhằm đƣa ra biểu đồ kế hoạch năm học, lịch giảng dạy và học tập cho giáo viên, học sinh. Trƣớc đây, khi CNTT chƣa đƣợc phát triển mạnh mẽ và ứng dụng rộng rãi thì công việc này thƣờng đƣợc thực hiện một cách thủ công trên giấy, tiêu tốn nhiều chi phí, thời gian và công sức. Bài toán lập Thời khóa biểu tronng trƣờng học là một một trƣờng hợp riêng của bài toán lập lịch đƣợc xếp vào hàng các bài toán khó chƣa có giải thuật tối ƣu nhất. Có rất nhiều thuật toán, phƣơng pháp tiếp cận khác nhau đƣợc các nhà khoa học trên thế giới đƣa ra nhằm giải quyết bài toán này. Song, một phƣơng pháp tiếp cận khá là mới và đƣợc cho là giải pháp tối ƣu cho các bài toán lập lịch đó là ứng dụng ngôn ngữ lập trình ràng buộc vào giải quyết các bài toán tổ hợp. Với mục tiêu xây dựng một chƣơng trình lập thời khóa biểu hoạt động hiệu quả, khóa luận xin trình bày về ngôn ngữ lập trình ràng buộc Comet và ứng dụng Comet để giải quyết bài toán lập thời khóa biểu. Comet là ngôn ngữ lập trình ràng buộc mới đƣợc phát triển và ứng dụng. Đây là ngôn ngữ lập trình điển hình nhất cho việc giải quyết các bài toán tổ hợp nhƣ lập lịch, lập kế hoạch … Đây cũng là một ngôn ngữ lập trình hƣớng đối tƣợng, dễ sử dụng và cấu trúc câu lệnh tƣơng đối giống với ngôn ngữ lập trình C++. 3 MỤC LỤC LỜI CẢM ƠN ....................................................................................................... 1 TÓM TẮT KHÓA LUẬN ..................................................................................... 2 MỤC LỤC ............................................................................................................ 3 BẢNG CÁC KÝ HIỆU VIẾT TẮT ....................................................................... 5 BẢNG CÁC THUẬT NGỮ CHUYÊN NGÀNH .................................................. 5 DANH SÁCH CÁC HÌNH VẼ ĐƢỢC SỬ DỤNG ............................................... 6 CHƢƠNG 1: MỞ ĐẦU ........................................................................................ 7 1.1. Ý nghĩa ứng dụng Comet vào giải quyết các vấ đề tối ƣu hóa tổ hợp ... 7 1.2. Cấu trúc khóa luận ............................................................................. 10 CHƢƠNG 2: LẬP TRÌNH RÀNG BUỘC .......................................................... 11 2.1. Lập trình ràng buộc là gì? .................................................................. 11 2.2. Nguồn gốc lập trình ràng buộc ........................................................... 11 2.3. Mô hình lập trình ràng buộc .............................................................. 12 2.4. Ứng dụng của ngôn ngữ lập trình ràng buộc (CP) .............................. 14 CHƢƠNG 3: NGÔN NGỮ LẬP TRÌNH COMET .............................................. 16 3.1. COMET là gì? ................................................................................... 16 3.2. Lập trình Comet ................................................................................. 17 3.2.1. Mô hình lập trình Comet ...................................................... 17 3.2.2. Ví dụ .................................................................................... 20 3.3. Ƣu điểm của Comet ........................................................................... 23 4 CHƢƠNG 4: ỨNG DỤNG COMET VÀO BÀI TOÁN LẬP THỜI KHÓA BIỂU ............................................................................................................................ 26 4.1. Đặt vấn đề xây dựng bài toán ............................................................. 26 4.2. Giải quyết bài toán ............................................................................. 28 4.3. Thực nghiệm ...................................................................................... 30 4.3.1. Các chức năng quản lý giảng viên, môn học, phòng học, khoa ...................................................................................................... 31 4.3.2. Chức năng phân công giảng dạy ........................................... 36 4.3.3. Chức năng xếp Thời khóa biểu ............................................. 37 4.3.4. Chức năng xem thời khóa biểu theo tên lớp, tên giảng viên, tên phòng học ...................................................................................... 38 CHƢƠNG 5: KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ..................................... 40 TÀI LIỆU THAM KHẢO ................................................................................... 41 5 BẢNG CÁC KÝ HIỆU VIẾT TẮT Ký hiệu Từ viết tắt ACM Association for Computing Achinery AI Artificial Intelligence API Application Programming Interface CHIP Constraint Handling In Prolog CLP Constraint Logic Programming CBLS Constraint-Based Local Search CP Constraint Programming LP Logic Programming BẢNG CÁC THUẬT NGỮ CHUYÊN NGÀNH Các thuật ngữ Ý nghĩa Artificial Intelligence Trí tuệ nhân tạo Application Programming Interface Giao diện lập trình ứng dụng Constraint Programming Lập trình ràng buộc Logic Programming Lập trình logic Search Tìm kiếm Search Tree Cây tìm kiếm 6 DANH SÁCH HÌNH ẢNH ĐƢỢC SỬ DỤNG Hình 1-1. Bài toán 4-Hậu ...................................................................................... 8 Hình 1-2. Một nhánh trong cây tìm kiếm của bài toán 4-Hậu ................................ 9 Hình 2-1. Mô hình CP ......................................................................................... 12 Hình 2-2. Ứng dụng CP vào phân tích chuỗi protein ........................................... 15 Hình 3-1. Thành phần tìm kiếm trong Comet ...................................................... 19 Hình 3-2. Code bài toán 16-Hậu bằng Comet ...................................................... 20 Hình 3-3. Kết quả bài toán 16-Hậu bằng Comet .................................................. 22 Hình 3-4. Kết quả trực quan bài toán 16-Hậu visualization.................................. 24 Hình 4-1. Mô hình chƣơng trình .......................................................................... 30 Hình 4-2. Quản lý giảng viên .............................................................................. 31 Hình 4-3. Quản lý phòng học .............................................................................. 32 Hình 4-4. Quản lý môn học ................................................................................. 33 Hình 4-5. Quản lý lớp học ................................................................................... 34 Hình 4-6. Quản lý khoa ....................................................................................... 35 Hình 4-7. Chức năng phân công giảng dạy .......................................................... 36 Hình 4-8. Chức năng xếp Thời khóa biểu ............................................................ 37 Hình 4-9. Xem Thời khóa biểu theo lớp .............................................................. 38 Hình 4-10. Xem Thời khóa biểu theo giảng viên ................................................. 39 Hình 4-11. Xem Thời khóa biểu theo phòng học ................................................. 39 7 CHƢƠNG 1: MỞ ĐẦU Ngày nay, với sự phát triển mạnh mẽ của CNTT góp phần mang lại những thành tựu rực rỡ cho các lĩnh vực, hoạt động trong đời sống. Cùng với sự phát triển của CNTT, các thế hệ ngôn ngữ lập trình lần lƣợt ra đời nhằm đáp ứng các yêu cầu công nghệ. Đóng góp quan trọng vào sự phát triển và ứng dụng CNTT, ngôn ngữ lập trình ràng buộc Comet thật sự mang lại tiện ích lớn trong việc giải quyết các bài toán tổ hợp nhƣ lập lịch, lập kế hoạch. 1.1. Ý nghĩa ứng dụng lập trình ràng buộc đối với vấn đề tối ƣu hóa tổ hợp Trong lĩnh vực nghiên cứu khoa học máy tính, các bài toán về tối ƣu hóa tổ hợp đƣợc đánh giá là các bài toán khó NP[1], đặc trƣng bởi bộ dữ liệu lớn, các ràng buộc phức tạp. Để giải quyết vấn đề này hiệu quả đòi hỏi phải có kinh nghiệm và kỹ năng. Trên thế giới có rất nhiều những công trình nghiên cứu, các thuật toán đƣợc ứng dụng và phát triển để giải quyết vấn đề này: các thuật toán quay lui, vét cạn, các thuật toán về quy hoạch động. Tuy nhiên, trong lập trình truyền thống chƣa có giải thuật hiệu quả nhất, đáp ứng đƣợc thời gian xử lý là đa thức. Do đó, đây vẫn là bài toán khó chƣa có lời tối ƣu nhất. Trong những năm gần đây, CP nổi lên nhƣ một công nghệ quan trọng, giải quyết hiệu quả các bài toán tối ƣu hóa tổ hợp, ứng dụng thành công trong nhiều lĩnh vực: hàng không, khoa học máy tính, công nghiệp sản xuất…CP thực sự là một giải pháp tối ƣu, đƣợc giới chuyên môn đánh giá cao về khả năng giải quyết các vấn đề phức tạp trong cuộc sống thực thế. Dƣới đây, ta sẽ xét bài toán N-Hậu trong lập trình truyền thống với giải thuật vét cạn, quay lui. Bài toán N-Hậu Bài toán 4-queens là bài toán đặ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, hay nói cách khác không quân hậu nào có thể di chuyển theo quy tắc cờ vua. Do đó, lời giải của bài 8 toán là một cách xếp bốn quân hậu trên bàn cơ vua sao cho không có hai quân nào đứng trên cùng hàng, hoặc cùng cột hoặc cùng đƣờng chéo. Hình 1-1. Bài toán 4-Hậu Đây là bài toán tổ hợp kinh điển, có nhiều giải thuật: quay lui, vét cạn, quy hoạch động. Tuy nhiên, độ phức tạp của các thuật toán này thƣờng là...Chƣa có giải thuật thỏa mãn thời gian chạy là đa thức. Dƣới đây, ta xét bài toán này trong môi trƣờng lập trình truyền thống ( bằng ngôn ngữ lập trình C/C++ hoặc Java...) với giải thuật vét cạn, quay lui (gọi đệ quy). 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” đƣợ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 (Hình 1-2). 9 Hình 1-2. 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ợ chƣơng trình tự động backtracking, coder phải tự viết chức năng thực hiện backtracking để 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. So với lập trình truyền thống, lập trình ràng buộc hỗ trợ chƣơng trình tự động backtracking, giải quyết vấn đề phân theo hai thành phần. Thứ nhất, vấn đề đƣợc mô hình hóa bởi tập các ràng buộc trên miền giới hạn của các biến. Thứ hai, là giải quyết các ràng buộc bằng cách sử dụng những thông tin đã đƣa ra trong mô hình để tự động tìm kiếm giải pháp. Quá trình này hệ thống tự động thực hiện, không có sự can thiệp của con ngƣời. Chúng ta sẽ tìm hiểu sâu về lập trình ràng buộc trong chƣơng tiếp theo. 10 1.2. Giới thiệu cấu trúc khóa luận Cấu trúc khóa luận gồm 5 chƣơng:  Chƣơng 1: Mở đầu  Chƣơng 2: Lập trình ràng buộc  Chƣơng 3: Ngôn ngữ lập trình Comet  Chƣơng 4: Áp dụng Comet vào bài toán ứng dụng “Lập thời khóa biểu” cho trường đại học  Chƣơng 5: Kết luận và hướng phát triển. 11 CHƢƠNG 2 LẬP TRÌNH RÀNG BUỘC Trong một vài năm gần đây, lập trình ràng buộc (CP) đã thu hút sự chú ý một số lƣợng lớn các chuyên gia CNTT vì khả năng giải quyết các vấn đề khó khăn trong thực tế. Theo [5] CP đƣợc ACM (Association for Computing Achinery) nhận định là một trong những hƣớng chiến lƣợc trong nghiên cứu tin học. Tuy nhiên CP vẫn là một trong những công nghệ ít đƣợc biết đến và hiểu rõ. 2.1. Lập trình ràng buộc là gì? Lập trình ràng buộc (CP - Constraint Programming) là ngôn ngữ lập trình ràng buộc, công nghệ điển hình giải quyết hiệu quả vấn đề mô hình hóa và tối ƣu hóa tổ hợp, đặc biệt là trong lĩnh vực quy hoạch và lập lịch. CP nghiên cứu các hệ thống tính toán dựa trên các ràng buộc. Ý tƣởng cơ bản của CP là giải quyết vấn đề bằng cách nêu rõ ràng buộc (các điều kiện, thuộc tính, yêu cầu) và tìm kiếm giải pháp thỏa mãn tất cả các ràng buộc. Lập trình ràng buộc ( CP ) là một cách tiếp cận mới về vấn đề giải quyết thỏa mãn các ràng buộc và các vấn đề tối ƣu hóa đang đƣợc sử dụng trong nhiều ứng dụng thƣơng mại. CP kết hợp tìm kiếm vét cạn, quay lui từ những ngôn ngữ lập trình logic với kỹ thuật ràng buộc từ lĩnh vực nghiên cứu trí tuệ nhân tạo. Monash là ngƣời tiên phong trong lĩnh vực này và đƣợc biết đến với công việc thiết kế ngôn ngữ lập trình ràng buộc logic và ngôn ngữ lập trình chức năng ràng buộc. 2.2. Nguồn gốc của lập trình ràng buộc Lập trình ràng buộc (CP) đƣợc phát triển khá sớm so với những ngôn ngữ lập trình phổ biến hiện nay nhƣ Java (1990s). Vào thập niên 60, 70, những ý tƣởng đầu tiên về lập trình ràng buộc có thể đƣợc tìm thấy trong lĩnh vực nghiên cứu trí tuệ nhân tạo (AI) mà cụ thể là ngôn ngữ lập trình logic Prolog (Alain Colmerauer, 1972). Một số ứng dụng đầu tiên của ngôn ngữ này đã đạt đƣợc 12 những thành tựu đáng kể nhƣ: hệ thống tƣơng tác đồ họa Sketchpad của Ivan Sutherland (1963), hệ thống ThingLab của Alan Borning (1981). Tuy nhiên, phải đến dòng ngôn ngữ lập trình logic ràng buộc (CLP- Constraint Logic Programming) mới đánh dấu bƣớc phát triển chính của lập trình ràng buộc. CLP đƣợc phát triển bởi hai nhà khoa học Jaffar & Lassez (1987)[5], dựa trên nền tảng lập trình logic, kết hợp cả hai khía cạnh khai báo của lập trình logic (LP) với giải quyết các ràng buộc. Tiếp theo, một số dòng ngôn ngữ lập trình ràng buộc lần lƣợt đƣợc phát triển, có t hể kể ra nhƣ: concurrent logic programming (1980s) , concurrent constraint programming(1990s). Và hiện nay, Comet đƣợc đánh giá là ngôn ngữ lập trình ràng buộc có ƣu thế nổi bật nhất. Chúng ta sẽ tìm hiểu ngôn ngữ lập trình Comet trong chƣơng tiếp theo. 2.3. Mô hình lập trình ràng buộc CP = Model + Search Hình 2-1. Mô hình CP[3] Bản chất của CP là kiến trúc hai thành phần: một mô hình lƣu trữ ràng buộc và mô hình tìm kiếm. Mô hình lƣu trữ ràng buộc là tập hợp các ràng buộc mô tả thuộc tính của biến, các mối liên quan, ràng buộc của biến trên miền giá trị, là một hệ thống lý luận về các thuộc tính cơ bản của hệ thống ràng buộc. Mô hình lƣu trữ ràng buộc chứa đựng các ràng buộc đã tích lũy tại một số bƣớc tính toán, hỗ trợ 13 các truy vấn và toán tử thực hiện trên trên nó. Thành phần tìm kiếm trong CP là duyệt cây với thuật toán backtracking, về bản chất giống nhƣ phƣơng pháp tìm kiếm nhánh và cận của lập trình truyền thống. Bài toán: SEND + MORE = MONEY Để hiểu rõ thêm về các ràng buộc, chúng ta hãy xét một bài toán chơi chữ cổ điển của Henry Dudeney công bố trên tạp chí Strand năm 1924[10]. Phƣơng trình của bài toán Mỗi ký tự đại diện cho một con số khác sau, các chữ số hàng đầu của một số nhiều hơn một chữ số phải là những số khác không. Và một lời giải đúng là tìm ra giá trị số tƣơng ứng cho từng ký tự và thỏa mãn phƣơng trình trên. Ở đây. Chúng ta sẽ đề cập đến một phƣơng pháp, áp dụng lập trình ràng buộc vào giải quyết bài toán. Code bài toán sendmore(Digits) :- Digits = [S,E,N,D,M,O,R,Y], % Khởi tạo biến Digits :: [0..9], % Xác định miền giá trị của biến S #\= 0, % Constraint: S, M phải khác 0 M #\= 0, alldifferent(Digits), % giá trị của các biến là khác nhau 1000*S + 100*E + 10*N + D % ràng buộc theo biểu thức + 1000*M + 100*O + 10*R + E #= 10000*M + 1000*O + 100*N + 10*E + Y, labeling(Digits). % Tìm kiếm Cấu trúc chƣơng trình chƣơng trình có ba phần rõ ràng:  Khai báo các biến và miền giá trị của biến: Các biến chính là các chữ cái tƣơng ứng trong đề bài: S, E, N, D, M, O, R, Y . Các biến này có miền giá trị thuộc vào đoạn [0,9]. 14  Ràng buộc giữa các biến Mỗi chữ cái có giá trị là một số nhất đinh, các biến phải có giá trị khác nhau. S, M là hai biến tƣơng ứng với giá trị đứng đầu các số, vì vậy, S, M là phải là các chữ số khác 0. Bên cạnh đó, tất cả các biến phải thỏa mãn biểu thức mà đầu bài đã đƣa ra SEND + MORE = MONEY.  Tìm kiếm: labeling(Digits) // Chƣơng trình sẽ duyệt theo từng biến. Phần tìm kiếm độc lập với các ràng buộc giữa các biến. Lời giải cho bài toán: O = 0, M = 1, Y =2, E = 5, N = 6, D = 7, R = 8, S = 9. 9567 + 1085 10652 2.4. Ứng dụng lập trình ràng buộc Từ thập niên 90 trở lại đây, nền kinh tế trên toàn thế giới tăng trƣởng mạnh mẽ, các doanh nghiệp tổ chức thƣơng mại không ngừng ra đời và phát triển lớn mạnh. Bên cạnh đó, khoa học kỹ thuật công nghệ thu đƣợc những thành tựu rực rỡ, đem đến những công nghệ tiên tiến nhất và hàng loạt công nghệ, kỹ thuật đƣợc ứng dụng rộng rãi và thành công trong các ngành kinh tế, thƣơng mại, góp phần thúc đẩy sự tăng trƣởng kinh tế. 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[5] … Đối 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 … 15 Không chỉ đƣợc ứng dụng thành công trong các ngành kinh tế, công nghệ CP còn đƣợc ứng dụng thành công trong các lĩnh vực khác nhƣ: - Lĩnh vực khoa học máy tính: Đồ họa máy tính (thể hiện gắn kết hình học trong phân tich phối cảnh), xử lỹ ngôn ngữ tự nhiên (phân tích cú pháp), hệ thống cơ sở dữ liệu (bảo đảm/phục hồi tính nhất quán của dữ liệu) … - Lĩnh vực đời sống, sinh hoạt: Lập thời gian biểu, lập lịch… - Lĩnh vực sinh học: phân tích phân tử sinh học (chuỗi DNA-protein)… Kỹ thuật lập trình ràng buộc có thể sử dụng hiệu quả để dự đoán cấu trúc của một phân tử protein, đƣợc coi là vấn đề quan trọng nhất trong tin sinh học. Hình 2-2. Ứng dụng CP vào phân tích chuỗi protein 16 CHƢƠNG 3 NGÔN NGỮ LẬP TRÌNH COMET 3.1. COMET là gì? Tối ƣu hóa tổ hợp là vấn đề mà chúng ta thƣờng xuyên bắt gặp trong cuộc sống, hoạt động sản xuất, trong các lĩnh vực hoạt động: từ ngành công nghiệp hàng không với các dịch vụ chuyển phát nhanh, chuỗi quản lý cung ứng trong công nghiệp sản xuất, vấn đề phân phối tài nguyên, nguồn lực… Đây là bài toán khó mang tính thách thức, là một nhánh nghiên cứu trong lĩnh vực khoa họ