Luận văn Thạc sĩ Khoa học máy tính: Bài toán ghép cặp và ứng dụng trong công tác tuyển sinh

Luận văn “Bài toán ghép cặp và ứng dụng trong công tác tuyển sinh” nhằm mục đích định hướng cho công tác tuyển sinh của các trường đại học đạt chất lượng và hiệu quả, hỗ trợ các em học sinh được học theo đúng sở trường, năng lực để có một điều kiện tốt hơn trong tương lai. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học máy tính: Bài toán ghép cặp và ứng dụng trong công tác tuyển sinh ĐẠI HỌC THÁI NGUYÊN ứTRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN HỒNG HẢI BÀI TOÁN GHÉP CẶP VÀ ỨNG DỤNG TRONG CÔNG TÁC TUYỂN SINH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 2 MỤC LỤCLỜI CẢM ƠN ............................................................................................................. 4DANH MỤC VIẾT TẮT ............................................................................................ 5DANH MỤC CÁC HÌNH ........................................................................................... 6DANH MỤC CÁC BẢNG.......................................................................................... 7Lời nói đầu .................................................................................................................. 8Chương 1: TỔNG QUAN MỘT SỐ VẤN ĐỀ VỀ ĐỒ THỊ .................................... 111.1.Các khái niệm cơ bản .......................................................................................... 111.1.1.Đồ thị ................................................................................................................ 111.1.2.Đồ thị hai phía .................................................................................................. 111.1.3.Đồ thị hai phía đầy đủ ...................................................................................... 121.2.Bài toán ghép cặp không trọng............................................................................ 141.2.1. Bài toán ........................................................................................................... 141.2.2.Thuật toán đường mở ....................................................................................... 161.3.Bài toán ghép cặp với trọng số cực tiểu .............................................................. 171.3.1.Bài toán ............................................................................................................ 171.3.2.Các khái niệm ................................................................................................... 181.3.3.Thuật toán Hungari .......................................................................................... 191.4. Bài toán ghép cặp với trọng số cực đại .............................................................. 211.4.1.Bài toán ............................................................................................................ 221.4.2.Thuật toán......................................................................................................... 221.5.Kết luận chương .................................................................................................. 24Chương 2: BÀI TOÁN GHÉP CẶP ......................................................................... 252.1.Giới thiệu bài toán ............................................................................................... 252.1.1.Phát biểu bài toán ............................................................................................. 252.2.Bài toán hôn nhân bền vững................................................................................ 27 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 32.2.1.Giới thiệu bài toán ............................................................................................ 272.2.2.Đặt bài toán ...................................................................................................... 282.2.3.Các đặc trưng của bài toán ............................................................................... 292.2.4.Điều kiện giải bài toán ..................................................................................... 302.2.5.Thuật toán cho bài toán hôn nhân bền vững .................................................... 302.2.5.1.Ý tưởng và lược đồ thuật toán ....................................................................... 302.2.5.2.Tính ổn định và bền vững ............................................................................. 352.2.6.Triển khai thuật toán ........................................................................................ 402.3.Một số ứng dụng phát triển dựa trên thuật toán hôn nhân bền vững .................. 422.3.1.Bài toán ghép tạng (cho và nhận thận) ............................................................. 422.3.2.Bài toán ghép cặp bác sĩ thực tập và bệnh viện ............................................... 432.4.Kết luận chương .................................................................................................. 43Chương 3: ỨNG DỤNG THUẬT TOÁN GHÉP CẶP TRONG BỐI CẢNHTUYỂN SINH ĐẠI HỌC Ở NƯỚC TA .................................................................. 453.1.Giới thiệu bài toán tuyển sinh ở nước ta ............................................................. 453.2.Ý nghĩa bài toán .................................................................................................. 463.3.Đặt bài toán ......................................................................................................... 483.4.Ý tưởng giải quyết bài toán ................................................................................. 493.5.Áp dụng bài toán hôn nhân bền vững ................................................................. 493.6.Sự khác nhau giữa bài toán hôn nhân bền vững và tuyển sinh đại học. ............. 503.7.Thuật toá ...