TAILIEUCHUNG - Bài toán NP-đầy đủ của toán tử bao đóng

Khóa tối tiểu và phản khóa là những khái niệm có vai trò quan trọng trong toán tử bao đóng. Bài báo giới thiệu về một bài toán tập không khóa của toán tử bao đóng. Bài toán này được bài viết chứng minh có độ phức tạp là NP-đầy đủ. | TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ Trường Đại học Khoa học ĐH Huế Tập 18 Số 1 2021 BÀI TOÁN NP-ĐẦY ĐỦ CỦA TOÁN TỬ BAO ĐÓNG Nguyễn Hoàng Sơn1 Trần Việt Khoa2 1 Khoa Toán Trường Đại học Khoa học Đại học Huế 2 Khoa CNTT Trường Đại học Khoa học Đại học Huế Email Ngày nhận bài 18 02 2021 ngày hoàn thành phản biện 21 5 2021 ngày duyệt đăng 02 6 2021 TÓM TẮT Khóa tối tiểu và phản khóa là những khái niệm có vai trò quan trọng trong toán tử bao đóng. Bài báo giới thiệu về một bài toán tập không khóa của toán tử bao đóng. Bài toán này được bài báo chứng minh có độ phức tạp là NP-đầy đủ. Từ khóa Toán tử bao đóng khóa tối tiểu phản khóa. 1. MỞ ĐẦU Toán tử bao đóng đã xuất hiện từ rất lâu trong toán cũng như toán ứng dụng. Tuy nhiên gần 30 năm trở lại đây toán tử bao đóng có nhiều ứng dụng quan trọng trong các lĩnh vực liên quan về dữ liệu như cơ sở dữ liệu các hệ suy diễn khai phá dữ liệu 1 4 6 9 . Ngoài ra các toán tử bao đóng này cũng có thể tìm thấy trong nhiều lý thuyết thời sự như siêu đồ thị matroid tập thô tập mờ trí tuệ nhân tạo lý thuyết quyết định 3 5 8 10 . Trong các vấn đề nghiên cứu về toán tử bao đóng thì khóa và phản khóa là được nhiều nhà nghiên cứu quan tâm nhất. Bài báo này cũng không ngoài mục đích đó. Trong bài báo này chúng tôi nghiên cứu độ phức tạp của bài toán xác định một tập cho trước có phải không khóa của toán tử bao đóng hay không. Cấu trúc bài báo chia làm 4 phần Sau phần mở đầu phần thứ 2 giới thiệu khái niệm toán tử bao đóng và một số khái niệm kết quả cơ sở liên quan. Phần thứ 3 chúng tôi giới thiệu và chứng minh một bài toán NP-đầy đủ về tập không khóa của toán tử bao đóng. Phần cuối cùng của bài báo là kết luận. 2. MỘT SỐ KHÁI NIỆM CƠ SỞ Mục này nhắc lại một số khái niệm và kết quả cơ sở. Các định nghĩa và kết quả này có thể tìm thấy trong 1 2 10 . 1 Bài toán NP-đầy đủ của toán tử bao đóng Cho U là một tập hữu hạn khác rỗng. Ký hiệu P U là tập lũy thừa của U . Ánh xạ L P U P U thỏa các điều kiện .

