Báo cáo tài liệu vi phạm
Giới thiệu
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
THỊ TRƯỜNG NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
NGÀNH HÀNG
NÔNG NGHIỆP, THỰC PHẨM
Gạo
Rau hoa quả
Nông sản khác
Sữa và sản phẩm
Thịt và sản phẩm
Dầu thực vật
Thủy sản
Thức ăn chăn nuôi, vật tư nông nghiệp
CÔNG NGHIỆP
Dệt may
Dược phẩm, Thiết bị y tế
Máy móc, thiết bị, phụ tùng
Nhựa - Hóa chất
Phân bón
Sản phẩm gỗ, Hàng thủ công mỹ nghệ
Sắt, thép
Ô tô và linh kiện
Xăng dầu
DỊCH VỤ
Logistics
Tài chính-Ngân hàng
NGHIÊN CỨU THỊ TRƯỜNG
Hoa Kỳ
Nhật Bản
Trung Quốc
Hàn Quốc
Châu Âu
ASEAN
BẢN TIN
Bản tin Thị trường hàng ngày
Bản tin Thị trường và dự báo tháng
Bản tin Thị trường giá cả vật tư
Thông tin
Tài liệu Xanh là gì
Điều khoản sử dụng
Chính sách bảo mật
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
Bài toán NP-đầy đủ của toán tử bao đóng
Đang chuẩn bị liên kết để tải về tài liệu:
Bài toán NP-đầy đủ của toán tử bao đóng
Khánh Ngọc
39
6
pdf
Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG
Tải xuố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 nhson.math@gmail.com 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 .
TÀI LIỆU LIÊN QUAN
Bài giảng Tin học 10 - Bài 4: Bài toán và thuật toán (Bùi Thanh Hoàn)
Ebook Phân loại và phương pháp giải các dạng bài tập Toán 11 (Tập 2): Phần 1
Ebook Phân loại và phương pháp giải các dạng bài tập Toán 11 (Tập 2): Phần 2
Bài giảng môn Toán lớp 2 sách Cánh diều - Bài 22: Bài toán liên quan đến phép cộng, phép trừ
Bài giảng Toán rời rạc - Chương 4: Bài toán tối ưu tổ hợp
Bài giảng Toán kinh tế: Bài toán vận tải mở rộng
Ebook Phân loại và phương pháp giải các dạng bài tập Toán 11 (Tập 1): Phần 1
Ebook Phân loại và phương pháp giải các dạng bài tập Toán 11 (Tập 1): Phần 2
Hướng dẫn giải bài tập Toán 5 (Tập 2): Phần 1
Ứng dụng thuật toán nhánh cận để giải một số bài toán tối ưu liên quan đến chu trình Hamilton dựa trên bài toán TSP
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.