TAILIEUCHUNG - Về độ phức tạp tính toán của một bài toán liên quan đến tập rút gọn trên bảng quyết định

Bài viết Về độ phức tạp tính toán của một bài toán liên quan đến tập rút gọn trên bảng quyết định trình bày về một bài toán co-NP - đầy đủ liên quan đến các tập rút gọn trên bảng quyết định. Chúng ta gọi A là tập tựa rút gọn trên bảng quyết định DS với tập thuộc tính C U {d} và d là thuộc tính quyết định nếu A chứa một tập rút gọn nào đó. | Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 DOI: VỀ ĐỘ PHỨC TẠP TÍNH TOÁN CỦA MỘT BÀI TOÁN LIÊN QUAN ĐẾN TẬP RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH Nguyễn Ngọc Cương1, Vũ Đức Thi2 1 Khoa Toán-Tin - Học viện an ninh nhân dân Viện Công nghệ thông tin - Đại học quốc gia Hà Nội 2 TÓM TẮT - Trên thực tiễn, các vấn đề liên quan đến tập rút gọn trên bảng quyết định đã được nhiều tác giả đề cập và nghiên cứu. Trong bài báo này, chúng tôi trình bày một bài toán co-NP - đầy đủ liên quan đến các tập rút gọn trên bảng quyết định. Chúng ta gọi A là tập tựa rút gọn trên bảng quyết định nhất quán DS với tập thuộc tính CU{d} và d là thuộc tính quyết định nếu A chứa một tập rút gọn nào đó. Tương tự chúng ta gọi A là tập tựa tối thiểu của thuộc tính d trên sơ đồ quan hệ s= nếu A chứa một tập tối thiểu của thuộc tính d. Gọi Q là tập tất cả các tập tựa rút gọn của bảng quyết định DS, P là tập tất cả các tập tựa tối thiểu của thuộc tính d trên s. Khi đó bài toán xác định Q có là tập con của P hay không là co-NP - đầy đủ. Việc tìm kiếm các tập rút gọn đóng vai trò quan trọng trong việc xử lí thông tin trên bảng quyết định. Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa để tìm ra các thuộc tính cơ bản phục vụ cho việc xử lí thông tin. Về thực chất, việc rút gọn thuộc tính là tìm tập con nhỏ nhất của tập các thuộc tính để bảo toàn thông tin phân lớp trên bảng quyết định. Trong bài báo này chúng tôi chỉ đề cập tới các bảng quyết định nhất quán. Trên thực tiễn, tùy theo từng bài toán cụ thể, chúng ta có thể chuyển bảng quyết định không nhất quán về bảng quyết định nhất quán. Bài báo này trình bày về một bài toán co-NP - đầy đủ liên quan đến các tập rút gọn trên bảng quyết định. Chúng ta gọi A là tập tựa rút gọn trên bảng quyết định DS với tập thuộc tính C U {d} và d là thuộc tính quyết định nếu A chứa một tập rút gọn nào đó. Tương tự chúng ta gọi A là tập tựa tối thiểu của

• Kỹ thuật lập trình
• Độ phức tạp tính toán
• Tập rút gọn trên bảng quyết định
• Bài toán co NP
• Bảng quyết định DS
• Hệ thông tin
• Tập rút gọn
• Lý thuyết độ phức tạp
• Bài giảng Lý thuyết độ phức tạp
• Lý thuyết NP Đầy đủ
• Bài toán quyết định
• Lược đồ mã hóa
• Tính toán không tất định
• Tạp chí Khoa học
• Cấu trúc
• độ bền phức platin(II)
• Tính chất của phức platin(II)
• Phương pháp hóa học tính toán
• Biến thiên enthalpy
• thuật toán
• độ phức tạp
• tính đúng đắn
• bài giảng toán học
• đại số
• độ tăng của hàm
• khoa học máy tính
• tài liệu công nghệ thông tin
• tài liệu về thuật toán
• độ phức tạp của thuật toán
• Anten thông minh
• Mô hình anten thông minh
• Phân loại anten
• Các thuật toán thích nghi
• Luận văn Thạc sĩ
• Luận văn Thạc sĩ Khoa học
• Bảo đảm toán học cho máy tính
• Hệ thống tính toán
• Máy Turing
• thời gian đa thức
• độ phức tạp toán
• hàm thời gian
• lũy thừa
• Luận văn Thạc sĩ Khoa học máy tính
• Cài đặt máy Turing
• Cải tiến bộ nhớ máy
• Lý thuyết độ phức tạp thuật toán
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu Chương 11
• Tính chất cơ bản của thuật toán
• Thuận toán nhanh tính toán lập
• Bảng quyết định đưa vào vùng dương
• Ma trận phân biệt đơn giản hóa
• Đề cương Tính toán song song
• Tính toán song song
• Thiết kế thuật toán
• Thuật toán song song
• Độ phức tạp thuật toán song song
• Mô hình phân loại Flynn
• Thuật toán khai triển đa cực
• Máy tính chuyên dụng GRAPE
• Hệ N Chất điểm
• Độ phức tạp tính toán tuyến tính
• Tăng tốc thuật toán
• Thuật toán tính tương tác
• Bài giảng Tính toán song song
• Phân tán dữ liệu
• Đánh giá thuật giải song song
• Độ phức tạp thời gian
• Định luật Amdahl
• Một số vấn đề về thuật toán
• Phân tích thuật toán
• Độ phức tạp thuật toán
• Phương pháp trong thuật toán
• Tính đúng đắn của thuật toán
• Bài giảng Phân tích thuật toán
• Ước lượng tiệm cận
• Bài giảng Thuật toán đánh giá và tiếp cận
• Thuật toán đánh giá
• Tính toán độ phức tạp thuật toán
• Giải quyết thuật toán
• Phân tích thiết kế giải thuật
• Biểu diễn thuật toán
• Tính hiệu quả của thuật toán
• Đánh giá độ phức tạp thuật toán
• Thuật toán tìm kiếm
• tìm kiếm tuyến tính
• số nguyên và thuật toán
• thuật toán đệ quy
• thuật toán nhị phân
• Số học thuật toán
• Nhập môn Số học thuật toán
• Thuật toán Karatsuba Ofman
• Quan hệ đồng dư
• Phương pháp đồng dư tuyến tính
• Thiết kế hệ thống cơ khí
• Độ tin cậy truyền bánh ma sát
• Phương pháp Monte Carlo
• Độ bền vật liệu
• Tính toán thanh chịu uốn
• Tính thanh chịu lực phức tạp
• Phương pháp cut set
• phần mềm máy tính
• ngôn ngữ lập trình
• Lịch sử khoa học máy tính
• lý thuyết độ phức tạp tính toán
• tương tác người máy
• thuật toán máy tính
• lưu trữ dữ liệu
• hệ thống dữ liệu
• dữ liệu máy tính
• quản trị dữ liệu
• Ngắn mạch trong hệ thống điện
• Hệ thống điện
• Tính toán ngắn mạch
• Tính toán dòng điện ngắn mạch quá độ
• Ngắn mạch không đối xứng
• Sự cố phức tạp
• Bồi dưỡng học sinh giỏi Tin học
• Chương trình Tin học phổ thông