Giáo trình Lý thuyết tính toán

Chia sẻ: Nguyễn Duy | Ngày: | Loại File: PDF | Số trang:108

Thêm vào BST

Báo xấu

288
lượt xem 52
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với kết cấu nội dung gồm 6 chương, giáo trình "Lý thuyết tính toán" giới thiệu đến các bạn những nội dung về nhập môn lý thuyết tính toán, mô hình các máy Ram, mô hình các máy Turing, luận đề Church,... Mời các bạn cùng tham khảo để có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu.

Chủ đề:

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

Lưu

Nội dung Text: 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Ì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 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
CHƯƠNG 1 Nhập môn lý thuyết tính toán (Introduction to the theory of computation) It’s not bad being the small fish. I. Các đối tượng được xử lý trong Tin học 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. Định nghĩa 1.1 : Một bảng chữ S là một tập hợp hữu hạn các chữ (letters), hay là các ký tự (symbols, hay characters). Số lượng các ký tự, còn gọi là bản số (cardinality) hay lực lượng của S, được ký hiệu ||S||, hay |S|, nếu không sợ nhầm lẫn. Một câu, hay một từ, trên bảng chữ S đã cho là một dãy hữu hạn các ký tự của bảng chữ S được viết liên tiếp nhau. Độ dài (length) của một câu (trên bảng chữ S đã cho) là số lượng các ký tự có mặt trong câu. Câu rỗng (empty word), được ký hiệu là e (ω hoặc e, hoặc l), là câu có độ dài không, tức không chứa ký tự nào. Ghép (concatenation) của hai câu là đặt kế tiếp hai câu đã cho (trên cùng dòng) để nhận được một câu mới. Bằng cách ghép liên tục như vậy cho mọi ký tự, mọi câu của S, ta nhận được một tập hợp chứa mọi câu có thể trên S, ký hiệu S*. Người ta nói S*là một cấu trúc đồng đẳng (nonoide), mà phần tử trung hòa (neutral element) chính là câu rỗng. Cho trước một bảng chữ S, người ta định nghĩa một quan hệ có thứ tự toàn phần (total order) trên S* như sau : cho một thứ tự tùy ý trên các ký tự của S, PGS.TS. PHAN HUY KHÁNH biên soạn 1
2 Lý thuyết tính toán người ta sắp xếp các câu theo một thứ tự phân cấp (hierechical order), đầu tiên là theo độ dài câu, sau đó theo thứ tự từ vựng (lexicography), hay thứ tự ABC. Ví dụ : Cho S = {a, b, c}, với giả thiết thứ tự phân cấp của các ký tự là a < b < c, ta có thể đánh số các câu của S* (kể cả câu rỗng e) bắt đầu từ 1 trở đi như sau : e1 a2 b3 c4 aa 5 ab 6 ac 7 ba 8 bb 9 bc 10 ca 11 cb 12 cc 13 aaa 14 aab 15 aac 16 . . . Hình 1.1. Thứ tự phân cấp trong S* II. Các máy (machines) II.1. Khía cạnh chức năng (functional look) Một máy (machine) được biểu diễn một cách hệ thống như sau : Dữ liệu vào Dữ liệu ra Máy Hình 1.2. Khía cạnh chức năng của một máy Ở lối vào, người ta cung cấp một hoặc nhiều dữ liệu (data) cho máy, thì lối ra, người ta nhận được kết quả (result). Giả thiết rằng các dữ liệu vào có dạng là dãy các ký tự, là một câu trên một bảng chữ nào đó đã cho (vào từ bàn phím chẳng hạn). Kết quả là một phần tử của một tập hợp xác định trước (predefini). Người ta phân biệt các kiểu máy (machine type) tùy theo bản chất của tập hợp kết quả này như sau : 1. Nếu tập hợp chỉ có hai phần tử { không, có } hay {0, 1}, máy sẽ chia dữ liệu vào thành ba phần tùy theo kết quả : Tập hợp các câu trên bảng chữ vào sau khi được xử lý sẽ cho ra một kết quả là có (đúng, true), hoặc không (sai, false). Tập hợp các câu mà máy đưa ra một kết quả khác. Tập hợp các câu trên bảng chữ vào mà máy không cho kết quả nào.
Nhập môn lý thuyết tính toán 3 Các tập hợp này tạo thành các ngôn ngữ (language). Hai tập hợp đầu là bù nhau nếu với mọi dữ liệu vào, máy đều cho một kết quả. Người ta gọi đó là máy đoán nhận (recognition machine) câu. 2. Nếu kết quả là một dãy hữu hạn các ký tự, ta nhận được một câu trên một bảng chữ G nào đó. Cho S là bảng chữ vào, máy xác định một hàm f từ S* vào G*, ta viết : f : S* → G * nghĩa là với một câu vào w ∈ S*, f(w) ∈ G*. Người ta nói máy thực hiện hàm f. Nếu với mọi câu vào w ∈ S*, máy đều cho một kết quả f(w) ∈ G*, thì f được gọi là hàm toàn phần (partial function). Người ta gọi đó là máy tính toán (computation machine) hay máy tính. Chú ý rằng kiểu máy thứ nhất (máy đoán nhận) mà chúng ta vừa phân biệt thực ra chỉ là một trường hợp đặc biệt của kiểu máy thứ hai (máy tính). 3. Nếu kết quả là một dãy vô hạn các ký tự và bảng chữ đang sử dụng chỉ có tối thiểu hai ký tự, trong đó có một dấu phân cách (separator) #, thì người ta nhận được kết quả là một dãy liên tiếp các câu phân cách nhau bởi dấu #, tạo thành một ngôn ngữ. Người ta gọi ngôn ngữ này là liệt kê được (enumerated) bởi máy. II.2. Khía cạnh cấu trúc (structural look) Ở đây, ta chỉ quan tâm đến các máy được mô tả đầy đủ về chức năng hoạt động của chúng. Những máy này có thê : Thực hiện các phép toán sơ cấp (elementary operation) trong một khoảng thời gian hữu hạn. Mỗi phép toán, giả thiết không chia cắt nhỏ hơn được, được chọn trong một tập hợp hữu hạn các phép toán là một phần mô tả cấu trúc máy. Lần lượt thực hiện các phép toán sơ cấp theo một thứ tự xác định trước, tạo thành một chương trình (program), là một phần mô tả cấu trúc máy. Một dãy các phép toán sơ cấp được máy thực hiện liên tiếp được gọi là một tính toán (computation) của máy.
4 Lý thuyết tính toán III. Mô hình tính toán Thay vì phải thay đổi lại máy tính mỗi lần thay đổi bài toán cần giải, người ta định nghĩa các lớp máy có cùng nguyên lý hoạt động và chúng chỉ khác nhau ở chương trình. Người ta gọi mô hình tính toán (model), ký hiệu T, là sự mô tả tất cả các phép toán sơ cấp có thể được thực hiện trên những đối tượng nào, cách tác động lên mỗi một trong chúng như thế nào, và mô tả cách thức chương trình được thực hiện (execution) trên máy. Một trường hợp riêng (instance) của mô hình là một máy biệt lập nào đó, gọi tắt là máy, hoạt động theo cách mô hình tính toán đã chỉ ra. Máy này được định nghĩa bởi dữ liệu vào của chương trình : Mô hình + Chương trình = Máy Một khi một mô hình tính toán T được định nghĩa, được gọi là một T−máy, vấn đề đặt ra là làm sao để có thể biết : − lớp ngôn ngữ đoán nhận được (recognized), được gọi là T−nhận biết được, hoặc − lớp các hàm tính được (computable), được gọi là T−tính được, hoặc − lớp các ngôn ngữ liệt kê được (enumerable) được gọi là T −liệt kê được, bởi một máy nào đó của mô hình này ? Hai mô hình tính toán được đưa ra so sánh với nhau : một mô hình T1 được nói là mạnh hơn so với một mô hình T2 nếu : − mọi ngôn ngữ T2−nhận biết được cũng là T1−nhận biết được, hoặc − mọi hàm T2-tính được cũng là T1−tính được, hoặc − mọi ngôn ngữ T2-liệt kê được cũng là T1-liệt kê được. Hai mô hình được gọi là tương đương (equivalent) nếu mỗi mô hình mạnh hơn mô hình kia và ngược lại. Hai mô hình là không thể so sánh với nhau được nếu không tồn tại mô hình nào ít ra đủ mạnh hơn mô hình kia.
Nhập môn lý thuyết tính toán 5 IV. Định nghĩa bài toán Trong Tin học lý thuyết, định nghĩa về bài toán (problem) có vai trò đặc biệt quan trọng, khác với khái niệm thông thường về bài toán được dùng trong lĩnh vực Toán học hoặc hiểu theo nghĩa thông dụng. Định nghĩa 1.2 : Một bài toán là : − Sự mô tả cách biểu diễn (hữu hạn) các phần tử của một tập hợp hữu hạn hay vô hạn đếm được. − Một phát biểu liên quan đến các phần tử của tập hợp này, có thể là đúng, hoặc có thể là sai tùy theo phần tử được chọn. Sau đây là một số ví dụ : Bài toán 1 : Dữ liệu: Một số nguyên viết trong hệ 10. Câu hỏi : Số nguyên đã cho có là số nguyên tố hay không ? Bài toán 2 : Dữ liệu : Một số nguyên viết trong hệ 10. Câu hỏi : Có phải số nguyên này được viết dưới dạng tổng của 4 số bình phương ? Bài toán 3 : Dữ liệu : Một số nguyên viết dưới dạng tích của các số hạng trong hệ 10. Câu hỏi : Số nguyên đã cho có là số nguyên tố hay không ? Bài toán 4 : Dữ liệu : Một đồ thị hữu hạn được biểu diễn bởi một danh sách gồm các đỉnh và các cung, trong đó mỗi đỉnh được biểu diễn bởi một số nguyên trong hệ 10. Câu hỏi : Có tồn tại một đường đi Hamilton (đi qua hết tất cả các đỉnh của đồ thị, mỗi đỉnh đi qua đúng một lần) trong đồ thị đã cho không ? Bài toán 5 : Dữ liệu : Một biểu thức chính quy (regular expression) được xây dựng trên một bảng chữ S (là một biểu thức nhận được từ các câu w∈S* bởi các phép hoặc, phép ghép tiếp, phép * và lấy bù). Câu hỏi : Có phải biểu thức đã cho biểu diễn (hay chỉ định) một ngôn ngữ trống (empty language) hay không ? Bài toán 6 : Dữ liệu : Một dãy hữu hạn các cặp câu (u1, v1), (u2, v2)..., (uk, vk). Câu hỏi : Tồn tại hay không một dãy chỉ số i1 , i2 ,...in sao cho thoả mãn ui1 ui2... uin = vi1 vi2... vin ?
6 Lý thuyết tính toán Việc biểu diễn tường minh các dữ liệu là một thành phần của bài toán. Điều này đóng vai trò đặc biệt quan trọng khi người ta quan tâm đến độ phức tạp (complexity) của một bài toán. Mỗi dữ liệu sẽ tạo thành một trường hợp cá biệt của bài toán, được biểu diễn bởi một câu trên một bảng chữ hữu hạn đã cho. Với mỗi bài toán P được hợp thành từ một biểu diễn các phần tử của một tập hợp và từ một phát biểu liên quan đến các phần tử này, người ta thường kết hợp bài toán P với một ngôn ngữ, gọi là ngôn ngữ đặc trưng (characteristic language) của bài toán, được hợp thành từ tập hợp các câu biểu diễn một phần tử của tập hợp để từ đó, kết quả của bài toán là câu trả lời đúng. Người ta ký hiệu LP là ngôn ngữ đặc trưng của bài toán P. Cho trước một bài toán P, bài toán ngược lại CP là bài toán nhận được từ P bằng cách giữ nguyên cách biểu diễn các dữ liệu nhưng riêng câu hỏi thì đặt ngược lại. Ví dụ, bài toán ngược với bài toán 1 sẽ là : Bài toán 1’ : Dữ liệu : Cho một số nguyên viết trong hệ 10. Câu hỏi : Số nguyên này không phải là một số nguyên tố ? Từ đó, lời giải một bài toán đưa đến sự nhận biết của một ngôn ngữ : ngôn ngữ kết hợp với bài toán này. Người ta đưa ra định nghĩa hình thức sau đây : Định nghĩa 1.2 : Một máy giải (solve) một bài toán P nếu và chỉ nếu với mọi câu f biểu diễn một phần tử của tập hợp liên quan đến bài toán này, máy cho phép xác định, trong một khoảng thời gian hữu hạn, nếu câu này thuộc về LP hay LCP. Người ta phân lớp các bài toán tùy theo độ khó (difficulty) để đưa ra câu trả lời từ dữ liệu vào đã cho. Một bài toán là tầm thường (trivial) nếu LP = ∅ hoặc nếu LCP = ∅. Thật vậy, trong trường hợp này, không cần thiết biết dữ liệu đưa vào để đưa ra câu trả lời. Chú ý rằng, những gì là tầm thường, đó là việc đưa ra câu trả lời, nhưng có thể rất khó để chứng minh rằng bài toán là tầm thường theo nghĩa này. Ví dụ, bài toán 2 là tầm thường. Các bài toán 1 và 3 có cùng câu hỏi, nhưng bài toán 3 giải quyết rất dễ dàng : chỉ cần đọc qua dữ liệu vào, người ta có thể đưa ra kết quả, tuy nhiên trong bài toán 1 thì cần phải xử lý dữ liệu vào. Bài toán 4 phức tạp hơn : người ta chưa biết phương pháp nào hoạt động một cách đơn định (deterministic) tiêu tốn một lượng thời gian đa thức (polynomial times) để giải quyết vấn đề đặt ra. Đối với bài toán 5 thì tính phức tạp còn lớn hơn nữa : người ta biết rằng mọi phương pháp đều hoạt động theo thời gian tối thiểu là lũy thừa. Cuối cùng bài toán 6 không thể giải được theo nghĩa đã đưa ra. Bài toán này được gọi là bài toán tương ứng Post (Post’s correspondence problem).
Nhập môn lý thuyết tính toán 7 Bài tập 1) Chứng minh rằng một tập hợp E là hữu hạn hay vô hạn đếm được nếu tồn tại một đơn ánh từ E vào N. Tương tự, nếu tồn tại một toàn ánh (surjection) từ Ν vào E. 2) Chứng minh rằng tích Đê-cac của hai tập hợp vô hạn đếm được cũng là một tập hợp vô hạn đếm được. 3) Chứng minh các tập hợp sau đây là vô hạn đếm được : N×N, Q, tập hợp Ν* gồm các dãy số nguyên, S*, S*×G*, S*×N, tập hợp (S*)* gồm các dãy các câu. Thể hiện các song ánh (bijection) giữa N và mỗi một tập hợp vừa nêu. 4) Cho S là một bảng chữ kích thước (bản số) n. Với mọi câu w∈S*, ký hiệu |w| là độ dài của w và m(w) là số thứ tự của w trong thứ tự phân cấp đã cho. Hãy tìm cách tính m(w) khi biết w. 5) Chứng minh rằng NN không phải là vô hạn đếm được. Tập hợp các chương trình Pascal có phải là vô hạn đếm được hay không ? Tập hợp các hàm f: N → N tính được nhờ một chương trình Psacal có là vô hạn đếm được hay không ? Từ đó suy ra rằng tồn tại các hàm từ N vào N không là vô hạn đếm được nhờ một chương trình Pascal. 6) Viết một chương trình để liệt kê : − các cặp số nguyên − các dãy hữu hạn các số nguyên − các câu trên một bảng chữ hữu hạn (chẳng hạn S={a, b, c}) − các cặp câu − các dãy hữu hạn các câu.
CHƯƠNG 2 Mô hình các máy RAM « I like the dreams of the future better than the history of the past » Jefferson I. Các máy RAM Máy RAM là một mô hình tính toán rất gần với máy tính điện tử và ngôn ngữ assembler. Máy RAM có các thành phần đặc trưng chung như sau : Một băng vào, hay dải vào (input tape) được chia thành nhiều ô (square hay pigeonhole) liên tiếp nhau, mỗi ô chứa một số nguyên hoặc một ký tự. Một đầu đọc (read head) đọc lần lượt nội dung từng ô trên băng vào, đọc từ trái qua phải. Một băng ra (output tape) cũng chia ra thành nhiều ô liên tiếp nhau và một đầu ghi (write head) có thể ghi mỗi lần lên một ô và tiến từ trái qua phải. Người ta nói rằng đầu đọc (hoặc ghi) được đặt trên (tại) một ô và di chuyển qua phải mỗi lần một ô. Trước tiên, ta xem rằng mỗi ô chứa một số nguyên có thể lớn tuỳ ý. Băng vào và băng ra của máy RAM được gọi là các cơ quan vào/ra. Máy RAM còn có các thành phần bên trong như sau : Các thanh ghi (registers) là các phần tử nhớ được đánh số thứ tự, số lượng các thanh ghi có thể lớn tuỳ ý. Mỗi thanh ghi có thể lưu giữ một số nguyên. Các thanh ghi lần lượt được đặt tên là R0, R1, R2, ... , Rn... Chỉ số i, i = 0, 1, 2, ..., được gọi là địa chỉ (address) của mỗi thanh ghi (hay của bộ nhớ). Riêng R0 là một thanh ghi đặc biệt, được gọi là thanh tổng (ACC − accumulator) hay thanh tích luỹ. Một tập hợp các đơn vị nhớ được đánh số chứa chương trình của máy RAM dưới dạng một dãy các lệnh sơ cấp (primary instructions) không bị thay đổi trong quá trình chạy (thực hiện). Mỗi lệnh được lưu trữ trong một đơn vị nhớ, được đánh số tương ứng với số thứ tự hay nhãn của lệnh (label). Một đơn vị nhớ chứa số thứ tự của lệnh đang được thực hiện, được gọi là thanh đếm lệnh (OC − Ordinal Counter). Lúc đầu nội dung là của OC là 1. Trong kiểu máy này, người ta truy cập trực tiếp đến mỗi thanh ghi bởi địa chỉ của thanh ghi đó. Chính lý do này mà kiểu máy này được đặt tên là Random Access Memory (viết tắt RAM). PGS.TS. PHAN HUY KHÁNH biên soạn 9
10 Lý thuyết tính toán x1 x2 ... xn Băng vào 1 R0 Thanh tổng Chương trình 2 R1 ... ... ... ... Các thanh ghi j Ri ... ... ... ... p Rn i Thanh đếm lệnh y1 y2 y3 ... Băng ra Hình 2.1 Sơ đồ một máy RAM Mỗi chương trình của máy RAM gồm một dãy lệnh sơ cấp, mỗi lệnh được tạo thành từ 2 thành phần : mã lệnh (operation code) và toán hạng (operand) : Mã lệnh Toán hạng Các lệnh được phân thành nhóm theo chức năng của phần mã lệnh như sau : Nhóm lệnh gán : LOAD Operand STORE Operand Nhóm lệnh số học : INCR Operand DECR Operand AD Operand SUB Operand MULT Operand DIV Operand Nhóm lệnh nhảy (hay lệnh ngắt, cũng còn gọi là lệnh chuyển điều khiển) : JUMP Label JGTZ Label JZERO Label HALT Nhóm lệnh vào − ra : READ Operand WRITE Operand
Mô hình các máy RAM 11 Theo nguyên tắc địa chỉ, phần toán hạng là địa chỉ (address) của toán hạng tham gia phép toán chỉ định bởi phần mã lệnh. Toán hạng có thể là một trong ba kiểu sau : Kiểu địa chỉ Ý nghĩa Số nguyên n Chỉ nội dung của thanh ghi thứ n (Rn). A: n (A = Absolute) toán hạng chính là số nguyên n đó. I: n (I = Indirection) toán hạng là nội dung của thanh ghi có số thứ tự là nội dung của thanh ghi Rn. Đây là kiểu lệnh gián tiếp. Nếu lệnh là một lệnh nhảy thì địa chỉ chính là số thứ tự của lệnh trong chương trình. Các lệnh trên đây của máy RAM điển hình cho các lệnh của ngôn ngữ assembler. Tuy nhiên ở đây vắng mặt các lệnh xử lý ký tự và các lệnh logic nhằm đơn giản cách trình bày. Thứ tự thực hiện các lệnh của chương trình là tuần tự (on sequence), bắt đầu từ lệnh đầu tiên (có nhãn 1). Ngoại lệ duy nhất là khi gặp lệnh nhảy (hay chuyển điều khiển) thì lệnh tiếp theo được thực hiện có nhãn chỉ định bởi lệnh nhảy này. Nguyên tắc thực hiện như sau : OC luôn luôn chứa nhãn của lệnh sẽ được thực hiện, lúc đầu nội dung OC là 1. Sau khi thực hiện lệnh, nội dung OC được tự động tăng thêm 1 (increment) nếu như lệnh vừa thực hiện không là lệnh nhảy. Nếu như lệnh vừa thực hiện là lệnh nhảy thì nội dung của OC lấy nhãn là phần địa chỉ của lệnh nhảy này. Sau đây sử dụng một số quy ước để giải thích cách thực hiện lệnh. ← dấu gán ; quy ước số nguyên i nằm bên trái dấu gán chỉ thanh ghi thứ i là Ri, số nguyên i nằm bên phải dấu gán chỉ giá trị chính là số nguyên i đó. Chỉ nội dung của thanh ghi Ri. Chỉ nội dung của thanh ghi có số thứ tự được chứa trong thanh ghi Ri đối với kiểu lệnh gián tiếp. ACC Chỉ thanh ghi R0. CO Chỉ thanh đếm lệnh. Nội dung của CO. Sau đây là bảng các lệnh RAM và ý nghĩa sử dụng của chúng.
12 Lý thuyết tính toán Lệnh Ý nghĩa LOAD  n ACC ← LOAD  A: n ACC ← giá trị n LOAD  I: n ACC ← STORE  n n ← STORE  I: n ← INCR  n n ← + 1 DECR  n n ← - 1 ADD  n ACC ← + SUB  n ACC ← − MULT  n ACC ← × DIV  n ACC ← / JUMP  n CO ← n JGTZ  n CO ← n nếu ≥ 0 JZERO  n CO ← n nếu = 0 Cả hai trường hợp trên, nếu không thỏa mãn, CO ← + 1  HALT  Dừng máy READ n  n ← số nguyên trong ô dưới đầu đọc của băng, đầu đọc dịch một ô qua phải WRITE n  Nội dung được ghi vào ô dưới đầu ghi, đầu ghi dịch qua phải một ô. Ví dụ 2.1 : Chương trình RAM sau đây đánh giá trị n! READ 0 đọc một giá nguyên n vào ACC JZERO 10 nếu n = 0, nhảy đến nhãn 10, nếu không, thực hiện lệnh tiếp theo STORE 1 R1 ← 4: STORE 2 R2 ← DECR 1 R1 ← < R1> − 1 LOAD 1 ACC ← JZERO 12 nếu = 0 nhảy đến 12 MULT 2 ACC ← * JUMP 4 CO ← 4 10: LOAD A: 1 ACC ← 1 STORE 2 R2 ← 12 : WRITE 2 ghi ra HALT Dừng máy
Mô hình các máy RAM 13 Ví dụ 2.2 : Chương trình RAM tính nn READ 1 R1 ← số nguyên trên ô của băng vào LOAD 1 ACC ← JGTZ 6 nếu ≥ 0, nhảy đều 6 WRITE A:0 in ra 0 JUMP 22 về lệnh dừng 6 : LOAD 1 ACC ← STORE 2 R2 ← LOAD 1 ACC ← DECR 0 ACC ← − 1 STORE 3 R3 ← 11 : LOAD 3 ACC ← JGTZ 14 nếu ≥ 0, nhảy đến 14 JUMP 21 nhảy đến 21 nếu < 0 14: LOAD 2 ACC ← MULT 1 ACC ← * STORE 2 R2 ← LOAD 3 ACC ← DECR 0 ACC ← − 1 STORE 3 R3 ← JUMP 11 nhảy đến 11 21: WRITE 2 in ra nội dung 22: HALT dừng Ta có thể viết đoạn trình Pascal minh họa trình RAM như sau : begin read (R1) if R1 < 0 then write (R0) else begin R2:= R1 ; R3:= R1 − 1 ; while R3 > 0 do begin R2:= R2*R1 ; R3:= R3–1 end ; write (R2) end end ; Ta thấy một trình RAM xác định một ánh xạ từ tập các băng vào lên tập các băng ra. Đây là ánh xạ bộ phận (partial map) vì một số ánh xạ có thể không xác định trên một số băng vào, nghĩa là chương trình ứng với băng vào đó không dừng. Ta có thể giải thích ánh xạ này ở dưới hai dạng : dạng hàm và dạng ngôn ngữ.
14 Lý thuyết tính toán Dạng hàm f : S* → S* Giả sử chương trình P luôn đọc được từ băng vào n số nguyên x1, x2, ..., xn và ghi lên băng ra không quá một số nguyên y ở ô đầu tiên, khi đó ta nói P tính hàm f (x1, x2, ..., xn) = y. Dạng ngôn ngữ L ⊆ S* Giả sử trên băng vào có câu w = a1a2 ... an với ai ở ô thứ i, i = 1.. n, còn ô thứ n+1 chứa # là ký tự kết thúc dãy. Ta nói w được thừa nhận bởi chương trình RAM nếu nó đọc được hết w, kể cả ký tự #, sau đó viết lên ô đầu tiên của băng ra một ký tự kết quả và dừng. Ta nói máy RAM thừa nhận một ngôn ngữ L đã cho nếu thừa nhận mọi câu w∈L. Nếu w∉L thì máy RAM có thể không đọc hết w, ghi ký tự kết thúc lên băng ra, hoặc bị hóc (crash), hoặc không bao giờ dừng. Sự khác nhau cơ bản giữa mô hình máy RAM vừa mô tả ở trên và các máy tinh điện tử hiện nay là ở chỗ : 1) Ta đã giả thiết có thể sử dụng một số lớn tùy ý các thanh ghi, tuy nhiên trong thực tế điều này rất khó thực hiện. Tương tự, ta đã giả thiết có thể đặt một số nguyên lớn tùy ý vào một thanh ghi nào đó, hoặc vào một ô nào đó trên băng vào, hoặc trên băng ra. Nhưng điều này cũng rất khó thực hiện trong thực tiễn. 2) Ta đã giả thiết rằng chương trình có sẵn trong bộ nhớ RAM chỉ có thể đọc (không thể bị thay đổi khi chạy chương trình), khác với các bộ nhớ kiểu thanh ghi. Điều này cũng không xảy ra với các máy tính thông dụng. Sự khác nhau chi tiết như sau : 3) Các lệnh sơ cấp được chọn hạn chế hơn so với các ngôn ngữ assembler Tuy nhiên, người ta có thể nói rằng vẫn không làm mất tính tổng quát nếu giảm đáng kể tập hợp các lệnh sơ cấp. 4) Các dữ liệu đưa vào không phải dưới dạng các số nguyên được đọc toàn bộ một lần trong một ô, mà dưới dạng một dãy ký tự (một dãy các chữ số), tương tự như vậy đối với các kết quả ra. Ta hãy xem làm cách nào để giải quyết vấn đề do 4) đặt ra : Trong các máy tính, các số nguyên thường được biểu diễn theo hai cách phân biệt là biểu diễn thập phân, hoặc biểu diễn nhị phân. Cách biểu diễn nhị phân có lợi thế hơn vì chỉ sử dụng hai chữ số. Máy tính sẽ chuyển đổi chuỗi ký tự biểu diễn số nguyên thành biểu diễn nhị phân để đặt trong các thanh ghi, sau đó chuyển đổi kết quả đang ở dạng biểu diễn nhị phân của số nguyên thành chuỗi ký tự trên băng ra. Điểm 1) trên đây có nghĩa : trong mọi trường hợp, kích thước của bài toán cần giải là đủ bé để bộ nhớ máy tính có thể chứa hết ở dạng nhị phân trong các đơn vị nhớ, hay từ nhớ (memory word). Chú ý rằng nếu chỉ làm việc với cách biểu diễn số nguyên bởi chuỗi các chữ số thì không còn giả thiết số lớn tùy ý nữa.