ứ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++.