Luận án: Lý thuyết và ứng dụng của các mô hình otomat nâng cao - Đặng Quyết Thắng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN --------------------------------------- Đặng Quyết Thắng MỘT SỐ VẤN ĐỀ LÝ THUYẾT VÀ ỨNG DỤNG CỦA CÁC MÔ HÌNH OTOMAT NÂNG CAO LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2013 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN --------------------------------------- Đặng Quyết Thắng MỘT SỐ VẤN ĐỀ LÝ THUYẾT VÀ ỨNG DỤNG CỦA CÁC MÔ HÌNH OTOMAT NÂNG CAO Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán Mã số: 62 46 35 01 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC: 1. Phan Trung Huy 2. Đặng Huy Ruận Hà Nội – 2013 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu khoa học của riêng tôi và chƣa từng đƣợc ai công bố trong bất kỳ công trình nào khác. Các kết quả viết chung với các tác giả khác đều đƣợc sự đồng ý của đồng tác giả trƣớc khi đƣa vào luận án.

Tác giả Đặng Quyết Thắng LỜI CẢM ƠN Tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS. Phan Trung Huy và GS. Đặng Huy Ruận - những ngƣời thầy đã tận tình hƣớng dẫn, chỉ ra cho tôi hƣớng nghiên cứu lý thú và động viên khích lệ tôi hoàn thành luận án này. Tôi xin chân thành cảm ơn Ban Giám đốc, Khoa Sau đại học, Ban đào tạo, Đại học Quốc gia Hà Nội; Ban Giám hiệu, Phòng Sau đại học, Khoa Toán - Cơ - Tin học, Bộ môn Tin học, Trƣờng Đại học Khoa học Tự nhiên đã tạo mọi điều kiện thuận lợi cho tôi trong quá trình học tập và nghiên cứu.

Tôi xin cảm ơn các nhà khoa học, các đồng nghiệp trong các xêmina tại Bộ môn Tin học thuộc Khoa Toán - Cơ - Tin học, Trƣờng Đại học Khoa học Tự nhiên; Bộ môn Tin học thuộc Viện Toán ứng dụng và Tin học, Trƣờng Đại học Bách khoa Hà Nội; phòng Cơ sở Toán học của Tin học thuộc Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện cho tôi trình bày một phần nội dung cơ bản của luận án và góp ý giúp tôi hoàn thiện luận án này. Tôi cũng xin chân thành cảm ơn Ban giám hiệu - Trƣờng Đại học Sƣ phạm Kỹ thuật Nam Định đã tạo điều kiện thuận lợi cho tôi trong công tác, học tập và nghiên cứu. Những lời biết ơn sâu nặng xin đƣợc dành cho những ngƣời thân, đặc biệt là mẹ và vợ con, cùng các bạn đồng nghiệp đã thông cảm, khích lệ và sẻ chia khó khăn trong thời gian tôi thực hiện luận án này. Tác giả Đặng Quyết Thắng MỤC LỤC LỜI CAM ĐOAN .5 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .8 DANH MỤC CÁC BẢNG VÀ HÌNH VẼ.

CÁC KIẾN THỨC CƠ SỞ. Một số khái niệm. Cấu trúc đại số cơ bản và ngôn ngữ. Khoảng cách soạn thảo.

Xâu con chung dài nhất. Một số loại mã. Máy biến đổi và otomat. Hợp thành của hai máy biến đổi.

Đồ thị hữu hạn. Khái niệm cơ bản. Biểu diễn đồ thị trong máy tính. Phƣơng pháp ma trận kề.

Phƣơng pháp danh sách kề. Tìm kiếm theo chiều sâu. Tìm đƣờng đi ngắn nhất nguồn đơn. Chuỗi hình thức.

Kết luận chƣơng 1. KHOẢNG CÁCH SOẠN THẢO CỦA HAI NGÔN NGỮ. Xâu con chung dài nhất của hai ngôn ngữ. Hình thức hóa khái niệm LCS.

Thuật toán tìm đƣờng đi dài nhất nguồn đơn. Xác định LCS của hai ngôn ngữ theo otomat. Chi phí của một dãy sánh LCS. Khoảng cách DL hạn chế của hai ngôn ngữ.

Hình thức hóa khái niệm khoảng cách DL hạn chế. Mở rộng kiểu 1 của otomat. Xác định khoảng cách DL hạn chế của hai ngôn ngữ theo otomat. Chi phí của một dãy sánh DL hạn chế.

