Luận án tiến sĩ 'Một số vấn đề lý thuyết và ứng dụng của các mô hình otomat nâng cao' - Đặng Quyết Thắng, ĐHQG Hà Nội
Luận án tiến sĩ nghiên cứu mô hình otomat nâng cao ứng dụng trong toán học, tối ưu giải thuật và hiệu suất tính toán.
Luan An
Luận án tiến sĩ
Năm xuất bản
Số trang
107
Thời gian đọc
17 phút
Lượt xem
0
Lượt tải
0
Phí lưu trữ
40 Point
Tổng quan nhanh
- Chủ đề:
- Nền tảng Lý Thuyết Otomat Nâng Cao và Toán Học Ứng Dụng.
- Số trang:
- 107 trang
- Trường:
- Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
- Chuyên ngành:
- Bảo đảm toán học cho máy tính và hệ thống tính toán
- Tác giả:
- Đặng Quyết Thắng
- Năm:
- 2013
Tóm tắt nội dung luận án
I.
Luận án đặt nền tảng cho việc nghiên cứu otomat nâng cao. Các khái niệm cơ bản về lý thuyết otomat được trình bày. Cấu trúc đại số và ngôn ngữ hình thức là những yếu tố cốt lõi. Otomat hữu hạn được giới thiệu như mô hình tính toán cơ bản. Toán học rời rạc cung cấp công cụ cần thiết. Đồ thị hữu hạn được xem xét. Các giải thuật tìm đường đi ngắn nhất và biểu diễn đồ thị cũng được đề cập. Những kiến thức này là nền tảng vững chắc cho các chương tiếp theo. Chúng giúp xây dựng mô hình hóa toán học phức tạp. Luận án nhấn mạnh tầm quan trọng của việc nắm vững các kiến thức cơ bản. Điều này tạo điều kiện thuận lợi cho việc phát triển các mô hình tiên tiến. Lý thuyết otomat là một nhánh quan trọng trong khoa học máy tính lý thuyết. Các ứng dụng của nó rất đa dạng. Việc hiểu rõ các khái niệm này giúp ứng dụng hiệu quả vào toán học ứng dụng.
1.1. Khái niệm cơ bản về lý thuyết otomat.
Phần này giới thiệu các định nghĩa nền tảng của lý thuyết otomat. Otomat hữu hạn là một mô hình tính toán cơ bản. Nó có vai trò quan trọng trong việc hiểu các quá trình xử lý thông tin. Các thành phần của otomat được mô tả chi tiết. Chúng bao gồm tập trạng thái, bảng chữ cái, hàm chuyển tiếp và trạng thái kết thúc. Khái niệm về ngôn ngữ được chấp nhận bởi otomat cũng được làm rõ. Sự hiểu biết này là cần thiết để xây dựng các mô hình phức tạp hơn. Lý thuyết otomat cung cấp một khung làm việc vững chắc cho nhiều lĩnh vực.
1.2. Cấu trúc đại số và ngôn ngữ hình thức.
Cấu trúc đại số đóng vai trò nền tảng cho ngôn ngữ hình thức. Khái niệm bảng chữ cái và các từ trên bảng chữ cái được trình bày. Ngôn ngữ được định nghĩa là một tập hợp các từ. Các phép toán trên ngôn ngữ, như phép nối và phép lặp, được giới thiệu. Khoảng cách soạn thảo và xâu con chung dài nhất (LCS) là những khái niệm quan trọng. Chúng có ứng dụng rộng rãi trong tin học. Việc hình thức hóa các khái niệm này giúp phát triển các giải thuật hiệu quả. Ngôn ngữ hình thức là công cụ mạnh mẽ trong mô hình hóa toán học các hệ thống. Nó tạo điều kiện thuận lợi cho việc phân tích và thiết kế.
1.3. Đồ thị hữu hạn và giải thuật nền tảng.
Đồ thị hữu hạn là một công cụ mạnh mẽ trong toán học rời rạc. Nó được sử dụng để biểu diễn nhiều vấn đề. Các khái niệm cơ bản về đồ thị được trình bày. Chúng bao gồm đỉnh, cạnh, đường đi và chu trình. Các phương pháp biểu diễn đồ thị trong máy tính được thảo luận. Phương pháp ma trận kề và danh sách kề được so sánh. Các giải thuật tìm kiếm theo chiều sâu (DFS) cũng được giới thiệu. Giải thuật tìm đường đi ngắn nhất nguồn đơn là một ví dụ quan trọng. Những giải thuật này có vai trò thiết yếu. Chúng giúp phân tích cấu trúc và hành vi của các mô hình otomat.
II.
Luận án tập trung vào việc ứng dụng mô hình otomat nâng cao để giải quyết các bài toán về khoảng cách soạn thảo. Khoảng cách soạn thảo của hai ngôn ngữ được định nghĩa một cách hình thức. Nó mở rộng khái niệm khoảng cách soạn thảo truyền thống giữa hai xâu. Việc xác định xâu con chung dài nhất (LCS) giữa hai ngôn ngữ là một thách thức. Otomat cung cấp một phương pháp hiệu quả cho bài toán này. Chi phí của một dãy sánh LCS được tính toán. Khoảng cách Damerau–Levenshtein (DL) hạn chế cũng được nghiên cứu. Đây là một loại khoảng cách soạn thảo quan trọng khác. Các mô hình otomat được mở rộng để tính toán khoảng cách DL này. Cụ thể, 'mở rộng kiểu 1 của otomat' được giới thiệu. Nó giúp định lượng chi phí của một dãy sánh DL hạn chế. Nghiên cứu này cung cấp những giải thuật mới. Chúng cho phép phân tích và so sánh ngôn ngữ một cách chính xác hơn. Ứng dụng mô hình hóa toán học là chìa khóa để giải quyết các vấn đề phức tạp này. Các phương pháp này có thể áp dụng trong nhiều lĩnh vực.
2.1. Xác định xâu con chung dài nhất LCS .
Xâu con chung dài nhất (LCS) là một vấn đề cơ bản trong tin học. Luận án mở rộng khái niệm LCS từ xâu sang ngôn ngữ. Phương pháp hình thức hóa khái niệm LCS được mô tả. Một thuật toán được phát triển để tìm đường đi dài nhất nguồn đơn. Thuật toán này được sử dụng để xác định LCS của hai ngôn ngữ theo otomat. Việc này đòi hỏi việc thiết kế otomat đặc biệt. Các otomat này có khả năng theo dõi các quá trình so sánh. Chi phí của một dãy sánh LCS được tính toán. Nó cung cấp một thước đo định lượng về sự tương đồng. Các giải thuật này có ứng dụng trong sinh học phân tử và xử lý văn bản.
2.2. Khoảng cách Damerau Levenshtein hạn chế.
Khoảng cách Damerau-Levenshtein (DL) là một thước đo quan trọng về sự khác biệt giữa hai xâu. Luận án nghiên cứu khoảng cách DL hạn chế của hai ngôn ngữ. Khái niệm này được hình thức hóa chi tiết. Nó xem xét các phép biến đổi như chèn, xóa, thay thế và hoán vị. Mô hình otomat được sử dụng để xác định khoảng cách DL hạn chế. Một 'mở rộng kiểu 1 của otomat' được giới thiệu cho mục đích này. Nó cho phép tính toán chi phí của một dãy sánh DL hạn chế. Phương pháp này cung cấp một công cụ mạnh mẽ. Nó giúp phân tích sự tương đồng giữa các ngôn ngữ. Các giải thuật liên quan có thể ứng dụng trong kiểm lỗi chính tả và nhận dạng tiếng nói.
2.3. Mô hình otomat cho khoảng cách ngôn ngữ.
Các mô hình otomat được thiết kế để tính toán khoảng cách soạn thảo giữa các ngôn ngữ. Việc này đòi hỏi sự điều chỉnh và mở rộng lý thuyết otomat cơ bản. Otomat có trọng số được sử dụng để gán chi phí cho các phép biến đổi. Luận án trình bày cách thức otomat có thể nhận diện các dãy sánh. Mỗi dãy sánh tương ứng với một chi phí nhất định. Việc tìm kiếm dãy sánh có chi phí tối thiểu là mục tiêu chính. Các giải thuật được phát triển dựa trên cấu trúc của otomat. Chúng cung cấp một phương pháp hệ thống. Điều này giúp định lượng sự khác biệt giữa hai ngôn ngữ. Mô hình hóa toán học là nền tảng của phương pháp này. Nó cho phép xử lý các vấn đề phức tạp một cách hiệu quả.
III.
Luận án khám phá việc kiểm định các loại mã khác nhau bằng cách sử dụng các mô hình otomat mở rộng. Các phép toán trên otomat được định nghĩa. Chúng bao gồm lưởng cực hóa và các loại mở rộng otomat mới. Cụ thể, 'mở rộng kiểu 2 và kiểu 3 của otomat' được giới thiệu. Những mở rộng này tăng cường khả năng biểu diễn của otomat. Chúng cho phép otomat xử lý các vấn đề phức tạp hơn trong lý thuyết mã. Sự tồn tại đường đi kiểu 1 và kiểu 2 trong otomat được phân tích. Các khái niệm này liên quan trực tiếp đến việc kiểm định tính chất của mã. Luận án đặc biệt tập trung vào kiểm định ω-mã và Z-mã. Phương pháp sử dụng otomat cho phép xác định các thuộc tính này một cách hiệu quả. Việc tích hợp otomat là một kỹ thuật quan trọng. Nó giúp xây dựng các mô hình phức tạp hơn. Các giải thuật được phát triển dựa trên các mô hình otomat này. Chúng cung cấp các công cụ mạnh mẽ để phân tích ngôn ngữ hình thức và mã. Mô hình tính toán này rất có giá trị trong lý thuyết truyền tin và an toàn thông tin.
3.1. Các phép toán và mở rộng trên otomat.
Để kiểm định mã, cần thực hiện các phép toán và mở rộng trên otomat. Phép toán lưỡng cực hóa được giới thiệu. Nó chuyển đổi otomat để phân tích các thuộc tính đối xứng. Các 'mở rộng kiểu 2 và kiểu 3 của otomat' được mô tả chi tiết. Những mở rộng này tăng cường cấu trúc của otomat. Chúng cho phép otomat xử lý các mẫu phức tạp hơn. Sự tồn tại đường đi kiểu 1 và kiểu 2 trong otomat được nghiên cứu. Các khái niệm này có ý nghĩa quan trọng trong việc xác định tính chất của ngôn ngữ. Các phép toán và mở rộng này là cần thiết. Chúng giúp otomat có thể phân tích sâu hơn các mã.
3.2. Kiểm định ω mã bằng phương pháp otomat.
ω-mã là một loại mã quan trọng trong lý thuyết ngôn ngữ hình thức. Luận án trình bày phương pháp kiểm định ω-mã bằng otomat. Các otomat đặc biệt được thiết kế. Chúng có khả năng nhận diện và phân tích các chuỗi vô hạn. Otomat mở rộng được sử dụng để kiểm tra các thuộc tính của ω-mã. Các giải thuật được xây dựng để xác định xem một ngôn ngữ có phải là ω-mã hay không. Việc này dựa trên cấu trúc và hành vi của otomat. Phương pháp này cung cấp một công cụ toán học chính xác. Nó giúp đánh giá tính đúng đắn và hiệu quả của ω-mã trong các ứng dụng. Mô hình tính toán này có vai trò lớn.
3.3. Phân tích Z mã qua tích hợp otomat.
Z-mã là một loại mã khác được nghiên cứu trong luận án. Việc kiểm định Z-mã đòi hỏi một cách tiếp cận phức tạp hơn. Kỹ thuật tích hợp otomat được áp dụng. Nó cho phép kết hợp nhiều otomat lại với nhau. Điều này tạo ra một mô hình tính toán mạnh mẽ hơn. Mô hình otomat tích hợp có khả năng phân tích các thuộc tính của Z-mã. Các giải thuật được phát triển để xác định tính chất của Z-mã. Chúng dựa trên sự tồn tại của các đường đi đặc biệt trong otomat. Phương pháp này cung cấp một cách hệ thống. Nó giúp kiểm tra tính hợp lệ và hiệu quả của Z-mã. Các kết quả này có thể áp dụng trong lý thuyết mã hóa và truyền dữ liệu.
IV.
Luận án tiếp tục mở rộng ứng dụng của lý thuyết otomat vào việc phân tích các thuộc tính quan trọng của ngôn ngữ hình thức. Độ không nhập nhằng của ngôn ngữ là một thuộc tính cơ bản. Nó liên quan đến việc mỗi từ có thể được sinh ra bằng một cách duy nhất hay không. Khái niệm này được xác định một cách hình thức. Để phân tích độ không nhập nhằng, các 'mở rộng kiểu 4 và kiểu 5 của otomat' được giới thiệu. Những otomat này được thiết kế để xử lý các vấn đề liên quan đến tính duy nhất của việc sinh từ. Giá của đường đi kiểu 2 và sự tồn tại đường đi kiểu 3 cũng được phân tích. Các khái niệm này cung cấp cơ sở để xác định độ không nhập nhằng. Ngoài ra, luận án còn xác định độ trễ giải mã. Độ trễ giải mã là một yếu tố quan trọng trong các hệ thống truyền thông. Nó ảnh hưởng đến hiệu quả của quá trình giải mã. Otomat được sử dụng để định lượng độ trễ này. Các giải thuật được phát triển dựa trên các mô hình otomat nâng cao. Chúng cung cấp các phương pháp chính xác và hiệu quả. Các phương pháp này hỗ trợ việc thiết kế các hệ thống truyền thông mạnh mẽ và đáng tin cậy. Mô hình hóa toán học đóng vai trò trung tâm.
4.1. Khái niệm độ không nhập nhằng ngôn ngữ.
Độ không nhập nhằng của ngôn ngữ là một khái niệm quan trọng. Một ngôn ngữ được gọi là không nhập nhằng nếu mỗi từ trong ngôn ngữ đó chỉ có một cách sinh duy nhất. Luận án hình thức hóa khái niệm này. Nó cung cấp một khung làm việc để phân tích tính chất này. Việc xác định độ không nhập nhằng có ý nghĩa lớn trong thiết kế trình biên dịch và xử lý ngôn ngữ tự nhiên. Otomat được sử dụng như một công cụ để kiểm tra tính duy nhất. Các mô hình otomat nâng cao giúp phát hiện các trường hợp nhập nhằng. Điều này đảm bảo tính toàn vẹn của các cấu trúc ngôn ngữ.
4.2. Mở rộng otomat kiểu 4 và kiểu 5.
Để phân tích độ không nhập nhằng và độ trễ giải mã, cần có các mô hình otomat mạnh hơn. Các 'mở rộng kiểu 4 và kiểu 5 của otomat' được giới thiệu. Những mở rộng này bổ sung các tính năng mới cho otomat. Chúng cho phép otomat xử lý các thông tin phức tạp hơn về cấu trúc ngôn ngữ. Cụ thể, chúng giúp theo dõi các đường đi sinh từ. Giá của đường đi kiểu 2 và sự tồn tại đường đi kiểu 3 được phân tích. Những yếu tố này là cơ sở để xác định độ không nhập nhằng. Việc phát triển các otomat mở rộng này là một đóng góp quan trọng của luận án. Chúng cung cấp các công cụ mới trong lý thuyết otomat.
4.3. Xác định trễ giải mã hiệu quả.
Độ trễ giải mã là một vấn đề then chốt trong các hệ thống truyền thông và mã hóa. Nó ảnh hưởng trực tiếp đến hiệu suất của hệ thống. Luận án sử dụng otomat để xác định độ trễ giải mã. Các mô hình otomat được thiết kế để phân tích quá trình giải mã. Chúng giúp định lượng thời gian cần thiết để giải mã một cách không nhập nhằng. Các giải thuật được xây dựng dựa trên otomat mở rộng. Chúng cho phép tính toán độ trễ giải mã một cách hiệu quả. Việc xác định chính xác độ trễ này giúp tối ưu hóa các hệ thống truyền dữ liệu. Nó cải thiện tốc độ và độ tin cậy của giao tiếp.
V.
Luận án đã trình bày những đóng góp quan trọng trong lý thuyết otomat nâng cao và các ứng dụng của nó. Nghiên cứu mở rộng các mô hình otomat truyền thống. Nó đưa ra các phương pháp mới để giải quyết các bài toán phức tạp trong toán học ứng dụng. Các vấn đề về khoảng cách soạn thảo, kiểm định mã, độ không nhập nhằng và độ trễ giải mã đã được giải quyết bằng otomat. Điều này chứng tỏ sức mạnh của mô hình hóa toán học dựa trên lý thuyết otomat. Các giải thuật được phát triển cung cấp công cụ hiệu quả cho các nhà khoa học. Chúng có thể áp dụng trong nhiều lĩnh vực như khoa học máy tính, xử lý ngôn ngữ tự nhiên, an toàn thông tin và sinh học tin học. Tiềm năng ứng dụng của otomat vượt xa các lĩnh vực truyền thống. Nó có thể tích hợp với các công nghệ mới như Học máy (Machine Learning). Các mô hình tính toán này có thể đóng vai trò quan trọng trong việc phát triển trí tuệ nhân tạo. Luận án mở ra nhiều hướng nghiên cứu tiếp theo. Chúng tập trung vào việc phát triển các otomat mạnh mẽ hơn. Việc ứng dụng các otomat này vào giải quyết các vấn đề thực tiễn là trọng tâm. Công trình khẳng định tầm quan trọng của otomat trong khoa học hiện đại.
5.1. Đóng góp lý thuyết của mô hình otomat nâng cao.
Luận án đã đóng góp vào việc mở rộng lý thuyết otomat. Các khái niệm về otomat mở rộng kiểu 1, 2, 3, 4, 5 được giới thiệu. Những mở rộng này tăng cường khả năng biểu diễn và tính toán của otomat. Chúng cho phép otomat xử lý các vấn đề phức tạp hơn. Việc hình thức hóa các khái niệm như khoảng cách DL hạn chế và độ không nhập nhằng ngôn ngữ là một đóng góp quan trọng. Các giải thuật mới được phát triển để giải quyết các vấn đề này. Những đóng góp này làm phong phú thêm kho tàng kiến thức về mô hình tính toán. Chúng cung cấp các công cụ lý thuyết mạnh mẽ cho nghiên cứu tiếp theo.
5.2. Tiềm năng ứng dụng trong các lĩnh vực khác.
Các mô hình otomat nâng cao có tiềm năng ứng dụng rộng rãi. Chúng có thể được sử dụng trong xử lý ngôn ngữ tự nhiên, chẳng hạn như nhận dạng giọng nói và dịch máy. Trong sinh học tin học, otomat có thể giúp phân tích chuỗi DNA và protein. An toàn thông tin cũng là một lĩnh vực tiềm năng. Otomat có thể được sử dụng để kiểm định giao thức và phát hiện các mối đe dọa. Hơn nữa, việc tích hợp otomat với Học máy (Machine Learning) có thể mở ra những hướng đi mới. Các mô hình otomat có thể cung cấp cấu trúc rõ ràng. Điều này giúp tăng cường khả năng học hỏi và suy luận của hệ thống AI. Khả năng mô hình hóa toán học của otomat là vô giá.
5.3. Hướng nghiên cứu tiếp theo về otomat và ML.
Luận án gợi mở nhiều hướng nghiên cứu tiếp theo. Một hướng quan trọng là phát triển các mô hình otomat mạnh mẽ hơn. Chúng có thể xử lý các ngôn ngữ phi hình thức hoặc dữ liệu không chắc chắn. Việc kết hợp lý thuyết otomat với Học máy (Machine Learning) là một hướng đi đầy hứa hẹn. Otomat có thể được sử dụng để học các mẫu ngôn ngữ. Chúng có thể tăng cường khả năng giải thích của các mô hình ML. Nghiên cứu cũng có thể tập trung vào việc tối ưu hóa các giải thuật. Điều này giúp cải thiện hiệu suất của otomat trong các ứng dụng thời gian thực. Việc mở rộng các mô hình otomat tế bào cũng là một lĩnh vực thú vị. Các nghiên cứu này sẽ tiếp tục khẳng định tầm quan trọng của otomat.
Mục lục chi tiết luận án
Tải xuống file đầy đủ để xem toàn bộ nội dung
Tải đầy đủ (107 trang)Trích đoạn nội dung luận án
Tải xuống để đọc toàn bộĐẠ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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ĐẠ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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 .32 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Đồ 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 .58 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 3. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ
Trích dẫn luận án này
Đặng Quyết Thắng (2013). Luận án tiến sĩ: Mô hình otomat nâng cao trong toán học ứng dụng [Luận án tiến sĩ, Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội]. LuanAn.net. https://luanan.net/toan-hoc/toan-ung-dung/luan-an-tien-si-mo-hinh-otomat-nang-cao-dang-quyet-thang
Câu hỏi thường gặp
Luận án "Luận án tiến sĩ: Mô hình otomat nâng cao trong toán học ứng dụng" nghiên cứu về vấn đề gì?
Luận án tiến sĩ nghiên cứu mô hình otomat nâng cao ứng dụng trong toán học, tối ưu giải thuật và hiệu suất tính toán.
Luận án "Luận án tiến sĩ: Mô hình otomat nâng cao trong toán học ứng dụng" được bảo vệ tại trường nào?
Luận án này được bảo vệ tại Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội. Năm bảo vệ: 2013.
Luận án "Luận án tiến sĩ: Mô hình otomat nâng cao trong toán học ứng dụng" thuộc chuyên ngành gì?
Luận án "Luận án tiến sĩ: Mô hình otomat nâng cao trong toán học ứng dụng" thuộc chuyên ngành Bảo đảm toán học cho máy tính và hệ thống tính toán. Danh mục: Toán Ứng Dụng.
Luận án "Luận án tiến sĩ: Mô hình otomat nâng cao trong toán học ứng dụng" có bao nhiêu trang?
Luận án "Luận án tiến sĩ: Mô hình otomat nâng cao trong toán học ứng dụng" có 107 trang. Bạn có thể xem trước một phần tài liệu ngay trên trang web trước khi tải về.
Cách tải luận án "Luận án tiến sĩ: Mô hình otomat nâng cao trong toán học ứng dụng" về máy như thế nào?
Để tải luận án về máy, bạn nhấn nút "Tải xuống ngay" trên trang này, sau đó hoàn tất thanh toán phí lưu trữ. File sẽ được tải xuống ngay sau khi thanh toán thành công. Hỗ trợ qua Zalo: 0559 297 239.