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

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG ĐỒN CƯỜNG NGHIÊN CỨU KẾT HỢP THUẬT TỐN CẶP GHÉP VÀ THAM LAM GIẢI QUYẾT BÀI TỐN THỜI KHĨA BIỂU TRƯỜNG CHUYÊN Chuyên ngành : KHOA HỌC MÁY TÍNH Mã số: : 60.48.01 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 hồ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: PGS.TS. 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 tồ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 tồ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 tồ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 tố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 tố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 đặt lớp học vào một phịng sao cho tương ứng về sức chứa của nĩ, tránh việc học trùng giờ tại một phịng của các lớp; giáo viên sẽ dạy theo giờ quy định trong bảng phân cơng, đảm bảo quy chế của Bộ Giáo dục & 4 Đào tạo. Thơng thường, cơng việc này được làm bằng tay, tất nhiên chúng ta luơn thực hiện được và cho ra kết quả tương đối tốt, nhưng phải mất nhiều thời gian và ít nhất phải cĩ kinh nghiệm xếp lịch nếu khơng muốn cĩ sai sĩt xảy ra, chẳng hạn như: chỗ này thừa phịng, chỗ khác lại thiếu, sai chỗ, sai giờ,... Vấn đề của bài tốn là ngồi việc thực hiện đúng, chính xác, cịn phải tốt hơn, nhanh hơn và hiệu quả hơn cơng việc xếp lịch bằng tay mà chúng ta vẫn phải làm. Trường THPT chuyên Lê Quý Đơn cĩ nhiều đặc trưng riêng. Nhu cầu đến lớp của giáo viên khác nhau, một số người thích đến lớp trong một số ngày nào đĩ trong tuần, nên việc xếp TKB cũng cĩ nhiều điểm khác so với các Trường THPT khác. Chính vì lý do này, đề tài nghiên cứu thuật tốn cặp ghép và áp dụng nĩ để làm sao thỏa mãn một cách tốt nhất các nhu cầu của giáo viên. Ví dụ khi chia TKB cho lớp ghép là một vấn đề, giả sử cĩ lớp vừa chuyên Anh vừa chuyên Pháp, thì tại một số thời điểm phải cĩ 2 giáo viên cùng dạy cho lớp này nhưng phải đảm bảo các tính chất của một lớp chuyên. Xuất phát từ những lý do trên mà tơi đã chọn đề tài “Nghiên cứu kết hợp thuật tốn cặp ghép và tham lam giải quyết bài tốn thời khĩa biểu trường chuyên” ứng dụng tại Trường THPT chuyên Lê Quý Đơn, cĩ giải pháp và chương trình, sản phẩm cụ thể làm đề tài luận văn tốt nghiệp thạc sĩ của mình. Chương trình được xây dựng và ứng dụng sẽ giúp hồn thiện hơn kiến thức được học và cĩ ý nghĩa khoa học, thực tiễn cao. 2. MỤC TIÊU VÀ NHIỆM VỤ NGHIÊN CỨU - Mục tiêu 5 o Hồn thành sản phẩm là một chương trình chia thời khĩa biểu Trường THPT Chuyên Lê Quý Đơn. o Tiếp tục phát triển ứng dụng chia thời khĩa biểu cho tất cả các trường THPT Chuyên, THPT trên tồn quốc. - Nhiệm vụ o Phân tích các đặc thù riêng biệt cĩ số liệu của tất cả các trường chuyên trên tồn quốc, đề ra giải pháp hợp lý trong việc xây dựng và triển khai hệ thống. o Nghiên cứu kết hợp thuật tốn cặp ghép và tham lam giải quyết bài tốn thời khĩa biểu Trường THPT chuyên Lê Quý Đơn. o Phân tích, đánh giá và đề ra giải pháp chia thời khố biểu một cách tự động và chính xác. o Nghiên cứu, ứng dụng cơng nghệ dotNet, ngơn ngữ C# trong tiến trình xây dựng hệ thống. o Xây dựng sản phẩm hồn thiện sử dụng tại Trường THPT chuyên Lê Quý Đơn. 3. PHƯƠNG PHÁP NGHIÊN CỨU - Tư liệu: Tổng hợp các tài liệu liên quan đến thuật tốn cặp ghép và tham lam, cũng như các quy chế trường chuyên. - Phân tích: Phân tích quy chế trường chuyên, xác định các yêu cầu của từng đối tượng cụ thể. - Thực nghiệm: Xây dựng chương trình chia thời khĩa biểu và xuất ra tệp Excel, tích hợp với CSDL của Phịng giáo vụ. 6 Tổng hợp lại hệ thống để đưa thời khĩa biểu lên WebSite của Trường chuyên Lê Quý Đơn Đà Nẵng. 4. Ý NGHĨA KHOA HỌC VÀ THỰC TIỄN CỦA ĐỀ TÀI - Về mặt lý thuyết: Đề tài nghiên cứu giúp hiểu rõ hơn về sự kết hợp thuật tốn cặp ghép và thuật tốn tham lam. - Về mặt thực tiễn: Xây dựng một chương trình phục vụ nhu cầu thực hiện chia thời khĩa biểu tự động nhằm giảm thời gian và chi phí bằng tay như hiện nay. 5. NỘI DUNG CỦA LUẬN VĂN Luận văn được trình bày cĩ 3 chương chính. Chương 1: Mơ hình bài tốn thời khĩa biểu trường chuyên Chương này trình bày tổng quan bài tốn thời khĩa biểu tại các trường THPT, THPT chuyên trên tồn quốc, cũng như các phần mềm thời khĩa biểu hiện cĩ tại Việt Nam và trên thế giới. Chương 2: Kết hợp thuật tốn cặp ghép và tham lam giải quyết bài tốn thời khĩa biểu Trong chương này trình bày cơ sở lý thuyết của thuật tốn cặp ghép và thuật tốn tham lam, giải pháp kết hợp của hai thuật tốn này vào việc giải quyết bài tốn thời khĩa biểu trường chuyên. Chương 3: Xây dựng chương trình và thử nghiệm Triển khai một chương trình máy tính cài đặt phần mềm thời khĩa biểu trường chuyên được thể hiện chi tiết; thử nghiệm và đánh giá các kết quả đạt được thơng qua việc áp dụng thuật tốn cặp ghép và tham lam, tự động hĩa bài tốn TKB 7 trường chuyên và các chức năng tinh chỉnh thủ cơng, nhằm tạo ra một thời khĩa biểu tinh về chất, áp dụng tốt cho trường chuyên trên tồn quốc. 8 CHƯƠNG 1 – BÀI TỐN THỜI KHĨA BIỂU TRƯỜNG THPT CHUYÊN Bài tốn xếp thời khĩa biểu đã từ lâu trở thành một bài tốn nổi tiếng và thu hút được sự quan tâm của rất nhiều nhà nghiên cứu, nhiều chuyên gia trong các lĩnh vực liên quan. Sự "nổi tiếng" của bài tốn này khơng chỉ được đo bởi độ phức tạp của vấn đề, mà cịn ở tính thực tiễn, khả năng áp dụng rất cao trên thực tế. Bất cứ một nhà trường nào, thời khĩa biểu học tập của học sinh và giảng dạy của giáo viên đã và luơn là bộ xương sống cơ bản nhất kết nối hầu như tồn bộ các hoạt động của nhà trường. Chính vì lẽ đĩ bài tốn xếp thời khĩa biểu trở thành một trong những vấn đề chính và quan trọng vào bậc nhất của mỗi nhà trường. Hiện nay ở Việt Nam cĩ khoảng 25 000 trường phổ thơng từ Tiểu học đến THCS và THPT và cĩ nghĩa là sẽ cĩ tối thiểu từng đĩ giáo viên đang làm nhiệm vụ xếp thời khĩa biểu. Xếp thời khĩa biểu thực sự là một cơng việc khĩ. Cái khĩ ở đây được thể hiện theo 3 lý do sau: Thứ nhất, việc xếp TKB là một việc địi hỏi tư duy, suy luận, tính tốn rất phức tạp, rất dễ nhầm lẫn, trùng giờ trùng tiết. Phải là người cĩ kinh nghiệm và hiểu biết về cơng việc này mới làm được. Thứ hai, người xếp thời khĩa biểu là người "làm dâu trăm họ", rất khĩ cĩ thể đáp ứng được các nhu cầu khác nhau của tồn bộ đội ngũ giáo viên trong trường. Các ràng buộc của giáo viên trong nhà trường lại rất mâu thuẫn, chồng chéo lẫn nhau. Thứ ba, cơng việc xếp TKB địi hỏi một số tư duy đặc biệt, rất đặc thù của "nghề xếp TKB". Khơng phải ai cũng cĩ thể rèn luyện để cĩ những kinh nghiệm và tư duy này. Người xếp TKB, ngồi việc phải 9 rất am hiểu về các chương trình mơn học, hiểu rõ tính nết và yêu cầu của các giáo viên trong nhà trường, cịn phải cĩ được những tư duy nghề nghiệp của cơng việc xếp thời khĩa biểu [16]. Trong chương này chúng tơi trình bày các vấn đề sắp xếp TKB tại các trường THPT trên tồn quốc, giới thiệu tổng quan bài tốn TKB trường chuyên, các phần mềm thời khĩa biểu hiện cĩ tại Việt Nam và thế giới. 1.1. VẤN ĐỀ SẮP XẾP THỜI KHĨA BIỂU TRƯỜNG THPT 1.1.1. Dùng phương pháp thủ cơng để sắp xếp thời khĩa biểu Trường THPT 1.1.2. Dùng phần mềm để sắp xếp TKB Trường THPT 1.2. SẮP XẾP THỜI KHĨA BIỂU TRƯỜNG THPT CHUYÊN Bài tốn sắp xếp TKB là một bài tốn khĩ. Việc chia thời khĩa biểu cho các Trường THPT Chuyên trên tồn quốc lại càng 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. Mặc dù hiện nay Cơng nghệ Thơng tin phát triển rất mạnh, đã giải quyết được nhiều ứng dụng trong cuộc sống, nhưng chưa cĩ thuật tốn nào tối ưu để giải quyết được bài tốn thời khĩa biểu. Các phần mềm sắp xếp TKB hiện nay, chưa cĩ phần mềm nào áp dụng được cho trường THPT chuyên trên tồn quốc nĩi chung, trường THPT chuyên Lê Quý Đơn nĩi riêng. Vì vậy, tại các trường này phải dùng tay để sắp xếp TKB nên tốn rất nhiều thời gian và 10 cơng sức, nhất là người sắp xếp TKB phải hiểu sâu sắc về chuyên mơn, cách phân chia số tiết cụ thể cho từng bộ mơn chuyên, nắm được quy chế trường chuyên cũng như các đặc thù của từng giáo viên dạy chuyên, họ phải biết phân chia theo từng giai đoạn để đáp ứng kịp thời tiến độ và theo kịp yêu cầu của Bộ Giáo dục và Đào tạo. Từ đĩ mới thực hiện việc chia TKB cho phù hợp, cuối cùng cho ra được một TKB tương đối tốt, tuy nhiên phải mất rất nhiều thời gian và cơng sức. 1.2.1. Giới thiệu bài tốn Từ những hiện trạng khĩ khăn trong vấn đề giải quyết bài tốn TKB trường THPT chuyên cũng như hệ thống THPT chuyên trong đại học (gọi tắt là trường chuyên), chúng tơi chọn “Nghiên cứu kết hợp thuật tốn cặp ghép và tham lam giải quyết bài tốn thời khĩa biểu trường chuyên” với bộ dữ liệu thực của trường THPT chuyên Lê Quý Đơn làm dữ liệu cở sở để giải quyết bài tốn TKB trong luận văn này. Bài tốn đặt ra là vấn đề xếp thời khĩa biểu cho trường THPT chuyên Lê Quý Đơ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 tốn đặt ra 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 Lê Quý Đơn, chẳng hạn như: đặt lớp học vào một phịng sao cho tương ứng về sức chứa của nĩ, tránh việc học trùng giờ tại một phịng của các lớp, nhất là những lớp ghép; giáo viên sẽ dạy theo giờ qui định trong bảng phân cơng. Thơng thường, cơng việc này được làm bằng tay, tất nhiên chúng ta luơn thực hiện được và luơn cho ra kết quả tương đối tốt, nhưng phải mất nhiều thời gian và ít nhất phải cĩ kinh nghiệm xếp lịch nếu 11 khơng muốn cĩ sai sĩt xảy ra, chẳng hạn như: chỗ này thừa phịng, chỗ khác lại thiếu, sai chỗ, sai giờ... .Vấn đề của bài tốn là ngồi việc thực hiện đúng, chính xác, cịn phải tốt hơn, nhanh hơn và hiệu quả hơn cơng việc xếp lịch bằng tay mà chúng ta vẫn phải làm. Trường THPT chuyên Lê Quý Đơn là trường cĩ nhiều đặc trưng riêng, nên việc xếp TKB cũng cĩ nhiều điểm khác so với các trường THPT khác. Khi chia TKB cho lớp ghép là một vấn đề cần quan tâm. Lớp ghép chuyên Anh - Pháp, thì tại một thời điểm phải cĩ hai giáo viên cùng dạy cho lớp này tại hai phịng khác nhau nhưng phải đảm bảo các tính chất của một lớp chuyên. Đối với giáo viên là nam cĩ độ tuổi từ 50 trở lên hoặc giáo viên nữ cĩ độ tuổi lớn hơn 40 thì khơng được phép dạy 4 tiết liên tục trên một buổi. Hay đối với giáo viên là nữ cĩ con nhỏ hơn 18 tháng tuổi thì khơng được dạy tiết đầu hay tiết cuối mỗi buổi. Điều đáng nĩi ở đây là phải làm thế nào đĩ mà TKB cho mỗi giáo viên phải được cho là tốt nhất. 1.2.2. Phát biểu bài tốn Ngay khi vấn đề được đặt ra, chúng ta đã thấy bài tốn phải được giải quyết trên hai nền tảng cơ bản: nghiệp vụ và kỹ thuật. Muốn đọc hiểu được một thơng tin của thời khĩa biểu, yêu cầu dữ liệu phải được hiển thị đầy đủ, khơng thiếu sĩt, khơng bị sai lệch, phải phù hợp với nghiệp vụ đề ra. Phần kỹ thuật cũng vậy, phải xử lý tất cả những yêu cầu riêng biệt từ các đối tượng gửi đến, chúng được xem như là thành phần ràng buộc của bài tốn, bắt buộc vấn đề phải thỏa mãn và đáp ứng hồn tồn. Vì vậy, chúng tơi sẽ phân tích bài tốn trên hai thành phần đĩ. 12 1.2.3. Dữ liệu bài tốn Như đã nĩi ở trên, thơng tin sẽ phát sinh từ các đối tượng chính trong bài tốn. Do đĩ, các dữ liệu luơn cĩ mối liên hệ với nhau, phần lớn vì nhu cầu nghiệp vụ mà dữ liệu xuất hiện tương đối nhiều. Trong bài tốn xếp thời khĩa biểu của trường THPT chuyên Lê Quý Đơn, cụ thể sẽ địi hỏi các thơng tin sau: - Danh sách cơ sở o Danh sách giáo viên. o Danh sách khĩa học (Khối 10, Khối 11, Khối 12). o Danh sách lớp học: o Danh sách phịng học (30 phịng, chia làm khu A, khu B và khu C). o Danh sách mơn học và số tiết học do Bộ Giáo dục và Đào tạo quy định. o Danh sách mơn học và số tiết học do trường điều chỉnh (theo từng giai đoạn). o Danh sách 12 mơn học bắt buộc cho các lớp: Tốn, Lý, Hĩa, Sinh, Tin, Văn, Sử, Điạ, Anh, Pháp, Cơng Dân, Nơng Nghiệp/Cơng Nghiệp. o Danh sách mơn chuyên cho từng lớp: Tốn học,Vật Lý, Hĩa học, Sinh học, Tin học, Ngữ Văn, Lịch Sử, Điạ Lí,Tiếng Anh, Tiếng Pháp. - Bảng phân cơng giáo viên giảng dạy tại các lớp. - Bảng yêu cầu ràng buộc của giáo viên với lịch dạy. - Bảng yêu cầu ràng buộc của lớp với lịch học. - Bảng yêu cầu ràng buộc của phịng với lịch sử dụng. 13 1.2.3.1. Các đối tượng sử dụng Các đối tượng chính yếu xung quanh mơ hình xếp thời khĩa biểu, chính là thành phần đầy đủ tính năng của chương trình trong bài tốn. Tất cả được liệt kê như sau: - Giáo viên, - Lớp học, - Mơn học, - Phịng học, - Số tiết. 1.2.3.2. Mối quan hệ giữa các đối tượng Trên lịch lớp học, thể hiện rõ thơng tin các đối tượng liên quan nhau ở tại thời điểm tiết học, tất cả cùng nằm trong một bảng này. Hay nĩi cách khác bảng lịch lớp học là phần thể hiện mối quan hệ của các đối tượng: giáo viên, lớp học và mơn học. Sau này lớp học đặt trong một lịch cơ sở cụ thể, gây phát sinh mới, tạo quan hệ thứ hai, giữa lớp học và phịng học. Đĩ là mối quan hệ lịch cơ sở. 1.2.4. Các ràng buộc bài tốn Trong mơ hình bài tốn, các đối tượng cĩ những yêu cầu, ràng buộc riêng biệt khác nhau với cơng việc của mình, và được nhập vào kèm theo ngay khi đối tượng xuất hiện. Song song đĩ, với nghiệp vụ lịch thực thi, cĩ rất nhiều thơng số, và mối quan hệ các đối tượng tạo ra một ràng buộc chung, như là bộ luật thống nhất trong tồn hệ thống. Phần mềm TKB phải thỏa mãn các ràng buộc dưới đây: - Mỗi giáo viên cĩ ràng buộc riêng. - Mỗi lớp học cĩ ràng buộc riêng. 14 - Mỗi phịng học cĩ ràng buộc riêng. - Mơn học tại một lớp khơng xuất hiện trong bảng lịch lớp nhiều lần. - Giáo viên và mơn học trong cùng một lớp khơng xuất hiện trong bảng lịch lớp nhiều lần. - Tại một thời điểm khơng xuất hiện nhiều lớp học tại một phịng trong bảng lịch cơ sở. - Sức chứa của phịng phải lớn hơn hoặc bằng số học sinh cĩ trong lớp học mà được xếp học ở phịng đĩ. - Tại một thời điểm lớp duy nhất học một mơn. - Mỗi lớp học chỉ học trong một buổi. - Số tiết học của một mơn trong 1 lần, phải theo qui định; tối đa 2 tiết trong một lần học, cịn đối với lớp học các mơn chuyên thì phải học liên tiếp 4 tiết. 1.2.4.1. Ràng buộc dữ liệu nhập vào 1.2.4.2. Ràng buộc nghiệp vụ - thời gian 1.2.4.3. Ràng buộc nghiệp vụ - chuyên mơn 1.2.4.4. Các yêu cầu chức năng 1.2.5. Các yêu cầu phi chức năng 1.3. CÁC CƠNG CỤ HỖ TRỢ HIỆN TẠI 1.3.1. Phần mềm thời khĩa biểu tại Việt Nam 1.3.2. Phần mềm thời khĩa biểu trên thế giới 15 1.4. TỔNG KẾT CHƯƠNG 1 Từ hiện trạng của bài tốn thời khĩa biểu trường THPT nĩi chung, trường chuyên trên tồn quốc nĩi riêng, đã cho chúng ta thấy được: Hiện nay, Cơng nghệ Thơng tin đang trên đà phát triển rất mạnh và đã ứng dụng nhiều vào trong cuộc sống, nhưng vẫn chưa cĩ thuật tốn nào tối ưu để giải quyết bài tốn thời khĩa biểu. Vì vậy, chúng tơi chọn kết hợp thuật tốn cặp ghép và thuật tốn tham lam giải quyết bài tốn TKB trường chuyên. CHƯƠNG 2 – KẾT HỢP THUẬT TỐN CẶP GHÉP VÀ THAM LAM GIẢI QUYẾT BÀI TỐN THỜI KHĨA BIỂU Từ những yêu cầu bức thiết của trường THPT chuyên Lê Quý Đơn nĩi riêng, trường chuyên trên tồn quốc nĩi chung, áp dụng các phần mềm TKB hiện cĩ trên thị trường vào việc sắp xếp TKB cho các trường chưa được tốt, chúng tơi đã chọn kết hợp thuật tốn cặp ghép và thuật tốn tham lam giải quyết bài tốn TKB với hai lý do chính sau: thứ nhất, thuật tốn cặp ghép dùng để thỏa mãn ràng buộc của từng giáo viên; Thứ hai, thuật tốn tham lam dùng để chọn các cặp giáo viên ở bước xếp thơ TKB đầu tiên. Trong chương này chúng ta trình bày cơ sở lý thuyết của thuật tốn cặp ghép và thuật tốn tham lam, giải pháp kết hợp của hai thuật tốn này vào việc giải quyết bài tốn thời khĩa biểu trường chuyên. 2.1. THUẬT TỐN CẶP GHÉP 2.1.1. Bài tốn phân cơng 2.1.2. Phân tích bài tốn 2.1.3. Thuật tốn 16 2.1.3.1. Các khái niệm - Đường pha (Alternating Path) - Một đường mở (Augmenting Path) 2.1.3.2. Thuật tốn Hungari (cặp ghép) Bước 1: Khởi tạo: Một bộ ghép M := Ø Bước 2: Với mọi đỉnh x*∈X, ta tìm cách ghép x* như sau: Bắt đầu từ đỉnh x* chưa ghép, thử tìm đường mở bắt đầu ở x* bằng thuật tốn tìm kiếm trên đồ thị (BFS hoặc DFS - thơng thường nên dùng BFS để tìm đường qua ít cạnh nhất) cĩ hai khả năng xảy ra: - Hoặc tìm được đường mở thì dọc theo đường mở, ta loại bỏ những cạnh đã ghép khỏi M và thêm vào M những cạnh chưa ghép, ta được một bộ ghép mới nhiều hơn bộ ghép cũ 1 cạnh và đỉnh x* trở thành đã ghép. - Hoặc khơng tìm được đường mở thì do ta sử dụng thuật tốn tìm kiếm trên đồ thị nên cĩ thể xác định được hai tập: o VisitedX = {Tập những X_đỉnh cĩ thể đến được từ x* bằng một đường pha} o VisitedY = {Tập những Y_đỉnh cĩ thể đến được từ x* bằng một đường pha} Gọi ∆ là trọng số nhỏ nhất của các cạnh nối giữa một đỉnh thuộc VisitedX với một đỉnh khơng thuộc VisitedY. Dễ thấy ∆ > 0 bởi nếu ∆ = 0 thì tồn tại một 0_cạnh (x, y) với x∈VisitedX và y∉VisitedY. Vì x* đến được x bằng một đường pha và (x, y) là một 0_cạnh nên x* cũng đến được y bằng một đường pha, dẫn tới y ∈ VisitedY, điều này vơ lý. 17 Biến đổi đồ thị G như sau: Với ∀ x ∈ VisitedX, trừ ∆ vào trọng số những cạnh liên thuộc với x, Với ∀ y ∈ VisitedY, cộng ∆ vào trọng số những cạnh liên thuộc với y. Lặp lại thủ tục tìm kiếm trên đồ thị thử tìm đường mở xuất phát ở x* cho tới khi tìm ra đường mở. Bước 3: Sau bước 2 thì mọi X_đỉnh đều được ghép, in kết quả về bộ ghép tìm được. Mơ hình cài đặt của thuật tốn Hungari cĩ thể viết như sau: ; for (x*∈ X) do begin repeat ; if then <Biến đổi đồ thị G: Chọn ∆ := …>; until ; <Dọc theo đường mở, loại bỏ những cạnh đã ghép khỏi M và thêm vào M những cạnh chưa ghép>; end; ;[4] 2.1.3.3. Cài đặt thuật tốn - Phương pháp đối ngẫu Kuhn-Munkres - Sơ đồ cài đặt phương pháp Kuhn-Munkres 2.1.3.4. Biểu diễn bộ ghép 2.1.3.5. Tìm đường mở 2.2. THUẬT TỐN THAM LAM 2.2.1. Khái niệm 18 2.2.2. Thuật tốn 2.2.2.1. Phương pháp 2.2.2.2. Cấu trúc tổng quát của thuật tốn Thamlam(C:tập hợp các ứng cử viên) // hàm trả về giải pháp tối ưu, gồm các ứng cử viên Begin S = Ø //S là giải pháp tối ưu While ( C ≠ Ø và S chưa là giải pháp) do X = chọn( C) // chọn x từ tập c theo tiêu chí của hàm chọn C = C – {x} If (SU {x} cĩ triển vọng là giải pháp) then S:=SU {x} Endif Endwhile if (S là lời giải) then return S else return 0 endif end 4 [1] 2.2.2.3. Ví dụ áp dụng[1] 2.2.2.4. Tính chất của chiến lược tham lam [1] 2.3. GIẢI PHÁP TỔNG THỂ CHO BÀI TỐN TKB Thuật tốn cặp ghép đĩng vai trị quan trọng trong quá trình giải quyết bài tốn TKB trường chuyên. Vì vậy, trước tiên chúng ta cần cải tiến thuật tốn cặp ghép. 2.3.1. Cải tiến thuật tốn cặp ghép 2.3.2. Đánh giá độ phức tạp 19 2.3.3. Giải pháp kết hợp Bài tốn thời khĩa biểu cĩ thể được định nghĩa là một bài tốn tìm kiếm chuỗi tối ưu để thực hiện một tập các hoạt động chịu tác động của một tập các ràng buộc cần phải được thỏa mãn. Người làm nhiệm vụ chia thời khĩa biểu thường cố gắng thử đến mức tối đa sự sử dụng các cá thể, máy mĩc và tối thiểu thời gian địi hỏi để hồn thành tồn bộ quá trình nhằm sắp xếp lịch. Vì thế bài tốn thời thĩa biểu là một vấn đề rất khĩ để giải quyết. Hiện nay cĩ nhiều khả năng để phát triển các kỹ thuật hiện đại để giải quyết bài tốn này. Những kỹ thuật đĩ bao gồm: các tiếp cận Trí tuệ nhân tạo như hệ thống tri thức cơ sở (knowledge-based systems), bài tốn thoả mãn ràng buộc, hệ chuyên gia, mạng Nơron và các tiếp cận của các Nghiên cứu hoạt động: lập trình tính tốn, quy hoạch động, tìm kiếm nhánh và đường biên, kỹ thuật mơ phỏng, tìm kiếm Tabu và phương pháp nút cổ chai. Ở đây chúng tơi chọn kết hợp thuật tốn cặp ghép và thuật tốn tham lam nhằm giải quyết bài tốn thời khĩa biểu trường chuyên với bộ dữ liệu thực của Trường THPT chuyên Lê Quý Đơn làm cơ sở để giải quyết bài tốn thời khĩa biểu. - Trong khi giải quyết bài tốn thời khĩa biểu trường chuyên cần chú ý đến giải pháp kết hợp thuật tốn cặp ghép và tham lam để giải quyết tùy theo từng trường hợp cụ thể mà cĩ thể sử dụng thuật tốn tham lam hay kết hợp tính tham lam trong khi dùng thuật tốn cặp ghép. - Bước đầu ta chọn những cặp ghép gồm các giáo viên cĩ cùng chung số tiết là lớn nhất trong một buổi dạy để ghép lại với nhau trước theo từng cặp cụ thể. Nhằm đưa các cặp ghép này 20 vào cho việc chia thời khĩa biểu trước, nhằm tạo được sự ưu tiên số một cho các cặp ghép này. - Bước tiếp theo ta chọn các giáo viên cĩ số tiết dạy ít dần tạo nên cặp ghép đồng thời ta sử dụng thuật tốn tham lam để quét tất cả các giáo viên cĩ số tiết dạy đơn trên một lớp trong từng buổi cụ thể để tạo nên giải pháp tốt hơn. - Tại bước này ta sử dụng thuật tốn cặp ghép cùng với tham lam để tạo nên việc tinh chỉnh tốt dần, tức làm mịn dần. - Sau cùng ta chọn tất cả số tiết cịn lại của từng giáo viên cụ thể để tạo nên cặp ghép tốt hơn, đồng thời từ đĩ ta đưa ra được kết quả đầu ra tương đối tốt hơn. - Việc giải quyết bài tốn thời khĩa biểu trường chuyên là nhu cầu cần thiết nhất hiện nay, tuy nhiên chúng ta cần vận dụng các thuật tốn đã nêu ở trên một cách thuần thục nhất. Cũng như kết hợp triệt để thuật tốn cặp ghép và tham lam thì mới cĩ thể cho ra kết quả tốt hơn từ các tập ứng viên đã chọn. Đầu vào là danh sách của giáo viên theo tổ bộ mơn, số tiết thực dạy theo từng buổi của giáo viên đĩ. Sau khi đưa vào xử lý bởi sự kết hợp của hai thuật tốn trên thì phải cho ra kết quả đầu ra tốt hơn kết quả hiện nay đang cĩ. Xuất phát từ những ý tưởng trên, chúng tơi đã chọn sự kết hợp thuật tốn cặp ghép và tham lam nhằm tìm ra giải pháp tốt hơn cho việc giải quyết bài tốn thời khĩa biểu trường chuyên. Với bộ dữ liệu của trường THPT chuyên Lê Quý Đơn làm dữ liệu cơ sở. 2.4. TỔNG KẾT CHƯƠNG 2 Trong chương này, chúng tơi đã trình bày được cơ sở lý thuyết cũng như các giải pháp kết hợp của thuật tốn cặp ghép và tham lam 21 với những ứng dụng cụ thể. Với các giải pháp kết hợp chúng tơi đã cải tiến thuật tốn cặp ghép nhằm giải quyết tốt hơn bài tốn thời khĩa biểu trường chuyên. Nội dung chính của chương này thể hiện đầy đủ các yêu cầu, giải pháp, tính đúng đắng khi vận dụng thuật tốn cặp ghép và thuật tốn tham lam. CHƯƠNG 3 – XÂY DỰNG CHƯƠNG TRÌNH VÀ THỬ NGHIỆM Nội dung chính của chương này gồm cĩ ba phần chính: thiết kế chi tiết, thử nghiệm và đánh giá kết quả, các giải pháp và định hướng của phần mềm thời khĩa biểu trường chuyên. 3.1. THIẾT KẾ CHI TIẾT Bài tốn thời khĩa biểu trường chuyên, cần được kết hợp chặt chẽ với khung chương trình đào tạo chi tiết được nhà trường thiết kế dựa trên khung chương trình chuẩn của Bộ giáo dục và Đào tạo, nhằm triển khai vào thực tế cho nhà trường. Vì vậy, tại mục này chúng ta nên biết sơ lược về chương trình quản lý khung đào tạo trường chuyên. 3.1.1. Chương trình quản lý khung đào tạo 3.1.2. Giải pháp chính cho bài tốn thời khĩa biểu trường chuyên Trường THPT chuyên cĩ những đặc thù riêng biệt và rất khác so với các trường THPT trên tồn quốc. Vì vậy, để giải quyết bài tốn thời khĩa biểu cho các nhà trường này cần phải cĩ mơ hình và giải pháp riêng. 22 3.1.3. Giải quyết vấn đề lớp ghép Anh – Pháp 3.1.4. Phân cơng giáo viên giảng dạy cho các lớp 3.1.5. Kết hợp thuật tốn cặp ghép và tham lam trong bài tốn TKB Trong khi giải quyết bài tốn TKB trường chuyên chúng tơi dùng thuật tốn cặp ghép để chọn các giáo viên cĩ tổng số tiết dạy cho các lớp trên buổi và trên tuần là nhiều nhất. Đồng thời dùng thuật tốn tham lam để chọn những giáo viên cịn lại để cuối cùng cho ra được một TKB thơ. 3.1.5.1. Thuật tốn cặp ghép Từ bảng phân cơng giảng dạy ta lọc những giáo viên cĩ tổng số tiết dạy cho các lớp và tổng số tiết dạy trên một buổi là lớn nhất, đồng thời chúng ta kiểm tra các ràng buộc nếu thỏa mãn ta dùng thuật tốn cặp ghép chia TKB cho những giáo viên này. 3.1.5.2. Xây dựng bộ ghép đầy đủ Áp dụng thuật tốn cặp ghép để chọn ra các cặp giáo viên thỏa mãn các yêu cầu ràng buộc của bài tốn TKB nhằm xây dựng được bộ ghép đầy đủ cho những giáo viên này được mơ tả qua hình 3.9. 3.1.5.3. Thuật tốn tham lam 3.1.6.Dữ liệu chính bài tốn thời khĩa biểu trường chuyên Bao gồm các dữ liệu tham chiếu quan trọng dùng làm cơ sở chính trong mơ hình bài tốn Thời khĩa biểu. Nhĩm này bao gồm 4 đối tượng chính là Lớp học, Giáo viên, Phịng học và Mơn học. 3.1.6.1. Lớp học 23 3.1.6.2. Giáo viên 3.1.6.3. Phịng học 3.1.6.4. Mơn học 3.1.6.5. Dữ liệu kế hoạch giảng dạy 3.2. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ Phần mềm xếp TKB trường chuyên với nhiều tính năng tính năng đột phá theo hướng tối ưu hĩa thời khĩa biểu, nhằm giải quyết bài tốn thời khĩa biểu trường THPT chuyên cũng như hệ thống trường chuyên trên tồn quốc. Kết hợp chặt chẽ thuật tốn cặp ghép và thuật tốn tham lam đã giúp cho việc giải quyết tốt hơn bài tốn thời khĩa biểu trường chuyên, với những tính năng nổi trội được thử nghiệm qua thực tế và cho ra kết quả khả quan. Sau đây là mơ tả một số tính năng chính quan trọng nhất của phần mềm TKB liên quan đến vấn đề quan trọng nhất của bài tốn xếp thời khĩa biểu là mơ phỏng tư duy xếp, đánh giá và tối ưu hĩa điều chỉnh thời khĩa biểu. 3.2.1. Xếp tự động hồn tồn thời khĩa biểu 3.2.2. Tinh chỉnh dữ liệu của các giáo viên tham gia 3.2.3. Ba chức năng tinh chỉnh xếp thời khĩa biểu trường chuyên 3.3. TỔNG KẾT CHƯƠNG 3 Trong chương này, chúng tơi đã phân tích chi tiết bài tốn TKB trường chuyên; thể hiện được giải pháp chính của bài tốn, giải quyết vấn đề lớp ghép, ứng dụng thuật tốn cặp ghép và thuật tốn tham lam trong khi giải quyết bài tốn. Sử dụng bộ dữ liệu thực của trường 24 THPT chuyên Lê Quý Đơn làm dữ liệu cơ sở để minh họa cho bài tốn, đồng thời đưa ra được một số chức năng tinh chỉnh thủ cơng và đã giải quyết tốt hơn bài tốn TKB trường chuyên. 25 KẾT LUẬN VÀ KIẾN NGHỊ 1. KẾT QUẢ ĐẠT ĐƯỢC Kết hợp thuật tốn cặp ghép và thuật tốn tham lam vào việc giải quyết bài tốn thời khĩa biểu trường chuyên là khâu đột phá ban đầu cho việc Tin học hĩa tồn bộ việc xếp thời khĩa biểu cũng như các cơng việc quản lý khác của Trường THPT Chuyên Lê Quý Đơn, hệ thống trường chuyên trên tồn quốc; cho ra được một sản phẩm xếp thời khĩa biểu tương đối tốt với nhiều tính năng nổi trội: Việc cập nhật, xử lý dữ liệu nhanh với tốc độ gần như tức thời. Thơng tin được thể hiện trên màn hình một cách hợp lý, cho phép người dùng quan sát một khơng gian rộng lớn của thời khĩa biểu, trên màn hình hiện rõ thơng tin trong 1 buổi học của một lớp học cĩ liên kết với thời khĩa biểu của giáo viên và phịng học tương ứng. Chương trình đã xử lý được các kỹ thuật đặc thù của thời khĩa biểu như ghép lớp, tách lớp. Phần mềm xếp tự động hồn tồn, dữ liệu đáp ứng hầu hết các ràng buộc thơng thường của thời khĩa biểu. Phần mềm TKB trường chuyên đưa ra được nhiều cơng cụ tinh chỉnh hợp lý như xếp tay, chuyển tiết, chuyển phịng học, chuyển giáo viên, gợi ý xếp, tìm kiếm thơng tin tối ưu, xĩa, ... Các cơng cụ này hồn tồn được thực hiện bằng các thao tác như chuột, bàn phím rất đơn giản, thuận tiện với người dùng. Phần mềm cĩ thể kết nối với các module khác của hệ thống như các phần mềm Tuyển Sinh, Quản lý Chương trình Đào tạo, Quản lý Giáo viên, Quản lý học tập của học sinh, quản lý thư viện. Tồn bộ các module của chương trình được viết bằng ngơn ngữ C# trên nền hệ điều hành Windows 2003/XP/Windown7 cĩ giao diện 26 thân thiện với người dùng và tồn bộ hệ thống thực đơn, giao diện là Tiếng Việt. 2. HƯỚNG PHÁT TRIỂN CỦA LUẬN VĂN Sau phần nghiên cứu trong luận văn, chúng tơi sẽ đi vào nghiên cứu, tìm hiểu giải pháp tốt hơn, nhằm tối ưu hĩa bài tốn TKB trường chuyên, đồng thời chia sẽ ứng dụng trên mạng LAN; dữ liệu TKB sẽ được tập trung lưu trữ và quản lý thống nhất trên máy chủ trong hệ thống mạng LAN. Các máy trạm được kết nối trực tuyến với dữ liệu và hệ thống cho phép nhiều người dùng cùng một lúc truy nhập và làm việc với dữ liệu thời khĩa biểu sẽ làm tăng chức năng hỗ trợ xếp thời khĩa biểu cho nhiều người dùng. Mơ hình TKB tích hợp hồn tồn trên Web; phần dữ liệu chính của chương trình tích hợp với Chương trình đào tạo được cài đặt trên mạng Intranet/Internet cho phép tồn bộ hệ thống được kết nối với các máy tính trên phạm vi lớn. Dữ liệu xếp thời khĩa biểu được kết nối với Server và cho phép nhiều người dùng cùng thao tác và điều khiển dữ liệu. TKB được tích hợp với Web, phần mềm Server cho phép mở rộng khơng hạn chế các chức năng, dịch vụ quan trọng khác của hệ thống quản lý thời khĩa biểu như dịch vụ truy nhập TKB từ xa, dịch vụ nhắn tin thơng qua email, hệ thống nhắc dạy giáo viên thơng qua điện thoại di động, ... Tĩm lại, phần mềm TKB trường chuyên chỉ là bước khởi đầu của việc triển khai ứng dụng phần mềm trong cơng việc hỗ trợ, xếp và quản lý thời khĩa biểu trong các trường THPT chuyên cũng như hệ thống trường chuyên trong đại học.