Luận án tiến sĩ ứng dụng lý thuyết đồ thị để khảo sát đặc trưng một số lớp ngôn

MỤC LỤC Trang Trang phụ bìa 1 Lời cam đoan 2 Mục lục 4 Danh mục các thuật ngữ 6 Danh mục các hình vẽ 9 MỞ ĐẦU 10 Chƣơng 1. Các khái niệm cơ sở 15 1. Đại cƣơng về đồ thị 15 1. Định nghĩa đồ thị 15 1.

Đƣờng đi trên đồ thị 16 1. Một số cách biểu diễn đồ thị trong máy tính 17 1. Bài toán đƣờng đi trên đồ thị 18 1. Các thuật toán duyệt đồ thị 20 1.

Ngôn ngữ hình thức và otomat 25 1. Bảng chữ cái, từ và ngôn ngữ 25 1. Các phép toán trên ngôn ngữ 25 1. Một số công cụ sinh ngôn ngữ chính quy 26 và mối liên hệ giữa chúng 1.

Hệ mạng điều kiện - biến cố 41 1. Hệ mạng vị trí - chuyển 43 1. Kết luận cuối chƣơng 47 Chƣơng 2. Các thuật toán điều khiển tƣơng tranh 49 TIEU LUAN MOI download :4skknchat@gmail.com trên hệ mạng và độ phức tạp của chúng 2.

Bài toán điều khiển tƣơng tranh các quá trình 49 2. Thuật toán điều khiển tƣơng tranh trên các hệ mạng điều kiện 51 - biến cố 2. Đồ thị các trƣờng hợp 51 2. Các bƣớc tƣơng tranh trên hệ mạng điều kiện - biến cố 53 2.

Đầy đủ hoá đồ thị các trƣờng hợp 55 2. Thuật toán điều khiển tƣơng tranh trên các hệ mạng vị trí - 59 chuyển 2. Đồ thị phủ của hệ mạng vị trí - chuyển 59 2. Các bƣớc tƣơng tranh trên hệ mạng vị trí - chuyển 62 2.

Tìm bƣớc tƣơng tranh bằng cách rút gọn đồ thị phủ 63 2. Kết luận cuối chƣơng 67 Chƣơng 3. Độ phức tạp otomat của các thuật toán 68 đoán nhận ngôn ngữ 3. Độ phức tạp otomat của nguồn 69 3.

Độ phức tạp otomat của biểu thức chính quy 70 3. Biểu thức chính quy 70 3. Xây dựng nguồn tƣơng đƣơng với biểu thức chính quy 71 3. Độ phức tạp otomat của sơ đồ sinh 72 3.

Khái niệm sơ đồ sinh 72 3. Độ phức tạp otomat của sơ đồ sinh 75 3. Độ phức tạp otomat của chùm đầu 83 3. Khái niệm chùm đầu 83 3.

Otomat hữu hạn đơn định đoán nhận ngôn ngữ 84 sinh bởi chùm đầu 3. Kết luận cuối chƣơng 94 PHẦN KẾT LUẬN 96 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ 98 LIÊN QUAN ĐẾN LUẬN ÁN TÀI LIỆU THAM KHẢO 100 TIEU LUAN MOI download :5skknchat@gmail.com DANH MỤC CÁC THUẬT NGỮ Đồ thị Graph Tập đỉnh Set of vertices Tập cạnh Set of edges ánh xạ kề Adjacency mapping Đƣờng đi Path Chu trình Cycle Đồ thị vô hƣớng Undirected graph Đồ thị có hƣớng Directed graph Đa đồ thị Multigraph Đồ thị gán nhãn Labelled graph Đồ thị liên thông Connected graph Mảng liên thông Connected component Đồ thị liên thông mạnh Strongly connected graph Ma trận kề Adjacency matrix Danh sách kề Adjacency list Duyệt đồ thị theo chiều sâu Depth-first search Duyệt đồ thị theo chiều rộng Breadth-first search Đồ thị hai phần Bipartite graph Đồ thị các trƣờng hợp Case graph Đồ thị phủ Coverage graph Ngôn ngữ hình thức Formal language Bảng chữ cái Alphabet Từ Word Từ vô hạn Infinitive word TIEU LUAN MOI download :6skknchat@gmail.com Văn phạm Grammar Văn phạm cảm ngữ cảnh Context-sensitive grammar Văn phạm phi ngữ cảnh Context-free grammar Văn phạm chính quy Regular grammar Otomat Automaton Otomat hữu hạn Finite automaton Otomat đơn định Deterministic automaton Otomat không đơn định Nondeterministic automaton Nguồn Source Biểu thức chính quy Regular expression Đồ thị sinh Generating graph Cung bù Complement arc Cung cốt yếu Essential arc Sơ đồ sinh Generating scheme Chùm đầu Heading bunch -ngôn ngữ -language Thuật toán đoán nhận Recognition algorithm Thuật toán phân tích Parsing algorithm Độ phức tạp Complexity Độ phức tạp đoán nhận Recognition complexity Độ phức tạp otomat Automata complexity Hệ mạng Net system Mạng Petri Petri net Tập vào Pre-set Tập ra Post-set Mạng đơn giản Simple net Quan hệ đạt đƣợc Reachability relation TIEU LUAN MOI download :7skknchat@gmail.com Tập tách đƣợc Detached set B-íc t-¬ng tranh Concurrent step HÖ m¹ng ®iÒu kiÖn - biÕn cè Condition-event net system HÖ m¹ng vÞ trÝ - chuyÓn Place-transition net system Tr-êng hîp Case D·y ho¹t ®éng Firing sequence Dung l-îng Capacity Bé ®¸nh dÊu Marking HÖ m¹ng sèng Live net system HÖ m¹ng chu tr×nh Cycle net system Qu¸ tr×nh Process Qu¸ tr×nh tuÇn tù Sequential process Qu¸ tr×nh t-¬ng tranh Concurrent process Hµnh vi Behaviour Hµnh vi tuÇn tù Sequential behaviour Hµnh vi t-¬ng tranh Concurrent behaviour TIEU LUAN MOI download :8skknchat@gmail.com DANH MỤC CÁC HÌNH VẼ Trong bản luận án 21 có hình vẽ Hình vẽ Trang Hình 1.1: Đồ thị hữu hạn 15 Hình 1. Đồ thị có hƣớng và ma trận kề tƣơng ứng 17 Hình 1. Mảng các danh sách kề biểu diễn đồ thị 18 Hình 1.

