Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu bài toán lập lịch và ứng dụng xếp thời khóa biểu cho trường phổ thông vùng cao Việt Bắc

Mục tiêu của đề tài là hoàn thành sản phẩm là phần mềm xếp thời khóa biểu cho trường Phổ thông Vùng cao Việt Bắc. Tiếp tục phát triển các phần mềm xếp thời khóa biểu cho các trường Phổ thông trung học trên toàn quốc. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu bài toán lập lịch và ứng dụng xếp thời khóa biểu cho trường phổ thông vùng cao Việt Bắc ĐẠI HỌC THÁI NGUYÊNTRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HOÀNG PHÚC LỢI NGHIÊN CỨU BÀI TOÁN LẬP LỊCH VÀ ỨNG DỤNG XẾP THỜI KHÓA BIỂU CHO TRƢỜNG PHỔ THÔNG VÙNG CAO VIỆT BẮC LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2017 ĐẠI HỌC THÁI NGUYÊNTRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HOÀNG PHÚC LỢI NGHIÊN CỨU BÀI TOÁN LẬP LỊCH VÀ ỨNG DỤNG XẾP THỜI KHÓA BIỂU CHO TRƢỜNG PHỔ THÔNG VÙNG CAO VIỆT BẮC Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS. TRƢƠNG HÀ HẢI Thái Nguyên - 2017 i LỜI CAM ĐOAN Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng cánhân tôi, không sao chép của ai, do tôi tự nghiên cứu, đọc, dịch tài liệu,tổng hợp và thực hiện. Nội dung lý thuyết trong trong luận văn tôi có sửdụng một số tài liệu tham khảo như đã trình bày trong phần tài liệu tham khảo.Các số liệu, chương trình phần mềm và những kết quả trong luận văn là trungthực và chưa được công bố trong bất kỳ một công trình nào khác. Thái nguyên 19 tháng 06 năm 2017 Học viên thực hiện Hoàng Phúc Lợi ii LỜI CẢM ƠN Lời đầu tiên, em xin gửi lời biết ơn sâu sắc đến TS. Trương Hà Hảingười đã tận tình hướng dẫn, chỉ bảo, giúp đỡ em trong suốt quá trìnhlàm luận văn. Em cũng xin gửi lời cảm ơn đến các thầy giáo, cô giáo trường Đại họcCông Nghệ Thông Tin và Truyền Thông Thái Nguyên, các thầy giáo, cô giáoViện Công nghệ thông tin đã truyền đạt những kiến thức và giúp đỡ em trongsuốt quá trình học của mình. Và cuối cùng tôi xin gửi lời cảm ơn tới các đồng nghiệp, gia đình vàbạn bè những người đã ủng hộ, động viên tạo mọi điều kiện giúp đỡ đểtôi có được kết quả như ngày hôm nay. Thái Nguyên 19, tháng 06 năm 2017 Học Viên Hoàng Phúc Lợi iii MỤC LỤCLỜI CAM ĐOAN .......................................................................................... iLỜI CẢM ƠN ............................................................................................... iiMỤC LỤC .................................................................................................... iiiDANH MỤC HÌNH ẢNH ............................................................................ vDANH MỤC BẢNG BIỂU ......................................................................... viMỞ ĐẦU ....................................................................................................... 1CHƢƠNG 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH ........................... 4 1.1. Giới thiệu chung về bài toán lập lịch ................................................. 4 1.2. Các đặc trưng của bài toán lập lịch .................................................... 4 1.3. Một số ví dụ về bài toán lập lịch: ....................................................... 5 1.4. Bài toán xếp thời khóa biểu ở trường phổ thông ............................... 7 1.4.1. Giới thiệu bài toán xếp thời khóa biểu ........................................ 7 1.4.2. Độ phức tạp của bài toán xếp thời khóa biểu .............................. 9 1.4.3. Phân loại mô hình xếp thời khóa biểu....................................... 10 1.4.4. Các đặc thù của thời khóa biểu hệ trung học phổ thông ........... 12 1.4.5. Nhu cầu bài toán xếp thời khóa biểu......................................... 14CHƢƠNG 2: MỘT SỐ HƢỚNG TIẾP CẬN VÀ THUẬT TOÁN GIẢIBÀI TOÁN XẾP THỜI KHÓA BIỂU. ....................................................... 17 2.1. Đề xuất các giải thuật giải bài toán .................................................. 17 2.1.1. Giải thuật vét cạn. ..................................................................... 17 2.1.2. Giải thuật chia để trị .................................................................. 17 2.1.3. Giải thuật Heuristic: .................................................................. 19 2.2. Đánh giá các phương pháp: .............................................................. 20 2.3. Giới thiệu giải thuật tối ưu hóa đàn kiến (ANT COLONY OPTIMIZATION: ACO) ........................................................................ 22 2.4. Mô ...