intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

CHUYÊN ĐỀ: LÝ THUYẾT ĐỘ PHỨC TẠP THUẬT TOÁN

Chia sẻ: Nguyễn Gia Thế | Ngày: | Loại File: PPT | Số trang:0

Thêm vào BST
Báo xấu
473
lượt xem 71
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài toán quyết định (Decision Problem - DP) là bài toán chỉ có câu trả lời là có hoặc không (hay còn gọi là trả lời nhị phân). Mỗi thể hiện của bài toán nghĩa là mỗi trường hợp cá biệt của bài toán có một trả lời. Một bài toán quyết định Π đơn giản bao gồm một tập hợp DΠ các thể hiện và tập con YΠ Í DΠ là các thể hiện đúng.Một bài toán quyết định phát biểu dưới dạng: Instance: … Question:…...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CHUYÊN ĐỀ: LÝ THUYẾT ĐỘ PHỨC TẠP THUẬT TOÁN

  1. CHUYÊN ĐỀ: LÝ THUYẾT ĐỘ PHỨC TẠP THUẬT TOÁN LÝ THUYẾT NP - ĐẦY ĐỦ (THE THEORY OF NP - COMPLETENESS) Giáo viên : Thầy Vũ Đình Hoà The theory of NP-Completeness 1
  2. NỘI DUNG Bài toán quyết định 1. Ngôn ngữ và lược đồ mã hóa 2. Máy Turing tất định và lớp P 3. Tính toán không tất định và lớp NP 4. Mối quan hệ giữa lớp P và lớp NP 5. Phép dẫn thời gian đa thức và lớp NPC 6. Thuyết Cook 7. The theory of NP-Completeness 2
  3. 1. BÀI TOÁN QUYẾT ĐỊNH  Bài toán quyết định (Decision Problem - DP) là bài toán chỉ có câu trả lời là có hoặc không (hay còn gọi là trả lời nhị phân).  Mỗi thể hiện của bài toán nghĩa là mỗi trường hợp cá biệt của bài toán có một trả lời.  Một bài toán quyết định ∏ đơn giản bao gồm một tập hợp D∏ các thể hiện và tập con Y∏ ⊆ D∏ là các thể hiện đúng The theory of NP-Completeness 3
  4. 1. BÀI TOÁN QUYẾT ĐỊNH  Một bài toán quyết định phát biểu dưới dạng:  Instance: …  Question:…  Ví dụ 1: bài toán sự đẳng cấu của đồ thị con  Instance: Cho 2 đồ thị G1 = (V1, E1) và G2 = (V2, E2)  Question: đồ thị G1 có chứa một đồ thị con G1’ mà G1’ đẳng cấu với đồ thị G2 hay không? The theory of NP-Completeness 4
  5. 1. BÀI TOÁN QUYẾT ĐỊNH  Giải thích về đồ thị đẳng cấu: G1’ đẳng cấu với G2 nếu như có |V1’| = |V2|, |E1’| = |E2| và ở đó tồn tại một song ánh f : V2  V1’ sao cho {u,v} ∈ E2 khi và chỉ khi {f(u), f(v)} ∈ E1’). The theory of NP-Completeness 5
  6. 1. BÀI TOÁN QUYẾT ĐỊNH  Ví dụ 2: Traveling Salesman  Instance: Tập hữu hạn các thành phố: C = {c1, c2,… cm}, khoảng cách giữa hai thành phố ci, cj là d(ci, cj) ∈ Z+, một số B ∈ Z+.  Question: tồn tại hay không một đường đi nào qua tất cả các thành phố trong C mà có tổng độ dài không lớn C π (1) , C π ( 2 ) ,..., C π ( m ) hơn B? (Tồn tại một sắp thứ tự sao m −1 cho (∑ d (C π ( i ) , C π ( i +1) )) + d (C π ( m ) , C π (1) ) ≤ B i =1 ) The theory of NP-Completeness 6
  7. 1. BÀI TOÁN QUYẾT ĐỊNH  Một bài toán quyết định có thể được chuyển hoá từ một bài toán tối ưu.  Ví dụ: Bài toán tối ưu là “tìm một đường đi có độ dài nhỏ nhất trong số tất cả các đường đi nối 2 đỉnh đồ thị” ↔ BTQĐ : thêm vào một tham số B và hỏi xem có đường đi nào có độ dài L mà L ≤ B hay không?  Với điều kiện là hàm chi phí phải tương đối dễ đánh giá, bài toán quyết định có thể không khó khăn hơn bài toán tối ưu tương ứng The theory of NP-Completeness 7
  8. 1. BÀI TOÁN QUYẾT ĐỊNH  Nếu tìm thấy một đường đi có độ dài nhỏ nhất cho bài toán TS theo thời gian đa thức, cũng có thể giải quyết bài toán quyết định được kết hợp theo thời gian đa thức.  Lý thuyết NP đầy đủ giới hạn là chỉ chú ý tới các bài toán quyết định nhưng cũng có thể mở rộng sự liên quan của thuyết NP đầy đủ tới các bài toán tối ưu.  Nguyên nhân của sự giới hạn này là các DPs có một bản sao rất tự nhiên và nó được gọi là ngôn ngữ. The theory of NP-Completeness 8
  9. 2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA  Định nghĩa ngôn ngữ:  Với bất kì một tập hữu hạn ∑ các kí hiệu, chúng ta có thể biểu diễn ∑* là tập hợp tất cả các xâu hữu hạn các kí hiệu lấy từ tập ∑.  Nếu L là một tập con của ∑*, chúng ta nói rằng L là một ngôn ngôn ngữ trên tập các chữ cái của ∑. The theory of NP-Completeness 9
  10. 2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA  Ví dụ: Nếu ∑ = {0, 1}, khi đó I* = {ε, 0, 1, 01, 10, 11, 000, 001,… } Khi đó {01,001,111,1101010} là một ngôn ngữ trên tập {0,1}  Sự tương ứng giữa bài toán quyết định và ngôn ngữ được dẫn đến bởi các lược đồ mã hoá.  Một lược đồ mã hoá e cho bài toán ∏ cung cấp một cách thức miêu tả mỗi sự kiện của ∏ bằng một xâu thích hợp các ký hiệu trên tập chữ cái cố định ∑. The theory of NP-Completeness 10
  11. 2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA  Bài toán ∏ và lược đồ mã hoá e cho ∏ chia ∑* thành 3 lớp: 1. Những xâu không mã hoá các biểu hiện của ∏. 2. Những xâu mã hoá các biểu hiện của ∏ mà trên đó câu trả lời là No. 3. Những xâu mã hoá các biểu hiện của ∏ mà trên đó câu trả lời là Yes. Ngôn ngữ: L[∏, e] = {x ∈ ∑* với ∑ được sử dụng bởi e, và x mã hóa một thể hiện I ∈ Yπ bằng e} The theory of NP-Completeness 11
  12. 2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA  Một lược đồ mã hoá hợp lý phải đảm bảo 2 tính năng là : “tính ngắn gọn” và có “khả năng giải mã”.  “Tính ngắn gọn” là các trường hợp của bài toán nên được mô tả với sự khúc chiết một cách tự nhiên.  “Khả năng giải mã” là đưa ra bất kì một thành phần cụ thể nào của một trường hợp chung, thì lược đồ có khả năng chỉ rõ một thuật toán có thời gian đa thức. The theory of NP-Completeness 12
  13. 2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA  Định nghĩa một lược đồ mã hoá chuẩn: Lược đồ mã hoá chuẩn sẽ ánh xạ các thể hiện sang các xâu có cấu trúc trên tâp chữ cái ψ = {0, 1, -, [,], (, ), …}.  Định nghĩa xâu cấu trúc một cách đệ quy như sau: The theory of NP-Completeness 13
  14. 2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA  Biểu diễn nhị phân của một số nguyên k (gồm các chữ số 0 và 1), (đằng trước là dấu - nếu k là số âm) là một xâu có cấu trúc biểu diễn số nguyên k.  Nếu x là một xâu có cấu trúc biểu diễn số nguyên k, khi đó [x] là một xâu có cấu trúc có thể được sử dụng như một “tên” (name) .  Nếu x1, x2, ..., xm là các xâu có cấu trúc biểu diễn các đối tượng X1,X2, …, Xm, khi đó (x1, …, xm) là một xâu có cấu trúc biểu diễn chuỗi (X1,…,Xm) The theory of NP-Completeness 14
  15. 2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA  Các biểu diễn cho 4 kiểu đối tượng như sau:  Một tập các đối tượng được biểu diễn bởi thứ tự các phần tử của nó như một chuỗi và xem như là xâu có cấu trúc tương ứng với chuỗi đó.  Một đồ thị với tập đỉnh là V và tập cạnh là E được biểu diễn bởi một xâu có cấu trúc (x, y), ở đó x là một xâu có cấu trúc biểu diễn tập V và y là xâu có cấu trúc biểu diễn tập E (các phần tử của E …) The theory of NP-Completeness 15
  16. 2. NGÔN NGỮ VÀ LƯỢC ĐỒ MÃ HÓA  Một hàm hữu hạn f : {U1, U2,…, Um} → W được biểu diễn bởi một xâu có cấu trúc {(x1, y1), …, (xm, ym)} ở đó xi là xâu có cấu trúc biểu diễn Ui và yi là xâu có cấu trúc biểu diễn f(Ui) ∈ W, 1 ≤ i ≤ m.  Một số hữu tỉ q được biểu diễn bởi một xâu có cấu trúc (x, y) ở đó x là xâu có cấu trúc biểu diễn một số nguyên a, y là xâu biểu diễn một số nguyên b và ở đó a / b = q, và ước chung lớn nhất của a và b là 1. The theory of NP-Completeness 16
  17. 3. MÁY TURING TẤT ĐỊNH VÀ LỚP P 3.1. Miêu tả máy Turing tất định (DTM) Máy Turing tất định gồm có: 1. Con trỏ điều khiển trạng thái 2. Một đầu đọc ghi 3. Một băng vô hạn nằm ngang với các ô vuông. Dưới các ô vuông có đánh các nhãn là:… -3, -2, -1, 0, 1, 2, 3… The theory of NP-Completeness 17
  18. 3. MÁY TURING TẤT ĐỊNH VÀ LỚP P 3.1. Miêu tả máy Turing tất định Bộ điều khiển trạng thái hữu hạn Đầu đọc ghi Băng vô hạn -3 -2 -1 0 1 2 3 4 The theory of NP-Completeness 18
  19. 3. MÁY TURING TẤT ĐỊNH VÀ LỚP P 3.1. Miêu tả máy Turing tất định  Một chương trình cho một DTM gồm các thông tin:  Một tập hợp T những kí hiệu, bao gồm một tập con ∑ ⊂ T và một kí tự trắng b ∈ T \ ∑.  Một tập hợp Q các trạng thái, bao gồm trạng thái bắt đầu qo và hai trạng thái kết thúc là qY và qN.  Một hàm chuyển trạng thái  ? : (Q - {qY, qN}) * T → Q * T * {-1, +1,0} The theory of NP-Completeness 19
  20. 2. MÁY TURING TẤT ĐỊNH VÀ LỚP P 3.1. Miêu tả máy Turing tất định  Hàm chuyển trạng thái: δ cho phép với mỗi trạng thái của máy và một kí kiệu đọc được từ ô trống đối diện, ta xác định được:  Trạng thái tiếp theo.  Kí hiệu sẽ được viết lên băng đè lên kí hiệu vừa đọc  Hướng dịch chuyển của đầu đọc The theory of NP-Completeness 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2