Đồ thị gán nhãn 19 Hình 1. Thứ tự của các đỉnh đƣợc duyệt theo chiều sâu 23 Hình 1. Thứ tự của các đỉnh đƣợc duyệt theo chiều rộng 24 Hình 1. Nguồn đơn định đầy đủ K1 32 Hình 1.

Nguồn K2 là nguồn bù của nguồn K1 33 Hình 1. Mạng Petri đơn giản 39 Hình 1. Một hệ mạng vị trí - chuyển 45 Hình 2. Sơ đồ biến đổi tƣơng tranh một quá trình tuần tự 50 H×nh 2.

§å thÞ c¸c tr-êng hîp cña hÖ  52 H×nh 2. §å thÞ c¸c tr-êng hîp ®Çy ®ñ 58 H×nh 2. Minh ho¹ §Þnh lý 2. Mét phÇn cña ®å thÞ phñ vµ ®å thÞ phñ rót gän 66 H×nh 3.

Hai ®å thÞ sinh ®¬n gi¶n I1 vµ I2 cã l(I1) = l(I2) = 0 75 H×nh 3. §å thÞ sinh lÊy tiÒn tè cña ®å thÞ sinh I1 – cung cj 78 H×nh 3. S¬ ®å sinh kh«ng chøa cung bï víi cj lµ cung lÊy tiÒn tè 83 H×nh 3. Chïm ®Çu víi ai = C(L(I1)) vµ aj = C(L(I2)) 84 H×nh 3.

Minh ho¹ hµm ZIi(pa) 87 TIEU LUAN MOI download :9skknchat@gmail.com MỞ ĐẦU Lý thuyết đồ thị là một ngành khoa học ra đời rất sớm và có nhiều ứng dụng. Nhờ lý thuyết đồ thị mà nhiều bài toán phức tạp, diễn giải dài dòng đƣợc mô tả hình học một cách trực quan và cô đọng. Lý thuyết đồ thị đã trở thành công cụ đắc lực cho việc thiết kế các thuật toán [4,7,12,23], mô hình hình học và phân tích các hệ thống [9,49,62], biểu diễn các quá trình của hệ thống [34,60]. Việc tổ chức thực hiện một cách nhanh chóng các quá trình xảy ra trên một hệ thống phân tán là một trong những mục tiêu của bài toán điều khiển hệ thống.

Ngoài kỹ thuật đồng bộ hoá thì kỹ thuật thực thi song song đã đƣợc xây dựng thành công nhờ một số công cụ nhƣ: ngôn ngữ vết [11,13], phép đẩy trái [62]. Chính điều này đã khích lệ tác giả trong việc nghiên cứu ứng dụng lý thuyết đồ thị để xây dựng các thuật toán điều khiển tối ƣu các quá trình tuần tự trên một số hệ thống phân tán đƣợc biểu diễn bởi các hệ mạng điều kiện - biến cố và hệ mạng vị trí - chuyển. Từ một hệ mạng đã cho chúng ta có thể xây dựng đƣợc ngôn ngữ sinh bởi hệ này. Đó chính là hành vi tuần tự của hệ.

