tailieunhanh - Luận văn:Nghiên cứu kết hợp thuật toán cặp ghép và tham lam giải quyết bài toán thời khóa biểu trường chuyên

Thuật toán ghép cặp của Edmonds (còn gọi là thuật toán bông hoa) là một thuật toán trong lý thuyết đồ thị để tìm cặp ghép cực đại trong đồ thị. Thuật toán được tìm ra bởi Jack Edmonds năm 1961,[1] và xuất bản năm 1965.[2] Cho trước một đồ thị vô hướng G = (V, E), thuật toán tìm ra cặp ghép M sao cho mỗi đỉnh trong V kề với tối đa một cạnh trong M và |M| là lớn nhất có thể. Cặp ghép được xây dựng bằng cách khởi đầu từ cặp ghép rỗng và tăng. | 1 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG ĐOÀN CƯỜNG NGHIÊN CỨU KẾT HỢP THUẬT TOÁN CẶP GHÉP VÀ THAM LAM GIẢI QUYẾT BÀI TOÁN THỜI KHÓA BIỂU TRƯỜNG CHUYÊN Chuyên ngành KHOA HỌC MÁY TÍNH Mã số TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nằng - Năm 2011 2 Công trình được hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học TS. Nguyễn Thanh Bình Phản biện 1 . Lê Văn Sơn Phản biện 2 TS. Trương Công Tuấn Luận văn được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp thạc sĩ kỹ thuật họp tại Đại học Đà Nằng vào ngày 18 tháng 06 năm 2011 Có thể tìm hiểu luận văn tại - Trung tâm Thông tin - Học liệu Đại học Đà nằng - Trung tâm Học liệu Đại học Đà Nằng. 3 MỞ ĐẦU 1. LÝ DO CHỌN ĐỀ TÀI Việc chia thời khóa biểu TKB cho các Trường THPT Chuyên trên toàn quốc là vấn đề hết sức khó khăn. Vì trường chuyên có những đặc thù riêng biệt đối với trường chuyên mỗi học kỳ phải chia thành nhiều giai đoạn tại mỗi giai đoạn số tiết dạy của từng bộ môn phải có sự thay đổi để đáp ứng được tiến độ của từng bộ môn chuyên nên tất cả các trường chuyên đều phải làm thủ công dẫn đến kết quả không mấy khả quan. Hiện có một số phần mềm xếp TKB của Cục Công nghệ Thông tin hay một số tổ chức khác dành cho trường THPT bình thường nhưng hiệu quả không cao không đáp ứng được nhu cầu của từng giáo viên. Vì vậy các trường này phải tự làm thủ công còn nếu áp dụng cho trường chuyên thì không thể được. Công nghệ Thông tin đã và đang trên đà phát triển mạnh mẽ trên toàn cầu nhưng việc chia thời khóa biểu cho tất cả các trường THPT trên toàn quốc nói chung trường THPT chuyên nói riêng vẫn phải làm thủ công nên hiệu quả không cao lại mất rất nhiều thời gian và công sức. Bài toán đặt ra là vấn đề xếp thời khóa biểu cho trường THPT chuyên với nhiều cơ sở khác nhau. Cần có sự sắp xếp lịch học cho các lớp tại các phòng ở mỗi địa điểm sao cho vừa hợp lý lại vừa tiện dụng nhất phù hợp với từng bộ môn chuyên. Bài toán bao gồm tất cả các vấn đề có liên quan đến việc xếp thời khóa biểu ở trường THPT chuyên chẳng hạn .