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
Tài liệu HOT
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
0
Trang chủ
Công Nghệ Thông Tin
Cơ sở dữ liệu
Chương 3: Chứng minh các kết quả của bài toán NP_đầy đủ
TAILIEUCHUNG - Chương 3: Chứng minh các kết quả của bài toán NP_đầy đủ
Lớp bài toán P (polynomial time) Lớp P là lớp bài toán quyết định giải được trong thời gian đa thức trên máy Turing tất định, hay lớp những bài toán dễ (có lời giải chấp nhận được). Lớp bài toán NP Là lớp bt quyết định giải được trong thời gian đa thức trên máy Turing không tất định | Chương 3: Chứng minh các kết quả của bài toán NP_đầy đủ Giảng viên : Đình Hòa I. Các khái niệm . Lớp bài toán P (polynomial time) . Lớp bài toán NP(Nondeterministic polynomial time) . Quan hệ giữa lớp P và lớp NP II. Các bài toán NP_Complete . Phép dẫn với thời gian đa thức . Bài toán NP_Complete (NPC) . Một số bài toán NPC Chương 3: Chứng minh các kết quả của bài toán NP_đầy đủ fg I. Các khái niệm . Lớp bài toán P (polynomial time) Lớp P là lớp bài toán quyết định giải được trong thời gian đa thức trên máy Turing tất định, hay lớp những bài toán dễ (có lời giải chấp nhận được). . Lớp bài toán NP Là lớp bt quyết định giải được trong thời gian đa thức trên máy Turing không tất định . Quan hệ giữa lớp P và lớp NP Ta có thể thấy một cách trực quan là P NP. Nhưng chúng ta vẫn chưa biết P=NP hay không, nhưng hầu hết các nhà nghiên cứu tin rằng P≠NP là sự tồn tại của của lớp bt NPC Dù chúng ta chưa biết chắc chắn liệu P≠NP song việc chỉ ra được một bài toán là NPC chứng tỏ 1 sự thật là bt đó không thể giải được về phương diện tính toán với thuật toán chính xác, tốt hơn hết là lời giải theo thuật toán gần đúng. Việc xem xét quan hệ giữa P và NP dẫn đến chúng ta đi đến nghiên cứu lớp NPC II. Các bài toán NP_Comlete (NPC) . Phép dẫn với thời gian đa thức Cho hai bài toán 1 và 2. Ta biết rằng . Phép dẫn với thời gian đa thức Một phép biến đổi f mỗi dữ kiện 1 thành dữ kiện 2 và thỏa mãn 2 điều kiện sau được gọi là phép dẫn thời gian đa thức : 1. f được thực hiện trong thời gian đa thức 2. Định Nghĩa: Một bt quyết định 1 dẫn về bt quyết định 2 trong thời gian đa thức nếu tồn tại một phép dẫn đa thức từ bt 1 về bt 2. Ký hiệu: 1 2 The theory of NP-Completeness Ví dụ 1: Chu trình Hamilton Instance: Đồ thị G vô hướng. Question: tồn tại hay không một chu trình đi qua tất cả đỉnh của đồ thị ? 1. Ví dụ phép dẫn thời gian đa thức The theory of NP-Completeness Ví dụ 2: Traveling Salesman Instance: Tập hữu hạn
Phương Thủy
105
25
ppt
Báo lỗi
Trùng lắp nội dung
Văn hóa đồi trụy
Phản động
Bản quyền
File lỗi
Khác
Upload
Tải xuống
đang nạp các trang xem trước
Không thể tạo bản xem trước, hãy bấm tải xuống
Tải xuống
TÀI LIỆU LIÊN QUAN
Xây dựng hệ thống phân loại trong việc thành lập bản đồ cảnh quan huyện Minh Hóa, tỉnh Quảng Bình (tỷ lệ: 1: 25.000)
8
1
1
Giáo án điện tử môn Tự nhiên và xã hội lớp 3 - Bài: Thực hành Phân tích và vẽ sơ đồ mối quan hệ họ hàng
18
57
3
Bài giảng Sinh học lớp 9 bài 19: Mối quan hệ giữa gen và tính trạng
10
1
1
Chuyển đổi mô hình lớp trong UML sang quan hệ và ứng dụng
43
50
0
Bài giảng Toán rời rạc - Chương 3: Quan hệ (ĐH Công nghệ Thông tin)
45
122
4
Chuyên đề Quan hệ song song Toán 11
116
99
1
Sáng kiến kinh nghiệm Tiểu học: Một số biện pháp giúp học sinh lớp 5 khắc phục lỗi sử dụng quan hệ từ theo mô hình VNEN
30
69
1
Bài giảng Lập trình hướng đối tượng: Quan hệ giữa các lớp - Lê Viết Mẫn
57
70
0
Bài giảng Lập trình hướng đối tượng: Quan hệ giữa các lớp
57
79
2
Giáo án Hóa học 9 bài 46: Mối liên hệ giữa etilen, rượu etylic và axit axetic
4
71
0
TÀI LIỆU XEM NHIỀU
Một Case Về Hematology (1)
8
462366
61
Giới thiệu :Lập trình mã nguồn mở
14
26902
79
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
11381
543
Câu hỏi và đáp án bài tập tình huống Quản trị học
14
10576
468
Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”
3
9858
108
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8911
1161
Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức
16
8528
426
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
8111
2279
Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152
8006
1826
Đề tài: Dự án kinh doanh thời trang quần áo nữ
17
7303
268
TỪ KHÓA LIÊN QUAN
Cơ sở dữ liệu
Quan hệ lớp P
lớp NP
bài toán NP
thời gian đa thức
phép dẫn thời gian
bài toán PNC
Tóm tắt luận văn Thạc sĩ Khoa học
Luận văn Thạc sĩ Khoa học
Tóm tắt luận văn Thạc sĩ
Lớp liên hợp
Quan hệ đồng chất
Quan hệ đồng chất giữa các nhóm
Luận văn Thạc sĩ Khoa học giáo dục
Phương pháp dạy học môn Toán
Thiết kế câu hỏi trắc nghiệm khách quan
Hệ phương trình
Phương pháp dạy học Toán lớp 10
TÀI LIỆU MỚI ĐĂNG
Giáo án mầm non chương trình đổi mới: Gia đình vui nhộn
4
396
3
13-01-2025
Báo cáo nghiên cứu khoa học " KẾT QUẢ NGHIÊN CỨU BƯỚC ĐẦU VỀ THIÊN ĐỊCH CHÂN KHỚP TRÊN CÂY THANH TRÀ Ở THỪA THIÊN HUẾ "
7
289
4
13-01-2025
THE ANTHROPOLOGY OF ONLINE COMMUNITIES BY Samuel M.Wilson and Leighton C. Peterson
19
231
4
13-01-2025
Data Structures and Algorithms - Chapter 8: Heaps
41
195
5
13-01-2025
Báo cáo nghiên cứu nông nghiệp " Field control of pest fruit flies in Vietnam "
14
196
4
13-01-2025
Quy Trình Canh Tác Cây Bông Vải
8
171
3
13-01-2025
báo cáo hóa học:" Quality of data collection in a large HIV observational clinic database in sub-Saharan Africa: implications for clinical research and audit of care"
7
164
4
13-01-2025
Báo cáo " Bàn về hành vi pháp luật và hành vi đạo đức "
11
182
2
13-01-2025
ETHICAL CODE HANDBOOK: Demonstrate your commitment to high standards
7
156
1
13-01-2025
Bệnh sán lá gan trên gia súc và cách phòng trị
3
170
1
13-01-2025
TÀI LIỆU HOT
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
8111
2279
Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152
8006
1826
Ebook Chào con ba mẹ đã sẵn sàng
112
4443
1376
Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1
62
6397
1280
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8911
1161
Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu
561
3864
680
Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122
3931
610
Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm
274
4793
567
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
11381
543
Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe
35
4540
490
Close
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
Tài liệu HOT
Đã 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.