Kết luận chƣơng 2. KIỂM ĐỊNH -MÃ VÀ Z-MÃ. Phép toán trên otomat. Lƣỡng cực hóa, mở rộng kiểu 2 và kiểu 3 của otomat.

Tích hợp otomat. Sự tồn tại đƣờng đi kiểu 1 và kiểu 2. Kiểm định ω-mã theo otomat. Kiểm định Z-mã theo otomat.

Kết luận chƣơng 3. XÁC ĐỊNH ĐỘ KHÔNG NHẬP NHẰNG VÀ ĐỘ TRỄ GIẢI MÃ. Độ không nhập nhằng của ngôn ngữ. Mở rộng kiểu 4 và kiểu 5 của otomat.

Giá của đƣờng đi kiểu 2 và sự tồn tại đƣờng đi kiểu 3. Xác định độ không nhập nhằng của ngôn ngữ theo otomat. Xác định độ trễ giải mã theo otomat. Kết luận chƣơng 4 .99 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN .101 TÀI LIỆU THAM KHẢO .103 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Các ký hiệu ε Từ (xâu) rỗng |A| Lực lƣợng của tập A w(i) Khúc đầu có độ dài i của xâu w w[i] Ký tự thứ i trong xâu w wg[e] Trọng số của cung e trên otomat hoặc máy biến đổi wg[π] Trọng số của đƣờng đi π wg[(u, v)] Trọng số của cạnh (u, v) trên đồ thị  Bảng chữ cái * Tập hợp tất cả các từ trên bảng chữ cái  L Ngôn ngữ trên bảng chữ cái  L+ Lặp cắt của ngôn ngữ L L Tập các từ đảo ngƣợc của các từ thuộc ngôn ngữ L Lω ω - ngôn ngữ Các chữ viết tắt DL Damerau–Levenshtein LCS Xâu con chung dài nhất (Longest Common Subsequence) DANH MỤC CÁC BẢNG VÀ HÌNH VẼ Bảng 1.

Độ dài LCS của khúc đầu của x và y……………………………… 24 Hình 1. Hợp thành của otomat hữu hạn với máy biến đổi trên nửa vành Tropical………………………………………………………………………… 33 Hình 1. Mảng danh sách kề của đồ thị G…………………………………. Otomat có trọng số đoán nhận chuỗi hình thức.

Máy biến đổi  thực hiện Ψ* trên bảng chữ cái Ω ………………. Mở rộng kiểu 1 của otomat hữu hạn……………………………… 54 Hình 2. Máy biến đổi  thực hiện Ψ* trên bảng chữ cái Γ ………………. Tích hai otomat…………………………………………………….

Nhãn của đƣờng đi giữa hai trạng thái kế tiếp cùng dạng………. Tích hợp hai otomat………………………………………………. Hai kiểu hai ω -phân tích phải khác nhau của từ w……………… 69 Hình 3. Bốn kiểu hai Z-phân tích khác nhau của từ w…………………….

Tính độ trễ giải mã của L…………………………………………. 91 MỞ ĐẦU Lý thuyết otomat nghiên cứu về lớp các thuật toán  đối tƣợng quan trọng trong toán học và khoa học máy tính. Turing đã đề xuất vấn đề thuật toán có thể giải quyết bởi phƣơng tiện máy mà sau này gọi là máy Turing [66]. Pitts đã đề xuất mô hình toán học của tế bào thần kinh [47].

Kleene đã phát triển báo cáo RAND của ông năm 1951, trong đó mô hình của W. Pitts đã đƣợc đƣa ra dạng toán học chi tiết [36]. Các đề xuất này đƣợc xem là nền tảng của lý thuyết otomat. Otomat và ngôn ngữ đƣợc ứng dụng trong nhiều lĩnh vực nhƣ thiết kế mạch [54], thiết kế chƣơng trình dịch [12], biểu diễn biểu thức chính quy [27], tìm kiếm mẫu [21], xử lý ngôn ngữ tự nhiên [57], mã hóa thông tin [42], tạo chuỗi các con số [29], mô tả thuật toán trong lý thuyết nhóm [63], phát triển lý thuyết đại số của các ngôn ngữ đoán nhận trong phạm vi lý thuyết nửa nhóm hữu hạn [55], D.

