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
Giới thiệu
Đăng ký
Đăng nhập
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
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
Phân tích thiết kế giải thuật - Chương 7: Vấn đề NP-đầy đủ
Đang chuẩn bị liên kết để tải về tài liệu:
Phân tích thiết kế giải thuật - Chương 7: Vấn đề NP-đầy đủ
Quang Ðạt
56
25
ppt
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Nội dung bài giảng: 1. Giải thuật thời gian đa thức tất định và không tất định 2. Vấn đề NP-đầy đủ 3. Định lý Cook 4. Một số bài toán NP-đầy đủ 5. Một số kỹ thuật để đối phó với những bài toán NP-đầy đủ | Chương 7 Vấn đề NP-đầy đủ Giải thuật thời gian đa thức tất định và không tất định Vấn đề NP-đầy đủ Định lý Cook Một số bài toán NP-đầy đủ Một số kỹ thuật để đối phó với những bài toán NP-đầy đủ Tồn tại hay không tồn tại giải thuật hữu hiệu Đối với nhiều bài toán chúng ta có những giải thuật hữu hiệu để giải. Tuy nhiên, có rất nhiều bài toán khác không có giải thuật hữu hiệu để giải. Và đối với một lớp khá lớn của những bài toán như vậy, chúng ta không thể nói có tồn tại giải thuật hữu hiệu để giải nó hay không. Những bài toán khó và những bài toán dễ Nhiều nghiên cứu đã được thực hiện và có những cơ chế để phân loại những bài toán mới là “khó bằng” một số bài toán cũ đã biết. Tuy nhiên, đôi khi ranh giới giữa những bài toán “khó” và những bài toán “dễ” là khá tế nhị Thí dụ: Dễ: Có tồn tại một lối đi từ x đến y mà trong số nhỏ hơn M? KHó: Có tồn tại một lối đi từ x đến y mà trọng số M? Bài toán 1 - BFS – thời gian tuyến tính Bài toán 2 – thời gian hàm mũ 1. Giải thuật . | Chương 7 Vấn đề NP-đầy đủ Giải thuật thời gian đa thức tất định và không tất định Vấn đề NP-đầy đủ Định lý Cook Một số bài toán NP-đầy đủ Một số kỹ thuật để đối phó với những bài toán NP-đầy đủ Tồn tại hay không tồn tại giải thuật hữu hiệu Đối với nhiều bài toán chúng ta có những giải thuật hữu hiệu để giải. Tuy nhiên, có rất nhiều bài toán khác không có giải thuật hữu hiệu để giải. Và đối với một lớp khá lớn của những bài toán như vậy, chúng ta không thể nói có tồn tại giải thuật hữu hiệu để giải nó hay không. Những bài toán khó và những bài toán dễ Nhiều nghiên cứu đã được thực hiện và có những cơ chế để phân loại những bài toán mới là “khó bằng” một số bài toán cũ đã biết. Tuy nhiên, đôi khi ranh giới giữa những bài toán “khó” và những bài toán “dễ” là khá tế nhị Thí dụ: Dễ: Có tồn tại một lối đi từ x đến y mà trong số nhỏ hơn M? KHó: Có tồn tại một lối đi từ x đến y mà trọng số M? Bài toán 1 - BFS – thời gian tuyến tính Bài toán 2 – thời gian hàm mũ 1. Giải thuật thời gian đa thức tất định và không tất định P: Tập hợp tất cả những bài toán có thể giải được bằng những giải thuật tất định trong thời gian đa thức. “Tất định” (Deterministic) : khi giải thuật đang làm gì, cũng chỉ có một việc duy nhất có thể được thực hiện kế tiếp. (whatever the algorithm is doing, there is only one thing it could do next). Thí dụ: Xếp thứ tự bằng phương pháp chèn thuộc lớp P vì có độ phức tạp đa thức O(N2 ) Tính không tất định Một cách để mở rộng quyền năng của máy tính là cho nó có năng lực làm việc không tất định (non-determinism). Không tất định: khi một giải thuật gặp một sự lựa chọn giữa nhiều khả năng, nó có quyền năng “tiên đóan” để biết chọn một khả năng thích đáng. Giải thuật không tất định (nondeterministic algorithm) Thí dụ: Cho A là một mảng số nguyên. Một giải thuật không tất định NSORT(A, n) sắp thứ tự các số theo thứ tự tăng và xuất chúng ra theo thứ tự này. Thí dụ về một giải thuật không tất định // An array B is used as temporary array. .
TÀI LIỆU LIÊN QUAN
Bài giảng Phân tích thiết kế giải thuật - Chương 37: Giải thuật xấp xỉ
Bài giảng Phân tích thiết kế thuật toán: Chương 3 - Nguyễn Văn Linh
Bài giảng Phân tích thiết kế giải thuật: Chương 1 - Trịnh Huy Hoàng
Bài giảng Phân tích thiết kế và giải thuật - Chương 2: Kỹ thuật thiết kế giải thuật
Bài giảng Phân tích thiết kế thuật toán: Chương 3 - Nguyễn Văn Linh
Bài giảng Phân tích thiết kế giải thuật - Chương 10: Single-Source Shortest Paths
Bài giảng Phân tích thiết kế giải thuật: Chương 4 - Trịnh Huy Hoàng
Bài giảng Phân tích thiết kế và giải thuật - Chương 1: Kỹ thuật phân tích giải thuật
Bài giảng Phân tích thiết kế giải thuật: Chương 3 - Trịnh Huy Hoàng
Bài giảng Phân tích thiết kế giải thuật: Chương 2 - Trịnh Huy Hoàng
crossorigin="anonymous">
Đã 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.