Thuật toán ghép đôi với thông tin không đầy đủ

• Main Author: Lê, Văn Đức
• Other Authors: Nguyễn, Thị Hồng Minh
• Format: Theses and Dissertations
• Language: Vietnamese
• Published: H. : Trường Đại học Khoa học tự nhiên 2018
• Subjects: Toán tin; Thuật toán; Thuật toán không đầy đủ
• Online Access: http://repository.vnu.edu.vn/handle/VNU_123/62462
• Institution: Vietnam National University, Hanoi

Luận văn trình bày tổng quan về vấn đề trong lý thuyết đồ thị và bài toán ghép đôi. Sau đó, trình bày chi tiết về bài toán ghép đôi với thông tin đầy đủ, tính ổn định trong bài toán hôn nhân bền vững. Đặc biệt là tập trung vào thuật toán ghép đôi với thông tin không đầy đủ trong bài toán hai thực tế: bài toán tuyển sinh đại học và bài toán tuyển dụng lao động của các công ty. Nội dung chính của luận văn như sau: Lý thuyết Đồ thị là một trong những ngành khoa học ra đời khá sớm và có nhiều ứng dụng trong hiện đại. Một trong những kết quả đầu tiên trong lý thuyết đồ thị xuất hiện trong bài báo của Leonhard Euler về Bảy cây cầu ở Königsberg, xuất bản năm 1736. Lý thuyết Đồ thị giúp mô tả hình học và giải quyết nhiều bài toán thực tế phức tạp liên quan đến các khái niệm như: đường đi, chu trình, tập ổn định, chu số, sắc số, duyệt đồ thị, đường đi ngắn nhất, tâm đồ thị, luồng vận tải, đồ thị phẳng, cây bao trùm, cây biểu thức, cây mã tối ưu …bằng các thuật toán ngắn gọn và lý thú, nó đã gắn kết nhiều ngành khoa học với nhau. Thuật toán ghép đôi là một ví dụ cụ thể trong lý thuyết đồ thị, Thuật toán ghép đôi được Lloyd Shapley và David Gale giới thiệu vào năm 1962. Shapley và Gale quan sát thấy một số trường hợp, ví dụ như việc tuyển sinh ở các trường đại học hay việc tìm kiếm bạn đời của mỗi người, giao dịch liên quan đến một dạng tương tác mà sau này các nhà kinh tế học gọi là “ghép đôi”. Năm 2012, Alvin Roth được nhận giải Nobel vì các công trình liên quan đến việc “thiết kế thị trường”. Lưu ý là thuật toán Dale - Shapley bản chất cũng là việc thiết kế một luật chơi cho một dạng thị trường, tuy nhiên, trong ví dụ về gán ghép áp dụng cho thị trường hôn nhân ở trên, khả năng áp dụng trên thực tế của nó hầu như không có mà chỉ có vẻ đẹp thuần túy về mặt lý thuyết. Alvin đi xa hơn bằng việc sáng tạo ra các luật chơi áp dụng được, và đã áp dụng trong thực tế. Nói cách khác, ông thiết kế ra các thị trường mà nếu không có các phát minh của ông thì đã không tồn tại hoặc tồn tại dưới một dạng rất không hiệu quả. Trong thực tế, thuật toán ghép đôi được nghiên cứu và phát triển rộng rãi, đặc biệt để giải quyết một số bài toán như: ghép đôi giữa các cặp đôi trong trung tâm môi giới hôn nhân, ghép đôi trong trường hợp hiến và ghép tạng, phân công công tác cho các sinh viên tốt nghiệp ngành y tới các bệnh viện, công tác tuyển sinh đại học, bài toán tuyển dụng lao động của các công ty,…Luận văn này sẽ tập trung trình bày về thuật toán ghép đôi với thông tin đầy đủ được áp dụng với bài toán hôn nhân bền vững, thuật toán ghép đôi với thông tin không đầy đủ được áp dụng với bài toán tuyển sinh đại học và thông tin không đầy đủ, tính ổn định trong bài toán tuyển dụng lao động của các công ty, đưa ra các ví dụ minh họa để có thể hiểu rõ hơn về thuật toán đối với cả thông tin đầy đủ và không đầy đủ.