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 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ÌNHTHÔ 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 PGS.TS. PHAN HUY KHÁNH biên soạn 1 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ác máy có băng ra...................................................49 IV.2.3. Các máy Turing không đơn định................................................................49 IV.2.4. Thu gọn một bảng chữ còn ba ký tự...........................................................50 IV.2.5. Rút gọn một bảng chữ còn hai ký tự..........................................................52 IV.3. Các máy Turing có băng vô hạn một phía.................................................52 V. MÁY TURING VẠN NĂNG..............................................................................................................53 VI. TỒN TẠI CÁC HÀM KHÔNG LÀ T−TÍNH ĐƯỢC............................................................55 CHƯƠNG 4 LUẬN ĐỀ CHURCH........................................................................59 I. TƯƠNG ĐƯƠNG GIỮA CÁC MÔ HÌNH MÁY TURING VÀ MÁY RAM.........................59 I.1. Mọi hàm T-tính được cũng là R−tính được................................................59 I.2. Mọi hàm R−tính được cũng là T−tính được...............................................60 I.2.1. Tăng nội dung thanh ghi n lên 1.................................................................60 I.2.2. Giảm 1 nội dung thanh ghi n......................................................................60 I.2.3. Đưa nội dung thanh ghi n về 0...................................................................60 I.2.4. Nhảy theo nội dung thanh ghi n.................................................................61 I.2.5. Hoán vị nội dung hai thanh ghi n và m......................................................61 I.3. Sự khác nhau giữa máy Turing và máy RAM.............................................61 II. MÔ HÌNH CÁC HÀM ĐỆ QUY.......................................................................................................62 II.1. Các hàm đệ quy nguyên thủy (primitive recursive functions)....................62 II.1.1. Xây dựng các hàm sơ cấp...........................................................................62 II.1.2. Sơ đồ hợp thành tổng quát..........................................................................62 II.1.3. Sơ đồ đệ quy đơn (simple recurrence) .......................................................63 II.1.4. Sơ đồ đệ quy đồng thời ..............................................................................63 II.1.5. Các hàm được định nghĩa bởi case.............................................................65 II.2. Các hàm đệ quy..........................................................................................67 II.2.1. Sơ đồ tối thiểu ............................................................................................67 II.2.2. Các hàm đệ quy trừu tượng (abstract recursive functions) ........................68 II.2.3. Một số ví dụ................................................................................................68 II.3. Các hàm đệ quy đều T−tính được...............................................................70 II.3.1. Sơ đồ hợp thành tổng quát..........................................................................70 II.3.2. Sơ đồ đệ quy đơn........................................................................................70 II.3.3. Sơ đồ tối thiểu ............................................................................................71 Nhập môn lý thuyết tính toán 3 II.4. Mọi hàm T−tính được là đệ quy bộ phận...................................................71 III. LUẬN ĐỀ CHURCH............................................................................................................................73 CHƯƠNG 5 CÁC BÀI TOÁN KHÔNG QUYẾT ĐỊNH ĐƯỢC ..........................77 I. CÁC NGÔN NGỮ LIỆT KÊ ĐỆQUY VÀ CÁC NGÔN NGỮĐỆQUY.......................................77 II. CÁC BÀI TOÁN KHÔNG QUYẾT ĐịNH ĐƯỢC................................................................................82 III. THUẬT TOÁN RÚT GỌN MỘT BÀI TOÁN VỀ BÀI TOÁN KHÁC .............................................83 CHƯƠNG 6 ĐỘ PHỨC TẠP TÍNH TOÁN.........................................................93 I. ĐỘ PHỨC TẠP VỀ THỜI GIAN VÀ VỀ BỘ NHỚ...............................................................84 II. CÁC LỚP CỦA ĐỘ PHỨC TẠP....................................................................................................84 II.1. Hiện tượng nén...........................................................................................84 II.2. Các họ P, NP và P−bộ nhớ (P−space).....................................................84 III. RÚT GỌN ĐA THỨC VÀ CÁC BÀI TOÁN NP−ĐẦY ĐỦ.........................................................84 III.1. Khái niệm...................................................................................................84 III.2. Các bài toán cổ điển ..................................................................................84 III.3. Ví dụ về rút gọn kiểu đa thức.....................................................................84 ... - tailieumienphi.vn