Nội dung

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN Tel. (84-511) 736 949, Fax. (84-511) 842 771 Website: itf.ud.edu.vn, E-mail: cntt@edu.ud.vn LUẬN VĂN TỐT NGHIỆP KỸ SƯ NGÀNH CÔNG NGHỆ THÔNG TIN MÃ NGÀNH: 05115 ĐỀ TÀI: XÂY DỰNG CHƯƠNG TRÌNH SẮP XẾP THỜI KHÓA BIỂU TRƯỜNG TRUNG HỌC CƠ SỞ SINH VIÊN: MÃ SV: LỚP: CBHD: Nguyễn Duy Tứ 120120355 12TLT.CNTT TS. Trần Thế Vũ ĐÀ NẴNG, 01/2014 LỜI CẢM ƠN Tôi xin chân thành cảm ơn các thầy các cô khoa Công nghệ thông tin, Trường Đại học Bách Khoa, đã hết lòng giảng dạy, truyền đạt cho tôi những kiến thức, kinh nghiệm quý báu giúp chúng tôi có một hành trang vững chắc bước vào đời. Tôi xin chân thành cảm ơn Thầy giáo TS. Trần Thế Vũ đã tận tình hướng dẫn, giúp đỡ tôi trong quá trình thực hiện đồ án tốt nghiệp này. Đồng thời, tôi cũng xin chân thành cảm ơn các bạn trong lớp 12TLT.CNTT đã khích lệ, giúp đỡ, tạo điều kiện thuận lợi để tôi học tập và tiếp xúc thực tế. Mặc dù tôi đã cố gắng hoàn thành đồ án song với khuôn khổ là đồ án tốt nghiệp không tránh khỏi sự thiếu sót. Vì vậy, tôi mong được sự thông cảm góp ý kiến của thầy cô và các bạn. Cuối cùng, tôi xin gởi đến tất cả mọi người lời chúc sức khỏe, hạnh phúc và thành đạt. Sinh viên Nguyễn Duy Tứ i LỜI CAM ĐOAN Chúng tôi xin cam đoan: 1 Những nội dung trong báo cáo này là do chúng tôi thực hiện dưới sự hướng dẫn trực tiếp của thầy giáo TS. Trần Thế Vũ 2 Mọi tham khảo dùng trong báo cáo này đều được trích dẫn rõ ràng tên tác giả, tên công trình, thời gian, địa điểm công bố. 3 Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, chúng tôi xin chịu hoàn toàn trách nhiệm. Sinh viên Nguyễn Duy Tứ ii MỤC LỤC LỜI CẢM ƠN ..............................................................................................................i MỤC LỤC ........................................................................................................... iii DANH MỤC HÌNH VẼ .............................................................................................vi THUẬT NGỮ VÀ TỪ VIẾT TẮT ......................................................................... viii PHẦN MỞ ĐẦU .........................................................................................................1 I. Lý do chọn đề tài ............................................................................................... 1 II. Mục tiêu của đề tài ............................................................................................1 III. Đối tượng nghiên cứu .......................................................................................1 IV. Phương pháp thực hiện .....................................................................................1 CHƯƠNG 1. CƠ SỞ LÝ THUYẾT ..........................................................................2 1.1. CÔNG NGHỆ .NET .........................................................................................2 1.1.1. Tổng quan về .Net ...............................................................................2 1.1.2. Giới thiệu về ngôn ngữ C# ..................................................................2 1.1.3. Lập trình trong môi trường .NET ........................................................4 1.2. GIỚI THIỆU SQL SERVER ............................................................................6 1.3. Giải thuật di truyền và Tính tiến hóa ................................................................ 6 1.3.1. Giải thuật di truyền ..............................................................................6 1.3.2. Tính tiến hóa ......................................................................................16 CHƯƠNG 2. PHÂN TÍCH VÀ THIẾT KẾ CHƯƠNG TRÌNH ............................26 2.1. KHẢO SÁT THỰC TẾ ..................................................................................26 2.1.1. Mô tả đề tài ........................................................................................26 2.1.2. Khảo sát thực tế .................................................................................26 2.2. PHÂN TÍCH THIẾT KẾ HỆ THỐNG ...........................................................30 2.2.1. Thuật toán tiến hóa cải tiến ............................................................... 30 2.2.2. Nhiễm sắc thể của bài toán Thời khóa biểu ......................................30 2.2.3. Quần thể............................................................................................. 33 iii 2.2.4. Thuật toán sắp xếp thời khóa biểu .....................................................33 2.2.5. Khởi tạo quần thể ..............................................................................34 2.2.6. Thuật toán đánh giá độ thích nghi .....................................................36 2.2.7. Thuật toán Đột biến, Biến dị, Lai ghép Nhiễm sắc thể .....................37 2.2.8. Thuật toán khử vi phạm số buổi học của một môn học ....................38 2.2.9. Thuật toán khử vi phạm trùng lịch giáo viên ....................................39 2.2.10. Thuật toán cân bằng số lượng tiết dạy của giáo viên ........................42 2.2.11. Các bước lập lịch ...............................................................................43 2.3. YÊU CẦU .......................................................................................................44 2.3.1. Yêu cầu chức năng ............................................................................44 2.3.2. Yêu cầu phi chức năng ......................................................................45 2.4. BIỂU ĐỒ CHỨC NĂNG................................................................................45 2.4.1. Biểu đồ phân cấp chức năng.............................................................. 45 2.4.2. Biểu đồ luồng dữ liệu ........................................................................46 2.4.3. Phân tích dữ liệu ................................................................................48 2.4.4. Mô hình ERD ....................................................................................49 2.4.5. Mô hình dữ liệu quan hệ....................................................................50 CHƯƠNG 3. XÂY DỰNG CHƯƠNG TRÌNH ......................................................53 3.1. TRANG CHÍNH ............................................................................................. 53 3.2. CÁC CHỨC NĂNG TRONG PHẦN MỀM ..................................................54 3.2.1. Trang giáo viên ..................................................................................54 3.2.2. Trang danh sách lớp ..........................................................................54 3.2.3. Danh sách môn học ...........................................................................55 3.2.4. Danh sách phòng học ........................................................................55 3.2.5. Trang phân lịch ..................................................................................56 3.2.6. Thời khóa biểu học sinh ....................................................................56 3.2.7. Thời khóa biểu giáo viên ...................................................................57 PHẦN KẾT LUẬN ...................................................................................................67 iv I. ĐÁNH GIÁ KẾT QUẢ ĐỀ TÀI ....................................................................67 a. Kết quả đạt được................................................................................67 b. Kết quả chưa đạt được .......................................................................67 II. HƯỚNG GIẢI QUYẾT CỦA ĐỀ TÀI ..........................................................67 TÀI LIỆU THAM KHẢO .........................................................................................68 v DANH MỤC HÌNH VẼ Hình 1-1: Thuật toán chương trình .............................................................................9 Hình 1-2: Bánh xe xổ số............................................................................................11 Hình 1-3: Mô tả các hoạt động của bánh xe xổ số ....................................................12 Hình 1-3: Sơ đồ hình cây của hai NST v1 và v2 ......................................................21 Hình 1-4: Hướng tiếp cận của GA cổ điển................................................................ 24 Hình 1-5: Hướng tiếp cận của Eps ............................................................................24 Hình 2-1: Thời khóa biểu lớp 6/2 ..............................................................................26 Hình 2-2: Thời khóa biểu lớp 7/2 ..............................................................................27 Hình 2-3: Thời khóa biểu lớp 8/3 ..............................................................................27 Hình 2-4: Thời khóa biểu lớp 9/4 ..............................................................................28 Hình 2-5: Mô hình tạo thời khóa biểu thủ công ........................................................29 Hình 2-6: Cấu trúc Nhiễm sắc thể (thời khóa biểu) và các đoạn Gens .....................32 Hình 2-7: Cấu trúc hoàn chỉnh của một Nhiễm sắc thể ............................................33 Hình 2-8: Quần thể ....................................................................................................33 Hình 2-9: Thuật toán phân thời khóa biểu ................................................................ 34 Hình 2-10: Thuật toán tạo quần thể...........................................................................35 Hình 2-11: Quy định tiết được học trong thời khóa biểu ..........................................36 Hình 2-12: Thuật toán tính độ thích nghi của Quần thể và NST .............................. 37 Hình 2-13: Thuật toán khử vi phạm số buổi NST.....................................................39 Hình 2-14: Thuật toán khử vi phạm trùng lịch giáo viên..........................................40 Hình 2-15: Thời khóa biểu trùng lịch dạy môn Toán ...............................................41 Hình 2-16: Thời khóa biểu sau khi hoán đổi hai môn Toán <-> Ngoại ngữ ............41 Hình 2-17: Thuật toán khử vi phạm trùng lịch dạy của giáo viên ............................42 Hình 2-18: Thuật toán lập lịch ..................................................................................43 vi Hình 2-19: Biểu đồ phân cấp chức năng ...................................................................45 Hình 2-20: Biểu đồ mức ngữ cảnh ............................................................................46 Hình 2-21: Biểu đồ mức 0 .........................................................................................46 Hình 2-22: Biểu đồ mức 1 quản lý danh mục ...........................................................47 Hình 2-23: Biểu đồ mức 1 xem thời khóa biểu .........................................................47 Hình 2-24: Mô hình ERD ..........................................................................................49 Hình 2-25: Mô hình dữ liệu quan hệ .........................................................................50 vii THUẬT NGỮ VÀ TỪ VIẾT TẮT Từ viết tắt Chú thích THCS Trung học cơ sở GA Genetic Algorithm (giải thuật di truyền) DNA Deoxyribonucleic acid (vật liệu di truyền) NST Nhiễm sắc thể ES Evolution Strateges TKB Thời khóa biểu CSDL Cơ sở dữ liệu viii Phần mềm sắp xếp thời khóa biểu THCS PHẦN MỞ ĐẦU I. Lý do chọn đề tài Để đáp ứng mục tiêu cơ bản của các dự án Tin học hoá quản lý trong các thời kỳ mới là tạo được một hệ thống thông tin thống nhất phục vụ điều hành và quản lý, chúng tôi chọn hướng phát triển phần mềm sắp xếp thời khóa biểu cho trường THCS nhằm: 1. Tổ chức quản lý, lưu trữ dữ liệu trên hệ thống máy vi tính làm tăng tính an toàn. 2. Sắp xếp, tính toán, phân chia thời khóa biểu một cách nhanh chóng và chính xác. 3. Chi phí đào tạo sử dụng phần mềm không tốn kém. 4. Tổ chức quản lý, phù hợp với các ứng dụng triển khai trên diện rộng. 5. Bảo trì, phát triển phần mềm, phát triển ứng dụng và tích hợp với các ứng dụng khác một cách dễ dàng nhanh chóng. Nên việc mở rộng ít tốn kém nhất. II. Mục tiêu của đề tài Hệ thống dữ liệu đảm bảo việc nhập dữ liệu, quản lý, tra cứu, khai thác dữ liệu được nhanh chóng, thuận tiện. Phần mềm giúp sắp xếp thời khóa biểu nhanh chóng giảm thiều tối đa thời gian và công sức so với việc thực hiện thủ công. Phần mềm có giao diện hài hòa, dễ nhìn, linh hoạt, năng động hơn và đáp ứng được yêu cầu ngày càng cao trong công tác quản lý giáo viên, lớp học, môn học… và nhu cầu của người sử dụng. III. Đối tượng nghiên cứu Toàn bộ cán bộ giáo vụ khoa của trường THCS Phan Bội Châu, huyện Hiệp Đức tỉnh Quảng Nam, các thành phần tin học liên quan đến công tác quản lý bao gồm: hệ quản trị cơ sở dữ liệu, phân tích thiết kế hệ thống, ngôn ngữ lập trình C#. IV. Phương pháp thực hiện Quan sát trực tiếp, trao đổi giao tiếp với cán bộ giáo vụ khoa, xin số liệu cụ thể. SVTH: Nguyễn Duy Tứ; 12TLT.CNTT Trang 1