ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN ANH TÙNG CÀI ĐẶT MÁY TURING VÀ ỨNG DỤNG MÁY TURING ĐÁNH GIÁ ĐỘ PHỨC TẠP THUẬT TOÁN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
THÁI NGUYÊN - 2015
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN ANH TÙNG CÀI ĐẶT MÁY TURING VÀ ỨNG DỤNG MÁY TURING ĐÁNH GIÁ ĐỘ PHỨC TẠP THUẬT TOÁN Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60480101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Người hướng dẫn khoa học: PGS.TSKH. NGUYỄN XUÂN HUY
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
THÁI NGUYÊN - 2015
i
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn này do chính tôi thực hiện, dưới sự hướng
dẫn khoa học của PGS.TSKH. Nguyễn Xuân Huy, số liệu và kết quả nghiên
cứu trong luận văn này hoàn toàn trung thực và chưa sử dụng để bảo vệ
một công trình khoa học nào, các thông tin, tài liệu trích dẫn trong luận văn
đã được chỉ rõ nguồn gốc. Mọi sự giúp đỡ cho việc hoàn thành luận văn
đều đã được cảm ơn. Nếu sai tôi hoàn toàn chịu trách nhiệm.
Thái Nguyên, tháng 8 năm 2015
Tác giả
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Nguyễn Anh Tùng
ii
LỜI CẢM ƠN
Em xin gửi lời cảm ơn chân thành nhất đến thầy giáo PGS.TSKH. Nguyễn
Xuân Huy đã định hướng và nhiệt tình hướng dẫn, giúp đỡ em trong quá trình
làm luận văn.
Em xin gửi lời biết ơn sâu sắc đến quý thầy cô giáo trường Đại học Công nghệ
thông tin và truyền thông, các thầy giáo, cô giáo ở Viện công nghệ thông tin
Hà Nội đã truyền đạt những kiến thức và kinh nghiệm quý báu cho chúng em
trong thời gian học tập.
Xin chân thành cảm ơn các bạn bè, đồng nghiệp, các bạn học viên lớp cao
học CK12I, những người thân trong gia đình đã động viên, chia sẻ, tạo điều
kiện giúp đỡ trong suốt quá trình học tập và làm luận văn.
Thái Nguyên, tháng 8 năm 2015
Học viên
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Nguyễn Anh Tùng
iii
MỤC LỤC LỜI CAM ĐOAN .............................................................................................. i
LỜI CẢM ƠN ................................................................................................... ii
MỤC LỤC ........................................................................................................ iii
DANH MỤC BẢNG BIỂU, HÌNH VẼ ............................................................ v
MỞ ĐẦU .......................................................................................................... 1
Chƣơng 1. TỔNG QUAN MÔ HÌNH MÁY TURING ................................ 1
1.1. Giới thiệu chung ..................................................................................... 1
1.2. Cấu trúc máy Turing ............................................................................... 2
1.3. Hoạt động của máy Turing ..................................................................... 6
1.4. Trạng thái và sơ đồ trạng thái của máy Turing....................................... 7
1.5. Máy Turing và định nghĩa thuật toán ................................................... 14
1.5.1. Độ phức tạp thuật toán ................................................................... 14
1.5.2. Ứng dụng máy Turing để đo độ phức tạp thuật toán ..................... 20
1.6. Kết luận ................................................................................................. 21
Chƣơng 2. CÀI ĐẶT MÁY TURING NGUYÊN THỦY VÀ MỘT SỐ
CẢI TIẾN .................................................................................... 22
2.1. Cài đặt Máy Turing ............................................................................... 22
2.1.1. Giao diện chương trình ................................................................... 27
2.1.2. Cấu trúc dữ liệu đầu vào ................................................................ 30
2.1.3. Các hàm xử lí dữ liệu ..................................................................... 34
2.2. Phát triển bộ nhớ máy Turing ............................................................... 37
2.2.1. Máy Turing nhiều băng .................................................................. 37
2.2.2. Cài đặt cấu trúc ngăn xếp (Stack) .................................................. 37
2.2.3. Cài đặt cấu trúc hàng đợi (Queue) ................................................. 39
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
2.2.4. Cài đặt bộ nhớ imem và cmem ....................................................... 40
iv
2.4. Kết luận ................................................................................................. 42
Chƣơng 3. MỘT SỐ CHƢƠNG TRÌNH ỨNG DỤNG MÁY TURING
ĐO ĐỘ PHỨC TẠP THUẬT TOÁN ......................................... 44
3.1. Bài toán trừ một vào số tự nhiên .......................................................... 44
3.2. Biểu diễn số thập phân n thành (n+1) vạch | ......................................... 47
3.3. Biểu diễn (n+1) vạch | thành số tự nhiên n ........................................... 50
3.4. Cộng hai số tự nhiên lớn ....................................................................... 53
3.5. Kết luận ................................................................................................. 62
KẾT LUẬN ..................................................................................................... 64
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
TÀI LIỆU THAM KHẢO ............................................................................ 65
v
DANH MỤC BẢNG BIỂU, HÌNH VẼ
Bảng
Bảng 1.1. So sánh câu lệnh giữa cách viết thông thường và cách viết gộp ............. 6
Bảng 1.2. Trạng thái máy Turing ............................................................................. 10
Hình vẽ
Hình 1.1. Mô hình máy Turing ....................................................................... 2
Hình 1.2. Mối quan hệ giữa lớp P và NP ...................................................... 18
Hình 1.3. Minh hoạ một phép dẫn bài toán 1 thành 2 trong thời gian
đa thức ........................................................................................... 19
Hình 1.4. Mối quan hệ giữa lớp P, NP và NPC ............................................ 20
Hình 2.1. Giao diện máy Turing ................................................................... 27
Hình 2.2. Chọn tệp mặc định ........................................................................ 28
Hình 2.3. Chọn chương trình do người dùng tạo .......................................... 28
Hình 2.4. Nhập dữ liệu từ bàn phím ............................................................. 29
Hình 2.5. Hiển thị kết quả ............................................................................. 29
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Hình 2.6. Hiển thị kết quả trung gian của chương trình ............................... 30
1
MỞ ĐẦU
Thuật toán là một trong những khái niệm quan trọng nhất trong tin học.
Thuật toán xuất phát từ nhà khoa học Arập Abu Ja’far Mohammed ibn Musa
al Khowarizmi. Chúng ta có thể xem thuật toán là một công cụ dùng để giải
bài toán được xác định trước. Việc nghiên cứu về thuật toán và độ phức tạp
của thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính
chỉ giải quyết được vấn đề khi đã có hướng dẫn giải chính xác và phù hợp với
điều kiện thực tế (điều kiện về công nghệ và chi phí bộ nhớ, thời gian). Nếu
hướng dẫn giải sai hoặc không phù hợp thì máy tính không thể giải đúng
được bài toán hoặc lãng phí tài nguyên. Trong khoa học máy tính, thuật toán
được định nghĩa là một dãy hữu hạn các thao tác được sắp xếp theo một trình
tự nhất định sao cho sau khi thực hiện dãy thao tác ấy, từ input của bài toán,
ta nhận được output cần tìm. Đối với một thuật toán điều rất quan tâm đến đó
chính là độ phức tạp của nó, đánh giá càng chính xác độ phức tạp của thuật
toán sẽ giúp cho quá trình lựa chọn và sử dụng.
Trước khi có máy tính điện tử Alan Turing đã trình bày các mô hình
máy Turing vào năm 1936 dành cho các thí nghiệm tưởng tượng để tìm hiểu
giới hạn tính toán trên máy móc. Tuy không trực tiếp ảnh hưởng tới việc chế
tạo máy tính điện tử nhưng máy Turing là một công cụ đo sự hiệu quả của
thuật toán của một bài toán cụ thể.
Bỏ qua các yếu tố phần cứng của công nghệ hiện hành các bài toán được
giải trên máy tính phải có thuật toán để xử lý và theo Alan Turing, tất cả các
thuật toán đều có thể mô tả lại trên mô hình máy Turing, vậy việc đánh giá các
thuật toán trên máy Turing sẽ cho kết quả chính xác và công bằng nhất.
Độ phức tạp thuật toán được đánh giá bằng máy Turing theo hai tiêu chí
là: thời gian (số nhịp làm việc của máy Turing) và bộ nhớ (số ô nhớ cần sử
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
dụng trong quá trình máy làm việc).
2
Thời gian (số nhịp làm việc của máy Turing): là số lần dịch chuyển của
đầu đọc trên băng.
Bộ nhớ (số ô nhớ cần sử dụng trong quá trình máy làm việc): là số ô trên
bang mà máy Turing ghi các kí tự trong khi xử lý.
Vì vậy học viên chọn đề tài: “Cài đặt máy Turing và ứng dụng máy
Turing đánh giá độ phức tạp thuật toán” với mục đích nghiên cứu một công
cụ đánh giá thuật toán.
Nội dung chính của luận văn bao gồm:
Chương 1: Luận văn trình bày tổng quan về máy Turing và các vấn đền
liên quan đến thuật toán.
Chương 2: Luận văn cài đặt máy Turing trên ngôn ngữ C++ và cải tiến
một số bộ nhớ tăng hiệu quả làm việc của máy.
Chương 3: Luận văn sử dụng máy Turing để giải một số bài toán và
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
đánh giá độ phức tạp cụ thể từng bài.
1
Chƣơng 1
TỔNG QUAN MÔ HÌNH MÁY TURING
Trong chương này của luận văn học viên giới thiệu lại một số định nghĩa
về máy Turing và thuật toán. Trong đó có mô tả về máy Turing học viên đã cài
đặt, từ đó chỉ ra quan hệ giữa máy Turing và độ phức tạp của thuật toán.
1.1. Giới thiệu chung
Máy Turing là một mô hình thiết bị xử lý kí tự, tuy đơn giản, nhưng có
thể thực hiện tất cả các thuật toán máy tính. Các máy Turing được Alan
Turing trình bày năm 1936. Các máy Turing không dành cho việc trực tiếp
tạo ra các máy tính thực tế mà dành cho các thí nghiệm tưởng tượng để tìm
hiểu về giới hạn của việc tính toán trên máy móc. Việc nghiên cứu tính chất
máy Turing cho nhiều kiến thức quan trọng trong lĩnh vực khoa học máy tính
và lý thuyết độ phức tạp thuật toán. [2]
Trong luận đề Church-Turing đã khẳng định mọi hàm toán học tính được
đều có thể dùng máy Turing để tính toán do đó có phép định nghĩa về các
khái niệm về sự tính được của hàm hoặc thuật toán.
Máy Turing có nhiều dạng đồng khả năng, tức là có nhiều mô hình và
định nghĩa cho máy Turing nhưng chúng đều tương đương nhau. Về cơ bản
mô hình máy Turing gồm 3 phần chính sau:
- Một bộ điều khiển hữu hạn.
- Một băng chia thành các ô.
- Một đầu đọc-ghi, mỗi lần đọc có thể duyệt qua một ô trên băng để đọc
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
hay viết ký hiệu.[2]
2
Bộ điều khiển có số trạng thái hữu hạn trong đó có trạng thái ban đầu và
trạng thái kết thúc. Như vậy khi máy Turing bắt đầu hoạt động sẽ nhận trạng
thái đầu tiên là trạng thái ban đầu, máy chỉ dừng khi đạt trạng thái kết thúc.
Trên băng mỗi ô có thể giữ một ký hiệu hợp lệ (ký hiệu được phép ghi
trên băng) khởi đầu xem như n ô bên trái ( ) giữ chuỗi nhập (input), các ô
còn lại là các ký tự trắng (ký tự trắng là ký tự đặc biệt nhưng không thuộc
chuỗi nhập), phần còn lại của băng được coi là vô hạn.
Đầu đọc ghi có thể di chuyển sang trái, phải hoặc đứng yên tùy vào trạng
thái hiện tại và ký tự nhận được. Đầu đọc ghi có thể nhận dạng kí tự hiện
hành và viết đè một ký tự khác vào ô đó để thay ký tự cũ.
Hình 1.1. Mô hình máy Turing
1.2. Cấu trúc máy Turing
Về mặt toán học máy Turing có thể được định nghĩa như sau:
Định nghĩa máy Turing:[7]
Máy Turing là một hệ thống M , trong đó:
Q là tập hữu hạn các trạng thái.
là bộ ký hiệu nhập.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
là tập hữu hạn các kí tự được phép viết trên băng.
3
B là ký hiệu thuộc dùng chỉ khoảng trắng trên băng (Blank).
là trạng thái bắt đầu của hệ thống.
là trạng thái kết thúc của hệ thống.
Hàm chuyển hoạt động như sau: (trái, phải, không
dịch chuyển).
Hàm chuyển được định nghĩa trước và máy Turing chỉ có thể hoạt
động theo hàm chuyển này.
Trong khuôn khổ luận văn, học viên cài đặt máy Turing theo các câu
lệnh để biểu diễn thuật toán. Trong đó mỗi câu lệnh có năm thành phần dạng
(S, C, R, T, Q)
Trong đó:
S: là trạng thái hiện hành của máy Turing.
C: là ký tự tại ô mà con trỏ đang trỏ.
R: là kí tự sẽ điền thay vào vị trị của C, nếu R = _ tức là giữ nguyên kí tự C.
T: là hướng dịch chuyển của con trỏ bao gồm L: dịch trái.
R: là dịch phải.
N: là không dịch chuyển.
Q: là trạng thái máy Turing chuyển đến sau khi thực hiện dãy lệnh.
Ngoài ra chương trình mặc định các trạng thái của máy Turing theo dạng
số nguyên dương, trạng thái bắt đầu là trạng thái 1, trạng thái kết thúc là trạng
thái 0.
Ví dụ:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
1 a b R 2
4
Câu lệnh trên sẽ hoạt động như sau:
Trạng thái hiện hành của máy Turing là 1, con trỏ máy đang chỉ vào ô
chứa kí tự “a”, máy Turing sẽ điền kí tự “b” thay thế vào ô đó. Con trỏ máy
sau đó chuyển dịch sang phải 1 ô, trạng thái máy chuyển thành 2.
Để cải tiến cách soạn thảo học viên cài đặt máy Turing nhận các câu lệnh
trong đó thay thế các thành phần không thay đổi trong lệnh máy thành dấu
gạch dưới. Và có thể dùng câu lệnh gộp khi 1 trạng thái gặp nhiều kí tự khác
nhau nhưng có cùng cách xử lý như nhau.
Ví dụ:
Lệnh 1 _ _ _ _ sẽ hoạt động như sau:
Nếu máy đang ở trạng thái 1.
Ô nhớ đang được con trỏ máy trỏ vào chứa bất cứ ký tự nào;
Giữ nguyên ký tự đó;
Con trỏ không dịch chuyển;
Trạng thái sau khi thực hiện lệnh không thay đổi là trạng thái 1.
Ví dụ: câu lệnh gộp.
1 {a,b,c} _ R _ sẽ hoạt động như sau:
Trạng thái hiện hành của máy Turing là trạng thái “1”.
Đầu đọc ghi trỏ tới một trong các kí tự “a”, “b”, “c” sẽ giữ nguyên kí tự đó.
Đầu đọc ghi dịch chuyển sang phải 1 ô.
Trạng thái máy Turing giữ nguyên là trạng thái “1”.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Ví dụ: Xét tính chẵn lẻ của một số.
5
- Tư tưởng thuật toán: để xét một số là chẵn hay lẻ chỉ cần chia lấy phần dư
cho 2, nếu kết quả là 1 suy ra số đó là số lẻ, còn kết quả là 0 số đó là số chẵn.
Hoặc nếu biểu diễn số cần xét là một dãy các chữ số: X = , nếu
chữ số cuối cùng thì số cần xét X là số chẵn, nếu chữ số cuối
cùng thì số cần xét X là số lẻ.
Mã chương trình máy Turing:
1 _ _ R _ // dịch phải chuỗi số.
1 # _ L 2
2 {0,2,4,6,8} 0 L 3 // kí tự “0” biểu thị số chẵn.
2 {1,3,5,7,9} 1 L 3 // kí tự “1” biểu thị số lẻ.
3 {0,1,2,3,4,5,6,7,8,9} # L 3 // loại các số không ở trong kết quả.
3 # _ _ 0 // trạng thái 0 là trạng thái kết thúc.
Kết quả của chương trình:
Mô phỏng với số đầu vào là 33.
Input: #33# (2)
Command: 1 _ _ R _ #33# (2)
Command: 1 _ _ R _ #33# (2)
Command: 1 # _ L 2 #33# (2)
Command: 2 3 1 L 3 #31# (2)
Command: 3 3 # R 3 #1# (2)
Command: 3 # _ N 0 #1# (2)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Final output: #1# (1)
6
Timer = 6
Chương trình trải qua 6 bước để đưa ra kết luận số 33 là số lẻ (tương ứng
với kết quả là “1”).
Vậy với thuật toán trên máy Turing trải qua 6 bước chuyển, số ô sử dụng
là 2.
So sánh cách soạn thảo viết rõ từng lệnh máy với cách sử dụng những
kí hiệu mà học viên cài đặt:
Bảng 1.1. So sánh câu lệnh giữa cách viết thông thƣờng
và cách viết gộp
Cách viết thông thường Cách viết gộp
2 {0,2,4,6,8} 0 L 3 2 0 0 L 3
2 2 0 L 3
2 4 0 L 3
2 6 0 L 3
2 8 0 L 3
Hai cách viết trên đều hoạt động giống nhau đó là khi máy Turing ở
trạng thái 2 gặp các kí tự “0”, “2”, “4”, “6”, “8” chuyển thành kí tự “0”, dịch
con trỏ sang trái một ô, chuyển trạng thái máy Turing thành trạng thái “3”.
Nhưng với cách viết thông thường học viên sẽ phải viết 5 dòng lệnh, trong đó
với cách viết lệnh gộp học viên chỉ cần 1 lệnh duy nhất để thực hiện.
1.3. Hoạt động của máy Turing
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Máy Turing hoạt động theo cơ chế như sau:[5]
7
- Đầu đọc ghi đọc một kí tự trên ô của băng, phụ thuộc vào trạng thái
bên trong mà đầu đọc ghi ghi một kí tự hợp lệ vào ô đó (kí tự thuộc tập ).
- Đầu đọc ghi dịch chuyển sang trái, sang phải hoặc đứng yên tại chỗ.
- Trạng thái bên trong được thay đổi tùy vào kí tự được đọc và trạng thái
hiện hành.
- Máy Turing bắt đầu từ trạng thái ban đầu và dừng khi đạt trạng thái
kết thúc.
Máy Turing được mô tả trong luận văn của học viên hoạt động theo
đúng cơ chế trên, cụ thể trong chương trình học viên quy ước trạng thái bắt
đầu của máy Turing là trạng thái “1”, trạng thái kết thúc là trạng thái “0”. Vậy
một chương trình viết bởi các câu lệnh để mô tả thuật toán sẽ dừng lại khi gặp
câu lệnh dạng (S C R T 0). Các thành phần của câu lệnh đã được học viên
trình bày ở phần 1.2.
1.4. Trạng thái và sơ đồ trạng thái của máy Turing[2]
Một hình thái của máy Turing M được cho bởi α1 q α2, trong đó q là
trạng thái hiện hành của M; α1α2 ∈ Γ* là nội dung của băng tính từ đầu băng
cho tới ký hiệu khác Blank bên phải nhất của băng. Giả sử Q và Γ rời nhau:
đầu đọc đang đọc ký hiệu bên trái nhất của α2 hoặc nếu α2 = ε thì đầu đọc
đọc Blank.
Hàm chuyển
Ta định nghĩa một phép chuyển trạng thái của TM như sau:
Đặt X1X2... Xi-1q Xi... Xn là một hình thái của máy Turing.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
+ Giả sử δ (q, Xi) = (p, Y, L), trong đó:
8
- Nếu i - 1 = n thì Xi là B.
- Nếu i =1 thì không có ID kế tiếp, nghĩa là đầu đọc không được phép
vượt qua cận trái của băng.
- Nếu i > 1 ta viết:
X1X2... Xi-1q Xi... Xn ⊢M X1X2... Xi-2p Xi-1Y Xi+1... Xn
+ Tương tự δ(q, Xi) = (p, Y, R) thì ta viết:
X1X2... Xi-1q Xi... Xn ⊢M X1X2... Xi-1Yp Xi+1... Xn
+ Tương tự δ(q, Xi) = (p, Y, ∅) thì ta viết:
X1X2... Xi-1q Xi... Xn ⊢M X1X2... Xi-1pY Xi+1... Xn
Chú ý rằng nếu i - 1 = n thì chuỗi Xi... Xn là rỗng và vế phải dài hơn vế
trái, nghĩa là TM M mở rộng chuỗi ký hiệu trên băng.
Nếu hai hình thái máy được quan hệ nhau bởi ⊢M thì ta nói hình thái thứ
hai là kết quả của hình thái thứ nhất bằng một lần chuyển, một bước áp dụng
hàm chuyển (hoặc nói hình thái thứ hai thu được từ hình thái thứ nhất bằng
một lần chuyển). Nếu một hình thái thu được từ hình thái khác bằng một số
lần chuyển (có thể bằng 0) thì ta ký hiệu quan hệ là ⊢M*. Ta cũng có thể bỏ đi
ký hiệu M trong cách viết các quan hệ trên nếu không có nhầm lẫn.
Ngôn ngữ được chấp nhận bởi TM.
Ký hiệu L(M): tập hợp các chuỗi trong Γ* là nguyên nhân đưa TM M đi
vào trạng thái kết thúc khi đã thực hiện việc thay thế từ bên trái các ký hiệu
trên băng của M với trạng thái bắt đầu q0. Một cách hình thức, ta định nghĩa
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
tập hợp ngôn ngữ được chấp nhận bởi TM M (Q, ∑, Γ, δ, q0, B, F) là tập:
9
L(M) = { w | w ∈ Γ* và q0 w ⊢M* α1 p α2 với p ∈ F còn α1α2 ∈ Γ*}
Cho TM nhận diện một ngôn ngữ L là cho lần lượt các từ của L vào TM
xem TM có chấp nhận từ đó không. TM sẽ dừng và đi vào một trong những
trạng thái kết thúc ∈ F (không có phép chuyển kế tiếp) khi từ được chấp
nhận, nhưng nếu TM không chấp nhận một từ nào đó thì TM có thể ngừng ở
một trạng thái ∉ F hoặc cũng có thể nó chạy mãi mà không dừng lại.
Ví dụ: Thiết kế TM chấp nhận ngôn ngữ L = { 0n1n | n ≥ 1}.
Cách 1: Thiết kế bằng định nghĩa của máy Turing:
- Tư tưởng thuật toán:
+ Khởi đầu TM chứa 0n1n bên trái nhất trên băng sau đó là vô hạn
khoảng trống Blank. TM lặp lại quá trình sau:
+ M thay 0 bên trái nhất bằng X rồi chuyển sang phải tới 1 trái nhất, TM
thay 1 này bằng Y rồi dịch chuyển về bên trái cho tới khi gặp X phải nhất nó
chuyển sang phải một ô (tới 0 trái nhất) rồi tiếp tục lặp một chu trình mới.
+ Nếu trong khi dịch chuyển sang phải để tìm 1 mà TM gặp Blank thì
TM dừng và không chấp nhận input. Tương tự, khi TM đã thay hết 0 bằng X
và kiểm tra còn 1 trên băng thì TM cũng dừng và không chấp nhận input.
+ TM chấp nhận input nếu như cũng không còn ký hiệu 1 nào nữa trên băng.
- Định nghĩa máy Turing:
Đặt TM M (Q, ∑, Γ, δ, q0, B, F) với các thành phần:
Q = {q0, q1, q2, q3, q4}; ∑= {0, 1}; Γ = {0, 1, X, Y, B} và F = {q4}.
Ta có thể hình dung mỗi trạng thái là một câu lệnh hoặc một nhóm các
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
câu lệnh trong chương trình. Trạng thái q0 là trạng thái khởi đầu và nó làm
10
cho ký hiệu 0 bên trái nhất thay bằng X. Trạng thái q1 được dùng để tiến sang
phải bỏ qua các số 0 và Y để tìm 1 bên trái nhất. Nếu M tìm thấy 1 nó thay 1
bằng Y rồi đi vào trạng thái q2. Trạng thái q2 đưa M tiến sang trái cho tới X
đầu tiên và đi vào trạng thái q0, dịch chuyển sang phải để tới 0 bên trái nhất và
tiếp tục một chu trình mới. Khi M tiến sang phải trong trạng thái q1, nếu B
hoặc X được tìm thấy trước 1 thì input bị loại bỏ (không chấp nhận) vì có
chứa nhiều ký hiệu 0 hơn 1 hoặc input không có dạng 0*1*.
Trạng thái q0 còn có vai trò khác. Nếu trạng thái q2 tìm thấy X bên phải
nhất và ngay sau đó là Y thì các số 0 đã được xét hết, do đó ở trạng thái bắt
đầu một chu trình mới q0 không tìm thấy ký hiệu 0 nào để thay thành X mà
chỉ gặp Y thì TM đi vào trạng thái q3 duyệt qua các Y để kiểm tra có hay
không có ký hiệu 1 còn lại. Nếu theo ngay sau các Y là B, nghĩa là trên băng
nhập không còn ký hiệu 1 nào nữa thì TM sẽ đi vào q4 (trạng thái kết thúc) để
chấp nhận input. Ngược lại input bị loại bỏ.
Hàm chuyển δ được cho trong bảng sau:
Bảng 1.2. Trạng thái máy Turing
đoán nhận ngôn ngữ L = {0n1n | n ≥ 1}
Kí hiệu
Trạng thái
0
X
1
Y
B
-
-
-
-
-
-
-
-
-
-
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
-
-
-
-
-
11
Ví dụ:
+ Các phép chuyển hình thái của TM M trên input 0011:
q00011 ⊢ Xq1011 ⊢ X0q111 ⊢ X q20Y1 ⊢ q2X0Y1 ⊢ X q00Y1 ⊢ XXq1Y1 ⊢ XXY
q11 ⊢ XX q2YY ⊢ X q2XYY ⊢ XX q0YY ⊢ XXYq3Y ⊢ XXYYq3 ⊢ XXYYq4
Với chuỗi input 0011 máy Turing đạt được trạng thái q4 thuộc tập trạng
thái dừng, nên máy Turing trên đoán nhận được xâu 0011.
+ Các phép chuyển hình thái của TM M trên input 0001
q00001 ⊢ Xq1001 ⊢ X0q101 ⊢ X 00q1 1 ⊢ X0q20Y ⊢ X q200Y ⊢ q2X00Y ⊢
Xq000Y ⊢ XX q10Y ⊢ X q2XYY ⊢ XX 0q1Y ⊢ XX0Yq1
Với chuỗi input 0001 TM M không đạt được trạng thái kết thúc nên
không đoán nhận được xâu 0001 hay xâu input 0001 không thuộc ngôn ngữ L
= { 0n1n | n ≥ 1}.
Cách 2: Thiết kế bằng lệnh máy Turing do học viên cài đặt:
- Tư tưởng thuật toán:
Về cơ bản thuật toán giống với cách 1. Học viên thêm vào kết thúc của các
xâu input kết luận máy TM M có đoán nhận được xâu hay không ở output.
- Mã lệnh chương trình:
1 0 X R 2
1 Y _ R 4
1 {1,X,#} _ N 7 // không đoán nhận được xâu
2 {0,Y} _ R 2 // dịch phải để tìm 1
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
2 1 Y L 3
12
2 {X, #} _ N 7
3 {0, Y} _ L 3 //dịch trái để tìm X
3 X _ R 1
3 {1,#} _ N 7
4 Y _ R 4 // dịch phải tìm #
4 # _ N 5 // đoán nhận được xâu
4 {0,1,X} _ N 7
5 # = R 6
6 # D N 0 // đạt trạng thái dừng đoán nhận được
7 {0, 1, X, Y} _ R 7 // dịch phải tìm #
7 # = R 8
8 # K N 0 // đạt trạng thái dừng không đoán nhận được
- Trong đoạn mã lệnh trên ta có:
+ Tập các kí tự được sử dụng = {0,1,X,Y,D,K}
+ Kí tự trắng: #
+ Tập các trạng thái = {0,1,2,3,4,5,6,7,8}
+ Trạng thái bắt đầu: 1
+ Trạng thái kết thúc: 0
- Ví dụ minh họa:
+ Chương trình chạy với input 0011
Input: #0011# (4)
Command: 1 0 X R 2 #X011# (4)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Command: 2 0 _ R _ # X011# (4)
13
Command: 2 1 Y L 3 # X0Y1# (4)
Command: 3 0 _ L 3 # X0Y1# (4)
Command: 3 X _ R 1 # X0Y1# (4)
Command: 1 0 X R 2 # XXY1# (4)
Command: 2 Y _ R 2 # XXY1# (4)
Command: 2 1 Y L 3 # XXYY# (4)
Command: 3 Y _ L 3 # XXYY# (4)
Command: 3 X _ R 1 # XXYY # (4)
Command: 1 Y _ R 4 # XXYY # (4)
Command: 4 Y _ R 4 # XXYY # (4)
Command: 4 # _ N 5 # XXYY # (4)
Command: 5 # = R 6 # XXYY = # (5)
Command: 6 # D N 0 # XXYY = D# (6)
Final output: #XXYY=D# (6)
Timer = 15
Vậy với input 0011 được máy Turing đoán nhận.
Thời gian hoàn thành là 15 bước chuyển.
Không gian bộ nhớ tối đa là 6 ô.
+ Chương trình chạy với input 010
Input: #010# (3)
Command: 1 0 X R 2 #X10# (3)
Command: 2 1 Y L 3 #XY0# (3)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Command: 3 X _ R 1 #XY0# (3)
14
Command: 1 Y _ R 4 #XY0# (3)
Command: 4 0 _ N 7 #XY0# (3)
Command: 7 0 _ R 7 #XY0# (3)
Command: 7 # = R 8 #XY0=# (4)
Command: 8 # K N 0 #XY0=K# (5)
Final output: #XY0=K# (5)
Timer = 8
Vậy máy TM M không đoán nhận được input 010.
Bộ nhớ tối đa cần dung là 5 ô.
Chương trình thực hiện sau 8 bước chuyển máy.
1.5. Máy Turing và định nghĩa thuật toán
1.5.1. Độ phức tạp thuật toán
a) Định nghĩa thuật toán[1]
Ta có thể định nghĩa (không chính thức) về thuật toán như sau:
Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các
phép toán, hoặc hành động cần thực hiện… để chuyển input thành output.
b) Các đặc trưng của thuật toán
- Đầu vào (Input).
Đầu vào của thuật toán chính là các giá trị cần đưa vào khi thuật toán bắt
đầu làm việc. Các giá trị này cần được lấy từ các tập hợp giá trị cụ thể nào đó.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
- Đầu ra (Output).
15
Mỗi thuật toán có một hoặc nhiều dữ liệu ra. Đó là các dữ liệu có quan
hệ hoàn toàn xác định với các dữ liệu vào, và là kết quả của sự thực hiện
thuật toán.
- Tính xác định.
Ở mỗi bước, các thao tác phải rõ ràng, không gây nên sự nhập nhằng.
Nói rõ hơn là trong cùng một điều kiện, hai bộ xử lí cùng thực hiện một thuật
toán phải cho cùng một kết quả như nhau.
- Tính khả thi.
Tất cả các phép toán có mặt trong thuật toán phải đủ đơn giản. Điều đó
có nghĩa là, các phép toán có thể được thực hiện trực tiếp (bằng giấy và bút).
- Tính dừng.
Với mọi bộ dữ liệu đầu vào (lấy từ các tập của dữ liệu vào), thuật toán
phải dừng sau một số hữu hạn bước thực hiên.
- Tính đơn trị (uniqueness).
Các giá trị trung gian của thuật toán trong từng bước và kết quả thực
hiện thuật toán được xác định một cách đơn trị và chỉ phụ thuộc vào đầu vào
và kết quả của các bước trước.
- Tính tổng quát (generality)-tính phổ dụng
Với mọi tập đầu vào thuộc dạng của bài toán thuật toán đều có thể giải
được. Tức là thuật toán phải dùng để giải được một lớp các bài toán cùng loại.
Xác định độ phức tạp về thời gian
* Quy tắc tổng: Giả sử T1(n) và T2(n) là thời gian thực hiện hai đoạn
chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì thời gian thực
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
hiện P1 và P2 kế tiếp nhau sẽ là:
16
T1(n) + T2(n) = O(max(f(n),g(n)))
Ví dụ: Trong một chương trình có 3 bước thực hiện mà thời gian thực
hiện từng bước lần lượt là O(n2), O(n3) và O(nlog2n) thì thời gian thực hiện 2 bước đầu là O(max(n2, n3)) = O(n3). Thời gian thực hiện chương trình sẽ là
O(max(n3, nlog2n)) = O(n3).
Một ứng dụng khác của quy tắc này là nếu g(n) ≤ f(n) với mọi n n0
thì O(f(n) + g(n)) cũng là O(f(n)). Chẳng hạn: O(n4 + n2) = O(n4) và
O(n+log2n) = O(n).
lồng nhau sẽ là:
* Quy tắc nhân: Nếu tương ứng với P1 và P2 là T1(n) = O(f(n)), T2(n) =
O(g(n)) thì thời gian thực hiện P1 và P2
T1(n)T2(n) = O(f(n)g(n))
Ví dụ: Câu lệnh gán: x:=x+1 có thời gian thực hiện bằng c (hằng số) nên
được đánh giá là O(1).
Câu lệnh for i:=1 to n do x:=x+1;
Có thời gian thực hiện O(n.1) = O(n)
Câu lệnh: for i:=1 to n do
for j:=1 to n do x:=x+1;
Có thời gian được đánh giá là O(n.n) = O(n2)
Cũng có thể thấy O(cf(n)) = O(f(n)). Ví dụ O(n2/2) = O(n2)
Các vấn đề liên quan đến thuật toán.
Thiết kế thuật toán.
Có một số kỹ thuật thiết kế thuật toán chung như:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
- Chia để trị (divide and conque).
17
- Phương pháp tham lam (greedy method).
- Phương pháp quy hoạch động (dynamic programing).
Nắm được các kỹ thuật thiết kế thuật toán là rất quan trọng giúp tìm ra
các thuật toán mới cho các bài toán mới.
Lớp P, NP và mối quan hệ giữa lớp P và lớp NP.[3],[7],[8]
- Lớp P.
* Định nghĩa:
Lớp P là lớp những bài toán giải quyết được bằng máy tính Turing tất
định trong thời gian đa thức.
* Ví dụ: Thuật toán Ơclide tìm UCLN của hai số là thuật toán giải được
trong thời gian đa thức. Do đó bài toán tìm UCLN của hai số m và n thuộc lớp P.
- Lớp NP.
* Định nghĩa:
Lớp NP là lớp các bài toán có thể giải được bằng máy Turing không tất
định trong khoảng thời gian đa thức.
* Ví dụ: Bài toán chu trình Hamilton.
- Instance: Cho đồ thị vô hướng G = (V,E).
- Question: Hỏi đồ thị vô hướng G = (V,E) có chu trình Hamilton hay không?
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
- Mối quan hệ giữa lớp P và lớp NP.
NP
P
18
Hình 1.2. Mối quan hệ giữa lớp P và NP
Bài toán lớp NPC.
Phép dẫn với thời gian đa thức.
* Định nghĩa:
Cho n 1 và 2 là hai bài toán quyết định.
y là lớp các Instance ứng với YES.
y là lớp các Instance ứng với NO.
Một cách biến đổi f biến mỗi Instance của 1 thành Instance của 2
được gọi là phép dẫn thời gian đa thức nếu điều đó thoả mãn:
- Phép dẫn f thực hiện được trong thời gian đa thức bởi máy tính Turing.
- Mỗi dữ kiện thuộc 1(y) thành dữ kiện thuộc 2(y).
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
- Mỗi dữ kiện thuộc 1(n) thành dữ kiện thuộc 2(n).
thuật toán 1
f(x)
dữ kiện 1
f
thuật toán 2
Yes/NO
dữ kiện 2
19
Hình 1.3. Minh hoạ một phép dẫn bài toán 1 thành 2
trong thời gian đa thức
Bài toán lớp NPC.[9]
* Định nghĩa: Một bài toán thuộc lớp NP mà mọi bài toán thuộc lớp NP
khác đều dẫn được về nó với thời gian đa thức được gọi là bài toán NPC.
* Tính chất: một bài toán là NPC nếu thoả mãn:
1. NP
2. Với ’ NP thì ’ dẫn được về với thời gian đa thức
Như vậy để chứng minh một bài toán là NPC ta cần chứng minh hai điều:
1. Bài toán đó phải thuộc lớp NP.
2. Mọi bài toán thuộc lớp NP đều dẫn được về bài toán đó với thời gian
đa thức.
Mối quan hệ giữa các bài toán lớp P, NP và NPC.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Mối quan hệ giữa P, NP và NPC được biểu diễn như hình sau:
NP
NPC
P
20
Hình 1.4. Mối quan hệ giữa lớp P, NP và NPC
1.5.2. Ứng dụng máy Turing để đo độ phức tạp thuật toán
Với phần sơ lược về thuật toán ở trên ta có thể thấy với một thuật toán
tính ưu việt được thể hiện ở hai thông số đó là thời gian xử lí (số bước hay
còn gọi là số xung làm việc của máy tính) và không gian bộ nhớ (là số ô nhớ
phải sử dụng trong quá trình đưa input thành output).
Khi Alan Turing phát biểu máy Turing thì ông đã chứng minh được mọi
thuật toán đều có thể mô tả được bằng máy Turing, chính vì thế việc dùng
máy Turing làm thước đo độ phức tạp của thuật toán là điều có thể làm được.
Hiện nay trên thế giới có nhiều cách để đánh giá độ phức tạp của thuật
toán nhưng xét cho cùng thì chưa có thước đo chuẩn nào.
Máy Turing, là một máy ảo, hoàn toàn có thể trở thành một thước đo
chính xác vì máy không phụ thuộc vào cấu hình phần cứng, máy chỉ dựa vào
số bước chuyển đầu đọc và số lượng ô nhớ cần dùng.
Mặt khác vì mọi câu lệnh đều có thể chuyển về hàm chuyển của máy
Turing nên hoàn toàn có thể đánh giá chính xác cách làm việc của một
thuật toán.
Hơn nữa phát hiện của Turing rằng "phần mềm luôn có thể thay cho
phần cứng" là then chốt của "ảo hóa" - công nghệ nền tảng của làn sóng hợp
nhất đang định hình lại hệ thống IT của các công ty lớn. Khi chi phí cho năng
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
lực tính toán và dung lượng lưu trữ tiếp tục đà rơi tự do từ chục năm nay, thì
21
ngày càng có thể biến càng nhiều phần cứng thành chương trình phần mềm -
dùng một máy tính thật mạnh để chạy nhiều máy ảo.
Tất cả thiết bị phần cứng gắn vào các trung tâm dữ liệu doanh nghiệp -
không chỉ server mà còn cả các ổ đĩa lưu trữ, thiết bị cân bằng tải, tường lửa,
chuyển mạch và thậm chí cả cáp nối - thực chất là để thực hiện các lệnh. Ảo
hóa đơn giản là biến các lệnh phần cứng thành mã lệnh chương trình (phần
mềm) và loại bỏ cỗ máy vật lý. Điều này không chỉ tiết kiệm hàng đống tiền
mà còn giúp hiện thực việc tự động hóa những qui trình CNTT thủ công trước
đây. Một khi hạ tầng CNTT biến thành phần mềm, nó có thể được lập trình,
dễ dàng và từ xa. Như thường lệ, chương trình phần mềm thay thế nhân công.
1.6. Kết luận
Trong chương này học viên đã trình bày những khái niệm cơ bản về máy
Turing và thuật toán nhằm phát triển máy Turing thành công cụ đo độ phức
tạp thuật toán. Cụ thể như sau:
- Trình bày các khái niệm như định nghĩa máy Turing, sơ đồ trạng thái,
hoạt động của máy Turing.
- Trình bày các khái niệm như thuật toán, các tính chất của thuật toán và
các vấn đề liên quan đến thuật toán.
- Khái quát một số bài toán dạng P, NP, NPC.
- Nêu mối liên hệ giữa thuật toán và máy Turing. Từ đó đề cập đến vấn
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
đề “ảo hóa” các thiết bị phần cứng.
22
Chƣơng 2
CÀI ĐẶT MÁY TURING NGUYÊN THỦY
VÀ MỘT SỐ CẢI TIẾN
Trong chương này học viên xin trình bày chương trình cài đặt máy Turing
nguyên thủy hay còn gọi là máy Turing đơn định một băng. Để cải tiến tốc độc
xử lí của máy học viên đề xuất một số giải pháp cải tiến bộ nhớ máy.[5]
2.1. Cài đặt Máy Turing
Để mô phỏng máy Turing học viên đã sử dụng ngôn ngữ lập trình C++.
Sau đây học viên xin giới thiệu các thành phần chính của chương trình.
main(){
cout << " T H E T U R I N G M A C H I N E ";
Run();
cout << "\n T H E E N D.";
cin.get();
return 0;
}
- Hàm chính để khởi động máy Turing:
- Hàm Run () được sử dụng để điều khiển chọn tệp chứa lệnh máy đưa
void Run(){
char fn[100];
cout << "\n File [Bam ENTER de nhan file mac dinh
Prog.tr]: ";
gets(fn);
if (CorrectTest(fn,0) == '\0') strcpy(fn,fname);
Test(fn);
}
vào máy Turing. Hàm này nhận lệnh từ bàn phím để nạp dữ liệu vào máy.
Sau khi hàm Run () được gọi trong chương trình, chương trình dừng lại
để người dùng nhập đường dẫn đến tệp chứa lệnh máy hoặc dùng tệp mặc
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
định Prog.tr.
23
Các hàm thành phần:
Hàm Test (): được dùng để kiểm tra sự đúng đắn của chương trình.
Ngoài ra hàm Test () còn điều khiển một số tác năng khác của máy Turing
như: hiển thị các bước trung gian của thuật giải, tín hiệu nhập dữ liệu từ bàn
phím, mở Help để xem chỉ dẫn. Một số chỉ dẫn điển khiển chương trình như:
+ Dấu chấm “.” để dừng chương trình đang chạy (ngắt chương trình bắt buộc).
void Test(const char * fn){
YY;
if (!ReadProg(fn)) {
Err(4);
return;
}
WW;
while(1){
cout << "\n Input [Bam (.) de dung, (?) de nap
test]: \n ";
GetComm(u); CorrectTest(u,0);
switch(toupper(u[0])){
case 'H': Help(); break;
case '.': return; break;
case 'L': YY; ReadProg(fn); WW; break;
case '$': show = !show; break;
case '?': CorrectTest(u,1); Exe(u);
} // switch
// else Exe(u); // Go();
}
}
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
+ Dấu hỏi chấm “?” đặt trước input để chạy chương trình máy Turing…
24
Hàm GetComm () có tác dụng lấy từng câu lệnh trong tệp mã lệnh (tệp
mặc định là tệp Prog.tr) sau đó hàm CorrectTest () kiểm tra tính đúng của
void GetComm(char * s, const char * msg = ""){
int i = 0;
cout << msg;
while(cin.good()){
s[i] = cin.get();
if (s[i] == NL) break; // NL = 10 = '\n'
++i;
}
s[i] = '\0';
}
char CorrectTest(char * s, int d = 0){
// cout << "\n|" << s << "| -> |";
int i, j, n = strlen(s);
// Bo cac dau cach dau s
for (i = d; i < n ; ++i){
if (s[i] != SPACE) break;
}
// Bo cac dau cach cuoi s
for (j = n-1; j >= i; --j)
if (s[j] != SPACE) break;
if (i > j) {
s[0] = EOL; return EOL;
}
for (n = 0 ; i <= j; ++i)
if (s[i] != TAB) s[n++] = s[i];
s[n] = EOL;
// cout << "\n |" << s << "|"; Go();
return s[0];
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
từng câu lệnh:
}
25
Một số hàm khác để chuẩn hóa câu lệnh:
+ Hàm Correct () loại bỏ các phần chú thích trong đoạn mã lệnh máy
char Correct(char * s, int d = 0){
// cout << "\n|" << s << "| -> |";
int i, j, n = strlen(s);
char * p;
// Bo cac dau cach dau s
for (i = d; i < n ; ++i){
if (s[i] == SLASH && s[i+1] == SLASH) {
s[0] = EOL; return s[0];
}
if (GOODCHAR(s[i])) break;
}
p = lstrstr(s,"//");
j = (p != NULL) ? j = p-s-1 : n-1;
// Bo cac dau cach cuoi s
for (; j >= i; --j)
if (GOODCHAR(s[i])) break;
if (i > j) {
s[0] = EOL; return EOL;
}
for (n = 0 ; i <= j; ++i)
s[n++] = (s[i] == TAB) ? SPACE : s[i];
s[n] = EOL;
// cout << "\n |" << s << "|"; Go();
return s[0];
}
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Turing.
26
+ Hàm ReadLine () đọc từng dòng trong tệp chứa lệnh Prog.tr hoặc tệp
char ReadLine(char * s){
memset(s,0,sizeof(s));
if (f.eof()) {
strcpy(s,"F");
// cout << "\n EXIT with " << s;
} else f.getline(s,100,'\n');
return Correct(s);
}
mã lệnh do người dùng tạo ra.
+ Hàm GetNum () có tác dụng chuyển định dạng từ dạng kí tự thành
int GetNum(char * s, int & i){
int v = 0;
for (; !Num(s[i]); ++i);
for (; Num(s[i]); ++i) v = v*10+Toint(s[i]);
--i;
return v;
}
dạng số.
inline void Space(char * s, int & i){
while(s[i] == SPACE) ++i;
}
+ Hàm GetChar () có tác dụng lấy các lí tự có nghĩa.
inline char GetChar(char * s, int & i){
Space(s,i);
return s[i];
}
// Nhan cac chu cai trong day {...}
inline void XuLiSet(const char *s, int i, int state,
Com & cm){
for (i++; s[i] != '}' ; ++i)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
+ Hàm Space () dùng để bỏ qua các dấu cách trống vô nghĩa.
if (GOODCHAR(s[i]) && s[i] != ',')
p[state][s[i]] = cm;
}
27
Các hàm trên sau khi hoạt động sẽ loại bỏ các các thành phần không cần
thiết như các dấu cách, phần chú thích trong mã lệnh ở tệp Prog.tr hoặc tệp
người dùng chỉ định để đơn giản hóa các câu lệnh khi chạy trên máy Turing.
2.1.1. Giao diện chương trình
- Chương trình máy Turing bắt đầu hoạt động sẽ được hiển thị như sau:
Hình 2.1. Giao diện máy Turing
Khi máy Turing bắt đầu hoạt động sẽ đưa ra gợi ý về các điều khiển của
chương trình.
- Chọn tệp chứa mã lệnh:
Có hai cách đẻ chọn tệp chứa mã lệnh là chọn tệp mắc đinh là tệp Prog.tr
hoặc tệp do người dùng tạo ra.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
+ Chọn tệp mặc định bằng cách nhấn phím enter:
28
Hình 2.2. Chọn tệp mặc định
Sau đó máy Turing sẽ tự động nạp các câu lệnh trong tệp Prog.tr và hiển
thị lên màn hình.
+ Cách hai chọn tệp do người dùng tự tạo bằng cách sử dụng phím điều
khiển “N” sau đó nhập địa chỉ tệp đó:
Hình 2.3. Chọn chƣơng trình do ngƣời dùng tạo
Như hình trên học viên đã chọn tệp “thu nghiem.txt” sau đó chương trình
từ tệp đã được nạp vào máy Turing để xử lý.
- Nhập dữ liệu từ bàn phím:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Để nhập dữ liệu từ bàn phím ta dùng dấu “?” đặt trước chuỗi input.
29
Hình 2.4. Nhập dữ liệu từ bàn phím
Sau khi nhập dữ liệu bằng dấu “?” khi người dùng nhấn phím enter
chương trình bắt đầu làm việc với bộ dữ liệu vừa nhập. Khi máy Turing xử lí
xong chuỗi input kết quả được hiển thị. Ví dụ với một chương trình như sau:
Hình 2.5. Hiển thị kết quả
Với ví dụ ở trên máy Turing đưa ra kết quả và dung lượng bộ nhớ, số
bước chuyển của đầu đọc, vậy tương đương với việc đưa ra độ phức tạp của
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
thuật toán với chuỗi input “111000”.
30
Ngoài ra học viên còn thiết kế một cách hiển thị kết quả khác là liệt kê tất
cả các bước trung gian hay nói cách khác là môt tả hoạt động của máy Turing
qua từng bước chuyển (mỗi bước chuyển tương ứng với một lệnh máy).
Hình 2.6. Hiển thị kết quả trung gian của chƣơng trình
Với cách hiển thị kết quả này người dùng có thể kiểm tra quá trình hoạt
động của máy Turing qua từng bước chuyển của đầu đọc và tại mỗi thời điểm
có thể chỉ ra vị trí của con trỏ máy, chuỗi kí tự trên băng.
Để chuyển cách hiển thị người dùng sử dụng kí tự điều khiển “$” nhưng
học viên cũng khuyến cáo tùy từng bài toán mà sử dụng chức năng này. Vì
khi gặp những bài toán mà máy Turing phải sử dụng nhiều bước chuyển làm
cho việc quan sát của người dùng trở nên khó khăn.
2.1.2. Cấu trúc dữ liệu đầu vào
Một số quy ước hằng số trong chương trình:
- Trong khuôn khổ luận văn học viên định nghĩa chiều dài của băng là
50000 ô nhớ, nhưng trên thực tế thì độ dài của băng chỉ phụ thuộc vào dung
lượng bộ nhớ RAM của máy tính. Vậy độ dài này có thể thay đổi được. Ngoài
ra số bước chuyển tối đa mà học viên thiết kế cho một thuật toán là 50000 bước
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
(số bước chuyển này cũng có thể thay đổi tùy vào cấu hình của máy tính).
const int MN = 50000;
const int MAXTIME = MN;
31
- Sau đây là một số kí hiệu đặc biệt dùng trong chương trình:
const char SPACE = ' '; // Dau cach
Dấu cách trống:
const char EOL = '\0'; // Het dong lenh
Kí hiệu kết thúc dòng lệnh:
const char UDL = '_'; // Undeline
Dấu gạch dưới “_”
const char BL = '#'; // Dau cach tren bang Turing
Khoảng cách trống trên băng:
const char NL = '\n'; // New line
const char TAB = '\t';
const char RT = '\r'; // RETURN
const char SLASH = '/'; // chu thich
#define Lochar(c) (((c) >= 'a') && ((c) <= 'z'))
#define Upchar(c) (((c) >= 'A') && ((c) <= 'Z'))
#define Alpha(c) (Lochar(c) || Upchar(c))
#define Num(c) (((c) >= '0') && ((c) <= '9'))
#define GOODCHAR(c) ((c) != SPACE && (c)!= TAB &&
(c) != SLASH)
#define Toint(c) (c)-'0'
const char INSET = '{';
const char OUSET = '}';
Một số kí hiệu khác:
Các kí hiệu quy định hướng dịch chuyển của đầu đọc:
+ “L” dịch đầu đọc sang trái một ô.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
+ “R” dịch đầu đọc sang phải một ô.
32
const char TL = 'L'; // LEFT: Dich dau doc viet
qua trai
const char TR = 'R'; // RIGH: Dich dau doc viet
qua phai
const char TN = 'N'; // NO MOVED: Khong dich dau
doc viet
+ “N” đầu đọc không dịch chuyển.
Một số quy ước của chương trình:
Để dễ dàng trong việc soạn thảo các chương trình học viên quy ước như sau:
+ Trạng thái bắt đầu của máy Turing là trạng thái “1”.
const int SSTART = 1; // Trang thai xuat phat
const int SEND = 0; // Trang thai ket thuc
+ Trạng thái kết thúc của máy là trạng thái “0”.
Các kí hiệu dùng trong tệp chứa mã lệnh máy:
+ Khi máy Turing đọc chương trình từ tệp mã lệnh (tệp mặc định là tệp
Prog.tr) gặp kí tự “S” máy sẽ bỏ qua các dòng lệnh sau đó.
+ Máy Turing gặp kí tự “B” sẽ bắt đầu nạp từ dòng lệnh tiếp theo trở đi.
+ Kí hiệu “E” đánh dấu điểm kết thúc của chương trình được viết bằng
mã lệnh.
const char SKIPLINE = 'S';
const char BEGINLINE = 'B';
const char ENDLINE = 'E';
const char ENDFILE = 'F';
+ Kí hiệu “F” đánh dấu điểm kết thúc của tệp.
const char * fname = "Prog.tr"; // ten file mac dinh
Quy ước về màu sắc:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Quy ước tệp mặc định khi chạy chương trình:
#define YY SetColor((DARKBLUE<<4)|YELLOW) // =
158 = 1001|1110
#define WW SetColor((DARKBLUE<<4)|WHITE) // = 159
= 1001|1111
#define GG SetColor((DARKBLUE<<4)|GRAY) // = 159
= 1001|1111
enum Color { DARKBLUE = 1, DARKGREEN, DARKTEAL,
DARKRED,
DARKPINK, DARKYELLOW, GRAY, DARKGRAY,
BLUE, GREEN, TEAL, RED, PINK,
YELLOW, WHITE };
33
Các kí tự điều khiển khi chương trình đang thực hiện:
Kí tự “$” bật tắt hiển thị quá trình xử lí trung gian.
Kí tự “N” chọn tệp mã lệnh do người dùng tạo.
Kí tự “L” hiển thị danh sách chương trình có sẵn.
Kí tự “H” mở Help (phần hướng dẫn của chương trình - trợ giúp
người dùng).
const char SHOW = '$'; // Yeu cau hien thi
Kí tự “.” dừng chương trình đang chạy.
Mỗi lệnh gồm 5 thành phần (S, C, R, T, Q) trong đó S là trạng thái hiện
tại, C là kí tự con trỏ máy đang trỏ vào, R là kí tự viết đè, T là hướng dịch
chuyển của con trỏ, Q là trạng thái tiếp theo sau khi thực hiện câu lệnh.
Ví dụ: 1 a b R 2
Trạng thái hiện hành là “1” gặp kí tự “a” trên băng, chuyển thành kí tự “b”,
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
con trỏ máy Turing dịch chuyển sang phải 1 ô, chuyển sang trạng thái “2”.
34
+ Các lệnh có thể không đầy đủ các thành phần nếu không có thay đổi gì
trong các thành phần tương ứng.
Ví dụ : 1 _ b L 2
Trạng thái hiện hành là 1 gặp bất cứ kí tự nào chuyển thành kí tự b, dịch
chuyển con trỏ sang trái, chuyển trạng thái sang trạng thái 2.
// Cau truc lenh cua may TR
typedef struct Com {
char R; // thay bang ki tu moi
char T; // Dich chuyen NLR
int Q; // Qua trang thai moi
int P;
char D; // Chi thi $
} Com;
Định nghĩa cấu trúc lệnh máy Turing:
inline void War(int e){
cout << "\n WARNING: ";
switch(e){
case 1: cout << " Lenh nay co the lap vo han.\n
Nen co them chi thi"
<< " CHUYEN dau doc-viet hoac trang thai.";
break;
}
}
inline void Go(){
if (cin.get() == '.') exit(0);
}
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
2.1.3. Các hàm xử lí dữ liệu
inline char Msgo() {
cout << "\n Bam phim cham (.) de dung ";
cout << "\n hoac phim bat ki de tiep tuc: ";
return cin.get();
}
// find the last str in str
char * lstrstr(const char *s1, const char *s2){
char * p = strstr(s1,s2);
if (p == NULL) return NULL;
char * q;
while (p != NULL) {
q = p;
// cout << endl << q;
p = strstr((q+2),s2);
}
return q;
}
// Chinh du lieu vao s tinh tu s[d]
// Cac dau cach: BL
// char *strstr(const char *s1, const char *s2);
inline void Help(){
cout << "\n. Ket thuc chuong trinh.";
cout << "\n L Hien thi chuong trinh.";
cout << "\n H Help.";
cout << "\n ? Thuc hien Test nap tu ban phim.";
cout << "\n $ Bat/Tat hien thi lenh va ket qua
trung gian.";
}
inline void Err(int e){
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
35
cout << "\n ERROR: ";
switch(e){
case 1: cout << " Mong gap so bieu thi trang
thai.";
break;
case 2: cout << " Mong gap ki tu dich chuyen: L,
R, N, _.";
break;
case 3: cout << " Mong gap so hoac _ bieu thi
trang thai.";
break;
case 4: cout << " Chuong trinh khong duoc thuc
hien.";
break;
case 5: cout << " Mong gap dau }.";
break;
case 6: cout << " Cau lenh cut.";
break;
case 7: cout << " Ngan xep rong.";
break;
case 8: cout << " Ngan xep day.";
break;
case 9: cout << " Hang doi rong.";
break;
case 10: cout << " Hang doi day.";
break;
case 11: cout << " Mong gap B.";
break;
}
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
36
}
37
2.2. Phát triển bộ nhớ máy Turing
Trên thực tế với cấu tạo máy Turing một băng có thể mô tả tất cả các
thuật toán nhưng với một đầu đọc và một băng ghi nhớ thì việc giải quyết các
bài toán sẽ phức tạp và mất nhiều thời gian. Hiện nay đã có nhiều cách cải
tiến hoạt động máy Turing nhưng trong khuôn khổ luận văn học viên đề xuất
cách cải tiến về bộ nhớ của máy. Bằng cách thêm vào các cấu trúc ngăn xếp
và hàng đợi việc giải quyết các bài toán đã được cải thiện rõ rệt.
2.2.1. Máy Turing nhiều băng
Xét máy Turing có một bộ điều khiển có k đầu đọc và k băng vô hạn hai
chiều. Mỗi phép chuyển của máy Turing, phụ thuộc vào trạng thái của bộ điều
khiển và ký tự đọc được tại mỗi đầu đọc, nó có thể thực hiện các bước sau:
1) Chuyển trạng thái.
2) In ký hiệu mới tại mỗi đầu đọc để thay thế ký hiệu vừa đọc.
3) Đầu đọc có thể giữ nguyên vị trí hoặc dịch trái hoặc dịch phải 1 ô một
cách độc lập nhau.
Khởi đầu input xuất hiện trên băng thứ nhất, các băng khác chỉ toàn Blank.
Một máy Turing như vậy gọi là máy Turing với nhiều băng vô hạn hai chiều.
Về mặt lí thuyết máy Turing nhiều băng có thể quy về máy Turing một băng.
2.2.2. Cài đặt cấu trúc ngăn xếp (Stack)
- Một số quy ước khi sử dụng:
Học viên sử dụng kí tự “[” để kí hiệu việc đẩy một kí tự vào ngăn xếp.
const char INST = '['; // S C [... : Nap Stack
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Kí tự “]” để kí hiệu việc lấy một kí tự trong ngăn xếp ra ngoài.
const char OUST = ']'; // S C ]... : Lay tu Stack
38
- Khởi tạo giá trị cho ngăn xếp:
Về mặt cấu trúc ngăn xếp được thiết kế theo nguyên tắc LIFO (Last In
Fist Out) có nghĩa là phần tử được đẩy vào ngăn xếp cuối cùng là phần tử đầu
tiên được lấy ra.
Hàm khởi tạo ngăn xếp Inits () học viên đưa con trỏ về vị trí đầu tiên và
inline void Inits(){ st = 0; stack[0] = 0; }
gán giá trị mặc định là 0.
- Đẩy giá trị vào ngăn xếp:
Khi đưa một giá trị, hay một kí tự vào ngăn xếp thì con trỏ tự động tăng
inline char Inst(char ch){
if (st+1 >= MN) {
Err(8);
return -1;
}
stack[++st] = ch;
return ch;
}
lên 1 đơn vị và kí tự được đưa vào lưu trong ngăn xếp.
- Lấy giá trị ở ngăn xếp:
Tương tự việc đưa giá trị vào nggăn xếp việc lấy giá trị trong ngăn xếp
hoạt động ngược lại là con trỏ tự động lùi lại 1 đơn vị và giá trị hay kí tự được
inline char Oust(){
if (st == 0) {
Err(7);
return -1;
}
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
lấy ra không còn lưu trong ngăn xếp nữa.
char ch = stack[st--];
return ch;
}
39
2.2.3. Cài đặt cấu trúc hàng đợi (Queue)
- Một số quy ước:
Học viên sử dụng kí tự “{” kí hiệu việc đưa một giá trị hay kí tự vào hàng
const char INQU = '{'; // S C {... : Nap queue
const char OUQU = '}'; // S C }... : Lay tu queue
đợi, kí tự “}” kí hiệu việc lấy ra một giá trị hay một kí tự ra khỏi hàng đợi.
- Khởi trị cho hàng đợi:
Hàng đợi được học viên thiết kế theo nguyên tắc FIFO (Fist In Fist Out)
có nghĩa là phần tử được nạp vào hàng đợi đầu tiên sẽ là phần tử được lấy ra
đầu tiên. Như vậy với hàng đợi học viên sử dụng hai con trỏ để nạp và lấy giá
// Khoi tri cho queue
inline void Initq(){ iq = oq = 0; queue[0] = 0; }
trị là iq và oq. Ban đầu hai con trỏ này trỏ cùng vào một vị trí.
- Đẩy giá trị vào hàng đợi:
Khi nạp giá trị vào hàng đợi con trỏ nạp iq của hàng đợi tự động tăng 1
inline char Inqu(char ch){
if (iq+1 >= MN) {
Err(10);
return -1;
}
queue[++iq] = ch;
}
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
đơn vị và giá trị hay kí tự nạp được lưu lại trong hàng đợi.
40
- Lấy giá trị ở hàng đợi:
Khi lấy một giá trị ra khỏi hàng đợi con trỏ oq của hàng đợi tự động tăng
inline char Ouqu(){
if (iq == oq) {
Err(9);
return -1;
}
char ch = queue[++oq];
return ch;
}
một đơn vị, giá trị hay kí tự lấy ra được loại bỏ khỏi hàng đợi.
2.2.4. Cài đặt bộ nhớ imem và cmem
Ngoài hai cấu trúc ngăn xếp và hàng đợi học viên tổ chức thêm hai bộ
nhớ imem và cmem. Hai bộ nhớ này thực chất là một biến nhớ tạm có thể lưu
một số (imem) hoặc một kí tự (cmem).
const char INMEM = '('; // S C (...: Nap Mem
const char OUMEM = ')'; // S C )...: Lay tu Mem
const char INC = '>'; // S C >...: ++out[ptr]
const char DEC = '<'; // S C <...: --out[ptr]
- Một số quy ước:
Vậy để sử dụng bộ nhớ imem học viên dùng kí tự “(” để nạp dữ liệu và
kí tự “)” để lấy dữ liệu từ bộ nhớ đó.
Với bộ nhớ cmem học viên dùng kí tự “>” để nạp dữ liệu và kí tự “<” để
lấy dữ liệu.
Ví dụ:
Bài toán chuyển một số thập phân dương sang (n+1) vạch thẳng “|”.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Cách 1 sử dụng máy Turing thuần túy:
41
% Bieu dien so thap phan n thanh (n+1) |
% 10 => ||||||||||| (11 vach)
1 0 | _ 0 // Neu la 0 thi viet |, stop
1 _ _ R 7 // Qua dau phai
7 _ _ R _
7 # | L 2 // Viet | dau tien. Chuan bi tru 1
2 {123456789} $| R 3 // Giam 1
2 0 9 L _ // Tru co nho
3 _ _ R _
3 | _ R _ // Qua dau phai
3 # | L 4 // Them |. Ve trai
4 | _ L _
4 0 _ L 5 // Kiem tra co phai toan 0
4 # _ _ 0
4 _ _ _ 2
5 0 _ L _
5 # _ R 6 // Day toan 0: xoa het 0, stop
6 0 # R _
6 | _ _ 0
5 _ _ R 7 // Con chu so khac 0: Quay ve dau phai
7 _ _ R _
7 | _ L 2
E
Kết quả khi thực hiện chương trình:
Input: #12# (2)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Final output: #|||||||||||||# (13)
42
Timer = 205
Cách sử dụng bộ nhớ được cải tiến:
% Bieu dien so tu nhien sang dang vach
% Dung imem
1 _ $< R 2 // Doc vao imem
2 _ _ R _ // To R
2 # : R 3
3 # | R 4
4 _ $I _ 0 6 // imem = 0 ? 0 : 6
6 # | R 7 // Ghi 1 vach
7 _ $- _ 4// --imem
E
Kết quả sau khi thực hiện chương trình:
Input: #12# (2)
Final output: #12:|||||||||||||# (16)
Timer = 41
So sánh kết quả hai cách trên dễ nhận thấy với cách hai, khi sử dụng
những cải tiến về bộ nhớ mã lệnh được viết ngắn hơn, số bước chuyển đầu
đọc cũng ít hơn, nên kết luận rằng khi cải tiến bộ nhớ cho kết quả tốt hơn.
2.4. Kết luận
Trong chương này học viên đã trình bày chương trình cài đặt máy Turing
và các thành phần của máy. Trong quá trình cài đặt học viên đã cải tiến bộ
nhớ của máy Turing cụ thể như sau:
- Cài đặt chương trình mô phỏng máy Turing.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
- Cài đặt stack và queue để tăng cường tốc độ sử lí của máy Turing.
43
- Cài đặt bộ nhớ imem và cmem dùng làm bộ nhớ đệm trong quá trình
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
xử lý.
44
Chƣơng 3
MỘT SỐ CHƢƠNG TRÌNH ỨNG DỤNG MÁY TURING
ĐO ĐỘ PHỨC TẠP THUẬT TOÁN
Trong chương này học viên ứng dụng máy Turing đã được cài đặt ở
chương 2 để lập trình một số bài toán, từ đó rút ra được độ phức tạp của các
thuật toán đó.
3.1. Bài toán trừ một vào số tự nhiên
Như học viên đã trình bày ở trên, máy Turing có thể mô tả tất cả các
thuật toán giải được trên máy tính, vì vậy máy Turing cũng có thể mô tả được
bốn phép toán cơ bản trong toán học là cộng, trừ, nhân, chia. Ở đây học viên
xin trình bày thuật toán trừ một vào số tự nhiên vì đây là phép toán cơ bản
nhất, trong toán học phép trừ tương đương với phép cộng, trừ (cộng) với một
số tự nhiên lớn tương đương với việc trừ (cộng) nhiều lần với số “1”. Phép
nhân và phép chia các số tự nhiên tương đương với việc trừ (cộng) nhiều lần
với số tự nhiên.
- Tư tưởng thuật toán:
Chuyển con trỏ về phải nhất, nếu kí tự phải nhất khác “0” trừ 1, dừng
chương trình, nếu kí tự phải nhất bằng “0” thay bằng “9” dịch con trỏ sang
trái. Lặp lại bước trên.
- Phần mã chương trình viết bằng lệnh máy Turing:
% Thi du: 120 => 119
% 100 => 099
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
// 8100 => 8099
45
1 _ _ R _ // Ve trai
1 # _ L 2 // Chuan bi tru
2 {123456789} $| _ 3
2 0 9 L 2
2 # _ R 3 // Xoa cac so 0 vo nghia
3 0 # _ 0
3 _ _ _ 0
E
- Trong chương trình trên ta có:
Tập kí tự được sử dụng: là các chữ số : 0,1,2,3,4,5,6,7,8,9. kí tự “#”
tương ứng với B là kí tự trắng trên băng.
Tập trạng thái bao gồm các trạng thái : 0,1,2,3. Trong đó trạng thái bắt
đầu là trạng thái 1, trạng thái kết thúc là trạng thái 0.
Kí tự “$|” thể hiện toán tử trừ 1.
- Kết quả đạt được:
Mô phỏng với số đầu vào là 12345.
Input: #12345# (5)
Command: 1 _ _ R _1 #12345# (5)
Command: 1 _ _ R _1 #12345# (5)
Command: 1 _ _ R _1 #12345# (5)
Command: 1 _ _ R _1 #12345# (5)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Command: 1 _ _ R _1 #12345# (5)
46
Command: 1 # _ L _2 #12345# (5)
Command: 2 5 $| N 3 #12344# (5)
Command: 3 _ _ N 0 #12344# (5)
Final output: #12344# (5)
Timer = 8
Vậy trong chương trình trên, máy Turing đã mất 8 bước chuyển đầu đọc
tương đương với thời gian là 8 nhịp xung của máy tính.
Tổng số ô nhớ là 5 ô được sử dụng.
Mô phỏng với số đầu vào là 800.
Input: #800# (3)
Command: 1 _ _ R _1 #800# (3)
Command: 1 _ _ R _1 #800# (3)
Command: 1 _ _ R _1 #800# (3)
Command: 1 # _ L _2 #800# (3)
Command: 2 0 9 L 2 #809# (3)
Command: 2 0 9 L 2 #899# (3)
Command: 2 8 $| N 3 #799# (3)
Command: 3 _ _ N 0 #799# (3)
Final output: #799# (3)
Timer = 8
Với đầu vào là số 800 thì máy Turing cũng cần 8 bước chuyển của đầu
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
đọc để xử lí. Tổng số ô nhớ là 3.
47
- Qua hai ví dụ ở trên học viên muốn truyền tải thông điệp là máy Turing
có thể đánh giá chính xác thời gian và dung lượng bộ nhớ cần cung cấp cho
thuật toán trong từng trường hợp cụ thể để rút ra được kết luận về độ phức tạp
thuật toán cho từng thuật toán.
3.2. Biểu diễn số thập phân n thành (n+1) vạch |
Tương tự với ý tưởng ở phần trên, học viên thiết kế bài toán đơn giản
chuyển số tự nhiên n thành n+1 vạch thẳng(“|”). Bài toán này theo học viên có
thể cung cấp một cách khác để cộng trừ các số tự nhiên lớn bằng cách quy đổi
về các vạch. Cũng theo lập luận ở trên từ các phép cộng trừ ta có thể thực
hiện các phép nhân chia bằng việc cộng hoặc trừ liên tiếp các số tự nhiên.
- Tư tưởng thuật toán:
Chuyển con trỏ về phải nhất, khi gặp kí tự đặc biệt “#” tiến hành điền
vạch |, trừ 1 vào số tự nhiên đầu vào, lặp lại bước trên đến khi kí tự trái nhất
bằng 0, thay 0 bằng “|”, thuật toán dừng.
- Mã lệnh máy Turing:
% Bieu dien so thap phan n thanh (n+1) |
% 10 => ||||||||||| (11 vach)
// Chu y: So gom k chu so thap phan sau khi giam 1
// lien tiep se thu duoc k so 0: 0...0
1 0 | _ 0 // Neu la 0 thi viet |, stop
1 _ _ R 7 // Qua dau phai
7 _ _ R _
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
7 # | L 2 // Viet | dau tien. Chuan bi tru 1
48
2 {123456789} $| R 3 // Giam 1
2 0 9 L _ // Tru co nho
3 _ _ R _
3 | _ R _ // Qua dau phai
3 # | L 4 // Them |. Ve trai
4 | _ L _
4 0 _ L 5 // Kiem tra co phai toan 0
4 # _ _ 0
4 _ _ _ 2
5 0 _ L _
5 # _ R 6 // Day toan 0: xoa het 0, stop
6 0 # R _
6 | _ _ 0
5 _ _ R 7 // Con chu so khac 0: Quay ve dau phai
7 _ _ R _
7 | _ L 2
E
- Trong mã lệnh trên:
Bảng chữ cái là: các chữ số từ 0 đến 9, dấu vạch thẳng |.
Tập trạng thái: 0,1,2,3,4,5,6,7. Trong đó trạng thái bắt đầu là 1, trạng thái
kết thúc là 0.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Các kí hiệu %, // là toán tử điều khiển chú thích.
49
- Mô phỏng với bộ số đầu vào 34.
Input: #34# (2)
Final output: #|||||||||||||||||||||||||||||||||||# (35)
Timer: 1315
Vậy với thuật toán trên máy Turing cần 1315 bước chuyển và ô nhớ cần 37
ô (vì các bước chuyển trung gian quá dài nên học viên chỉ đưa ra kết quả cuối
cùng, số ô nhớ 37 là số ô được dùng trong quá trình xử lý của thuật toán).
* Thuật toán sử dụng imem
- Tư tưởng thuật toán:
Khởi tạo imem, khi đầu đọc hoạt động từ trái qua phải nạp dần vào imem
theo công thức lấy giá trị trong imem nhân 10 cộng với giá trị số của kí tự
được đẩy vào. Sau khi nạp xong dữ liệu đầu đọc gặp kí tự “#” chuyển thành
vạch đầu tiên (“|”), kiểm tra imem nếu rỗng (số đầu vào = 0) dừng thuật toán,
ngược lại trừ imem 1 đơn vị và chuyển kí tự “#” trên băng thành “|”.
- Mã lệnh chương trình:
% Bieu dien so tu nhien sang dang vach
% Dung imem
1 _ $< R 2 // Doc vao imem
2 _ _ R _ // To R
2 # : R 3
3 # | R 4
4 _ $I _ 0 5 // imem = 0 ? 0 : 5
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
5 # | R 6 // Ghi 1 vach
50
6 _ $- _ 4// --imem
E
- Trong mã lệnh trên:
Bảng chữ cái là: các chữ số từ 0 đến 9, dấu vạch thẳng |, kí tự hai chấm
“:”, kí tự khoảng trắng mặc định là “#”.
Sử dụng bộ nhớ imem và các toán tử liên quan đến imem.
Tập trạng thái: 0,1,2,3,4,5,6. Trong đó trạng thái bắt đầu là 1, trạng thái
kết thúc là 0.
Các kí hiệu %, // là toán tử điều khiển chú thích.
- Mô phỏng với bộ số đầu vào 34.
Input: #34# (2)
Final output: #34:|||||||||||||||||||||||||||||||||||# (38)
Timer: 107
Khi sử dụng imem máy Turing cần 107 bước chuyển đầu đọc và cần 38
ô nhớ trên băng.
3.3. Biểu diễn (n+1) vạch | thành số tự nhiên n
- Tư tưởng thuật toán:
Đầu dọc máy Turing gặp dấu vạch đầu tiên “|” chuyển thành kí tự “0”, nếu
gặp kí tự “#” chương trình dừng, gặp vạch “|” chuyển thành “?” cộng 1 vào số
trước “?” trái nhất. Khi hết kí tự “|” xóa các kí tự “?”. Dừng chương trình.
- Mã lệnh chương trình:
% Bien doi bieu dien vach sang so thap phan |||| => 3
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
// Ket qua ghi ben trai
51
% Bien doi bieu dien vach sang dang thap phan
1 | 0 R 2 // Khoi tri 0 tai | dau tien (Trai nhat)
2 # _ _ 0 // input = |: stop
2 | ? L 3 // Xoa | trai nhat
3 _ _ L 3 // Cong 1
3 {012345678} $& R 4
3 9 0 L _
3 # 1 R 4 // Cong xong
4 _ _ R _ // Ve dau phai
4 # _ L 5 // Xoa ?
5 ? # L _
5 _ _ _ 0
4 | ? L 3
E
- Trong mã lệnh trên:
Bảng chữ cái là: các chữ số từ 0 đến 9, dấu vạch thẳng |, kí tự hai chấm
“?”, kí tự khoảng trắng mặc định là “#”.
Tập trạng thái: 0,1,2,3,4,5. Trong đó trạng thái bắt đầu là 1, trạng thái kết
thúc là 0.
Các kí hiệu %, // là toán tử điều khiển chú thích.
- Mô phỏng với bộ số đầu vào |||||||||||||| (14 vạch)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Input: #||||||||||||||# (14)
52
Final output: #13# (2)
Timer: 213
Vậy với thuật toán trên máy Turing cần 213 bước chuyển và ô nhớ cần
15 ô (vì các bước chuyển trung gian quá dài nên học viên chỉ đưa ra kết quả
cuối cùng, số ô nhớ 15 là số ô được dùng trong quá trình xử lí của thuật toán).
* Thuật toán sử dụng imem:
- Tư tưởng thuật toán:
Khởi tạo imem, đầu đọc máy Turing gặp kí tự “|” trái nhất chuyển thành
kí tự “#” (xóa vạch đầu tiên). Nếu hết vạch, dừng chương trình, gặp vạch
cộng thêm 1 vào imem. Nạp hết kí tự “|” trên băng đưa giá trị trong imem ra
băng, chương trình kết thúc.
- Mã lệnh chương trình:
% Chuyen dang vach sang so thap phan
% Dung imem
1 _ $i _ 2 // Khoi tri imem
2 | # R 3
3 # $> N 0 // Xuat imem, stop
3 | # N 4
4 _ $+ R 3 // Tang imem
E
- Trong mã lệnh trên:
Bảng chữ cái là: các chữ số từ 0 đến 9, dấu vạch thẳng |, kí tự khoảng
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
trắng mặc định là “#”.
53
Tập trạng thái: 0,1,2,3,4. Trong đó trạng thái bắt đầu là 1, trạng thái kết
thúc là 0.
Sử dụng bộ nhớ imem và các toán tử liên quan đến imem.
Các kí hiệu %, // là toán tử điều khiển chú thích.
- Mô phỏng với bộ số đầu vào |||||||||||||| (14 vạch).
Input: #||||||||||||||# (14)
Final output: #13# (2)
Timer: 29
Vậy với thuật toán trên máy Turing cần 29 bước chuyển và ô nhớ cần 14
ô (vì các bước chuyển trung gian quá dài nên học viên chỉ đưa ra kết quả cuối
cùng, số ô nhớ 14 là số ô được dùng trong quá trình xử lí của thuật toán).
3.4. Cộng hai số tự nhiên lớn
- Tư tưởng thuật toán:
Với bài toán này học viên quy định bộ dữ liệu đầu vào được viết theo
quy cách: “a+b=”. Với a, b là các số tự nhiên lớn (nhiều chữ số không quy
định độ dài với mỗi số a và b). “a” là số hạng 1, “b” là số hạng 2.
Ví dụ:
Input: 123+45=
Bước 1: Khởi tạo bộ nhớ imem và bộ nhớ ngăn xếp (stack).
Bước 2: Tìm chữ số phải nhất của số hạng 1. Đầu đọc ghi máy Turing
gặp bất cứ kí tự nào tự động dịch phải cho đến khi gặp kí tự “+” đầu đọc ghi
dịch trái tìm chữ số phải nhất của số hạng 1. Khi đầu đọc ghi trỏ vào chữ số
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
phải nhất của số hạng 1 chia thành hai trường hợp:
54
+ imem rỗng (chưa nhớ) ghi kí tự đang được trỏ vào imem.
+ imem khác rỗng (đang nhớ) cộng kí tự đang được trỏ vào imem.
Chuyển kí tự vừa xét thành ?.
Bước 3: Tìm chữ số phải nhất của số hạng 2. Chuyển đầu đọc ghi của
máy Turing về phải. Khi gặp kí tự “=”, đầu đọc ghi dịch trái tìm chữ số phải
nhất của số hạng 2. Khi đầu đọc ghi máy Turing tìm được chữ số phải nhất
của số hạng 2 cộng dồn vào bộ nhớ imem. Cộng xong chuyển kí tự đang được
đầu đọc ghi trỏ vào thành “?”. Chuyển đầu đọc ghi về sau kí tự “=” ghi giá trị
trong imem. Chuyển đầu đọc về chữ số phải nhất của kết quả tạm, ghi kí tự
này vào bộ nhớ stack, chuyển kí tự vừa xét thành “#”. Dịch trái đầu đọc ghi,
xảy ra hai trường hợp sau:
+ Đầu đọc ghi trỏ vào kí tự “1”, phép cộng có nhớ. Làm rỗng imem, ghi
“1” vào imem. Chuyển “1” thành “#”, dịch trái đầu đọc ghi về đầu xâu.
+ Đầu đọc ghi trỏ vào kí tự “=”, phép cộng không nhớ, dịch trái đầu đọc
ghi về đầu xâu.
Trở về trạng thái ban đầu. Bắt đầu vòng lặp.
Bước 4: Điều kiện kết thúc là khi các chữ số của hai số a,b được chuyển
thành “?”, bộ nhớ imem, bộ nhớ stack được làm rỗng.
Các trường hợp kết thúc:
+ a và b có số chữ số bằng nhau. Khi máy Turing xác nhận trạng thái tất
cả chữ số của số hạng 1 chuyển thành kí tự “?” và gặp trạng thái tất cả chữ số
của số hạng 2 chuyển thành kí tự “?”. Đầu đọc ghi dịch phải đến vị trí sau dấu
bằng “=”, nếu imem không rỗng nạp kí tự đó vào stack, làm rỗng imem, ghi
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
kết quả. Dừng chương trình.
55
+ a có ít chữ số hơn b. Khi máy Turing xác nhận trạng thái tất cả chữ số
của số hạng 1 chuyển thành kí tự “?” và số hạng 2 vẫn còn chữ số chưa
chuyển thành kí tự “?”. Đầu đọc dịch phải đến hết xâu, dịch trái tìm chữ số
phải nhất của số hạng 2. Khi tìm được, nếu imem rỗng nạp kí tự đó vào stack,
dịch trái đến khi gặp trạng thái tất cả chữ số của số hạng 2 chuyển thành kí tự
“?” (đầu đọc gặp kí tự “+”) chuyển đầu đọc ghi về vị trí sau dấu bằng “=” ghi
kết quả, làm rỗng imem và stack.
+ a có nhiều chữ số hơn b. Khi máy Turing xác nhận trạng thái tất cả chữ
số của số hạng 2 chuyển thành kí tự “?” và số hạng 1 vẫn còn chữ số chưa
chuyển thành “?”. Đầu đọc ghi chuyển về vị trí sau dấu bằng “=”, ghi kết quả
trong imem vào stack, nếu có nhớ làm rỗng imem ghi số nhớ, dịch trái con trỏ
tìm chữ số phải nhất của số hạng 1 nạp vào imem, chuyển thành “?”. Lặp lại
quá trình trên đến khi gặp trạng thái tất cả chữ số của số hạng 2 chuyển thành
kí tự “?” (đầu đọc gặp kí tự “+”) chuyển đầu đọc ghi về vị trí sau dấu bằng
“=” ghi kết quả, làm rỗng imem và stack.
- Mã lệnh chương trình:
%=========================
% Cong hai so tu nhien lon
% ************************
// khoi tao imem stack
1 _ $i N 2 // khoi tao imem
2 _ $s N 3 // khoi tao stack
// bat dau
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
3 _ _ R 3 // tim +
56
3 + _ L 4 tim thay +
4 {0,1,2,3,4,5,6,7,8,9} _ N 5 // tim chu so nho nhat
4 ? _ L 4 // day trai tim so hang can cong
4 # _ N 120 // sh1 het
5 _ $I N 6 7 // xet imem rong
6 {0,1,2,3,4,5,6,7,8,9} $< N 8 // day chu so nho nhat vao imem (1)
8 {0,1,2,3,4,5,6,7,8,9} ? N 12 // chuyen chu so da cong thanh ? (2)
7 _ $- N 9 // lam rong stack
9 {0,1,2,3,4,5,6,7,8,9} $< N 10 // (1)
10 _ $+ N 11 // tra lai 1 da xoa o imem
11 {0,1,2,3,4,5,6,7,8,9} ? N 12 // (2)
12 _ _ R 12 // day phai tim chu so o sh 2
12 = _ N 13
13 _ _ L 13
13 + _ N 80 // sh2 het
// tim so hang 2
13 9 _ N 15
13 8 _ N 16
13 7 _ N 17
13 6 _ N 18
13 5 _ N 19
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
13 4 _ N 20
57
13 3 _ N 21
13 2 _ N 22
13 1 _ N 23
// cong don sh2 vao imem
15 _ $+ N 16
16 _ $+ N 17
17 _ $+ N 18
18 _ $+ N 19
19 _ $+ N 20
20 _ $+ N 21
21 _ $+ N 22
22 _ $+ N 23
23 _ $+ N 24
24 {0,1,2,3,4,5,6,7,8,9} ? N 24 // bien chu so da cong thanh ?
// ghi ket qua tam
24 _ _ R 24
24 = _ R 25 // tim dau =
25 _ $> N 26 // lay gia tri tu imem
26 _ _ R 26 // tim # o cuoi
26 # _ L 27 // tim thay #
27 {0,1,2,3,4,5,6,7,8,9} $[ N 28 // nap chu so dang o cuoi
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
28 {0,1,2,3,4,5,6,7,8,9} # L 29 // chuyen so da nap stack thanh #
58
29 _ $I N 30 31
30 1 $< N 32
32 1 # L 33
30 = _ N 33
31 _ $- N 29
33 _ _ L 33
33 # _ R 3 // vong lap
// sh2 het truoc
80 _ _ R 80
80 # $> N 81
81 _ _ R 82
82 _ _ R 82
82 # _ L 83
83 {0,1,2,3,4,5,6,7,8,9} $[ N 84
84 {0,1,2,3,4,5,6,7,8,9} # L 85 //ghi tam xong
85 _ $I N 86 87
86 1 $< N 88
88 1 # L 89
86 = _ N 89
87 _ $- N 85 // sh2 da cong het
89 _ _ L 89
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
89 # $> N 92
59
92 {0,1} $[ N 93
93 {0,1} # N 94
94 _ $I N 95 96
95 _ _ N 100
96 _ $- N 94
89 {0,1,2,3,4,5,6,7,8,9} $I N 90 91
90 {0,1,2,3,4,5,6,7,8,9} $[ L 90
90 # _ N 100
91 _ $- N 97
97 {0,1,2,3,4,5,6,7,8,9} $< N 98
98 _ $+ N 99
99 {0,1,2,3,4,5,6,7,8,9} ? N 111
111 _ _ N 80
// sh1 het
120 _ _ R 120
120 + _ R 121
121 _ _ R 121
121 # _ _ 122
122 _ _ L 122
122 + $I N 100 128
128 _ _ R 128
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
128 # $> N 129
60
129 _ _ R 129
129 # _ L 130
130 1 $[ N 131
131 1 # N 132
132 _ _ L 132
132 + _ N 100
122 {0,1,2,3,4,5,6,7,8,9} $I N 123 124
123 _ $[ N 125
125 {0,1,2,3,4,5,6,7,8,9} ? L 122
124 9 0 N 126
126 _ $[ N 127
127 0 ? N 122
124 {0,1,2,3,4,5,6,7,8} $& N 133
133 _ $[ N 134
134 _ $I N 136 137
136 _ ? N 122
137 _ $- N 134
// ket thuc
100 _ _ R 100
100 = _ R 101
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
101 _ $S N 102 103
61
102 _ _ _ 0
103 _ $] R 101
E
- Trong mã lệnh trên.
Bảng chữ cái là: các chữ số từ 0 đến 9, dấu cộng “+”, dấu bằng “=”, dấu
hỏi chấm “?”, kí tự khoảng trắng mặc định là “#”.
Tập trạng thái: 0,1,2,3,4,5,6,7,8,9… 13, 15, 16… 33,80,81 … 103,
111,120,121… 134. Trong đó trạng thái bắt đầu là 1, trạng thái kết thúc là 0.
Sử dụng bộ nhớ imem, bô nhớ stack và các toán tử liên quan đến imem, stack.
Các kí hiệu %, // là toán tử điều khiển chú thích.
- Mô phỏng với bộ số đầu vào 2015+3999= (hai số 4 chữ số)
Input: #2015+3999=# (10)
Final output: #????+????=6014# (14)
Timer: 315
Vậy với thuật toán trên máy Turing cần 315 bước chuyển và ô nhớ cần 14 ô
(vì các bước chuyển trung gian quá dài nên học viên chỉ đưa ra kết quả cuối
cùng, số ô nhớ 14 là số ô được dùng trong quá trình xử lý của thuật toán).
- Mô phỏng với bộ số đầu vào 33+3456= (số hạng 1 có ít chữ số số hạng 2)
Input: #33+3456=# (8)
Final output: #??+????=3489# (12)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
Timer: 164
62
Vậy với thuật toán trên máy Turing cần 164 bước chuyển và ô nhớ cần 12 ô
(vì các bước chuyển trung gian quá dài nên học viên chỉ đưa ra kết quả cuối cùng,
số ô nhớ 12 là số ô được dùng trong quá trình xử lý của thuật toán).
- Mô phỏng với bộ số đầu vào 3389+56= (số hạng 2 có ít chữ số số hạng 1)
Input: #3389+56=# (8)
Final output: #??+????=3445# (12)
Timer: 223
Vậy với thuật toán trên máy Turing cần 223 bước chuyển và ô nhớ cần
12 ô (vì các bước chuyển trung gian quá dài nên học viên chỉ đưa ra kết quả
cuối cùng, số ô nhớ 12 là số ô được dùng trong quá trình xử lí của thuật toán).
3.5. Kết luận
Trong chương này học viên đã trình bày chương trình cài đặt một số bài
toán trên máy Turing và trình bày cụ thể các thành phần, ví dụ mô phỏng quá
trình thực hiện của máy. Trong qua trình cài đặt học viên đã sử dụng bộ nhớ
được cải tiến ở chương 2 của máy Turing cụ thể như sau:
- Bài toán trừ 1 vào số tự nhiên nhằm giới thiệu cách viết mã lệnh cho
máy Turing.
- Bài toán biểu diễn số thập phận n thành (n+1) vạch thẳng “|” và bài
toán biểu diễn (n+1) vạch thẳng “|” thành số tự nhiên n. Trong hai bài toán
này học viên đã cài đặt bằng 2 phương pháp có so sánh, phương pháp 1 dùng
máy Turing thường, phương pháp 2 học viên đã sử dụng bộ nhớ imem để tăng
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
hiệu quả làm việc của máy Turing.
63
- Bài toán cộng hai số tự nhiên lớn. Trong bài toán này học viên sử dụng
hai bộ nhớ imem và ngăn xếp để xử lý, qua bài toán này học viên sử dụng các
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
bộ nhớ cùng lúc để tăng hiệu quả hoạt động của máy Turing.
64
KẾT LUẬN
Thuật toán và độ phức tạp thuật toán là một mảng rất rộng, nếu tìm hiểu
tất cả vấn đề đó là một khối lượng kiến thức khổng lồ. Trong luận văn đã tập
trung nghiên cứu, trình bày những kiến thức cơ bản về máy Turing, thuật toán
và ứng dụng máy Turing vào đánh giá độ phức tạp thuật toán. Qua đó luận
văn đã đạt được một số kết quả như sau:
Về lý thuyết:
Luận văn tập trung nghiên cứu các kiến thức chung nhất về máy Turing,
thuật toán và độ phức tạp của thuật toán. Luận văn đã phân tích kỹ về độ phức
tạp thuật toán của các bài toán ứng dụng.
Về ứng dụng:
Luận văn đã phân tích và cài đặt máy Turing, thông qua đó cài đặt một
số bài toán bằng máy Turing.
Phạm vi và khả năng áp dụng.
Luận văn là một tài liệu tham khảo tốt cho cho những người đang tham
gia vào việc nghiên cứu thuật toán và độ phức tạp thuật toán.
Hướng nghiên cứu tiếp theo.
Hoàn thiện và tối ưu cài đặt máy Turing để chuẩn hóa thành thước đo
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
thuật toán chính xác, hiệu quả.
65
TÀI LIỆU THAM KHẢO
Tài liệu tiếng Việt
[1] Nguyễn Thanh Bình (2007), Giáo trình - bài giảng thuật toán nâng cao,
trường Đại học Bách khoa - Đại học Đà Nẵng.
[2] Nguyễn Gia Định (2004), Lý thuyết ngôn ngữ hình thức và ôtômát,
Đại học Huế.
[3] Nguyễn Hữu Điển (2002), Một số vấn đề về thuật toán, Nxb Giáo dục.
[4] Lê Minh Hoàng (2002), Giải thuật và lập trình, Nxb ĐHSP Hà Nội.
[5] Nguyễn Xuân Huy (2012), Sáng tạo trong thuật toán và lập trình, T1,2,3,
Nxb Thông tin và truyền thông.
[6] Đỗ Xuân Lôi (1998), Cấu trúc dữ liệu và giải thuật, Nxb Giáo dục.
Tài liệu tiếng nƣớc ngoài
[7] John E. Hopcroft; Jeffrey D.Ullman (2013), Introduction to Automata Theory, Languages and Computation, 5th Edision, Wesley Publishing
Company, (Chapter 7: Turing Machines).
[8] Peter Linz (2011), An Introduction to Formal Languages and Automata,
7th Edision, D.C.Heath and Company.
[9] Garey Michael R-David S Johnson (2007), Computers and Intractability:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
A Guide to the Theory of NP-Completeness, W.H. Freeman.
