LUẬN VĂN: Ứ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

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...
Nội dung trích xuất từ tài liệu:
LUẬN VĂN: Ứ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 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 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 Cán bộ hƣớng dẫn: Th.S Lê Hồng Hải Hà Nội - 2010 ii 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 1 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++. 2 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 3 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............ ...