tailieunhanh - THUẬT TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG XẾP LỊCH THI

Lý thuyết đồ thị là một ngành khoa học có nhiều ứng dụng hiện đại. Đề tài này có mục tiêu là nghiên cứu thuật toán tô màu đồ thị, mục đích là xây dựng chương trình xếp lịch thi học kỳ. ABSTRACT Graphics theory is an important science which has many modern application. This subject has got the goal: research graph coloring algorithm, the purpose: build an exams scheduling application. | Tuyển tập Báo cáo Hội nghị Sinh viên Nghiên cứu Khoa học lần thứ 6 Đại học Đà Nẵng - 2008 THUẬT TOÁN TÔ MÀU ĐỒ THỊ VÀ ỨNG DỤNG XẾP LỊCH THI THE GRAPH COLORING ALGORITHM AND EXAMS SCHEDULING APPLICATION SVTH NGHIÊM VĂN HƯNG Lớp 04CCT02 Trường Đại học Sư Phạm gVhd pgs. tskH trần quốc chiến Khoa Tin học Trường Đại học Sư Phạm TÓM TẮT Lý thuyết đồ thị là một ngành khoa học có nhiều ứng dụng hiện đại. Đề tài này có mục tiêu là nghiên cứu thuật toán tô màu đồ thị mục đích là xây dựng chương trình xếp lịch thi học kỳ. ABSTRACT Graphics theory is an important science which has many modern application. This subject has got the goal research graph coloring algorithm the purpose build an exams scheduling application. 1. MỞ ĐẦU . Lý do chọn đề tài Với hình thức học chế tín chỉ sinh viên có thể chủ động chọn đăng kí môn học theo kế hoạch học tập của mình. Điều này làm cho việc xếp lịch thi trở nên khó khăn hơn. Phòng đào tạo phải sắp xếp lịch thi sao cho không có sinh viên nào thi nhiều hơn một môn tại cùng một thời điểm. Việc xếp lịch thủ công như trước đây là không khả thi. Do đó đề tài này có mục đích là xây dựng một chương trình xếp lịch thi góp phần tin học hóa công tác đào tạo. . Đối tượng nghiên cứu Lý thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Một đồ thị là một tập hợp các đỉnh và các đường nối các đỉnh gọi là cạnh cung . Tô màu đồ thị là phép gán màu cho mỗi đỉnh sao cho không có hai đỉnh kề nhau được gán cùng màu. Bài toán xếp lịch thi được mô hình hóa thành bài toán tô màu đồ thị như sau lập đồ thị có các đỉnh là các môn thi hai môn thi kề nhau nếu có một sinh viên thi cả hai môn này. Thời điểm thi của mỗi môn được biểu thị bằng các màu khác nhau. . Giải pháp công nghệ - Phân tích thiết kế hướng đối tượng với UML. - Ngôn ngữ lập trình Visual C 2005. - Hệ quản trị cơ sở dữ liệu SQL Server 2000. 271 Tuyển tập Báo cáo Hội nghị Sinh viên Nghiên cứu Khoa học lần thứ 6 Đại học Đà Nẵng - 2008 2. NỘI DUNG . Cơ sở