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...
Nội dung trích xuất từ tài liệu:
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 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 : : 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 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: 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 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 ñ 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 toán là ngoà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 toá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 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” 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 hoà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 Hoà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 toà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 toà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 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 THPT chuyên Lê Quý Đôn. o Phân tích, ñánh giá và ñ ra gi i pháp chia th i khoá 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 hoà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 toá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 toán c p ghép và thu t toá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 ...