Giáo trình Lý thuyết tính toán
Trong Tin học, các đối tượng (objects) được xử lý thông thường là những
phần tử thuộc vào những tập hợp vô hạn đếm được. Những phần tử này luôn luôn
được biểu diễn (represented) dưới một dạng nào đó.
Chẳng hạn trong ngôn ngữ tự nhiên, số nguyên 1999 được biểu diễn trong hệ
đếm cơ số 10 (hệ thập phân) gồm một dãy bốn chữ số thập phân thuộc bảng chữ
số {0, 1, ., 9}. Việc xử lý (thực hiện các phép toán số học thông thường) đối với
các số nguyên được tiến hành trên cách biểu diễn cơ số 10 này.
Ví dụ : Phép cộng hai số 1999 + 1 = 2000.
Người ta giả thiết rằng các đối tượng được xử lý là những câu (word, hay
sentence) được xây dựng trên một bảng chữ (alphabet) hữu hạn, được xem như là
sự biểu diễn của đối tượng trong một bản chất khác.
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Trang 7
Trang 8
Trang 9
Trang 10
Tải về để xem bản đầy đủ
Tóm tắt nội dung tài liệu: Giáo trình Lý thuyết tính toán
ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN GIÁO TRÌNH LÝ THUYẾT TÍNH TOÁN PGS.TS. PHAN HUY KHÁNH ĐÀ NẴNG 1999 PGS.TS. PHAN HUY KHÁNH biên soạn 1 MỤC LỤC CHƯƠNG 1 NHẬP MÔN LÝ THUYẾT TÍNH TOÁN ........................................... 1 I. CÁC ĐỐI TƯỢNG ĐƯỢC XỬ LÝ TRONG TIN HỌC.............................................................1 II. CÁC MÁY (MACHINES).......................................................................................................................2 II.1. Khía cạnh chức năng (functional look)........................................................ 2 II.2. Khía cạnh cấu trúc (structural look)............................................................ 3 III. MÔ HÌNH TÍNH TOÁN .........................................................................................................................4 IV. ĐỊNH NGHĨA BÀI TOÁN.....................................................................................................................5 CHƯƠNG 2 MÔ HÌNH CÁC MÁY RAM ............................................................... 9 I. CÁC MÁY RAM .....................................................................................................................................9 II. MÔ PHỎNG MỘT MÁY BỞI MỘT MÁY KHÁC .........................................................16 III. MỘT MÔ HÌNH THÔ SƠ KIỂU RAM..................................................................................19 III.1. Mô phỏng các phép toán trên chuỗi ký tự bởi các phép toán trên các số nguyên........................................................ 19 III.2. Thu gọn tập hợp các lệnh ngắt................................................................... 20 III.3. Thu gọn tập hợp các lệnh số học................................................................ 20 IV. MÁY RAM VẠN NĂNG....................................................................................................................22 CHƯƠNG 3 MÔ HÌNH CÁC MÁY TURING ....................................................... 25 I. MÔ TẢ VÀ HOẠT ĐỘNG CỦA MÁY TURING.......................................................................25 I.1. Mô tả máy Turing....................................................................................... 25 I.2. Hoạt động của máy Turing ........................................................................ 26 I.3. Cấu hình xuất phát của máy Turing........................................................... 29 I.4. Máy Turing đơn định.................................................................................. 29 II. CAC HÀM T-TÍNH ĐƯỢC...............................................................................................................30 III. LỚP CÁC HÀM T-TÍNH ĐƯỢC .....................................................................................................32 III.1. Một số hàm sơ cấp ..................................................................................... 32 III.1.1. Các hàm hằng (constant functions)............................................................ 32 III.1.2. Các hàm chiếu (projection functions) ........................................................ 33 III.2. Các hàm kế tiếp (successor functions) ....................................................... 33 III.3. Các hàm kế trước (predecessor functions).......................................................... 34 III.4. Sự hợp thành (composition) ....................................................................... 34 III.3.1. Các máy được tiêu chuẩn hóa .................................................................... 35 III.3.2. Các máy Turing được chuẩn hóa ............................................................... 36 III.3.3. Tổ hợp các máy Turing.............................................................................. 36 III.5. Lập trình trên ngôn ngữ bậc cao máy Turing ............................................ 37 III.4.1. Cấu trúc if then else và cấu trúc rẽ nhiều nhánh ........................................ 37 III.4.2. Cấu trúc while ............................................................................................ 38 III.6. Quản lý bộ nhớ ........................................................................................... 39 III.5.1. Máy Turing chuyển một ô qua phải ........................................................... 39 2 Lý thuyết tính toán III.5.2. Máy Turing chỉ sử dụng phần băng bên phải kể từ vị trí đầu tiên của đầu đọc-ghi ...........................................................39 III.7. Một số máy Turing thông dụng ..................................................................40 III.6.1. Sao chép .....................................................................................................40 III.6.2. Kiểm tra bằng nhau ....................................................................................41 III.6.3. Liệt kê các câu, các cặp câu và dãy các câu ...............................................41 III.6.4. Các hàm chiếu ngược (antiprojection function) .........................................42 III.6.5. Các hàm giao hoán .....................................................................................42 III.7. Các hàm T-tính được phức tạp hơn............................................................42 III.8. Nhận xét......................................................................................................43 IV. CÁC BIẾN THẾ KHÁC CỦA MÔ HÌNH MÁY TURING........................................................46 IV.1. Mô phỏng một máy Turing bởi một máy khác............................................46 IV.2. Các biến thể của máy Turing .....................................................................48 IV.2.1. Máy Turing có k băng ................................................................................48 IV.2.2. Các máy off−line và c ... sử dụng một thừa số c không đổi, ta có thể giảm bớt độ phức tạp về bộ nhớ để nhận biết một ngôn ngữ đã cho. Nếu T là một máy Turing off-line có k băng, ta có thể nhận biết cùng một ngôn ngữ bằng cách sử dụng một máy Turing off−line chỉ có một băng, sử dụng cùng một phương pháp để không sử dụng không gian nhớ nhiều hơn T. Đối với độ phức tạp về bộ nhớ, việc ta giảm bớt số lượng băng làm việc không có nghĩa, cho nên, từ nay, ta chỉ xét đến các máy Turing off−line có một băng, thậm chí, trong trường hợp S(n) = n, ta chỉ xét các máy Turing có một băng mà không thêm gì nữa. Ta cũng có thể áp dụng phương pháp nén vừa trình bày trên đây đối với độ phức tạp về thời gian. Tuy nhiên phương pháp này không miễn đọc dữ liệu, mà cần một thời gian n + 1 để đọc dữ liệu có độ dài n. Như vậy, ta có thể giảm bớt nhờ một thừa số không đổi là c ngay khi T(n)/n có khuynh hướng tăng vô hạn. Bây giờ ta xem xét hiệu quả của độ phức tạp về thời gian khi giảm bớt số lượng các băng làm việc. Khi giảm bớt còn một băng, phân tích phương pháp đã trình bày ở chương 3 để chuyển từ k băng về một băng, ta chứng minh được : L ∈ DTIME (T (n)) ⇒ L được thừa nhận bởi một máy Turing một băng với chi phí thời gian là T2(n). Khi cần thực hiện việc sao chéo, ta có thể chuyển từ một băng sang hai băng nhằm làm giảm đáng kể số bước tính toán. Ta chứng minh được rằng việc rút gọn còn hai băng thay vì chỉ còn một băng làm tối ưu rõ rệt chi phí về thời gian : L ∈ DTIME (T (n)) ⇒ L được thừa nhận bởi một máy Turing có hai băng với thời gian T (n).log2(T (n)) Tuy nhiên, để trả lời câu hỏi : Với chi phí thời gian nhiều hơn (tương ứng : nhiều bộ nhớ hơn) thì người ta có nhận biết được thực sự nhiều ngôn ngữ hơn không ? ta có mệnh đề sau đây : Mệnh đề 6.1 : Với mọi hàm đệ quy toàn phần f, tồn tại một ngôn ngữ đệ quy L không thuộc họ DTIME (f (n)) (một cách tương ứng : không thuộc họ DSPACE (f (n))). Chứng minh : Sử dụng kỹ thuật đường chéo cho ngôn ngữ : L = { wi | Ti không thừa nhận câu wi sau f (|wi|) bước tính toán } Thật vậy, L là một ngôn ngữ đệ quy không thuộc họ DTIME (f (n)). Độ phức tạp tính toán 97 Giữa các phép đo độ phức tạp tính toán khác nhau này, ta có thể thiết lập các mối quan hệ. Một số quan hệ dễ dàng nhận được như sau : L ∈ DTIME (f (n)) ⇒ L ∈ DSPACE (f (n)) Thật vậy, máy Turing thăm một ô tại mỗi bước tính toán. Trường hợp xấu nhất xảy ra khi tất cả các ô đều khác nhau. L ∈ DSPACE (f (n)) và f (n) = log2 (n) ⇒ L ∈ DTIME (cf (n)) Thật vậy, nếu f (n) = log2 (n), tồn tại một hằng c sao cho cf(n) là lớn hơn số các cấu hình phân biệt có độ dài tối đa là f (n) của một máy Turing đã cho. L ∈ NTIME (f (n)) ⇒ L ∈ DTIME (cf (n)). Thật vậy, quan hệ này đến từ việc tăng thêm số cấu hình phân biệt đối với một dữ liệu có độ dài n. Thời gian tăng thêm là cf (n). Sau đây là một quan hệ được cho bởi định lý Savitch. Định lý Savitch WJ : L ∈ NSPACE (f (n)) và f (n) = log2 (n) ⇒ L ∈ DSPACE (f2 (n)). II.2. Các họ P, NP và P−bộ nhớ (P−space) Các lớp của độ phức tạp tính toán sau đây đủ quan trọng để có tên riêng : P = U 1i ≥ DTIME (ni), NP = U 1i ≥ NTIME (ni). Như vậy : P là lớp các ngôn ngữ được nhận biết bởi một máy Turing đơn định cần một lượng thời gian bậc đa thức, NP là lớp các ngôn ngữ được nhận biết bởi một máy Turing không đơn định cần một lượng thời gian bậc đa thức. Ta đưa vào các lớp P−bộ nhớ (P−space) và NP−bộ nhớ (NP−space) như sau : P−bộ nhớ = U 1i ≥ DSPACE (ni), NP−bộ nhớ = U 1i ≥ NSPACE (ni). P−bộ nhớ là lớp các ngôn ngữ được nhận biết bởi một máy Turing đơn định cần một lượng bộ nhớ bậc đa thức, NP−bộ nhớ là lớp các ngôn ngữ được nhận biết bởi một máy Turing không đơn định cần một lượng bộ nhớ bậc đa thức. Rõ ràng ta có đẳng thức : 98 Lý thuyết tính toán P−bộ nhớ = NP−bộ nhớ Và ta có các bao hàm sau đây : DSPACE (log2 (n)) ⊆ P ⊆ NP ⊆ P−bộ nhớ = NP−bộ nhớ. Trong thực tế, người ta ước lượng một bài toán là : − xử lý được (tractable), nếu bài toán đó thuộc lớp P hay giải được (workable) − không xử lý được (untractable), nếu bài toán đó không thuộc lớp P. hay không giải được (unworkable) Vì vậy, ít khi người ta giải quyết những bài toán cần một lượng thời gian và bộ nhớ dạng đa thức có bậc lớn hơn 4 vì sẽ làm tăng độ phức tạp tính toán. III. Rút gọn đa thức và các bài toán NP−đầy đủ III.1. Khái niệm Rút gọn đa thức (polynomial reduction) là làm mịn (refinement) khái niệm rút gọn số học đã định nghĩa ở chương 5. Ta vẽ lại sơ đồ rút gọn số học như sau : Hình 6.1 Rút gọn bài toán A về bài toán B Định nghĩa 6.1 Người ta nói bài toán A được rút gọn kiểu đa thức về bài toán B nếu tồn tại một máy Turing dừng cho mọi dữ liệu và thực hiện tính hàm f hết một lượng thời gian đa thức (polynomial time). Hàm f được xác định từ tập hợp các biểu diễn dữ liệu của bài toán A vào tập hợp các biểu diễn dữ liệu của bài toán B, thỏa mãn : w ∈ LA ⇔ f (w) ∈ LB Người ta nói rằng máy Turing này đã thực hiện kiểu đa thức (polynomially work) việc rút gọn bài toán A về bài toán B. Từ đó, ta có mệnh đề sau : Mệnh đề 6.2 : Nếu bài toán A được rút gọn kiểu đa thức về bài toán B, thì nếu B là một bài toán thuộc lớp P (một cách tương ứng : thuộc lớp NP), thì A cũng là một bài toán thuộc lớp P (một cách tương ứng : thuộc NP). Người ta cũng nói rằng các lớp P và NP là đóng đối với phép rút gọn đa thức. LPA S*\LPA LPB S*\LPB Anh của f từ các biểu diễn dữ liệu của bài toán A Biểu diễn dữ liệu của bài toán B Biểu diễn dữ liệu của bài toán A f f Độ phức tạp tính toán 99 Chứng minh : Thật vậy, giả sử T là một máy Turing luôn luôn dừng và nhận biết ngôn ngữ LB một lượng thời gian đa thức. Giả sử T’ là một máy Turing thực hiện việc rút gọn hết một lượng thời gian đa thức từ bài toán A về bài toán B. Rõ ràng, máy Turing T’ next T luôn luôn dừng và nhận biết ngôn ngữ LA một lượng thời gian đa thức. Một cách tương tự, ta định nghĩa khái niệm rút gọn sử dụng bộ nhớ logarit. Định nghĩa 6.2 : Người ta nói bài toán A được rút gọn về bài toán B cần một lượng bộ nhớ logarit nếu tồn tại một máy Turing luôn luôn dừng cho mọi dữ liệu và thực hiện tính hàm f sử dụng một lượng bộ nhớ theo logarit. Hàm f được xác định từ tập hợp các biểu diễn dữ liệu của bài toán A vào tập hợp các biểu diễn dữ liệu của bài toán B, thỏa mãn : w ∈ LA ⇔ f (w) ∈ LB Ta có mệnh đề sau : Mệnh đề 6.3 : Lớp P đóng đối với phép rút gọn sử dụng bộ nhớ logarit. Việc chuyển một chương trình RAM thành một chương trình của một máy Turing được thực hiện sao cho thời gian chạy của máy Turing được tính theo số bước tính toán, là một đa thức theo thời gian chạy chương trình của máy RAM được tính theo số các lệnh (instructions) đã thực hiện. Tương tự, việc chuyển một công thức trong một ngôn ngữ bậc cao thành một công thức của một máy RAM được thực hiện sao cho thời gian chạy công thức của máy RAM được tính theo số các lệnh của RAM đã thực hiện, là một đa thức về thời gian chạy công thức trên ngôn ngữ bậc cao, được tính theo số các lệnh đã thực hiện. Từ đó, việc định nghĩa các lớp P và NP được dựa trên mô hình các máy Turing nhưng không phụ thuộc chính xác vào mô hình này, và để đảm bảo rằng một ngôn ngữ là thuộc một trong hai lớp này, chỉ cần đếm số lượng các phép toán một cách đơn giản. III.2. Các bài toán cổ điển Sau đây là sáu bài toán cổ điển trong Tin học. 1. Bài toán tô màu các đỉnh của một đồ thị Dữ liệu : Một đồ thị G = và một số nguyên k. Câu hỏi : Ta có thể tô mỗi đỉnh của đồ thị một màu sao cho cứ hai đỉnh của đồ thị được nối với nhau bởi một cung thì không được tô cùng màu được chọn trong số k màu ? 2. Bài toán lập kế hoạch làm việc Dữ liệu : Cho n việc và một số nguyên k, mỗi việc được đặc trưng bởi bộ ba các số nguyên (ti, di, pi), với ti, di, và pi lần lượt biểu diễn thời gian thực hiện, thời gian kết thúc và hình phạt ứng với việc thứ i. 100 Lý thuyết tính toán Câu hỏi : Có thể sắp xếp các việc sao cho tổng số các hình phạt là nhỏ hơn hoặc bằng k ? Nói cách khác, với mọi hoán vị P của n số nguyên đầu tiên, ta kết hợp một số nguyên : Pp = p(j) j 1, n p (j) p(r) r 1, j P t d 0 = = ⎧ ⎡ ⎤= >⎣ ⎦⎪⎨⎪=⎩ ∑ ∑nãuú nãúu khäng và người ta tìm một hoán vị P nếu hoán vị P tồn tại sao cho Pp = k. 3. Bài toán sắp xếp trong các thùng chứa Dữ liệu : Cho số nguyên c (dung lượng của các thùng), n vật đặc trưng bởi các kích thước s1, s2, ..., sn với 0 < si ≤ c và một số nguyên k. Câu hỏi : Có thể đặt n vật vào nhiều nhất là k thùng chứa được không ? 4. Bài toán ba-lô (rucksack) Dữ liệu : Cho một số nguyên c (kích thước ba-lô) và n vật có các kích thước lần lượt s1, s2, ..., sn. Câu hỏi : Có thể bỏ đầy hoàn toàn ba-lô bởi một số vật lấy từ n vật đã cho ? 5. Bài toán thỏa mãn các biểu thức boolean ở dạng chuẩn hội Dữ liệu: Một biểu thức boolean ở dạng chuẩn hội. Câu hỏi : Có thể gán giá trị nào đó cho các biến làm biểu thức thỏa mãn ? 6. Bài toán đường đi Hamilton Dữ liệu: Một đồ thị G = . Câu hỏi : Tồn tại hay không một đường đi Hamilton (đi qua tất cả các đỉnh) trong đồ thị đã cho ? III.3. Ví dụ về rút gọn kiểu đa thức Bây giờ ta xét một ví dụ : hãy rút gọn kiểu đa thức bài toán ba-lô về bài toán sắp đặt các việc có hình phạt. Giả sử I = (s1, s2, ..., sn; c) là một dữ liệu vào cho bài toán ba-lô. - Nếu c n 1, j s j∑ = < thì câu trả lời là không. Khi đó, ta xét bài toán sắp đặt các việc có hình phạt được định nghĩa bởi ti = 2, di = pi = 1 và k = 0 với câu trả lời không. - Nếu trái lại, c n 1, j s j∑ = ≥ thì câu trả lời là thoả mãn. Ta xét bài toán sắp đặt các việc có hình phạt được định nghĩa bởi ti = pi = si và di = c với ∀i = 1 .. n, và k = c n 1, j s j∑ = − Bây giờ ta kiếm tra trường hợp cá biệt I của bài toán ba-lô có một lời giải nếu và chỉ nếu bài toán sắp đặt các việc có hình phạt mà ta sẽ đưa về cũng có một lời giải : Độ phức tạp tính toán 101 Nếu bài toán ba-lô có một lời giải, khi đó tồn tại một tập hợp con J thuộc khoảng { 1, ..., n } sao cho ∑j∈J sj = c. Ta chọn một hoán vị P sao cho tất cả các việc có chỉ số trong J được chọn trước các việc khác. Cả || J || việc này đều được làm xong trước ngày kết thúc của chúng, trong khi đó, các việc khác được làm xong sau ngày kết thúc, từ đó sinh ra một hình phạt: ∑J = || J|| + 1, npP (J) = ∑J = || J|| + 1, n sP (J) = ∑J = 1, n J ∈J = ∑J = 1, n sJ - c = k Như vậy, các việc được làm xong với một hình phạt nhỏ hơn hoặcbằng k, giả sử m là số nguyên lớn nhất sao cho m việc đầu tiên được làm xong trước ngày kết thúc chung của chúng là c. Như vậy, ta có: ∑J -- 1, m tP(J) ≤ c và hình phạt là : ∑J = m + 1, n PP(J) ≤ k Do ti = Pi = si, ta có ∑J - 1, m tP(J)z + ∑J - m + 1, n PP(J) = ∑J - 1,n sJ = c + k Do đó, cả hai bất đẳng thức đều bằng nhau và các vật có chỉ số P(j) với j = 1..m sẽ làm đầy ba-lô. Ta cần kiểm chứng rằng việc rút gọn là theo thời gian đa thức, nghĩa là chỉ có một phép tính duy nhất là tính giá trị ∑J - 1, n sJ - c. Rõ ràng phép tính này đòi hỏi một thời gian đa thức. Việc xây dựng bài toán sắp đặt các việc có hình phạt sẽ là có thời gian hằng nếu số nguyên này âm, có thời gian tuyến tính nếu số nguyên này dương. Cho đến lúc này, ta chưa biết có bài toán nào trong sáu bài toán trên thuộc vào lớp không P. Tuy nhiên, người ta dễ dàng chứng minh được rằng chúng đều thuộc lớp NP. Ví dụ 6. 2 Bài toán tô màu các đỉnh của một đồ thị là thuộc lớp NP. Thật vậy, máy Turing không đơn định sau đây nhận biết ngôn ngữ kết hợp với bài toán này về thời gian tuyến tính (và do vậy, là đa thức) : trong thời gian đầu, máy Turing thực hiện tô cho mỗi đỉnh, một cách không đơn định, một màu nào đó trong số k màu. Sau đó, máy Turing kiểm tra việc tô màu này đã thỏa mãn chưa, nghĩa là kiểm tra tại các mút của các cung xem các đỉnh có cùng một tô một màu không ?. Bây giờ ta chứng minh rằng thực tế tất cả sáu bài toán trên đều có thể rút gọn kiểu đa thức từ bài toán kia. Từ đó, cả sáu bài toán đều thuộc lớp P nếu và chỉ nếu một trong chúng thuộc P. Ta có định nghĩa sau đây : Định nghĩa 6.3 Một bài toán là NP-cứng (NP - Comlete) nếu nó ở trong lớp NP. Rõ ràng, định nghĩa trên có ích vì tồn tại những bài toán NP-đầy đủ như vậy. 102 Lý thuyết tính toán Định ký Cook - 1971 (Stephen Cook) : Bài toán về tính thỏa mãn của các biểu thức boolean dưới dạng chuẩn hội là một bài toán NP -đầy đủ. Ta không chứng minh định lý này. Bổ đề 6. 1 Cả sáu bài toán trên đây đều là NP-đầy đủ. Ta có mệnh đề sau: Mệnh đề 6. 4 P = NP nếu và chỉ nếu tồn tại ngôn ngữ L ∈ P sao cho L là NP-đầy đủ. Bài tập 1. Xét ngôn ngữ L = { wcw’ | w ∈ { a, b }* và w ≠ w’ } Chứng minh rằng L ∈ NTIME (n) ∩ DSPACE (log2 (n)). 2. Chứng minh rằng cả sáu bài toán đã nêu đều có thể rút gọn kiểu đa thức từ bài toán này về bài toán kia. 3. Một đồ thị được gọi là đầy đủ nếu có hai đỉnh bất kỳ được nối với nhau bới một cạnh. Đồ thị được gọi là k-đầy đủ nếu tồn tại một đồ thị con có k đỉnh là đầy đủ. Bài toán đầy đủ k-đầy đủ như sau: Dữ liệu : Một đồ thị G và một số nguyên k Câu hỏi : G có phải là k-đầy đủ? Chứng minh rằng bài toán đồ thị k-đầy đủ là bài toán NP đầy đủ. 4. Những bài toán sau đây thuộc lớp NP, thuộc lớp P, thuộc lớp NP-bộ nhớ ? Bài toán nào là NP-đầy đủ ? a) Dữ liệu : Một câu w biểu diễn một biểu thức Boolean. Câu hỏi : Câu w có phải là một hằng đúng (tautology) không ? b) Dữ liệu : Một máy Turing T trên bảng chữ { a, b }. Câu hỏi : Có tồn tại không một câu w ∈ S* có độ dài n sao cho máy Turing T nhận biết w hết một lượng thời gian nhỏ hơn boặc bằng n ? c) Dữ liệu : Một máy Turing trên bảng chữ { a, b }. Câu hỏi : Tồn tại hay không một câu có độ dài n sao cho T nhận biết câu này về bộ nhớ nhỏ hơn hoặc bằng n ? d) Dữ liệu : Một cặp đồ thị (G, G’). Câu hỏi : Đồ thị G’ có đẳng cấu (isomorphic) với một đồ thị con của G hay không ?
File đính kèm:
- giao_trinh_ly_thuyet_tinh_toan.pdf