Epstein cho thấy otomat là một công cụ quan trọng trong lý thuyết nhóm tổ hợp và hình học [26]… Ngôn ngữ có thể đƣợc biểu diễn bởi một tập các xâu, biểu thức chính quy, văn phạm, cây, otomat hay đồng cấu vị nhóm… Nhƣng ngôn ngữ biểu diễn bởi otomat đƣợc sử dụng khá rộng rãi vì tính đơn giản trong cài đặt. Ứng dụng khả năng biểu diễn ngôn ngữ của otomat, sử dụng các kỹ thuật trên otomat để thiết kế các thuật toán hiệu quả  có độ phức tạp thời gian đa thức bậc thấp, nhằm giải quyết các bài toán trọng tâm trong xử lý thông tin nhƣ: bài toán so mẫu xấp xỉ, bài toán kiểm định mã, nghiên cứu các đặc tính của mã, hay ngôn ngữ hình thức trong mối quan hệ với mã. Tăng tốc độ tính toán cho các thuật toán giải quyết các bài toán này, trong môi trƣờng bùng nổ thông tin là một vấn đề nghiên cứu mở, có tính thời sự và luôn thu hút sự quan tâm của cộng đồng nghiên cứu. Trong lĩnh vực khoa học máy tính, so mẫu xấp xỉ là một bài toán quan trọng đƣợc ứng dụng rộng rãi trong tìm kiếm, tính toán, trích rút thông tin, xử lý tín hiệu và nhận dạng.

So mẫu xấp xỉ là bài toán tìm sự xuất hiện của một mẫu trong văn bản, trong đó sự “khớp” giữa mẫu và xuất hiện của nó có thể chấp nhận một số “lỗi”. Mô hình lỗi đƣợc dùng phổ biến nhất là khoảng cách soạn thảo (edit distance) [52], các phép toán soạn thảo gồm phép xóa, chèn, thay thế một ký tự và đổi chỗ hai ký tự khác nhau liền kề. Do vai trò quan trọng của bài toán xấp xỉ, đã có nhiều công trình [11, 23, 30, 31, 32, 34, 35, 40, 51, 52, 71] nghiên cứu khoảng cách soạn thảo giữa hai xâu. Mohri đã giải quyết bài toán xác định khoảng cách soạn thảo Levenshtein (gồm ba phép toán soạn thảo là phép xóa, chèn, thay thế một ký tự) của hai otomat hữu hạn [48].

Không thể áp dụng một cách hiệu quả các phƣơng pháp cổ điển, hay áp dụng trực tiếp phƣơng pháp của M. Mohri để giải quyết bài toán xác định khoảng cách soạn thảo của hai ngôn ngữ, trong trƣờng hợp hai phép toán soạn thảo (phép xóa, chèn) hoặc bốn phép toán soạn thảo (phép xóa, chèn, thay thế một ký tự, đổi chỗ hai ký tự khác nhau liền kề). Từ đó, bài toán thứ nhất đặt ra là: cho hai otomat hữu hạn đoán nhận hai ngôn ngữ L1 và L2 (hữu hạn hoặc vô hạn) tương ứng. Sử dụng kỹ thuật otomat, có thể xây dựng phương pháp xác định xâu con chung dài nhất (phép toán soạn thảo gồm phép xóa, chèn), hay tập các xâu con chung dài nhất của hai ngôn ngữ L1 và L2, cũng như xác định khoảng cách soạn thảo Damerau–Levenshtein (phép toán soạn thảo gồm bốn phép nói trên) của hai ngôn ngữ L1 và L2, với các thuật toán có độ phức tạp thời gian là đa thức bậc thấp hay không? Lý thuyết mã bắt nguồn từ lý thuyết thông tin do C.

Những năm sau đó, lý thuyết mã phát triển theo nhiều hƣớng khác nhau xuất phát từ nhu cầu của thực tiễn. Một hƣớng nghiên cứu liên quan đến mã độ dài cố định, ứng dụng để phát hiện và sửa lỗi xuất hiện trên các kênh truyền tin. Schüzenberger đề xuất hƣớng nghiên cứu về mã có độ dài biến đổi. Từ đó, nhiều công trình đã nảy sinh, phát triển và nhận đƣợc những kết quả phong phú trong cả lý thuyết và ứng dụng.