TAILIEUCHUNG - Bài giảng Phân tích và thiết kế giải thuật: Chương 7 - PGS.TS. Dương Tuấn Anh

Chương 7 trình bày về vấn đề NP-đầy đủ. Các nội dung chính trong chương này gồm có: 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 đủ. . | 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. .

• Kỹ thuật lập trình
• Thiết kế giải thuật
• Phân tích giải thuật
• Định lý Cook
• Giải thuật thời gian đa thức tất định
• Vấn đề NP đầy đủ
• Bài toán NP đầy đủ
• Phân tích thiết kế giải thuật
• Kỹ thuật thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ thuật phân tích thiết kế giải thuật
• Bài giảng phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Cắt tỉa Alpha Beta
• Phương pháp thiết kế thuật giải
• Thuật toán chính xác
• Thuật toán gần đúng
• Bước thiết kế một thuật giải
• Giải thuật quay lui
• Giải thuật tham lam
• Quy hoạch động
• Phân tích thiết kế thuật toán
• Phân tích thuật toán
• Thiết kế thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Giải thuật xấp xỉ
• Bài toán che phủ đỉnh
• Phân tích thiết kế giải thuật chương 37
• Phân tích thuật giải
• Thiết kế thuật giải
• Chiến lược thiết kế thuật giải
• Biểu diễn thuật giải
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Chia để trị
• Tiêu chuẩn đánh giá giải thuật
• Phương pháp đánh giá giải thuật
• Giải thuật nâng cao
• Kỹ thuật phân tích giải thuật
• Hệ thống thông tin
• Giải thuật hình học
• Giải thuật so khớp chuỗi
• Single Source Shortest Paths
• Phân tích thiết kế giải thuật chương 10
• Giải bài toán các đường đi ngắn nhất
• Biểu diễn các đường đi ngắn nhất
• Kỹ thuật mã hóa
• Cây khung nhỏ nhất
• Giải thuật tổng quát
• Giải thuật của Kruskal
• Giải thuật của Prim
• Phân tích thiết kế thuật toán
• Công nghệ thông tin
• Bài giảng Giải thuật
• Kỹ thuật phân tích và thiết kế giải thuật
• Giải thuật đơn giản
• Phương pháp thiết kế giải thuật
• Phương pháp chia để trị
• Phương pháp quy hoạch động
• Mô tả công việc
• Mô tả công việc ngành IT
• Mô tả công việc Trưởng phòng thiết kế đồ họa
• Trưởng phòng thiết kế đồ họa
• Thiết kế đồ họa
• Quy trình thiết kế
• Bản vẽ kỹ thuật
• Ý tưởng thiết kế
• Giải trình thiết kế
• Đào tạo nhân viên thiết kế
• Kỹ thuật tối ưu hóa chương trình
• Mức thiết kế một chương trình
• Kỹ thuật tinh chế mã
• Kỹ thuật tối ưu hóa rẽ nhánh
• Bài Giảng điện tử
• Dương Tuấn Anh
• Thuật toán chương trình
• Kỹ thuật lập trình
• bài toán giải thuật
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• Giải thuật đệ quy
• Thiết kế giải thuật đệ quy
• Đệ quy tuyến tính
• Đệ quy nhị phân