Luận văn Thạc sĩ Khoa học máy tính: Cài đặt máy Turing và ứng dụng máy Turing đánh giá độ phức tạp 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à đánh giá độ phức tạp cụ thể từng bài. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học máy tính: Cài đặt máy Turing và ứng dụng máy Turing đánh giá độ phức tạp thuật toán ĐẠ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 ...