Báo cáo nghiên cứu khoa học: BÀI TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG XÂY DỰNG PHẦN MỀM XẾP LỊCH THI CHO HỌC CHẾ TÍN CHỈ

Với mô hình đào tạo mới theo học chế tín chỉ, bài toán xếp lịch thi cũng có nhiều yêu cầu mới khác với bài toán lập lịch cổ truyền. Ứng dụng thuật toán tô màu đồ thị vào bài toán lập lịch đuợc coi là một giải thuật tối ưu cổ điển, thì với yêu cầu lập lịch thi cho học chế tín chỉ cần phải cải tiến lại giải thuật cho phù hợp với các yêu cầu ràng buộc mới.
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học: " BÀI TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG XÂY DỰNG PHẦN MỀM XẾP LỊCH THI CHO HỌC CHẾ TÍN CHỈ" TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(35).2009BÀI TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG XÂY DỰNG PHẦN MỀM XẾP LỊCH THI CHO HỌC CHẾ TÍN CHỈ THE PROBLEM OF GRAPH COLORING AND ITS APPLICATION TO THE DEVELOPMENT OF AN EXAMINATION SCHEDULE SOFTWARE FOR CREDIT–BASED ACADEMIC COURSES Trần Quốc Chiến Phan Thị Ngà Trường Đại học Sư phạm, ĐH Đà Nẵng Trường Đại học Thể dục Thể thao Đà Nẵng TÓM T ẮT Với mô hình đào tạo mới theo học chế tín chỉ, bài toán xếp lịch thi cũng có nhiều yêucầu mới khác với bài toán lập lịch cổ truyền. Ứng dụng thuật toán tô màu đồ thị vào bài toán lậplịch đuợc coi là một giải thuật tối ưu cổ điển, thì với yêu cầu lập lịch thi cho học chế tín chỉ cầnphải cải tiến lại giải thuật cho phù hợp với các yêu cầu ràng buộc mới. Đề tài tập trung nghiên cứu về lý thuyết đồ thị và bài toán tô màu, tìm hiểu về học chếtín chỉ. Ứng dụng giải thuật tô màu đồ thị để đề ra giải pháp, thuật toán cho bài toán xếp lịch thicho học chế tín chỉ. Xây dựng, thiết kế phần mềm xếp lịch thi cho học chế tín chỉ. ABSTRACT W ith new credit-based academic programmes, the math problem of an examinationschedule has a number of new requisites that differ from those of a traditional examinationschedule. While the application of algorithms to colored graphs in the math problem ofexamination schedule is considered to be a classic optimum, the schedule for credit-basedprogramme examinations needs improved algorithms in accordance with new constraints. This topic focuses on the graph theory, the problem of coloring, the credit-basedprogramme investigation, the application of algorithms to colored graphs in the math problemsolving, the algorithms for the problem of examination schedule for credit-based academicprogrammes and the development and design of a software for credit-based examinationschedule.1. Đặt vấn đề Hiện nay sự phát triển của các thuật toán trên đồ thị là một trong các mối quantâm chính của ngành khoa học máy tính. Đề án đổi mới giáo dục đại học Việt Nam đangđược thực thi, một trong những nội dung quan trọng là xây dựng mô hình đào tạo ở bậcđại học theo học chế tín chỉ. Quản lý và xếp lịch thi cho học chế tín chỉ vẫn luôn là sựquan tâm của nhiều trường đại học. Các phần mềm về quản lý đào tạo theo học chế tínchỉ đã có đều là phần mềm đã đóng gói. Vấn đề nghiên cứu về quản lý học chế tín chỉđang được phát triển. Hướng nghiên cứu và kết quả của đề tài nhằm đóng góp một phầnvào việc đưa ra giải pháp và thuật toán để xây dựng phần mềm xếp lịch thi cho học chếtín chỉ.2. Bài toán xếp lịch thi cho học chế tín chỉ. Các trường đại học tổ chức học theo tín chỉ. Nếu sinh viên tích lũy đủ số chứng 85 TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(35).2009chỉ cho một số môn quy định của một ngành là có quyền nhận bằng tốt nghiệp củangành đó. Đối với các đại học như thế, việc học và thi không tổ chức theo lớp mà theocác môn học. Hàng năm nhà trường thông báo các môn sẽ học để sinh viên tự đăng kýhọc các môn học theo ngành mình chọn. Cuối kỳ hoặc cuối năm nhà trường tổ chức thicho các môn đã giảng trong năm. Mỗi môn thi trong một ngày nhưng trong một ngày cóthể tổ chức thi nhiều môn. Do một sinh viên có thể đăng ký thi nhiều môn nên lịch thicần phải bố trí để nếu có một sinh viên đăng ký thi nhi u môn nào đó thì các môn đó ềkhông được thi cùng ngày. Để sinh viên có thời gian ôn tập, lịch thi sẽ được xếp theo sao cho: nếu sinh viênthi nhiều môn thì điều kiện là hai môn thi kế tiếp phải cách nhau tối thiểu là nDay ngày. Mỗi đợt thi chỉ giới hạn trong một khoảng thời gian nhất định.Trong một ngày,một phòng có thể tổ chức nhiều ca thi.3. Xây dựng giải thuật cho bài toán Đầu vào: + dsInpMHoc: là danh sách các môn học + dsInpDK: là danh sách đ tả mối quan hệ sinh viên đăng ký dự thi mô n học ặcnào + dsInpPHoc: là danh sách các phòng ọc, tương ứng với thông tin về số hiệu hphòng, sức chứa của phòng + dtiBegin: là ngày bắt đầu tổ chức thi + nDay: là số lượng ngày tối thiểu tương ứng với khoảng cách hai lần thi củamột thí sinh tương ứng + numOfCathi: là số lượng ca thi tổ chức trong ngày, mặc định nhận giá trị là 1hoặc 2 ca thi/1 ngày + numOfRoom: là số lượng thi sinh tối thiểu. Trong trường hợp số lượng thí sinhkhông vượt quá numOfRoom là không tổ chức thi. Đầu ra: ...