Về một cấu trúc vị nhóm mới và mã

- HỒ NGỌC VINH VỀ MỘT CẤU TRÚC VỊ NHÓM MỚI VÀ MÃ Chuyên ngành: Đảm bảo toán học cho máy tính và các hệ thống tính toán Mã số LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2012 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI.
- HỒ NGỌC VINH VỀ MỘT CẤU TRÚC VỊ NHÓM MỚI VÀ MÃ Chuyên ngành: Đảm bảo toán học cho máy tính và các hệ thống tính toán Mã số LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1.
- Phan Trung Huy Hà Nội LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, chưa từng được công bố trong bất kỳ một công trình khoa học của ai khác.
- 6 CHƯƠNG 1 : KHÁI NIỆM VÀ KẾT QUẢ LIÊN QUAN.
- 12 1.1 Một số khái niệm.
- 12 1.1.2 Đồng cấu.
- 13 1.1.3 Từ và ngôn ngữ.
- 14 1.1.4 Ngôn ngữ chính quy và Otomat hữu hạn.
- 15 1.2 Mã và các tính chất của mã.
- 21 1.2.1 Mã và vị nhóm tự do.
- 27 2.2 Mã luân phiên.
- 30 2.3 Đặc trưng của mã luân phiên.
- 36 CHƯƠNG 3 : -NGÔN NGỮ CHÍNH QUY VÀ OTOMAT MỞ RỘNG.
- 47 3.1 Từ định biên.
- 47 3.2 -ngôn ngữ chính quy.
- 53 3.3 Vị nhóm biểu diễn -ngôn ngữ.
- 65 - 3 - CHƯƠNG 4 : MÃ VỚI TỪ ĐỊNH BIÊN.
- 71 4.1 Mã với từ định biên.
- 71 4.2 Thuật toán kiểm tra -mã.
- 80 4.3 Thuật toán kiểm tra -mã chặt.
- 89 4.4 Thuật toán xác định độ trễ giải mã cho -mã.
- 109 - 4 - DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Từ viết tắt Giải nghĩa LC Lớp mã thông thường LALT Lớp mã luân phiên LWLALT Lớp mã luân phiên yếu trái LWRALT Lớp mã luân phiên yếu phải LEALT Lớp mã luân phiên chẵn LC Lớp -mã LWLC Lớp -mã yếu trái LWRC Lớp -mã yếu phải LSC Lớp -mã chặt SPC Thủ tục kiểm tra -mã (the Sardinas−Patterson for Codes of bounded words) MSPC Thủ tục kiểm tra -mã mở rộng (the Modification of Sardinas−Patterson for Codes of bounded words) SPSC Thủ tục kiểm tra -mã chặt (the Sardinas−Patterson for Strict Codes of bounded words.
- Quan hệ của các lớp mã đã xét trên A.
- Otomat A đoán nhận ngôn ngữ b*a.
- Phân bậc của các lớp mã.
- -ngôn ngữ có độ trễ giải mã hữu hạn d.
- 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, điển hình là mã sửa sai, ứ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.
- hay một hướng nghiên cứu khác có liên quan đến mã độ dài biến đổi, được nghiên cứu đầu tiên bởi Schüzenberger.
- Một số bài toán cơ bản trong nghiên cứu lý thuyết mã là: các tính chất liên quan đến sự phân tích một từ thành dãy các từ thuộc một tập cho trước.
- tính chất không nhập nhằng của ngôn ngữ trong quan hệ với mã.
- mã trong mối quan hệ với đại số, tổ hợp trên từ, lý thuyết ngôn ngữ hình thức và otomat.
- Bảo mật thông tin là một hướng nghiên cứu luôn được nhiều người quan tâm nhằm xây dựng những hệ mật mã với độ an toàn cao, nhưng cho đến nay vẫn chưa có một hệ mật mã nào có thể có độ an toàn tuyệt đối.
- Đây là động lực quan trọng thúc đẩy sự liên tục phải cải tiến, nghiên cứu xây dựng các hệ mã mới, cả về khía cạnh lý thuyết cũng như thực hành.
- Gần đây, một xu hướng mới trong nghiên cứu lý thuyết mã là các tác giả đưa vào xét các yếu tố điều khiển, nhập nhằng, đa trị để mở rộng khái niệm tích, từ đó cho phép xây dựng những lớp mã mới.
- Phân tích zigzag [34] là một tiếp cận mở rộng khái niệm tích, được đề xuất bởi M.
- Các vấn đề cơ bản đối với mã truyền thống như - 7 - đồng cấu mã, kiểm tra tính chất mã đã được nghiên cứu cho trường hợp Z-mã bởi Đỗ Long Vân, B.
- Các đặc trưng đại số của tích trộn và mã theo tích trộn đã được nghiên cứu bởi A.
- Nam đã đề xuất các hình thức mã mới, là mã của một cặp hai ngôn ngữ (mã luân phiên, mã luân phiên chẵn) dựa vào phân tích luân phiên của hai ngôn ngữ trên một bảng chữ và thiết lập được một số tính chất cơ sở ban đầu về hai lớp mã mới này.
- Mã luân phiên, mã luân phiên chẵn là một phát triển mở rộng tự nhiên, nhưng không tầm thường của mã truyền thống.
- Trong khi mỗi mã truyền thống là một ngôn ngữ X trên một bộ chữ nào đó thì mã luân phiên, mã luân phiên chẵn là một cặp {X,Y} của hai ngôn ngữ mà mỗi một trong chúng không nhất thiết phải là một mã truyền thống.
- Mặt khác, nếu X là một mã truyền thống thì {X, X} là một mã luân phiên chẵn.
- Như vậy mã luân phiên, mã luân phiên chẵn là một mở rộng thực sự của mã truyền thống, hứa hẹn một khả năng ứng dụng rộng rãi hơn và khả năng thúc đẩy phát triển các nghiên cứu mới, sâu sắc hơn về ngôn ngữ nói chung, lý thuyết mã nói riêng.
- Mã từ định biên được đề xuất trong luận án cũng nảy sinh từ nhu cầu nghiên cứu, xây dựng các thuật toán kiểm định mã luân phiên, mã luân phiên chẵn.
- Thật ra, thể hiện của một số hệ mã luân phiên, mã luân phiên chẵn cụ thể đã xuất hiện và được sử dụng từ lâu trong thực tiễn như trong việc biểu diễn thông tin trong máy tính, trong phông chữ Unicode, trong mã sửa sai,… nhưng chưa được đề cập nghiên cứu trong lý thuyết mã trước - 8 - đây.
- Đó chính là những gợi ý ban đầu và là động lực cho việc nghiên cứu mã luân phiên, mã luân phiên chẵn về mặt lý thuyết như một bộ phận của Lý thuyết mã nói riêng và Ngôn ngữ hình thức nói chung.
- Nam, một câu hỏi tự nhiên đặt ra là một hệ gồm bốn điều kiện (trong Định lý 2.3.4) có thiết yếu hay không?.
- có thể xây dựng các tiêu chuẩn cần và đủ để kiểm tra mã luân phiên đơn giản hơn hay không?.
- Một kết quả của luận án chỉ ra rằng 4 điều kiện đặc trưng của mã luân phiên trong Định lý 2.3.4 đã nêu là độc lập, nghĩa là thiết yếu, thể hiện sự khó khăn khi cần thiết lập một thuật toán để kiểm tra một cặp ngôn ngữ chính quy cho trước có là mã luân phiên hay không nếu dùng định lý này.
- Các tiếp cận mở rộng khái niệm tích đã gợi mở hướng nghiên cứu của luận án.
- Trong đó, các yếu tố biên của từ được đưa vào làm cơ sở xây dựng các loại tích mới theo biên của một dạng từ mới (tích biên trên các từ định biên) và từ đó đề xuất, nghiên cứu các lớp mã mới theo các tích này.
- Với các lớp mã mới, luận án đã cho ta câu trả lời khẳng định đối với câu hỏi thứ hai nhờ đưa ra một mô tả khác của mã luân phiên, luân phiên chẵn dựa trên các từ định biên và cho phép biểu diễn mã luân phiên một cách đơn giản, giảm độ phức tạp của thuật toán kiểm định mã luân phiên so với thuật toán kiểm tra trực tiếp hệ 4 điều kiện trong Định lý 2.3.4.
- Từ việc nghiên cứu các lớp mã từ định biên, cho phép ta nhận được một sơ đồ phân bậc tổng quát các lớp mã đã xét (xem thêm Hình 4.1), trong đó chỉ ra rằng mã truyền thống, mã luân phiên và -mã chặt là các lớp mã cực tiểu.
- Luận án đã tập trung nghiên cứu và giải quyết các vấn đề sau: 1) Xem xét và thiết lập mới một số tính chất cùng với đặc trưng cần và đủ đối với các lớp mã dựa trên tích luân phiên.
- 2) Đề xuất khái niệm từ định biên, từ đó xây dựng hình thức tích mới (tích biên) trên tập các từ định biên A.
- 9 - 3) Nghiên cứu lớp ngôn ngữ của các từ định biên trên A.
- đặc biệt là lớp ngôn ngữ chính quy của các từ định biên trong mối liên hệ với đại số và otomat thông qua các hình thức -otomat.
- 4) Nghiên cứu các lớp mã mới dựa trên tích biên, mối quan hệ của nó với mã, mã luân phiên, mã luân phiên yếu trái (yếu phải), mã luân phiên chẵn và các bài toán cơ bản cho trường hợp lớp mã mới.
- 5) Nghiên cứu độ trễ giải mã của lớp mã mới và thiết lập thuật toán xác định độ trễ giải mã cho lớp mã mới đã đề xuất ở trên.
- Chương 1 – Khái niệm và kết quả liên quan.
- Chương này nhắc lại các khái niệm cơ sở về đại số, ngôn ngữ chính quy và otomat, trình bày mối liên hệ giữa ngôn ngữ với đại số.
- Phần tiếp theo của chương giới thiệu về lý thuyết mã, vị nhóm tự do, mối quan hệ giữa mã với vị nhóm tự do, thủ tục kiểm tra một ngôn ngữ cho trước có là mã hay không.
- Các chương tiếp theo trình bày các kết quả nghiên cứu chính của luận án.
- Chương 2 – Mã luân phiên.
- Trong lý thuyết mã, yếu tố nhập nhằng đa trị sử dụng yếu tố ngữ cảnh như là tín hiệu nhiễu chèn vào tích các từ, là một xu hướng được nhiều người quan tâm.
- Trong chương này, nhắc lại khái niệm tích không nhập nhằng, mối quan hệ giữa tích không nhập nhằng và mã, khái niệm mã luân phiên chẵn, mã luân phiên.
- Từ đó đề xuất hai lớp mã mới dựa trên tích luân phiên (mã luân phiên yếu trái, mã luân phiên yếu phải) và thiết lập mới một số tính chất của tích không nhập nhằng, mã luân phiên chẵn, mã luân phiên yếu trái (yếu phải), mã luân phiên trong quan hệ với mã, đồng cấu mã.
- Các kết quả chính được thể hiện trong Mệnh đề 2.2.13 về mã luân phiên chẵn, mã luân phiên trong quan hệ với phép đồng cấu.
- các Định lý 2.3.1, Định lý 2.3.2, Định lý 2.3.3, Định lý 2.3.4 về các đặc trưng cần và đủ để một cặp ngôn ngữ X, Y cho trước có là mã luân phiên chẵn, mã luân phiên yếu trái (yếu phải), mã luân phiên hay không.
- 10 - Chương 3 – -ngôn ngữ chính quy và otomat mở rộng.
- Nếu như trong Chương 2, các lớp mã được biểu diễn theo tích luân phiên của hai ngôn ngữ thuộc A+ thì trong Chương 3 này, luận án trình bày hình thức tích luân phiên theo quan điểm đại số trên dạng từ mới - từ định biên và tích của các từ định biên trên tập các từ định biên A.
- Từ đó, cho phép ta đề xuất các khái niệm -ngôn ngữ chính quy, -otomat, -đoán nhận được và nhận được một số kết quả rất cơ bản về -ngôn ngữ chính quy trên A.
- (Định lý 3.3.8, -ngôn ngữ chính quy trong quan hệ với -otomat đa định (đơn định) hữu hạn, -đồng cấu vị nhóm).
- Chương 4 – Mã với từ định biên.
- Chương này đưa ra bốn lớp mã mới (-mã, -mã yếu trái, -mã yếu phải, -mã chặt) dựa trên tích của các từ định biên trên A* và biểu diễn lớp mã, mã luân phiên, mã luân phiên yếu trái (yếu phải), mã luân phiên chẵn dưới góc độ các phép toán đại số, cấu trúc đại số mới trên các từ định biên.
- Từ đó, thiết lập mối quan hệ giữa -mã, -mã yếu trái (yếu phải), -mã chặt với mã luân phiên chẵn, mã luân phiên yếu trái (yếu phải), mã luân phiên qua các Định lý 4.1.13, Định lý 4.1.14, Định lý 4.1.15, Định lý 4.1.16 và xây dựng hai thuật toán kiểm tra tính chất mã của -mã, -mã chặt của một -ngôn ngữ chính quy cho trước cùng với đánh giá độ phức tạp của chúng.
- Hệ quả 4.2.14 và Hệ quả 4.3.7 đóng vai trò cơ sở cho phép đề xuất hai thuật toán hiệu quả kiểm tra một cặp ngôn ngữ X, Y cho trước có là mã luân phiên chẵn, mã luân phiên hay không, với độ phức tạp thấp hơn so với hai thuật toán được thiết lập trực tiếp nếu dựa vào các Định lý 2.3.1, Định lý 2.3.4.
- Hội thảo quốc gia lần thứ XII “Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông”, Biên Hòa .
- Hội thảo khoa học quốc gia lần thứ IV “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin” (FAIR 2009), Hà nội .
- Hội thảo quốc gia lần thứ XIII “Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông”, Hưng Yên .
- Tác giả xin bày tỏ lòng biết ơn sâu sắc đối với các thầy hướng dẫn, những người thầy đã chỉ bảo tận tình, chỉ ra hướng nghiên cứu lý thú để có được kết quả trong luận án này.
- Tác giả xin bày tỏ lòng biết ơn đến gia đình, bạn bè, Ban Giám hiệu Trường Đại học Sư phạm Kỹ thuật Vinh, các thầy cô giáo và các bạn đồng nghiệp Khoa CNTT đã tạo điều kiện thuận lợi và giúp đỡ tác giả trong quá trình học tập, nghiên cứu.
- Cụ thể sẽ nhắc lại một số khái niệm và tính chất cơ bản của mã, mối quan hệ giữa lý thuyết mã với đại số, ngôn ngữ hình thức, otomat.
- 1.1 Một số khái niệm 1.1.1 Cấu trúc đại số cơ bản Cho M là một tập.
- Một phép toán hai ngôi trên M là một ánh xạ T : M × M → M.
- 13 - Một tập khác rỗng M được gọi là vị nhóm nếu M là một nửa nhóm và có phần tử đơn vị.
- Một phần tử x của vị nhóm M được gọi là khả nghịch nếu tồn tại phần tử x.
- Một vị nhóm được gọi là nhóm nếu mỗi phần tử của nó đều khả nghịch.
- 1.1.2 Đồng cấu Một cách tổng quát, một đồng cấu giữa hai cấu trúc đại số là một ánh xạ bảo toàn các phép toán.
- Nghĩa là, một đồng cấu nửa nhóm là một ánh xạ ϕ từ một nửa nhóm M vào một nửa nhóm N sao cho ∀m1, m2 ∈M ϕ(m1m2.
- ϕ(m1)ϕ(m2) (1.1) Nếu M = N thì đồng cấu ϕ gọi là tự đồng cấu.
- Nếu ϕ là đơn ánh (t.ứng, toàn ánh, song ánh) thì gọi là đơn cấu (t.ứng, toàn cấu, đẳng cấu), một tự đồng cấu song ánh gọi là một tự đẳng cấu.
- Tương tự, một đồng cấu vị nhóm là một ánh xạ ϕ từ một vị nhóm M vào một vị nhóm N thỏa mãn điều kiện (1.1) và ϕ(1M.
- Một đồng cấu ϕ : M → N là một đẳng cấu nếu tồn tại một đồng cấu β : N → M sao cho ϕ ◦β = IdN và β ◦ϕ = IdM.
- 14 - 1.1.3 Từ và ngôn ngữ Cho tập hợp các ký tự A gọi là bảng chữ cái.
- Một từ w trên A là một xâu hữu hạn các phần tử của A, w = (a1, a2.
- Một ngôn ngữ (hình thức) L là một tập hợp các từ của bảng chữ cái A nào đó.
- an) Mỗi phần tử a ∈A được gọi là một chữ cái.
- Khi đó: ∈=∑aa Aw w (1.4) Ta nói, từ w ∈A* là một khúc con (factor) của một từ x ∈A* nếu ∃u, v ∈ A* sao cho: x = uwv.
- Một từ w ∈A* là một khúc đầu (prefix) của một từ x ∈A* nếu ∃v ∈A* sao cho: x = wv.
- Tương tự, một từ w ∈A* là một khúc đuôi (suffix) của một từ x ∈A* nếu ∃u ∈A* sao cho: x = uw

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt