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

Đề tài của các tác giả Trần Quốc Chiến, Trường Đại học Sư phạm, ĐH Đà Nẵng, Phan Thị Ngà, Trường Đại học Thể dục Thể thao Đà Nẵng, 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 thi cho 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ỉ.

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 quan tâ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 <_st13a_country-region w:st="on"><_st13a_place w:st="on">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ín chỉ đã 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ần và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ỉ.

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 chỉ 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ủa ngà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à theo cá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 thi cho 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 thi cầ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ên thi 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.

Thiết kế xây dựng phần mềm xếp lịch thi cho học chế tín chỉ: Sử dụng hệ quản trị cơ sở dữ liệu SQL Server 2005, ngôn ngữ lập trình C# trong bộ Visual studio 2005. Demo phần mềm đã cài đặt chạy ổn định với giao điện dễ sử dụng. Có các modul chức năng như: Quản lý sinh viên học tín chỉ, quản lý phòng học, môn học, chức năng lập lịch, tìm kiếm môn học, tìm kiếm sinh viên học tín chỉ, tra cứu lịch thi. Trong đó chức năng lập lịch, kết quả lập lịch là chức năng trọng tâm nhất của phần mềm có giao diện chính như sau:

Nội dung đề tài khái quát được các kiến thức chung về lý thuyết đồ thị và ứng dụng. Nêu được chi tiết bài toán tô màu và thuật toán tô màu trên đồ thị. Phân tích các yêu cầu của bài toán lập lịch thi cho học chế tín chỉ, thiết kế cơ sở dữ liệu, áp dụng giải thuật ô màu cổ điển để xây dựng giải thuật cải tiến cho yêu cầu mới của bài toán đề ra. Qua các bước xây dựng thuật toán, thiết kế cơ sở dữ liệu, code chương trình đã được cài đặt, xây dựng được demo phần mềm kiểm định thuật toán cho kết quả khả quan và mang tính ứng thực tế.