- 1 TÓM TẮT LUẬN VĂN THẠC SĨ Đề tài: Ngôn Ngữ từ vô hạn và mã Tác giả luận văn: Nguyễn Thị Tý Khóa: CH2014B Người hướng dẫn: TS. - Lý thuyết mã bắt nguồn từ lý thuyết thông tin do C.E.Shannon khởi xướng đã đặt nền móng toán học cho lý thuyết thông tin hiện đại. - Do nhu cầu thực tiễn, lý thuyết mã phát triển theo nhiều hướng khác nhau, chẳng hạn như hướng nghiên cứu liên quan đến mã độ dài cố định, hay mã độ dài biến đổi, mã hữu hạn của từ vô hạn. - Để đáp ứng được các yêu cầu đòi hỏi khắt khe của các hệ thống đối với mỗi bài toán, mỗi ứng dụng đặt ra vấn đề về chất lượng, độ chính xác, độ ổn định, thời gian đáp ứng của hệ thống thì việc nghiên cứu, tìm hiểu các công cụ kỹ thuật, công cụ lập trình, thuật toán mô phỏng là rất cần thiết. - Cho đến nay, qua công trình tổng quan của Augros và Litovsky về các thuật toán kiểm định ω-mã, thuật toán tốt nhất kiểm định một ngôn ngữ chính quy X cho trước có là ω-mã có độ phức tạp thời gian 𝒪(n3) với n là cỡ của vị nhóm các phép chuyển dịch của otomat đơn định tối tiểu đoán nhận X. - Đề tài của luận văn “Ngôn ngữ từ vô hạn và mã” có ý nghĩa thực tiễn và thời sự cao, có khả năng phát triển cả về mặt lý thuyết và ứng dụng trong thực tế. - Dựa trên các thành tựu của đại số, lý thuyết otomat và lý thuyết mã của các từ hữu hạn, thiết lập các thuật toán kiểm định ω-mã trên ngôn ngữ, trên vị nhóm và trên đồ thị. - Sử dụng phương pháp và công cụ của đại số, otomat hữu hạn, lý thuyết về otomat để làm công cụ và phương tiện sử dụng nghiên cứu. - Chương 1: Khái niệm và kết quả liên quan Trình bày các kiến thức cơ sở được sử dụng trong luận văn. - Cụ thể sẽ nhắc lại một số khái niệm về cấu trúc đại số cơ bản, đồng cấu, từ và ngôn ngữ. - ngôn ngữ chính quy và otomat hữu hạn. - Chương 2: Mã của các từ hữu hạn Chương này trình bày một số khái niệm và tính chất cơ bản của mã bao gồm mã và vị nhóm tự do, thủ tục kiểm tra tính chất mã, mối quan hệ giữa lý thuyết mã với đại số, thuật toán Sardinas – Patterson cải tiến để kiểm tra tính chất mã của ngôn ngữ chính quy, độ trễ giải mã. - Chương 3: Mã của các từ vô hạn Chương 3 trình bày các khái niệm về từ và ngôn ngữ từ vô hạn, ω- mã, thuật toán kiểm định ω-mã trên ngôn ngữ, thuật toán kiểm định ω-mã trên vị nhóm, thuật toán kiểm định ω-mã trên đồ thị. - Đóng góp mới của luận văn: Luận văn đề xuất các thuật toán mới kiểm tra một ngôn ngữ X có phải là ω - mã hay không với độ phức tạp thời gian là 𝒪(n2). - Các kết quả chính của luận văn. - Trình bày lại một số khái niệm và tính chất cơ bản của đại số, ngôn ngữ chính quy và otomat - Trình bày các tính chất cơ bản của mã, mối quan hệ giữa lý thuyết mã với đại số, thuật toán Sardinas – Patterson cải tiến để kiểm tra tính chất mã, thuật toán tính độ trễ giải mã. - Trình bày các khái niệm từ và ngôn ngữ từ vô hạn, ω – mã - Đề xuất thuật toán kiểm định ω-mã trên ngôn ngữ, thuật toán kiểm định ω-mã trên vị nhóm, thuật toán kiểm định ω-mã trên đồ thị Với các thuật toán đã đề xuất trong luận văn, tác giả mong muốn đóng góp một phần nhỏ vào việc xây dựng các thuật toán kiểm định mã mới, làm giảm đáng kể độ phức tạp so với các thuật toán trước đó. - Hướng phát triển Ứng dụng otomat hữu hạn vào việc thiết lập các thuật toán kiểm định tính chất mã của các lớp mã khác như mã bao trùm, mã luân phiên, mã tích trộn và tính toán độ trễ giả mã của chúng. - Tiếp tục cải tiến thuật toán để làm giảm độ phức tạp hơn nữa so với thuật toán được trình bày trong luận văn.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt