phần mở đầu là 3 chƣơng chính. Chƣơng 1 trình bày các khái niệm cơ sở và các kết quả liên quan sẽ đƣợc dùng trong hai chƣơng sau. Những khái niệm cơ bản xuyên suốt luận án là lý thuyết đồ thị. Đó là công cụ toán học hữu ích mà tác giả đã sử dụng để biểu diễn các khái niệm, các hệ thống và xây dựng nên các thuật toán hữu hiệu.
Bên cạnh đó, tác giả cũng nhắc lại các khái niệm cơ bản của ngôn ngữ hình thức, otomat và của các hệ mạng. Chƣơng 2 trình bày bài toán điều khiển tƣơng tranh các quá trình xảy ra trên một hệ thống và xây dựng hai thuật toán điều khiển tƣơng tranh dựa trên đồ thị gán nhãn có hƣớng và phân tích độ phức tạp của chúng. Thuật toán thứ nhất làm đầy đủ đồ thị các trƣờng hợp của một hệ mạng điều kiện - biến cố. Từ đó ta nhận đƣợc một bức tranh đầy đủ về hành vi tƣơng tranh của hệ thống đƣợc biểu diễn bởi hệ mạng này.
Đồng thời ta cũng nhận ra đƣợc các quá trình tƣơng tranh với các bƣớc tƣơng tranh cực đại xảy ra trên hệ thống. Thuật toán thứ hai rút gọn đồ thị phủ của một hệ mạng vị trí - chuyển để từ đó nhận đƣợc các quá trình tƣơng tranh cực đại. Chúng tôi cũng đƣa ra các cải tiến từ thuật toán đã có trong [34] để xây dựng đồ thị phủ cho hệ mạng điều kiện - biến cố một cách đơn giản hơn. Các thuật toán này góp phần phát triển lý thuyết điều khiển hệ thống.
Chƣơng 3 trình bày các kết quả nghiên cứu về độ phức tạp otomat. Cụ thể là các tính toán xác định cận trên độ phức tạp otomat đoán nhận ngôn ngữ sinh bởi nguồn, biểu thức chính quy, sơ đồ sinh và chùm đầu. Cuối cùng là phần kết luận, danh sách các công trình khoa học đã công bố của nghiên cứu sinh liên quan đến luận án và danh sách các tài liệu tham khảo. TIEU LUAN MOI download :14skknchat@gmail.com Chƣơng 1 CÁC KHÁI NIỆM CƠ SỞ Trong chƣơng này, chúng tôi nhắc lại một số khái niệm và các kết quả rất cơ bản của lý thuyết đồ thị, lý thuyết ngôn ngữ hình thức và otomat cùng khái niệm mạng Petri, hệ mạng điều kiện - biến cố và hệ mạng vị trí - chuyển.
Những khái niệm này đƣợc trích dẫn từ các tài liệu [1,4,8,12,23,29,49] và là các công cụ để xây dựng lên các kết quả đƣợc trình bày ở hai chƣơng sau của bản luận án. ĐẠI CƢƠNG VỀ ĐỒ THỊ Lý thuyết đồ thị là một ngành khoa học phát triển rất sớm và trở thành công cụ hữu ích cho sự phát triển của nhiều ngành khoa học khác. Với trực quan hình học, lý thuyết đồ thị đã giúp chúng ta thiết kế và phân tích nhiều thuật toán lớn để giải quyết các bài toán phức tạp. Định nghĩa đồ thị Định nghĩa 1.1: Đồ thị là một cặp G = (V, E), trong đó: 1) V là tập hợp các đỉnh, 2) E V V, là tập hợp các cạnh.
TIEU LUAN MOI download :15skknchat@gmail.1: Một đồ thị có 5 đỉnh 8 cạnh.1: Đồ thị hữu hạn Đồ thị G cho ở Hình 1.1 có tập các đỉnh V = {a, b, c, d, e} và tập các cạnh E = {(a, b), (a, c), (b, c), (d, b), (d, c), (e, a), (e, b), (e, d)}. Giữa hai đỉnh của một đồ thị có thể có nhiều cạnh nối chúng. Đồ thị mà mỗi cặp đỉnh đƣợc nối với nhau không quá một cạnh, đƣợc gọi là đơn đồ thị (và gọi tắt là đồ thị). Đồ thị có những cặp đỉnh đƣợc nối với nhau nhiều hơn một cạnh đƣợc gọi là đa đồ thị.
Nếu (a, b) là một cạnh của đồ thị thì ta nói rằng đỉnh b kề với đỉnh a. Do vậy, ta có thể định nghĩa đồ thị bằng ánh xạ kề nhƣ sau.2: Đồ thị là một cặp G = (V, F), trong đó: 1) V là tập hợp các đỉnh, 2) F : V 2V và đƣợc gọi là ánh xạ kề. Ánh xạ kề của đồ thị trong Ví dụ 1.1 đƣợc xác định nhƣ sau: F(a) = {b, c}, F(b) = {c}, F(c) = , F(d) = {b, c} và F(e) = {a, b, d}. Sự tƣơng đƣơng của hai định nghĩa của đồ thị đƣợc thể hiện bằng mệnh đề sau đây: x, y V : (x, y) E y F(x).
Về bản chất, đồ thị là một tập hợp các đối tƣợng đƣợc biểu diễn bằng các đỉnh và giữa các đối tƣợng này có một quan hệ nhị nguyên biểu diễn bằng các cạnh. Cặp đỉnh (x, y) E không sắp thứ tự đƣợc gọi là cạnh vô TIEU LUAN MOI download :16skknchat@gmail.com hướng, còn nếu nó có sắp thứ tự thì đƣợc gọi là cạnh có hướng. Cạnh có hƣớng còn đƣợc gọi là cung của đồ thị. Ngƣời ta thƣờng phân các đồ thị thành hai lớp.3: Đồ thị chỉ chứa các cạnh vô hƣớng đƣợc gọi là đồ thị vô hướng còn đồ thị chỉ chứa các cạnh có hƣớng (cung) đƣợc gọi là đồ thị có hướng.
Đường đi trên đồ thị Giả sử G = (V, E) là một đồ thị.4: Đường đi trên đồ thị G là một dãy các đỉnh của đồ thị: < x1, x2,. , xk-1 , xk > sao cho, mỗi đỉnh trong dãy (không kể đỉnh đầu tiên) kề với đỉnh trƣớc nó bằng một cạnh nào đó, nghĩa là: i = 2, 3,. Ta nói rằng đƣờng đi này đi từ đỉnh đầu x1 đến đỉnh cuối xk. Số cạnh của đƣờng đi đƣợc gọi là độ dài của đƣờng đi.
Một số cách biểu diễn đồ thị trong máy tính a) Biểu diễn đồ thị bằng ma trận kề Giả sử G = (V, E) là một đồ thị có n đỉnh. Ta đánh số các đỉnh của đồ thị bằng các số tự nhiên: 1, 2,. Xây dựng ma trận vuông A cấp n biểu diễn đồ thị nhƣ sau: i, j V : A[i,j] = d, với d là số các cạnh nối đỉnh i với đỉnh j trong G. Ma trận A đƣợc gọi là ma trận kề của đồ thị G.2: Ma trận kề của đa đồ thị có hƣớng.
2 0 1 1 2 0 0 1 0 A = 0 0 1 0 1 3 0 1 1 0 4 TIEU LUAN MOI download :17skknchat@gmail. Đa đồ thị có hƣớng và ma trận kề tƣơng ứng b) Biểu diễn đồ thị bằng các danh sách kề Với mỗi đỉnh của đồ thị ta xây dựng một danh sách liên kết chứa các đỉnh kề với đỉnh này. Danh sách này đƣợc gọi là danh sách kề. Một đồ thị đƣợc biểu diễn bằng một mảng các danh sách kề.3: Biểu diễn mảng các danh sách kề của đồ thị G trong Ví dụ 1.
Mảng các danh sách kề biểu diễn đồ thị 1. Bài toán tìm đường đi trên đồ thị Bài toán: Cho đồ thị G và hai đỉnh a, b thuộc G. Có hay không một đƣờng đi từ đỉnh a đến đỉnh b trên đồ thị G? Dựa vào các kết quả đã có, chúng ta xây dựng thuật toán sau đây để giải bài toán trên.1 (Xác định đường đi) [4,12] Đầu vào: Đồ thị G = (V, E) và ha đỉnh a, b thuộc V. Đầu ra: Câu trả lời: ”có / không”.
1) Xây dựng ma trận kề A cho đồ thị G. TIEU LUAN MOI download :18skknchat@gmail.com 2) Tính ma trận tổng các luỹ thừa T = A1 + A2 +. 3) Nếu T[a,b] 1 thì kết luận là có đƣờng đi từ đỉnh a đến đỉnh b, ngƣợc lại thì kết luận là không có. Hiển nhiên, thuật toán trên có độ phức tạp là O(n4).
Đồ thị gán nhãn Giả sử G = (V, E) là một đồ thị và L là một tập hợp không rỗng nào đó. Hàm n : E L đƣợc gọi là hàm gán nhãn trên các cạnh của đồ thị đã cho. Khi đó, mỗi cạnh e E sẽ đƣợc gán nhãn n(e) L. Đồ thị G với các cạnh đƣợc gán nhãn đƣợc gọi là đồ thị gán nhãn.4: Đồ thị đƣợc gãn nhãn là các số tự nhiên trên các cạnh.
Đồ thị gán nhãn Đƣờng đi trên đồ thị gãn nhãn đƣợc biểu diễn chi tiết hơn. Cụ thể là: Định nghĩa 1.5: Đƣờng đi trong đồ thị gán nhãn là một dãy các đỉnh và các nhãn: < x1, l12,, x2, l23. , xi , li i+1, xj+1,. , xk-1 , lk-1 k, xk > sao cho, mỗi đỉnh trong dãy (không kể đỉnh đầu tiên) kề với đỉnh trƣớc nó bằng một cạnh nào đó có nhãn tƣơng ứng, nghĩa là: i = 2, 3,.
Ta nói rằng đƣờng đi này đi từ đỉnh đầu x1 đến đỉnh cuối xk với dãy nhãn là = l12 l23. TIEU LUAN MOI download :19skknchat@gmail.com Ngƣời ta thƣờng viết: x1 xk. Nghĩa là, trên đƣờng đi từ đỉnh x1 đến đỉnh xk ta nhận đƣợc từ tạo bởi dãy các nhãn trên mỗi cạnh. Để biểu diễn các nhãn trên các cạnh của một đồ thị đƣợc gán nhãn ta thực hiện nhƣ sau: - Trong ma trận kề: phần tử A[i,j] chứa nhãn của cạnh nối đỉnh i với đỉnh j.
- Trong biểu diễn mảng các danh sách kề: tại mỗi phần tử của danh sách ta thêm vào một trƣờng mới chứa nhãn của cạnh nối từ đỉnh tƣơng ứng với danh sách tới đỉnh nằm trong phần tử này. Thuật toán xác định đƣờng đi trên đồ thị gán nhãn giúp ta xác định các quá trình của một hệ thống khi hành vi của nó đƣợc biểu diễn bởi đồ thị gán nhãn có hƣớng (Chƣơng 2). Các thuật toán duyệt đồ thị Phép duyệt đồ thị là một cách liệt kê tất cả các đỉnh của đồ thị này thành một danh sách tuyến tính. Nói một cách khác, phép duyệt đồ thị cho ta một cách “đi qua” tất cả các đỉnh của đồ thị để truy nhập, thêm bớt thông tin ở các đỉnh của đồ thị này.
Với các đồ thị không liên thông thì thuật toán sẽ duyệt lần lƣợt từng mảng liên thông và kết quả sẽ là danh sách ghép của các danh sách các đỉnh trong từng mảng liên thông của đồ thị đã cho. Các thuật toán duyệt đồ thị đã đƣợc trình bày trong [4,12,23]. Chúng tôi nhắc lại các thuật toán này để sử dụng trong các thuật toán điều khiển tƣơng tranh sẽ đƣợc trình bày ở Chƣơng 2. a) Thuật toán duyệt đồ thị tổng quát Giả sử G là một đồ thị đã cho.
Ký hiệu DS là một cấu trúc dữ liệu kiểu danh sách dùng để chứa các đỉnh của đồ thị, L là một danh sách dùng để lƣu TIEU LUAN MOI download :20skknchat@gmail. Thuật toán tổng quát duyệt đồ thị đƣợc trình bày sơ lƣợc nhƣ sau.2 (Duyệt đồ thị) [4,12] Đầu vào: Đồ thị G = (V, F) đƣợc cho dƣới dạng ánh xạ kề.