Hành vi tuần tự của hệ tạo bởi các quá trình xảy ra trên hệ với các bƣớc đơn, mỗi bƣớc chỉ gồm một hành động. Các hành động này đƣợc thực hiện kế tiếp nhau. Chúng ta có thể xây dựng đồ thị có hƣớng gán nhãn biểu diễn hành vi tuần tự của hệ mạng. Trong trƣờng hợp hành vi tuần tự có chứa các quá trình vô hạn thì kỹ thuật phủ đỉnh [34] sẽ giúp ta hữu hạn hoá đồ thị biểu diễn hành vi của hệ.

TIEU LUAN MOI download :10skknchat@gmail.com Việc phân tích và điều khiển tƣơng tranh các quá trình tuần tự xảy ra trên một hệ thống phân tán dựa vào ngôn ngữ sinh bởi hệ thống đang là một vấn đề thời sự. Để điều khiển tƣơng tranh các quá trình trên hệ mạng, chúng tôi xây dựng kỹ thuật ghép cạnh trên đồ thị biểu diễn hành vi của hệ mạng này. Sau mỗi lần ghép cạnh ta nhận đƣợc các quá trình với các bƣớc tƣơng tranh có nhiều hành động hơn. Hơn nữa, khi ghép cạnh thì số bƣớc trên một quá trình sẽ giảm đi.

Đến khi không thể ghép cạnh đƣợc nữa thì các bƣớc tƣơng tranh mà ta nhận đƣợc trở thành cực đại và số bƣớc của quá trình là ít nhất có thể. Khi đó, các quá trình với các bƣớc tƣơng tranh cực đại đƣợc thực thi trong môi trƣờng song song với thời gian ít nhất. Đó chính là ý nghĩa của điều khiển tối ƣu mà chúng ta mong muốn. Ngôn ngữ sinh bởi hệ mạng nói riêng và ngôn ngữ hình thức nói chung đều có các cơ chế sinh ngôn ngữ.

Cơ chế sinh ngôn ngữ từ các lớp văn phạm và cơ chế đoán nhận ngôn ngữ bởi các lớp otomat đã đƣợc nghiên cứu khá chi tiết. Trong thời gian gần đây, chúng ta cũng đã xây dựng thêm đƣợc một số công cụ khác để sinh ngôn ngữ nhƣ: đồ hình, nguồn, biểu thức chính quy, sơ đồ sinh, chùm đầu. Do vậy, việc nghiên cứu, khảo sát, tính toán độ phức tạp otomat của một số lớp ngôn ngữ đƣợc sinh ra từ các công cụ trên vẫn là một đề tài đang đƣợc nhiều ngƣời quan tâm. Sau sự ra đời và phát triển của lý thuyết ngôn ngữ từ hữu hạn cùng với nhu cầu ứng dụng của thực tiễn, việc nghiên cứu tính chất của các lớp ngôn ngữ từ vô hạn (-ngôn ngữ) trở nên cần thiết.

Lý thuyết ngôn ngữ từ vô hạn đƣợc đề xuất từ các công trình nghiên cứu về logic của J. Buchi [20], lý thuyết mạch điện của D. Muller [43], otomat của R. Ngôn ngữ từ vô hạn đƣợc tiếp tục quan tâm nghiên cứu và ứng dụng trong nhiều lĩnh vực khác nhau, chẳng hạn nhƣ: lý thuyết mật mã của G.

Staiger [59], Nguyễn Hƣơng Lâm và Đỗ Long Vân [37], lý thuyết TIEU LUAN MOI download :11skknchat@gmail.com các quá trình của M. Nivat [45], lý thuyết đô phức tạp của Đặng Huy Ruận [52,53], Đỗ Long Vân và Phan Trung Huy [32,70], hành vi hệ thống của A. Reisig [49], Hoàng Chí Thành [60], lý thuyết trò chơi của M. Davis [25], ngôn ngữ vết của J.

Rozenberg [13] … Một trong những vấn đề quan trọng đƣợc nhiều ngƣời quan tâm nghiên cứu trong lý thuyết ngôn ngữ hình thức là tính toán độ phức tạp otomat đoán nhận các lớp ngôn ngữ sinh bởi các công cụ khác nhau. Trên cơ sở đó đƣa ra các đặc trƣng cho các công cụ sinh và các lớp ngôn ngữ tƣơng ứng. Hơn nữa các ngôn ngữ này còn đƣợc dùng để biểu diễn hành vi tuần tự của các hệ thống nói chung và các hệ thống phân tán nói riêng.