Cài đặt máy Turing và ứng dụng máy Turing đánh giá độ phức tạp thuật toán

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

ĐẠ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

THÁI NGUYÊN - 2015

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

ĐẠ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

THÁI NGUYÊN - 2015

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

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ả

Nguyễn Anh Tùng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

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

Nguyễn Anh Tùng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

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

2.2.4. Cài đặt bộ nhớ imem và cmem....................................................... 40

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

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

TÀI LIỆU THAM KHẢO ............................................................................ 65

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

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

Hình 2.6. Hiển thị kết quả trung gian của chương trình ............................... 30