• Toán học
• Toán tử bao đóng
• Bài toán tập không khóa
• Trí tuệ nhân tạo
• Bài toán NP đầy đủ
• Thuật toán đa thức
• Khóa tối tiểu
• Siêu đồ thị
• Hệ suy diễn
• Khai phá dữ liệu
• Toán ứng dụng
• Khoa học máy tính
• Phép toán hội
• Hàm chọn đặc biệt
• Điện tử
• dòng điện xoay chiều
• Mạch điện ba pha
• Chỉnh lưu và ổn áp
• Các thiết bị đóng cắt và bảo vệ mạch điện
• Chiếu sáng
• Tính toán mạch điện
• Tài liệu được viết dễ hiểu
• đầy đủ các phần về kỹ thuật điện học
• điện căn bản
• Mang đến cho các bạn khối lượng kiến thức điện học to lớn
• t điện
• mạng điện
• chỉnh lưu
• ổn áp
• mạch điện 3 pha
• Luận văn Thạc sĩ
• Luận văn Thạc sĩ Toán học
• Thuật toán Berlekamp
• Đa thức bất khả quy
• Phân tích đa thức
• Phương pháp toán sơ cấp
• Luận án Tiến sỹ Toán học
• Thuật toán phân tích đa thức một biến
• Đa thức một biến thành nhân tử
• Thuật toán Zassenhaus
• Thuật toán Yu
• Thuật toán phân tích đa thức
• Đại số
• Toán cao cấp
• bài toán đa thức
• Bài toán tối ưu trên tập hữu hiệu
• Bài toán tối ưu đa mục tiêu
• Hàm phân thức a phin
• Thuật toán giải bài toán WP
• Kính lúp table
• Chia đa thức chứa nhiều căn
• Ôn thi THPT Quốc gia
• Kỹ thuật chia đa thức
• Giải Toán phương trình vô tỷ
• Bài giảng Phương pháp tính
• Phương pháp tính
• Toán kỹ thuật
• Nội suy và xấp xỉ hàm
• Xấp xỉ hàm
• Đa thức nội suy
• Đa thức nội suy Lagrange
• Đa thức nội suy Newton
• Bài toán kỹ thuật
• Nội suy
• Spline bậc ba
• Khử Gauss – Jordan
• Vẽ đường cong thực nghiệm đa thức
• Nghiệm đa thức
• Thuật toán khử Gauss Jordan
• Hệ phương trình tuyến tính
• Chu trình Hamilton
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Xây dựng thuật toán đa thức
• Bài toán thuộc lớp NP – khó
• Thuật toán xấp xỉ
• Không gian Euclide
• Thuật toán xấp xỉ nhanh
• Mô hình đa thức
• khoa học điều khiển
• hệ thống kỹ thuật
• điều khiển học
• nghiên cứu tin học
• Lý thuyết thuật toán
• tự động học
• Thuật toán tối ưu hóa dẫn từ xa
• Tên lửa dưới dạng đa thức
• Phương pháp dẫn
• Điều khiển tối ưu
• Hàm chỉ tiêu
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Tiếp cận chia để trị
• Bài toán tháp Hà Nội
• Bài toán tính giá trị đa thức
• Bài toán đếm số dãy con
• Giao thức lớp MAC
• Giao thức lớp Vật lý
• Mạng ad hoc đa chặng
• Thuật toán DSA
• Giải thuật cấp phát kênh động DSA
• Ảnh dải động cao
• Toán tử ánh xạ tông màu hình ảnh
• Nội suy đa thức
• Chỉ số chất lượng tông màu
• Hệ thống thị giác con người
• Luận văn Thạc sĩ Kỹ Thuật
• Hệ thống thông tin
• Bài toán Logarit rời rạc
• Hệ mật ElGamal trên trường đa thức
• Hệ mật ElGamal cổ điển
• Tóm tắt Luận văn Thạc sĩ Kỹ Thuật
• Ngôn ngữ C
• ngôn ngữ lậm trình
• 101 thuật toán
• Thuật toán lập trình
• Ký thuật lập trình
• Hệ phương trình đại số tuyến tính
• Ngôn ngữ lập trình
• Kỹ thuật lập trình
• Đại số đại cương
• Đồng cấu nhóm
• Vành và trường
• Vành đa thức
• Thuật toán chia
• Bài giảng Toán Cao cấp A2
• Thuật Toán chéo hóa ma trận
• Đa thức đặc trưng
• Không gian riêng
• Toán cao cấp A2
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Lý thuyết đồ thị
• Thuật toán đa thức xác định chu trình Hamilton
• phương pháp sai phân
• phương trình elliptic
• công thức đa miền
• thuật toán chia miền
• luận văn
• báo cáo khoa học
• Bài giảng Toán tổ hợp
• Toán tổ hợp
• Kỹ thuật đếm
• Sử dụng sơ đồ ven
• Nguyên lý bù trừ
• Đa thức quân xe