LuanVan.vnLuận Văn
Gửi thư

Một số thuật toán xấp xỉ cho bài toán tối ưu hàm dạng submodular với ràng buộc

Luận án · Tiến sĩ · năm 2024 · đề tài tham khảo

Loại tài liệuLuận án
Bậc họcTiến sĩ
NgànhCông nghệ thông tin
Tác giảHà Thị Kim Dung
Người hướng dẫnHoàng Xuân Huấn; Phạm Văn Cảnh
Cơ sở đào tạoĐại học Quốc gia Hà Nội
Năm2024
NguồnThư viện số Đại học Quốc gia Hà Nội · trang gốc

Tóm tắt

Luận án chọn chủ đề nghiên cứu: “Một số thuật toán xấp xỉ cho bài toán tối ưu hàm dạng submodular với ràng buộc”. Trong đó, do tính độc đáo, giá trị thực tiễn lớn của ba bài toán đã nêu, cùng với các thách thức của chúng, luận án đặt vấn đề nghiên cứu các thuật toán xấp xỉ để giải quyết các bài toán này. Trong đó, mục tiêu chung là các thuật toán xấp xỉ phải hiệu quả với tỉ lệ xấp xỉ cạnh tranh và giảm độ phức tạp truy vấn. Mục tiêu cụ thể như sau: 1. Nghiên cứu bài toán 1 - kSMK với các mục tiêu: - Đề xuất thuật toán xấp xỉ giải quyết bài toán kSMK. Thuật toán đưa ra cho tỉ lệ xấp xỉ cạnh tranh với các thuật toán cho tỉ lệ xấp xỉ tốt nhất hiện nay. Đồng thời, giảm độ phức tạp truy vấn xuống còn tuyến tính; - Giải bài toán khi hàm mục tiêu không còn đơn điệu; 2. Nghiên cứu bài toán 2 - SMKN với các mục tiêu: - Xây dựng mô hình bài toán tối đa hàm submodular với ràng buộc chi phí dưới sự tác động của 2 loại nhiễu: nhiễu cộng và nhiễu nhân; - Đề xuất thuật toán tham lam giải quyết bài toán; - Đề xuất thuật toán luồng cải tiến phương pháp tham lam. 3. Nghiên cứu bài toán 3 - DRSC với các mục tiêu: - Nghiên cứu tính chất DR-submodular và mô hình hóa bài toán DRSC; - Đề xuất thuật toán xấp xỉ hiệu quả giải quyết bài toán DRSC. Với bài toán này, hướng thuật toán đề xuất dựa trên thiết kế song song với độ phức tạp truy vấn và độ phức tạp song song thấp.
Bản toàn văn lưu tại thư viện Đại học Quốc gia Hà Nội

Thông tin và tóm tắt ở trên lấy từ kho số mở của thư viện trường. Bản toàn văn do thư viện trường quản lý — có nơi cho đọc trực tuyến, có nơi cần tài khoản bạn đọc của trường.

Mở tại thư viện trường ↗
Dùng tài liệu tham khảo cho đúng
  • Đọc để hiểu cách người trước đặt câu hỏi, chọn phương pháp, trình bày số liệu — rồi tự làm với dữ liệu và bối cảnh của bạn.
  • Ý, số liệu, bảng biểu lấy từ tài liệu này phải trích dẫn (tác giả, năm, tên đề tài, cơ sở đào tạo).
  • Đề tài trùng tên vẫn làm được nếu khác đơn vị khảo sát, thời gian hoặc cách tiếp cận — nêu rõ điểm khác trong phần mở đầu.

Hướng dẫn chọn đề tài, cấu trúc và số liệu cho ngành này: Luận văn công nghệ thông tin · Hỏi đáp từng chương với người hướng dẫn số: Học Giả Số · Công cụ số: Luận Văn Số.

Đề tài cùng ngành

Tác giả muốn gỡ, sửa thông tin hoặc bổ sung bản toàn văn: gửi yêu cầu qua trang Liên hệ, kèm đường dẫn trang này.