Các mô hình tương tranh - Hoàng Chí Thành

124 trang huongle 4490

Download

Bạn đang xem 20 trang mẫu của tài liệu "Các mô hình tương tranh - Hoàng Chí Thành", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

cac_mo_hinh_tuong_tranh_hoang_chi_thanh.pdf

Nội dung text: Các mô hình tương tranh - Hoàng Chí Thành

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN HOÀNG CHÍ THÀNH CÁC MÔ HÌNH TƯƠNG TRANH Hà Nội
MỞ ĐẦU Mô tả, thiết kế và điều khiển hệ thống là các vấn đề chính cần đặt ra khi chúng ta xây dựng một hệ thống nào đó và sử dụng nó trong thực tiễn. Lý thuyết mạng là lý thuyết tổ chức hệ thống được C.A. Petri khởi xướng vào đầu thập niên sáu mươi của thế kỷ trước trong Luận án Tiến sĩ của ông. Từ đó đến nay các nhà tin học trên thế giới đã nghiên cứu phát triển nhiều mô hình mạng khác nhau và ứng dụng chúng vào nhiều lĩnh vực khoa học khác nhau. Ưu điểm chính của lý thuyết mạng là khả năng nhận biết và biểu diễn sự tương tranh, an toàn, xung đột, sống, tắc nghẽn , cung cấp kỹ thuật phân tích và thiết kế hệ thống và cảnh báo sự hữu hạn của các tài nguyên của hệ thống. Bên cạnh lý thuyết mạng nhiều mô hình biểu diễn tương tranh khác đã ra đời. Một số mô hình dựa trên ngôn ngữ hình thức như: ngôn ngữ vết của A. Mazurkiewicz, ngôn ngữ CSP của C.A.R. Hoare, ngôn ngữ CCS của R. Milner, ngôn ngữ COSY của P. Lauer, ngôn ngữ nửa vết của H.C. Thành Công cụ đại số cũng được sử dụng để biểu diễn tương tranh. Từ đó ra đời: đại số các quá trình của V.E. Kotov và của J.A. Bergstra, cấu trúc biến cố của G. Winskel Do khuôn khổ của chuyên đề, chúng tôi chỉ chọn lựa một số mô hình tiêu biểu nhất để đưa vào các bài giảng với mục tiêu giúp người học nắm bắt được các khái niệm mới, kỹ thuật cơ bản và ứng dụng chúng vào các vấn đề thực tiễn như: hệ thống thông tin, cơ sở dữ liệu, thiết kế mạch lôgic, kiến trúc máy tính, lập trình song song, công nghệ phần mềm, điều khiển hệ thống Cuốn sách là nội dung chuyên đề dành cho học viên cao học và nghiên cứu sinh chuyên ngành Tin học, Công nghệ Thông tin, Đảm bảo Toán học cho Máy tính và Các hệ thống tính toán mà tác giả đã giảng dạy nhiều năm tại ĐHQG Hà Nội và một số trường đại học khác. Nhiều thảo luận lý thú giữa tác giả với đồng nghiệp và học viên đã góp phần phát triển nội dung và nâng cao chất lượng của cuốn sách. Chúng tôi hy vọng rằng cuốn sách nhỏ này sẽ thật sự cần thiết cho những ai muốn nghiên cứu, khám phá những vấn đề kỳ diệu và hóc búa trong các hệ thống tương tranh. Tác giả 2
Chương 1 HỆ TƯƠNG TRANH VÀ CÁC MÔ HÌNH BIỂU DIỄN 1.1 Khái niệm về tương tranh Trong đời sống hàng ngày, chúng ta thường thấy các sự kiện mà các hành động trong nó xảy ra một cách tuần tự hoặc không tuần tự. Tương ứng với các sự kiện trên ta có các quá trình và chúng cũng được phân thành hai loại: các quá trình tuần tự và các quá trình không tuần tự. Một số quá trình được kết hợp lại với nhau tạo thành một hệ thống. Hệ thống tuần tự được tạo bởi các quá trình tuần tự. Các quá trình không tuần tự tạo nên hệ thống không tuần tự. Trong một hệ thống tuần tự tại mỗi thời điểm chỉ có một hành động xuất hiện (được thực hiện). Hành động sau xảy ra khi hành động trước đó đã kết thúc. Chúng chỉ có thể kế thừa kết quả của nhau. Chẳng hạn: - Khách xếp hàng mua hàng khi chỉ có một nhân viên bán hàng - Các thuật toán tính toán tuần tự - Các otomat hữu hạn Còn trong hệ thống không tuần tự, tại một thời điểm có thể xảy ra đồng thời nhiều hành động. Các hành động này có thể cạnh tranh lẫn nhau trong việc sử dụng tài nguyên. Trước khi đưa ra định nghĩa hệ tương tranh chúng ta xét một số ví dụ cụ thể sau đây. Ví dụ 1.1: Quá trình sản xuất công nghiệp Giả sử một thiết bị nào đó được tạo ra từ việc chế tạo và lắp ráp ba chi tiết. Việc chế tạo từng chi tiết không phụ thuộc vào nhau. Việc lắp ráp thì thực hiện tuần tự: trước tiên lắp ráp hai chi tiết đầu sau đó lắp thêm chi tiết thứ ba. Hình 1.1. Quy trình tổ chức chế tạo và lắp ráp song song một thiết bị 3
Ta có thể đưa quá trình sản xuất thiết bị trên về một hệ thống tương tranh như sau: chế tạo đồng thời hai chi tiết 1 và 2, việc lắp ráp hai chi tiết 1 và 2 đồng thời với việc chế tạo chi tiết thứ ba, cuối cùng lắp ráp thêm chi tiết 3. Như vậy, trong hệ thống sản xuất này việc chế tạo chi tiết 1 và việc chế tạo chi tiết 2 là tương tranh với nhau. Chúng chỉ có thể được thực hiện đồng thời nếu không tranh chấp các máy móc Quá trình sản xuất một sản phẩm có thể biểu diễn ngắn gọn bằng sơ đồ sau: 1 ⁪ 2 ; 3 ⁪ 4 ; 5 Với việc tổ chức sản xuất như trên, ta thấy ngay các lợi ích sau đây: 1) Các chi tiết kỹ thuật được chế tạo trên các máy khác nhau, việc chế tạo đồng thời có thể xoá bỏ thời gian chết của các máy. 2) Giảm thời gian chế tạo ra một sản phẩm. Ví dụ 1.2: Tính giá trị của một biểu thức toán học Giả sử ta cần phải tính giá trị của biểu thức sau đây: A * B - (C + D) / (E - F) Hình 1.2. Tổ chức tính toán song song một biểu thức Sơ đồ tính toán giá trị biểu thức như trên giống như sơ đồ quá trình sản xuất trong Ví dụ 1.1. Nếu máy tính có ít nhất hai bộ xử lý thì quá trình tính giá trị biểu thức sẽ nhanh hơn nhiều. Ví dụ 1.3: Chu trình xử lý Xét chu trình tính toán được viết trên ngôn ngữ lập trình Pascal sau đây: for i := 1 to 100 do if A[i] > 0 then A[i] := A[i] + 1 else A[i] := 0 ; 4
100 lệnh if trên có thể được thực hiện đồng thời nếu máy tính có trên 100 bộ xử lý. Tuy nhiên, không phải chu trình nào cũng có thể thực hiện đồng thời được. Chẳng hạn, xét chu trình sau đây: S := 0 ; for i := 1 to 100 do S := S + A[i] ; Đây là các lệnh lặp phụ thuộc. Trong trường hợp này có nhiều cách giải quyết. Chẳng hạn, ta tính toán đồng thời theo sơ đồ sau đây: Hình 1.3. Một sơ đồ tính toán song song Ví dụ 1.4: Tương tranh trong máy tính Tương tranh trong máy tính được thể hiện ở các máy tính có nhiều bộ xử lý (multi-processor). Đó là các máy tính có thể xử lý đồng thời nhiều quá trình tại cùng một thời điểm. Hình 1.4. Sơ đồ máy tính song song Với kỹ thuật này nảy sinh các vấn đề sau đây mà ta cần phải giải quyết: 5
- Sự chung sống của các bộ xử lý thuộc nhiều chủng loại khác nhau - Số lượng tối đa của các bộ xử lý trong một máy tính - Phần mềm để tự động hoá các quá trình tương tranh trên máy tính nhiều bộ xử lý 1.2 Định nghĩa hệ tương tranh Một hệ thống được gọi là hệ tương tranh (concurrent system) nếu nó được hợp thành từ một số hệ con (tuần tự) và có các biến cố được xảy ra một cách đồng thời. Hệ tương tranh là đồng bộ nếu các hệ con của nó có chung một số biến cố và trong quá trình hoạt động của hệ chúng xuất hiện trùng hợp trong tất cả các hệ con có chung các biến cố này. Điều này chỉ ra rằng, mỗi biến cố chung xuất hiện ở bước nào đó thì nó phải có khả năng xuất hiện ở bước đó trong tất cả các hệ con có chung biến cố này. Số lần xuất hiện và thứ tự xuất hiện của biến cố chung trong các hệ con phải giống nhau. 1.3 Sơ lược về các mô hình biểu diễn tương tranh 1) Mô hình đầu tiên để biểu diễn hệ tương tranh được đề xuất bởi C.A. Petri (Đức) vào năm 1962 trong Luận án Tiến sĩ của ông. Đó là mạng Petri. Nếu otomat hữu hạn chỉ mô tả được các hệ thống tuần tự thì mạng Petri, một công cụ toán học được phát triển trên cơ sở của otomat hữu hạn, mô tả được các hệ thống không tuần tự mà trong đó có các hệ thống tương tranh. Hiện nay mạng Petri vẫn được nghiên cứu phát triển mạnh mẽ cả về lý thuyết lẫn ứng dụng [5,7,10,11]. Đã có hơn mười loại mạng khác nhau và được áp dụng vào rất nhiều lĩnh vực. 2. Ngôn ngữ vết (trace language) do A. Mazurkiewicz (Ba Lan) đưa ra vào năm 1977. Đây là một ngôn ngữ được phát triển từ ngôn ngữ hình thức để mô tả hành vi của các hệ tương tranh [1]. 3. CSP (Communicating Sequential Processes) là một ngôn ngữ để biểu diễn các hệ tương tranh [3] do C.A.R. Hoare (Anh) đưa ra vào năm 1978. 4. CCS (Calculus of Communicating Systems) được R. Milner (Anh) xây dựng vào năm 1980 như một công cụ toán học rõ ràng và tổng quát về tương tranh và được thể hiện như một ngôn ngữ lập trình [4]. Ngoài những mô hình kể trên, các hệ tương tranh còn được mô tả bằng các mô hình sau đây: - Đại số các quá trình (Algebra of Processes) của J.A. Bergstra (Hà Lan) 6
- COSY (COncurent SYstem) do P. Lauer (Canada) đề xuất - Cấu trúc biến cố (Event Structure) của G. Winskel (Đức), và nhiều mô hình khác. Một số nhóm nghiên cứu các hệ tương tranh trên thế giới: Hệ tương tranh được nhiều nhà khoa học trên thế giới nghiên cứu và phát triển tại các trường đại học và các viện nghiên cứu. - Tại Đại học Bonn (Đức), nơi ra đời của mạng Petri, có một nhóm các nhà khoa học có tên tuổi như: C.A. Petri, E. Best, W. Reisig, W. Brauer, U. Goltz phát triển nhiều mô hình khác nhau của mạng Petri. - Đại học Aarhus (Đan Mạch) xây dựng các mô hình mạng Petri màu và ứng dụng trong thiết kế. - Đại học Amsterdam (Hà Lan) với tên tuổi của G. Rozenberg và J.W. de Baker chủ trì dự án REX (Research and Education in Concurrent Systems) - Đại học Oxfort (Anh) là nơi C.A.R. Hoare và R. Milner xây dựng trường phái mô hình các hệ tương tranh bằng ngôn ngữ trừu tượng. - Trường phái dùng monoid của đại số để phát triển lý thuyết tương tranh được nghiên cứu tại Đại học Milan (Italia) với tên tuổi các nhà khoa học như: U. Montarari, F. de Cindio, C. Simone - A. Mazurkiewicz và J. Winkowski chủ trì nhóm nghiên cứu tương tranh tại Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học Ba Lan. - Đại học Tổng hợp Novosibierk (Nga) có một nhóm các nhà khoa học trẻ nghiên cứu về tương tranh bằng các công cụ đại số như: V.E. Kotov, L. Cherkasova - P.S. Thiagarajan đã xây dựng một nhóm nghiên cứu mạnh về tương tranh tại Viện Toán học Chennai (Ấn độ). - Dự án châu Âu ESPRIT có trụ sở tại Đại học Newcastle (Anh) dưới sự điều hành của R.P. Hopkin với 44 nhà khoa học tham gia trực tiếp trong 10 nhóm làm việc (WG) sau đây: 1. WG.1: Các lớp modul mạng 2. WG.2: Mô phỏng tương đương 3. WG.3: Các kỹ thuật chứng minh 4. WG.4-5: Các mô hình trừu tượng 5. WG.6: Các nghiên cứu thời sự 6. WG.7: Đặc tả 7
7. WG.8: Lập trình 8. WG.9-10: Công bố kết quả Hội thảo khoa học hàng năm toàn thế giới về tương tranh (CONCUR) được tổ chức tại nhiều trung tâm nghiên cứu trên khắp các châu lục đã thu hút sự chú ý của nhiều người về Lý thuyết Tương tranh. Nhiều kết quả nghiên cứu lý thuyết và ứng dụng của hệ tương tranh đã được trình bày tại hội thảo này. 8
Chương 2 MẠNG PETRI 2.1 Ví dụ về mạng Petri Chúng ta nghiên cứu việc tổ chức cho mượn sách và nhận trả lại sách ở một thư viện. Hình 2.1. Cấu trúc đơn giản của một thư viện Đây là cấu trúc đơn giản của một thư viện. Bạn đọc có thể truy nhập vào thư viện thông qua ba bàn: bàn yêu cầu, bàn nhận sách và bàn trả sách. Trong thư viện tất cả các sách đều được để trên giá và mỗi cuốn sách có một thẻ mục. a) Bạn đọc yêu cầu: Nếu cuốn sách có trong thư viện thì thủ thư lấy sách, thẻ mục của cuốn sách đó được cập nhật và bạn đọc nhận sách tại bàn nhận sách. b) Bạn đọc trả sách: Thẻ mục của sách được cập nhật và sách được đặt trở lại giá. Làm mịn sơ đồ thư viện trên bằng cách thêm vào hai bộ phận làm việc là: “cho mượn sách” và “nhận lại sách” và hai thành phần thụ động là “kho sách” và “hộp thẻ mục sách đã mượn”. Khi đó ta có sơ đồ mới chi tiết hơn của một thư viện như dưới đây: Hình 2.2. Sơ đồ tổ chức đầy đủ của một thư viện 9
Đây là một ví dụ về mạng Petri. 2.2 Các khái niệm cơ sở 2.2.1 Mạng Petri Định nghĩa 2.1: Bộ ba N = (S, T; F) được gọi là một mạng Petri nếu: 1) S và T là hai tập hợp không giao nhau. Các phần tử của tập S được gọi là S-phần tử, còn các phần tử của tập T được gọi là T-phần tử. 2) F  (S T)  (T S) là một quan hệ nhị nguyên và được gọi là lưu đồ của mạng N. Người ta thường biểu diễn đồ thị định hướng cho mạng Petri bằng cách coi mỗi phần tử của tập S  T là một đỉnh của đồ thị. Các S-phần tử được biểu diễn bằng các hình tròn, còn các T-phần tử được biểu diễn bằng các hình vuông. Quan hệ lưu đồ F chính là các cung nối giữa các đỉnh tương ứng. Mỗi cung của quan hệ lưu đồ F chỉ nối hai đỉnh khác loại. Do vậy, đồ thị biểu diễn một mạng Petri là một đồ thị định hướng hai phần. Giả sử N là một mạng Petri. Nếu không nhầm lẫn đôi khi ta viết N thay cho S  T. Đó chính là tập các phần tử của mạng N. i) Với mỗi phần tử x N thì: x = { y N  (y, x) F } - được gọi là tập vào của x, x = { y N  (x, y) F } - được gọi là tập ra của x. với mỗi tập con X  N thì: X =  x và X =  x x X x X Chú ý rằng, với cặp phần tử x, y N ta có: x y y x ii) Cặp (s, t) S T được gọi là một nút (self-loop) nếu (s, t) F và (t, s) F. Mạng N được gọi là tinh khiết (pure) nếu quan hệ lưu đồ F không chứa một nút nào. iii) Phần tử x N được gọi là cô lập nếu x  x = . iv) Mạng N được gọi là đơn giản (simple) nếu và chỉ nếu các phần tử khác nhau không có chung tập vào và tập ra, nghĩa là: x, y N : ( x = y )  ( x = y ) x = y. 10
Ví dụ 2.2: Xét mạng Petri được cho dưới dạng đồ thị dưới đây. Hình 2.3. Biểu diễn đồ thị của một mạng Petri Mạng ở ví dụ trên là đơn giản, không tinh khiết và không có phần tử cô lập. 2.2.2 Các mạng Petri đẳng cấu Giả sử N và N' là hai mạng Petri. 1) Cho một song ánh  : N N'. Ta nói hai mạng N và N' là -đẳng cấu nếu và chỉ nếu: s SN (s) SN’ và (x, y) FN ((x), (y)) FN’ Điều này cũng suy ra rằng: t TN (t) TN’. 2) Hai mạng N và N' được gọi là đẳng cấu nếu chúng là -đẳng cấu với một song ánh  nào đó. Hiển nhiên, hai mạng đẳng cấu với nhau thì đồ thị biểu diễn của chúng cũng đẳng cấu với nhau và ngược lại. Do vậy, các mạng đẳng cấu với nhau được xem là “giống nhau”. 11
Chương 3 HỆ MẠNG ĐIỀU KIỆN - BIẾN CỐ 3.1 Các trường hợp và các bước Chúng ta xét hệ thống được tạo bởi các điều kiện (condition) và các biến cố (event). Các điều kiện được biểu diễn bởi các S-phần tử còn các biến cố được biểu diễn bởi các T-phần tử của một mạng Petri. Ta biết rằng, các điều kiện hoặc là thoả mãn hoặc là không và sự xuất hiện của các biến cố sẽ làm thay đổi sự thoả mãn của các điều kiện. Trong mỗi một hình trạng của hệ, một số điều kiện nào đó thoả mãn, số còn lại thì không. Tập các điều kiện được thoả mãn trong một hình trạng được gọi là một trường hợp (case). Biến cố e có thể xuất hiện trong trường hợp c nếu và chỉ nếu các điều kiện vào của e thoả mãn trong c còn các điều kiện ra thì không. Khi biến cố e xuất hiện, các điều kiện vào của e không thoả mãn nữa còn các điều kiện ra của e bắt đầu thoả mãn. Vì các S-phần tử và T-phần tử được thể hiện như các điều kiện và các biến cố nên ta ký hiệu mạng Petri là (B, E; F) thay cho (S, T; F). Định nghĩa 3.1: Giả sử N = (B, E; F) là một mạng Petri. 1) Tập con c  B được gọi là một trường hợp hay một trạng thái. 2) Giả sử e E và c  B. Ta nói rằng e là kích hoạt được trong c (hay e là c- kích hoạt) nếu và chỉ nếu e  c và e  c = . 3) Giả sử e E , c  B và e là kích hoạt được trong c. Khi đó, c' = (c \ e)  e được gọi là trường hợp kế tiếp của c (c’ là kết quả của sự xuất hiện của biến cố e trong trường hợp c). Và ta viết: c [ e > c'. Một biến cố của hệ mạng có thể xảy ra nếu trong hệ có trạng thái làm thoả mãn các điều kiện trước (tập vào) của biến cố đó và khi ấy các điều kiện sau (tập ra) của biến cố này chưa thoả mãn. Khi biến cố xảy ra, các điều kiện trước không thoả mãn nữa và các điều kiện sau được thoả mãn. Trạng thái kế tiếp nhận được sau khi biến cố trên xảy ra phải thuộc không gian các trạng thái để có thể kích hoạt các biến cố khác. Không gian các trạng thái của hệ thống là môi trường để dãy các bước có thể xảy ra trên hệ, tạo nên các quá trình trên hệ. Nếu có điều kiện sau nào đó làm cản trở sự xuất hiện của biến cố e, nghĩa là e  c nhưng e  c ≠  thì ta gọi hiện tượng này là tình trạng không an toàn. Tập con các biến cố G  E mà các tập vào và các tập ra của các biến cố trong G là rời nhau thì G được gọi là tách được (detached). Các biến cố trong 12
một tập tách được G có thể xuất hiện đồng thời trong một bước nếu mọi biến cố trong G đều được kích hoạt bởi cùng một trường hợp. Định nghĩa 3.2: Giả sử N = (B, E; F) là một mạng Petri. 1) Tập con các biến cố G  E được gọi là tách được nếu: e1, e2 G : e1 ≠ e2 e1  e2 = e1  e 2 = e 1  e2 = e 1  e 2 = . 2) Giả sử c và c' là các trường hợp của mạng N và tập con các biến cố G là tách được. G được gọi là một bước từ c tới c' nếu và chỉ nếu mỗi biến cố e trong G là c-kích hoạt và c' = (c \ G)  G . Khi đó, ta cũng ký hiệu là: c [ G > c'. Bước G đã dẫn từ trường hợp c tới trường hợp c'. Hiển nhiên, nếu G chỉ chứa một biến cố e thì: c [ G > c' c [ e > c'. Bổ đề 3.1: Giả sử N = (B, E; F) là một mạng Petri, tập con các biến cố G  E là tách được và c, c' là các trường hợp của N. Khi đó thì: c [ G > c' c \ c' = G  c' \ c = G . Chứng minh: 1) Nếu c [ G > c' thì mọi e G là c-kích hoạt và c' = (c \ G)  G . Từ đó suy ra: G  c và G  c' = . Hơn nữa: c \ c' = c \ ((c \ G)  G ) = (c \ (c \ G))  (c \ G ) – theo lý thuyết tập hợp = (c  G)  (c \ G ) = c  G vì c \ G = c = G vì G  c. c' \ c = ((c \ G)  G ) \ c = ((c \ G) \ c)  (G \ c) =   (G \ c) = G vì G  c = . 2) Ngược lại, nếu c \ c' = G thì G  c. Đồng thời, nếu c' \ c = G thì G  c = . Vậy mỗi biến cố e trong G là c-kích hoạt. Hơn nữa: (c \ G)  G = (c \ (c \ c'))  (c' \ c) = (c  c')  (c' \ c) = c'. Vậy thì: c [ G > c'. Bổ đề được chứng minh. 13
Nói chung có một số khả năng để ghép các biến cố thành một bước. Ví dụ 3.3: Xét hệ mạng Petri được cho như đồ thị dưới đây. Chọn trường hợp đầu tiên c0 = {b1}. Hình 3.1. Các bước trên mạng Không chỉ {e1,e2} mà {e2,e3} cũng tạo nên một bước. Khi thay thế các trường hợp, bước tiếp theo bước sinh ra các quá trình. Nếu bước hữu hạn thì nó có thể được thể hiện bởi sự xuất hiện của các biến cố của nó theo thứ tự tuỳ ý. Do vậy, các biến cố trong một bước hữu hạn có thể thực hiện đồng thời với nhau. Bổ đề 3.2: Giả sử N = (B, E; F) là một mạng Petri, c1, c2 là các trường hợp của mạng N và G là một bước hữu hạn dẫn c tới c'. Giả sử G = {e1, e2, , ek} và là một dãy nào đó của các biến cố trong G. Vậy thì có các trường hợp c0, c1, , ck mà c = c0, c' = ck và ci-1[ ei > ci với i = 1, 2, , k. Chứng minh: Giả sử ei, ej là hai biến cố nào đó trong G và c là trường hợp kích hoạt được hai biến cố này. Thế thì: ei  ej = e i  e j = e i  ej = ei  e j = . Khi đó nếu c [ ei > c' thì ej  c'. Tương tự có thể chỉ ra rằng e j  c' = . Điều này có nghĩa là ej kích hoat được trong c'. Với i = 1, 2, , k ta có ei vẫn bảo toàn tính kích hoạt được khi xuất hiện lần lượt của e1, e2, , ei-1 và dẫn ci-1 tới ci. Có thể xảy ra trường hợp là hai biến cố đều được một trường hợp kích hoạt nhưng chỉ có thể xuất hiện trong các bước đơn thôi. Đó là trường hợp mà hai biến cố này có chung điều kiện vào hoặc điều kiện ra. Khi đó sự xuất hiện của chúng loại trừ lẫn nhau. Tình trạng như thế được gọi là xung đột lẫn nhau (conflict). Không phải lúc nào cũng có thể nhận biết một cách rõ ràng rằng xung đột có xảy ra hay không. 14
Ví dụ 3.4: Xét mạng Petri sau đây. Hình 3.2. Tình trạng xung đột Trong mạng trên với trường hợp được chỉ ra (các điều kiện tô màu) nếu e1 xuất hiện trước e2 thì không có xung đột giữa e1 và e3, còn nếu e2 xuất hiện trước e1 thì xảy ra xung đột. Do không có thứ tự xác định trước giữa e1 và e2 nên tình trạng này được gọi là mập mờ. 3.2 Hệ mạng điều kiện - biến cố Một mạng Petri bao gồm các điều kiện và các biến cố chưa đủ để mô tả hệ thống. Vì vậy ngoài mạng ta phải thêm vào các trường hợp mà ta muốn xét. Tập các trường hợp C này phải thoả các tính chất sau đây: 1. Nếu tập G  E là một bước được kích hoạt bởi trường hợp c C thì G dẫn tới một trường hợp khác cũng thuộc C. Như vậy, các bước không được dẫn ra ngoài C. 2. Ngược lại, nếu trường hợp c C là kết quả của bước G  E thì tình huống mà ta đi từ đó cũng phải là một trường hợp thuộc C. Hay nói một cách khác, nếu ta quay trở lại tìm trường hợp trước thì ta chỉ cần tìm trong C. 3. Mỗi trường hợp trong C đều có thể biến đổi (tiến hoặc lùi sau một số lần) thành các trường hợp còn lại trong C. 4. C phải đủ rộng để mà: - Mỗi điều kiện b B phải thuộc vào ít nhất một trường hợp trong C nhưng không thuộc vào mọi trường hợp trong C. Điều này giúp loại trừ điều kiện cô lập và chu trình hẹp. - Mỗi biến cố e E phải có ít nhất một trường hợp trong C kích hoạt được nó. Ta cũng loại trừ các biến cố cô lập vì sự xuất hiện của các biến cố phải quan sát được. Hơn nữa, ta cũng không cho phép hai điều kiện hay hai biến cố khác nhau có chung tập vào và tập ra vì không phân biệt được chúng. 15
Định nghĩa 3.5: Bộ bốn  = (B, E; F, c0) được gọi là một hệ mạng điều kiện - biến cố (C/E-system) nếu: 1) Bộ ba (B, E; F) là một mạng Petri đơn giản, không có phần tử cô lập và B  E ≠ . 2) c0  B, là trường hợp đầu tiên của hệ mạng . Tập C = [c0]R là một lớp -1 * tương đương của quan hệ đạt được R = (r  r ) , trong đó quan hệ r  P(B) P(B) được định nghĩa như sau: (c1, c2) r G  E : c1 [ G > c2. C được gọi là không gian các trường hợp của hệ . 3) e E , c C để e kích hoạt được trong c. Ví dụ 3.6: Cho mạng Petri: Hình 3.3. Cấu trúc tĩnh của một hệ mạng điều kiện - biến cố Lấy c0 = {b1}. Khi đó không gian C = {{b1}, {b2, b3}, {b3, b4}, {b4}, {b5}} và ta có một hệ mạng điều kiện - biến cố. Định lý 3.3: Giả sử  là một hệ mạng điều kiện - biến cố. Thế thì: 1) B ≠   E ≠   F ≠ . 2) Với c C , c'  B và G  E : - c [ G > c' c' C - c' [ G > c c C 3) b B , c, c' C mà b c  b c'. 4) Hệ  là tinh khiết. Chứng minh: 1) Vì B  E ≠  và các phần tử cô lập đã bị loại trừ nên phải có các phần tử x, y của  sao cho (x, y) F. 2) Suy từ định nghĩa của hệ mạng điều kiện - biến cố. 16
3) Vì b không cô lập nên có biến cố e trong b  b và theo định nghiã thì phải có c, c' C mà c [ e > c' và vì b c  c'. 4) Biến cố trong chu trình hẹp không bao giờ được kích hoạt. Ví dụ 3.7: Bài toán sắp đặt lại các tập hợp. Cho hai tập không rỗng, hữu hạn, rời nhau A và B. Sắp đặt lại các phần tử trong tập A  B thành hai tập A' và B' sao cho |A'| = |A|, |B'| = |B| và max (A) c2. -1 * Nếu tập các biến cố E hữu hạn thì R = ( r  r ) . Chứng minh: -1 * Vì R = ( r  r ) nên hiển nhiên ta có: R  R . * Tập E hữu hạn nên mỗi bước trong E cũng hữu hạn. Do vậy, ta có r  r và -1 -1 * r  ( r ) . Từ đây suy ra: R  R . 17
Giả sử  = (B, E; F, c0) là một hệ mạng điều kiện - biến cố. Các trường hợp trong không gian các trường hợp kích hoạt liên tiếp các biến cố cho ta một dãy hành động xảy ra trên hệ. Chẳng hạn, c1 [e1 > c2 [e2 > c3 [e3 > c4 ci [ei > ci+1 cn [en > cn+1 , với c1, c2, cn+1 C và e1, e2, en E. Khi đó,  = e1e2 en được gọi là từ sinh bởi hệ mạng . Ngôn ngữ sinh bởi hệ mạng điều kiện - biến cố , ký hiệu bởi L(), là tập tất cả các từ sinh bởi hệ mạng này. L() = { = e1e2 en |  c1, c2, cn+1 C ,  e1, e2, en E : c1 [e1 > c2 [e2 > c3 [e3 > c4 ci [ei > ci+1 cn [en > cn+1}. Ngôn ngữ này thể hiện hành vi tuần tự của hệ mạng. Nó chỉ cho ta tất cả các dãy các hành động có thể xảy ra tuần tự trên hệ. 3.3 Hệ chu trình và hệ sống Những yêu cầu đặt ra cho không gian các trường hợp C của hệ mạng điều kiện - biến cố  sẽ rõ ràng hơn bằng cách thể hiện được rằng C là tập tất cả các trường hợp kế tiếp của một trường hợp ban đầu nào đó. Nếu mọi trường hợp của  đều được tái sản xuất thì mỗi một không gian các trường hợp như thế sẽ trùng với tập C. Định nghĩa 3.8: Hệ mạng điều kiện - biến cố  được gọi là chu trình nếu và chỉ nếu: * c1, c2 C : (c1, c2) r . Định lý 3.5: Giả sử  là một hệ mạng điều kiện - biến cố chu trình và c là một * trường hợp nào đó trong không gian C. Thế thì: C = {c' (c, c') r } . Chứng minh: -1 * Vì hệ  là chu trình nên r  r . Suy ra R  r . Trong một hệ chu trình mỗi một biến cố luôn luôn được xuất hiện trở lại. Định nghĩa 3.9: Hệ mạng điều kiện - biến cố  được gọi là sống nếu và chỉ nếu: * c C , e E : c' C để cho (c, c') r và e là c'-kích hoạt. 18
Định lý 3.6: Mọi hệ mạng điều kiện - biến cố chu trình là sống. Chứng minh: Giả sử c C và e E. Theo định nghĩa của hệ mạng điều kiện - biến cố phải có trường hợp c' trong C * để nó kích hoạt được e. Theo tính chu trình thì (c, c') r . Điều ngược lại thì không phải khi nào cũng đúng. Ta hãy xét phản ví dụ sau đây. Ví dụ 3.10: Hệ mạng điều kiện - biến cố sống nhưng không là chu trình. Hình 3.5. Hệ sống nhưng không là chu trình 3.4 Các hệ mạng điều kện - biến cố tương đương Ta nói rằng hai hệ mạng điều kiện - biến cố đã cho là tương đương nếu các trường hợp và các bước của chúng tương ứng với nhau theo cách sau đây. Định nghĩa 3.11: Giả sử  và ' là hai hệ mạng điều kiện - biến cố. 1) Giả sử có hai song ánh : C C’ và  : E E’ . - Hai hệ  và ' được gọi là ( ,)-tương đương nếu và chỉ nếu: c1, c2 C , G  E : c1 [ G > c2 (c1) [ (G) > (c2). - Hai hệ  và ' được gọi là tương đương nếu và chỉ nếu chúng là ( ,)- tương đương đối với cặp song ánh ( ,) nào đó và ta ký hiệu:   '. 2) Hai hệ  và ' được gọi là đẳng cấu nếu và chỉ nếu hai mạng (B , E , F) và (B', E' , F’) là -đẳng cấu với song ánh  nào đó và: c C {(b) b c} C’ . Định lý 3.7: Sự đẳng cấu mạnh hơn sự tương đương. Quan hệ  là một quan hệ tương đương. 19
Định lý 3.8: Các hệ mạng điều kiện - biến cố tương đương có số các trường hợp, số các biến cố và số các bước như nhau nhưng số các điều kiện của chúng có thể khác nhau. Ví dụ 3.12: Hai hệ mạng điều kiện - biến cố tương đương biểu diễn các mùa trong năm. Hình 3.6. Hai hệ mạng điều kiện - biến cố tương đương Tập các điều kiện B' : s1 – xuân hoặc hạ s2 – xuân hoặc thu s3 – hạ hoặc thu. Tập các trường hợp C' : {s1, s2} = xuân , {s1, s3} = hạ , {s2, s3} = thu ,  = đông. Định lý 3.9: Giả sử  và ' là hai hệ mạng điều kiện - biến cố tương đương. 1. Hệ  là chu trình hệ ' là chu trình. 2. Hệ  là sống hệ ' là sống. Hệ mạng điều kiện - biến cố tuần tự với các trường hợp bao gồm chỉ một điều kiện tương ứng với các otomat hữu hạn. Với hai hệ như thế sự tương đương trùng với sự đẳng cấu. Bổ đề 3.10: Giả sử  và ' là hai hệ mạng điều kiện - biến cố mà: c C  C’, |c| = 1. Khi đó thì:   ' khi và chỉ khi chúng là đẳng cấu. Chứng minh: Giả sử  là ( ,)-tương đương với '. Vì mỗi trường hợp của chúng chỉ chứa đúng một điều kiện nên mỗi điều kiện b tạo nên trường hợp {b}. Song ánh : C C’ sinh ra song ánh ' : B B’ như sau: 20
'(b) = b' ({b}) = {b'}. Ánh xạ ' :  ' được định nghĩa như sau: '(b) = '(b) nếu b B và '(e) = (e) nếu e E . Hiển nhiên ' là một song ánh. Mọi biến cố đều phải có khả năng xuất hiện. Do vậy, với mọi biến cố e trong E thì 0 < | e| + |e | 2. Giả sử (b, e) F . Thế thì biến cố e là {b} -kích hoạt. Vậy (e) là ({b}) -kích hoạt và ('(b), '(e)) F’. Chứng minh một cách tương tự thì từ (e, b) F suy ra ('(e), '(b)) F'. Điều ngược lại là hiển nhiên. 3.5 Hệ mạng điều kiện - biến cố an toàn Trong phần 3.1 chúng ta đã chỉ ra rằng biến cố sẽ không được kích hoạt trong tình trạng không an toàn. Tình trạng như thế có thể loại trừ được nhờ một phép biến đổi tương đương trên các hệ mạng điều kiện - biến cố. Để làm việc này, ta thêm cho mỗi điều kiện b một điều kiện bù b của nó sao cho trong mỗi trường hợp của hệ thì hoặc b hoặc b được thoả mãn. Định nghĩa 3.13: Giả sử  là hệ mạng điều kiện - biến cố và b, b' là các điều kiện trong B. 1. Điều kiện b' được gọi là bù của điều kiện b khi và chỉ khi b = b' và b = b'. 2. Hệ  là đầy đủ nếu mỗi điều kiện b trong B đều có điều kiện bù b' cũng trong B. Bổ đề 3.11: Giả sử  là hệ mạng điều kiện - biến cố và b là một điều kiện trong B. 1) b có nhiều nhất một bù, được ký hiệu là b . 2) Nếu b có bù là b thì b cũng có bù và b = b. 3) c C : hoặc b c hoặc b c. Nếu hệ  là đầy đủ thì: 4) e E : | e| = |e |. 1 5) c C : |c| = |B|. 2 Chứng minh: 1) Suy từ tính đơn giản của hệ . 2) Suy từ định nghĩa của điều kiện bù. 21
3) Điều này đúng vì trong trường hợp ngược lại thì các biến cố liên quan không thể được kích hoạt trong bất kỳ một trường hợp nào và mâu thuẫn với định nghĩa của hệ mạng điều kiện - biến cố. 4) Suy từ định nghĩa của điều kiện bù. 5) Suy từ 3). Ví dụ 3.14: Cách xây dựng điều kiện bù. Hỉnh 3.7. Điều kiện b và bù của nó b Định nghĩa 3.15: Giả sử  là hệ mạng điều kiện - biến cố. Ký hiệu B là tập các điều kiện trong B không có bù. Với mỗi điều kiện b trong B ta thêm vào điều kiện bù b . Đặt quan hệ: F = { (e, b ) b B  (b, e) F }  { (b , e) b B  (e, b) F }. Với c C đặt (c) = c  {b b B  b c}. Khi đó hệ mạng điều kiện - biến cố  = ( B  {b b B}, E ; F  F, (C)) được gọi là đầy đủ của hệ . Hiển nhiên, mỗi điều kiện b trước đây không có bù trong hệ  thì nay đã có bù trong hệ  . Định lý 3.12: Giả sử  là hệ mạng điều kiện - biến cố và trường hợp c C . 1.  =  2. b B , c C : b (c) b (c). 3. c = (c)  B. Bổ đề 3.13: Hàm : C C’ như trong Định nghĩa 3.15 là một song ánh. 22
Chú ý: Giả sử  là hệ mạng điều kiện - biến cố và biến cố e E. Để đơn giản ký hiệu ta viết –e và e– chỉ tập vào và tập ra tương ứng của e trong hệ đầy đủ  . Định lý 3.14: Giả sử  là hệ mạng điều kiện - biến cố và tập G  E. Ký hiệu B là tập các điều kiện không có bù trong B . a) –G = G  {b b B  b G } và G– = G  {b b B  b G } – – b) G = G  B , G = G  B . Bây giờ ta chỉ ra rằng việc làm đầy đủ một hệ mạng điều kiện - biến cố sẽ cho ta một hệ mạng điều kiện - biến cố an toàn tương đương. Định lý 3.15: Nếu hệ  là đầy đủ của hệ  thì  tương đương với  . Chứng minh: Vì : C C  là một song ánh nên ta chỉ cần chỉ ra rằng: c1, c2 C , G  E : c1 [ G > c2 (c1) [ G > (c2). Theo Bổ đề 3.13 ta cần chỉ ra rằng: – – ( c1 \ c2 = G  c2 \ c1 = G ) ( (c1) \ (c2) = G  (c2) \ (c1) = G ). Chứng minh mệnh đề  : Theo Định lý 3.12 và 3.14 ta có: – – c1 = (c1)  B , c2 = (c2)  B , G = G  B và G = G  B. Vậy thì: – c1 \ c2 = ( (c1)  B) \ ( (c2)  B) = ( (c1) \ ( (c2))  B) = G  B = G. Tương tự ta có: c2 \ c1 = G . Chứng minh mệnh đề ngược lại : Giả sử tập B là tập các điều kiện không có bù của hệ  và: B 1 = {b b B \ c1} và B 2 = {b b B \ c2}. Vậy thì: (c1) = c1  B 1 và (c2) = c2  B 2 . (c1) \ (c2) = (c1  B 1) \ (c2  B 2) = (c1 \ (c2  B 2))  ( B 1 \ (c2  B 2) 23
= (c1 \ c2)  ( B 1 \ B 2) vì c1  B 2 = B 1  c2 =  = G  ({b b B \ c1} \ {b b B \ c2}) = G  {b b (B \ c1)  b (B \ c2)} = G  {b b B  b c1  b c2} = G  {b b B  b (c2 \ c1)} = G  {b b B  b G } = –G (theo Định lý 3.12). – Chứng minh tương tự ta cũng có: (c2) \ (c1) = G . Định nghĩa 3.16: Giả sử  là hệ mạng điều kiện - biến cố. Hệ  được gọi là an toàn (safe) nếu với mỗi biến cố e E và mỗi trường hợp c C : 1. e  c e  B \ c , nghĩa là e  c = . 2. e  c e  B \ c , nghĩa là e  c = . Chú ý rằng, trong định nghĩa trên mệnh đề 2. không phải bao giờ cũng suy được từ mệnh đề 1. Chẳng hạn, xét hệ đơn giản sau đây: Hình 3.8. Một hệ mạng đơn giản Định lý 3.16: 1) Mọi hệ mạng điều kiện - biến cố đầy đủ là an toàn. 2) Mỗi hệ mạng điều kiện - biến cố đều có một hệ mạng an toàn tương đương. 3) Nếu hệ  là an toàn thì: e E : e   e . Chứng minh: 1) Giả sử hệ  là đầy đủ, b B , e E và c C. Nếu b e  c thì b e  (B \ c). Do vậy: e  c. Còn nếu b e  c thì b e  (B \ c). Do vậy: e  c. 2) Hệ  chính là hệ đầy đủ, an toàn tương đương cần tìm. 3) Giả sử rằng e = . Thế thì e  vì e không cô lập. Khi đó, c C mà e  c. Vì e  B \ c nên mâu thuẫn với giả thiết e = . Chứng minh tương tự cho trường hợp e = . Hiển nhiên, không phải mọi hệ mạng điều kiện - biến cố an toàn nào cũng đầy đủ. 24
3.6 Đồ thị các trường hợp Để có cái nhìn đầy đủ tất cả các bước của một hệ mạng điều kiện - biến cố, ta xây dựng đồ thị các trường hợp của hệ này. Các đỉnh của đồ thị chính là các trường hợp còn các cung là các bước xảy ra trên hệ mạng. Định nghĩa 3.17: Giả sử  là một hệ mạng điều kiện - biến cố. Ký hiệu  là tập tất cả các bước của hệ này. Đặt: P = { (c1, G, c2) C  C  c1 [ G > c2 }. Đồ thị  = (C, P) được gọi là đồ thị các trường hợp của . Định lý 3.17: Hệ mạng điều kiện - biến cố  là chu trình nếu và chỉ nếu đồ thị các trường hợp của nó là liên thông mạnh. Chứng minh: Giả sử hệ mạng điều kiện - biến cố  với tập các bước . Khi đó: *  là chu trình c, c' C : (c, c') r c, c' C , G1, G2, Gn  , c0, c1, cn C : c = c0 [G1 > c1 [G2 > c2 . cn-1 [Gn > cn = c'  là liên thông mạnh. Định lý 3.18: Hệ mạng điều kiện - biến cố  là sống khi và chỉ khi với mỗi trường hợp c C và với mỗi biến cố e E đều có một đường đi trong đồ thị  mà nhãn Gn = {e}. Chứng minh: Hệ mạng điều kiện - biến cố  là sống * c C , e E , c', c" C : (c, c') r  c' [e > c" Tồn tại đường đi mà cn-1 = c' , Gn = {e} và cn = c". Đó chính là điều phải chứng minh. Ví dụ 3.18: 25
Hệ mạng điều kiện - biến cố Đồ thị các trường hợp Hình 3.9. Hệ mạng điều kiện - biến cố và đồ thị các trường hợp của nó Hệ này là chu trình và đồ thị các trường hợp của nó là liên thông mạnh. Định lý 3.19: Hai hệ mạng điều kiện - biến cố là tương đương khi và chỉ khi đồ thị các trường hợp của chúng là đẳng cấu với nhau. Chứng minh: Giả sử  và ' là hai hệ mạng điều kiện - biến cố với đồ thị các trường hợp tương ứng là  = (C , P) và ’ = (C’, P'). Ký hiệu  là tập các bước của .  là ( ,)-tương đương với ' ( c, c' C , G  : c [G > c' (c) [ (G) > (c') ) (c, c' C , G  : (c, G, c')  ( (c), (G), (c') ’)  là ( ,)-đẳng cấu với ’. Không phải mọi đồ thị định hướng đều có thể thể hiện như đồ thị các trường hợp của hệ mạng điều kiện - biến cố. Ta xét đồ thị định hướng gán nhãn sau đây: Hình 3.10. Một đồ thị định hướng gán nhãn Theo đồ thị trên thì hai biến cố e1 và e2 đều được trường hợp c1 kích hoạt. Nếu trong c1 có xung đột giữa e1 và e2 thì c2 không thể kích hoạt e2. Khi đó, trong 26
đồ thị phải bỏ cung (c2, {e2}, c4) đi. Ngược lại, nếu trong c1 không có xung đột giữa e1 và e2 thì c3 có thể kích hoạt e1. Vậy thì, trong đồ thị phải thêm cung (c3, {e1}, c4) vào. Đồ thị các trường hợp trở nên rất phức tạp đối với các hệ tương tranh mạnh. Chẳng hạn, một bước chứa n biến cố sẽ sinh ra 2n cung trong đồ thị các trường hợp. Định lý sau đây sẽ thể hiện điều đó. Định lý 3.20: Giả sử  là hệ mạng điều kiện - biến cố và c1, c2, c3 C , G1, G2  E. 1. Nếu là một đường đi trong đồ thị  thì G1  G2 = . 2. Giả sử G1  G2 = . Nếu (c1, G1  G2, c2) là một cung trong  thì tồn tại c C sao cho cũng là một đường đi trong đồ thị . Chứng minh: 1) Giả sử biến cố e G1. Khi đó thì e  c2 = . Thế thì e không là c2 -kích hoạt. Suy ra e G2. Giả sử e G2. Suy ra, c2  e = . Vậy thì e G1. 2) Nếu (c1, G1  G2, c2) là một cung trong đồ thị  thì c1 [G1  G2 > c2. Khi đó, ta có: c1 [G1 > c và c[G2 > c2 với c = (c1 \ G1)  G1 . BÀI TẬP CHƯƠNG 3 3.1. Bài toán sói, dê và bắp cải: Một con sói, một con dê và một thùng bắp cải đang ở bên bờ sông. Người lái đò phải đưa chúng sang bên kia sông. Nhưng thuyền quá bé nên mỗi chuyến chỉ chở được một “hành khách” thôi. Vì những lý do mà ai cũng biết, không thể bỏ mặc sói với dê hoặc dê với bắp cải mà không có người trông. Bạn hãy tổ chức giúp người lái đò một cách sang sông thích hợp dưới dạng một hệ mạng điều kiện - biến cố. 3.2. Xây dựng hệ mạng điều kiện - biến cố biểu diễn chương trình tương tranh cộng hai số nguyên dương m, n theo thuật toán tương tranh sau đây: Lần lượt tăng m thêm 1 đồng thời giảm n đi 1 cho đến khi n = 0, rồi in m ra. 3.3. Xây dựng hệ mạng đầy đủ cho hệ mạng điều kiện - biến cố dưới đây: 27
Hình 3.11. Hệ mạng điều kiện - biến cố Xây dựng đồ thị các trường hợp cho hệ mạng này. 3.4. Bài toán "bữa ăn tối của năm nhà triết học": Mỗi buổi tối năm nhà triết học cùng ngồi quanh một cái bàn tròn vừa suy nghĩ vừa ăn. Trên bàn có một đĩa mì ống, năm đĩa ăn nhỏ đặt trước mặt các nhà triết học và năm cái dĩa để xen kẽ giữa các đĩa ăn. Khi ăn, mỗi nhà triết học phải dùng cả hai dĩa ở bên trái và bên phải mình. Ăn xong, ông ta đặt cả hai dĩa xuống chỗ cũ và tiếp tục suy nghĩ. Hãy mô tả bữa ăn này bằng một hệ mạng điều kiện - biến cố. 28
Chương 4 CÁC QUÁ TRÌNH TRÊN HỆ MẠNG ĐIỀU KIỆN - BIẾN CỐ Trong chương này chúng ta nghiên cứu các quá trình xảy ra trên một hệ mạng điều kiện - biến cố. Có thể định nghĩa quá trình của hệ mạng điều kiện - biến cố như là một đường đi trong đồ thị các trường hợp của nó. Song đường đi như thế không mô tả chính xác được cái mà ta hiểu trực quan từ quá trình. Thứ tự tổng thể của các phần tử của nó cũng không cho ta một thông tin nào về sự xuất hiện trước sau của các biến cố hoặc liệu chúng có độc lập với nhau hay không. Thứ tự bộ phận mà trong đó các biến cố xuất hiện chỉ được biểu diễn gián tiếp trong đồ thị các trường hợp bởi tập tất cả các khả năng xuất hiện kế tiếp của các bước. Bởi vậy, chúng ta muốn tìm một cách mô tả thích hợp hơn cho quá trình. Đặc biệt là, nó phải rõ ràng và chỉ ra được một cách tường minh rằng các biến cố có xuất hiện một cách đồng thời hay không. Mô tả như thế được xem như là bản ghi sự xuất hiện của các biến cố và sự thay đổi của các điều kiện. Các phần tử của bản ghi này được sắp thứ tự bộ phận nhờ quan hệ “a là điều kiện trước cho b”. Hơn nữa, sự lặp lại của chính biến cố hay chính điều kiện này được ghi lại như một phần tử mới. Có một biểu diễn thực sự đúng đắn cho các bản ghi như thế lại là một loại mạng. Chẳng hạn, mọi sự xuất hiện trên mạng ở ví dụ trong phần 3.6 được biểu diễn đầy đủ như sau: Hình 4.1. Biểu diễn mạng tương ứng với mạng trong Hình 3.17 T- phần tử đã cho biểu diễn sự xuất hiện của biến cố và được ký hiệu bởi nhãn của nó. Các T-phần tử khác nhau nhưng có cùng một nhãn ký hiệu sự xuất hiện nhiều lần khác nhau của chính biến cố này. Tương tự, một S- phần tử s chỉ ra bởi diễn tả b của mình rằng: “b được thoã mãn khi s xuất hiện và 29
thôi không thoả mãn nữa khi s xuất hiện". Như trong các tình huống cụ thể tương ứng, các xung đột đã được giải quyết vì tất cả các S-phần tử không phân nhánh. Để dễ dàng điều khiển các quá trình được mô tả như thế, chẳng hạn “mạng được sắp thứ tự bộ phận”, ta cần phải xét một số tính chất của tập có thứ tự bộ phận và sau đó xét các mạng hiện. Đó là các mạng được sắp thứ tự bộ phận và thích hợp để mô tả các quá trình. Sau đó, ta trình bày khái niệm quá trình và chỉ ra rằng các quá trình có thể hợp thành và phân tách như thế nào. Đồng thời, ta cũng nghiên cứu mối liên hệ của chúng với đồ thị các trường hợp. 4.1 Tập có thứ tự bộ phận Các quan hệ độc lập hay phụ thuộc thường là đối xứng, phản xạ nhưng nói chung là không bắc cầu. Trước hết, ta xét quan hệ tương tự. Định nghĩa 4.1: Giả sử A là một tập hợp. Quan hệ nhị nguyên  A A được gọi là quan hệ tương tự nếu: 1. a A : (a, a) (tính phản xạ). 2. a, b A : (a, b) (b, a) (tính đối xứng). Tập con B  A được gọi là một vùng của quan hệ tương tự nếu: a) a, b B : (a, b) (tính đầy đủ) b) a A \ B , b B : (a, b) (tính cực đại). Định lý 4.1: Giả sử A là một tập hợp và là một quan hệ tương tự trên A. 1. Mỗi phần tử của A phải thuộc vào một vùng của . 2. Các vùng của tập không rỗng A là khác rỗng và không có vùng nào là tập con thực sự của một vùng khác. 3. Nếu là quan hệ tương đương thì các vùng của chính là các lớp tương đương của nó. Biểu diễn đồ thị cho quan hệ tương tự: Một quan hệ tương tự trên tập hữu hạn A có thể biểu diễn như một đồ thị vô hướng: A là tập các đỉnh và: E = { (a, b)  a b  (a, b) } là tập các cạnh. 30
Ví dụ 4.2: Một quan hệ tương tự với 4 vùng. Hình 4.2. Quan hệ tương tự và các vùng của nó Bây giờ ta xét tập hợp có thứ tự bộ phận, nghĩa là tập hợp mà trên nó có một quan hệ không phản xạ và bắc cầu. Hai quan hệ li và co được định nghĩa như sau: Định nghĩa 4.3: Giả sử A là tập có thứ tự bộ phận < . 1. Quan hệ li  A A được xác định như sau: (a, b) li a < b  b < a  a = b. 2. Quan hệ co  A A được xác định như sau: (a, b) co  (a < b)  a = b. Định lý 4.2: Giả sử A là tập có thứ tự bộ phận và a, b A. 1. (a, b) li  (a, b) co , 2. (a, b) li  (a, b) co a = b. Định lý 4.3: Với mỗi tập có thứ tự bộ phận A thì li và co là các quan hệ tương tự. Chứng minh: Tính phản xạ và đối xứng của li suy từ chính định nghĩa. Phần bù của quan hệ li là đối xứng và do thêm vào các cặp (x, x) nên trở thành phản xạ. 31
Ví dụ 4.4: Giả sử tập A và quan hệ thứ tự bộ phận < được cho như sau: Hình 4.3. Đồ thị định hướng biểu diễn tập có thứ tự bộ phận Khi đó, hai quan hệ tương tự li và co được biểu diễn bằng đồ thị vô hướng sau đây: li co Hình 4.4. Hai quan hệ tương tự sinh từ tập có thứ tự bộ phận Định nghĩa 4.5: Giả sử A là tập có thứ tự bộ phận và tập con B  A. 1. Tập con B được gọi là một đường nếu nó là một vùng của quan hệ li. 2. Tập con B được gọi là một nhát cắt nếu nó là một vùng của quan hệ co. Chẳng hạn, tập A trong ví dụ trên có 3 đường là {a,b,c}, {e,f,g}, {a,b,d,f,g} và 5 nhát cắt là {e,a}, {e,b}, {e,d,c}, {f,c}, {g,c}. Định lý 4.4: Giả sử A là tập có thứ tự bộ phận và tập con B  A. 1. Tập con B là một đường nếu và chỉ nếu: i) a, b B : a < b  b < a  a = b và 32
ii) a A \ B , b B :  (a < b  b < a) . 2. Tập con B là một nhát cắt nếu và chỉ nếu: i) a, b B :  (a < b  b < a) và ii) a A \ B , b B : a < b  b < a . Khái niệm tập bị chặn và tập trước được định nghĩa như sau: Định nghĩa 4.6: Giả sử A là tập có thứ tự bộ phận và giả sử B và C là các tập con của tập A. 1. Tập A là bị chặn nếu và chỉ nếu có một số nguyên dương n N sao cho mọi đường đi L trong A đều thoả mãn: |L| n . 2. Tập con B được gọi là trước tập con C (ta viết: B C) nếu: b B , c C : b < c  (b, c) co. ( B < C có nghĩa là: B C  B C ). 3. Ta ký hiệu: B = {a A  {a} B} và B+ = {a A  B {a}} - được gọi là tập trước và tập sau của B. B = {b B b' B : (b, b') co  b < b'} và B = {b B b' B : (b', b) co  b' < b}. Cụ thể là, B bao gồm các phần tử ”cực tiểu” của B và B bao gồm các phần tử ”cực đại” của B. Định lý 4.5: Nếu A là tập có thứ tự bộ phận bị chặn thì các tập con A và A là các nhát cắt. Chứng minh: Giả sử a và b là các phần tử tuỳ ý của A. Thế thì, (a, b) co bởi vậy  (a < b  b < a). Giả sử c A \ A và giả sử L là một đường đi trong A mà c L. Vì L hữu hạn nên có phần tử d L  A và d < c. Theo Định lý 4.4 suy ra A là một nhát cắt. Tương tự, chỉ ra rằng A cũng là một nhát cắt. Một đường và một nhát cắt có chung nhiều nhất một phần tử. 33
Định lý 4.6: Giả sử A là tập có thứ tự bộ phận, L là một đường và D là một nhát cắt trên A. Khi đó: |L  D | 1. Chứng minh: Giả sử a, b L  D. Thế thì, (a, b) li vì a, b L. Mặt khác, ta có: (a, b) co vì a, b D. Theo Định lý 4.2 ta có a = b. Tính K-trù mật của một tập có thứ tự bộ phận được định nghĩa như sau: Định nghĩa 4.7: Tập có thứ tự bộ phận A được gọi là K-trù mật nếu mỗi đường và mỗi một nhát cắt trong A đều có giao khác rỗng. Chẳng hạn, tập A trong ví dụ trên là K-trù mật. Tuy nhiên, không phải tập có thứ tự bộ phận nào cũng là K-trù mật. Ví dụ 4.8: đường L = {c, b}, nhát cắt D = {a, d} và L  D =  Hình 4.5. Tập không K-trù mật 4.2 Mạng hiện Mạng hiện là một mạng phi chu trình với các S-phần tử là không rẽ nhánh. Thế thì, ta sẽ có một thứ tự bộ phận trên các phần tử của mạng. Ta sẽ chỉ ra rằng các mạng hiện là K-trù mật. Do vậy, mạng hiện thường được ding để biểu diễn các quá trình trên một hệ mạng điều kiện - biến cố. Định nghĩa 4.9: Mạng K = (SK, TK; FK) được gọi là một mạng hiện (occurrence net) nếu và chỉ nếu: + + 1. a, b K : (a, b) FK (b, a) FK (mạng K là phi chu trình). 34
2. s SK : | s| 1  |s | 1 (S-phần tử không phân nhánh). Định lý 4.7: Giả sử K là một mạng hiện. Quan hệ < được định nghĩa như sau: + a, b K : a < b (a, b) FK là một thứ tự bộ phận trên K. Vậy thì, các khái niệm liên quan đến thứ tự bộ phận như: đường, nhát cắt, tính bị chặn, K-trù mật đều có thể áp dụng cho các mạng hiện. Định nghĩa 4.10: Nhát cắt của mạng hiện K chỉ chứa các S-phần tử được gọi là một lát cắt. Ký hiệu: sl(K) là tập tất cả các lát cắt của mạng hiện K. Ví dụ 4.11: Xét mạng hiện sau đây: Hình 4.6. Một mạng hiện Mạng này có 3 đường, 11 nhát cắt trong đó có 5 lát cắt. Chẳng hạn: - đường: {s1, t2, s4, t3, s6} , - nhát cắt: {t1, s4, s5} , - lát cắt: {s1, s3} , Định lý 4.8: Mọi mạng hiện không rỗng bị chặn đều là K-trù mật. Chứng minh: Ta chứng minh định lý bằng phản chứng. Giả sử K là một mạng hiện nào đó không rỗng, bị chặn nhưng không là K-trù mật. Thế thì có một đường L và một nhát cắt D trong K mà L  D = . Vì 35
đường L không rỗng và hữu hạn nên tồn tại x1 = min (L) và x2 = max (L).   Hiển nhiên, x1 K và x2 K . Vì D là một nhát cắt và x1 D nên tồn tại  d D sao cho x1 < d  d < x1. Hơn nữa, do x1 K nên x1 < d.  Bằng cách lý luận tương tự, do x2 K nên tồn tại d' D sao cho d' < x2. Đặt a1 = max {x L  d D : x < d} và a2 = min {x L  d' D : d' < x}. Sự tồn tại của x1 và x2 suy từ tính hữu hạn của L. Nếu a2 a1 thì phải tồn tại d, d' D sao cho d' < a2 a1 < d. Nhưng điều này không thể xảy ra vì D là một nhát cắt. Do vậy, a1 < a2 vì a1, a2 L. Từ định nghĩa của a1 và a2 suy ra rằng có đường đi từ a1 tới phần tử d nào đó trong nhát cắt D và có đường đi từ phần tử d' nào đó trong nhát cắt D tới a2. Vậy thì: b1 a1 , d D sao cho b1 d và b2 a2 , d' D sao cho d' b2. Hình 4.7. Đường L và nhát cắt D không giao nhau Cũng theo định nghĩa của a1 và a2 suy ra rằng phần tử b1, b2 không thể nằm trên L. Vì a1, a2 L và a1 < a2 nên tồn tại c1 a1 và c1 L . Đồng thời, tồn tại c2 a2 và c2 L . Hiển nhiên, b1 c1 và b2 c2. Các S-phần tử là không phân nhánh nên a1, a2 phải cùng thuộc TK. Do vậy, (a1, a2) FK. Thế thì phải có ít nhất một S-phần tử s L sao cho a1 < s < a2. 36
Mà theo định nghĩa của a1 ta có: d D : (s, d) co. Nhưng điều này không thể xảy ra vì D là một nhát cắt. Vậy giả thiết của phản chứng là sai và mạng hiện K là K-trù mật. Định lý được chứng minh. Chú ý rằng, mạng hiện không bị chặn chưa chắc đã là K-trù mật. Xét phản ví dụ sau đây. Ví dụ 4.12: Xét mạng hiện không bị chặn dưới đây. Hình 4.8. Một mạng hiện không bị chặn Mạng hiện không bị chặn này là không là K-trù mật, bởi vì đường L = {s0, t1, s1, t2, s3, } không giao với nhát cắt D = {s1', s2', }. 4.3 Các quá trình Bây giờ chúng ta định nghĩa các quá trình của một hệ mạng điều kiện - biến cố bằng cách sử dụng các mạng hiện bị chặn. Vì mỗi hệ mạng điều kiện - biến cố đều có thể biến đổi thành một hệ mạng điều kiện - biến cố an toàn tương đương nên ta chỉ định nghĩa quá trình cho các hệ mạng điều kiện - biến cố an toàn. Các quá trình sẽ được mô tả như các ánh xạ từ các mạng hiện bị chặn vào hệ mạng điều kiện - biến cố an toàn và thoả mãn hai yêu cầu sau đây: 1. Mỗi lát cắt được ánh xạ 1 - 1 vào một trường hợp. 2. Ánh xạ mỗi T-phần tử vào một biến cố và phải bảo toàn môi trường của biến cố này. Hay nói một cách khác, mỗi quá trình là việc "nhúng" một mạng hiện vào một hệ mạng điều kiện - biến cố an toàn. 37
Định nghĩa 4.13: Giả sử K là một mạng hiện bị chặn và  là một hệ mạng điều kiện - biến cố an toàn. Một ánh xạ p : K  được gọi là một quá trình của  nếu với mỗi lát cắt D của K và mỗi phần tử t TK thoả mãn: 1. pD là ánh xạ 1 - 1 và p(D) C . 2. p( t) = p(t) và p(t ) = p(t) . Trong biểu diễn đồ thị của quá trình p : K , mỗi phần tử x của K được gán nhãn bởi ảnh p(x) của nó. Tính K-trù mật của các mạng hiện bị chặn là một tính chất quan trọng để sử dụng mạng hiện trong mô tả các quá trình không tuần tự. Mỗi đường biểu diễn dãy các phần tử mà chúng phụ thuộc nhân quả lẫn nhau, thể hiện như một quá trình con tuần tự. Tính K-trù mật của mạng hiện đảm bảo rằng mỗi quá trình con đều tuần tự được. Định lý 4.9: Với mỗi quá trình p : K  ta có: 1. p(SK)  B  p(TK)  E – quá trình p không làm thay đổi loại. 2. x, y K : (x, y) FK (p(x), p(y)) F – quá trình p bảo toàn quan hệ lưu đồ. 3. x, y K : p(x) = p(y) (x, y) li – không có điều kiện hoặc biến cố nào tương tranh với chính mình. 4. t TK : t   t  – mọi biến cố đều có tập vào và tập ra. 5. Với mỗi nhát cắt D của K thì pD là ánh xạ 1 - 1. Chứng minh: 1. Mệnh đề p(SK)  B suy trực tiếp từ Định nghĩa 4.13 vì mỗi s SK thuộc vào ít nhất một lát cắt. Với t TK có tồn tại x  sao cho x p(t)  p(t) . Vậy theo Định nghĩa 4.13 phải tồn tại y t  t mà p(y) = x. Vì y SK nên ta có: x B và p(t) x  x  E. 2. Với s SK và t TK thì: (s, t) FK s t p(s) p(t) (p(s), p(t)) F . Tương tự với (t, s) FK thì: 38
(t, s) FK s t p(s) p(t) (p(t), p(s)) F . 3. Với x,y SK thì kết quả suy trực tiếp từ định nghĩa. x, y TK , x y , p(x) = p(y) suy ra p(x) = p(y) và p(x) = p(y) . .Từ Định nghĩa 4.13 suy ra p( x) = p( y) và p(x ) = p(y ). Giả sử ngược lại là (x, y) co. Khi đó tồn tại các lát cắt D1  x  y và D2  x  y . Hoặc x  y hoặc x  y là không rỗng và x  y =  = x  y vì các S- phần tử của mạng hiện K là không rẽ nhánh. Thế thì, pD1 hoặc pD2 không phải là ánh xạ 1 - 1. Mâu thuẫn với định nghĩa của quá trình. Do vậy, x li y. 4. Với t TK , sử dụng 1. ta có p(t) E. Theo Định lý 3.16 ta có: p(t)  và p(t)  . Dựa vào Định nghĩa 4.13. 2. ở trên ta suy ra điều phải chứng minh. 5. Suy từ 3. và Định nghĩa 4.13. 1. ở trên. Định lý 4.10: Giả sử p : K  là một quá trình và tập con T  TK thoả mãn t1, t2 T : (t1, t2) co. Thế thì, c1, c2 C : c1 [ p(T) > c2 . Chứng minh: Hiển nhiên, s1, s2 T : (s1, s2) co. Khi đó tồn tại một lát cắt D sl(K) mà T  D . Theo Định nghĩa 4.13 ta có p(D) C và p(T) = p( T)  p(D) . Từ đây suy ra: s T , s1 D sao cho s1 < s. Do vậy, T  D =  và p(D)  p(T ) = p(D)  p(T) = . Vậy thì, p(T) là p(D) -kích hoạt. Đó là điều phải chứng minh. Định nghĩa 4.14: Hai quá trình p1 : K1  và p2 : K2  của cùng một hệ mạng điều kiện - biến cố  được gọi là đẳng cấu nếu mạng hiện K1 là -đẳng cấu với mạng hiện K2 và: x K1 : p1(x) = p2((x)). Từ đây ta không phân biệt các quá trình đẳng cấu mà ta có thể hiểu hoặc là lớp các tương đương các quá trình đẳng cấu với nhau hoặc là một đại diện nào đó của lớp này. 39
Một quá trình p : K  thường được biểu diễn bởi tập hợp các cặp {(x, p(x)) x K}. Các hệ mạng điều kiện - biến cố an toàn được đặc trưng một cách đầy đủ bởi tập các quá trình của chúng. Định lý 4.11: Giả sử 1, 2 là hai hệ mạng điều kiện - biến cố an toàn và giả sử Pi là tập các quá trình của i (i = 1, 2). Khi đó thì: P1 = P2 1 = 2. Chứng minh: Giả sử i = (Bi, Ei; Fi, Ci) , i = 1, 2 và giả sử 1 2. Không mất tính tổng quát, có thể khẳng định là tồn tại b B1  B2 hoặc e E1  E2 hoặc c C1  C2 mà b B1 \ B2 hoặc e E1 \ E2 hoặc (b, e) F1 \ F2 hoặc (e, b) F2 \ F1 hoặc c C1 \ C2. Vậy thì sẽ có một bước c1 [ e' > c2 trong hệ 1 nhưng không xảy ra trong hệ 2. Chẳng hạn, chọn b c1  c2 hoặc e' = e hoặc c = c1 hoặc c = c2 một cách tương ứng.  Với K = (S, {t}; F), giả sử p : K 1 là một quá trình mà p( K) = c1 và  p(K ) = c2 và p(t) = e'. Thế thì, p P1 \ P2. 4.4 Sự hợp thành của các quá trình Với hai quá trình p1, p2 mà p1 kết thúc ở chính trường hợp mà từ đó p2 bắt đầu thì ta có thể định nghĩa phép toán hợp thành trên các quá trình này. Bổ đề 4.12: Nếu p : K  là một quá trình thì tập K và K là các lát cắt của K. Chứng minh: Theo Định lý 4.5 thì K và K là các nhát cắt của K. Vì hệ  là an toàn   nên: e E : e  và e  . Từ Định nghĩa 4.13 suy ra K  K  SK. Bổ đề được chứng minh.   Bổ đề 4.13: Giả sử pi : Ki , i = 1, 2 là hai quá trình với p1(K1 ) = p2( K2). Thế thì có đúng một mạng hiện K sai khác một đẳng cấu, với lát cắt D và quá + trình p : K  thoả mãn: pD- = p1 và pD+ = p2, trong đó D và D là tập trước và tập sau của D. Chứng minh: 40
Giả sử Ki = (Si, Ti; Fi) , i = 1, 2 là hai mạng hiện và không mất tính   tổng quát, giả thiết (S1  T1)  (S2  T2) = K1 = K2 =  .   Khi đó mạng K = (S1  S2 , T1  T2 ; F1  F2), lát cắt D = K1 = K2 và quá trình p được xác định như sau: p(x) = pi(x) x Ki , i = 1, 2 thoả mãn các đòi hỏi trên. Định nghĩa 4.15: Giả sử p1, p2 và p là các quá trình thoả mãn các yêu cầu của Bổ đề 4.13 ở trên. Khi đó, quá trình p được gọi là hợp thành của các quá trình p1 và p2 và ta ký hiệu p = p1 p2 . Dẽ thấy rằng, mỗi lát cắt chia quá trình thành các quá trình con có thể hợp thành được. Định lý 4.14: Giả sử p : K  là một quá trình và giả sử D là một lát cắt của + + mạng hiện K. Giả sử p = pD- và p = pD+ . Thế thì, p và p cũng là các quá trình của hệ  và p = p p+. Ví dụ 4.16: Hợp thành của hai quá trình.  = Hình 4.9. Hợp thành các quá trình Phép toán hợp thành của các quá trình là kết hợp. Định lý 4.15: Giả sử p1, p2, p3 là các quá trình mà hợp thành p1 p2 và p2 p3 xác định. Khi đó thì: p1 (p2 p3) và (p1 p2) p3 là hai quá trình đẳng cấu với nhau. 41
Ta gọi một quá trình là cơ sở nếu nó mô tả một bước. Mỗi quá trình có thể phân tích thành hợp thành của một số hữu hạn quá trình cơ sở.   Định nghĩa 4.17: Quá trình p : K  được gọi là cơ sở nếu SK = K  K .  Chẳng hạn, quá trình p1 trong Ví dụ ở trên là cơ sở với K1 = {b1, b2}  và K1 = {b2, b3, b4}. Định lý 4.16:   1) Quá trình p : K  là cơ sở p( K) [ p(TK) > p(K ) là một bước trên . 2) Nếu quá trình p : K  là cơ sở thì: t1, t2 TK : (t1, t2) co. Định nghĩa 4.18: Quá trình p : K  được gọi là rỗng nếu và chỉ nếu TK =  . Định lý 4.17: 1. Mọi quá trình rỗng đều là cơ sở. 2. Nếu p' là một quá trình rỗng và p p' (hoặc p' p) xác định thì p = p p' (hoặc p = p' p) một cách tương ứng. Định lý 4.18: Với mọi quá trình p : K  đều tồn tại một số hữu hạn quá trình cơ sở p1, p2, , pn sao cho p = p1 p2 pn . Chứng minh: Gọi m là số T-phần tử nhiều nhất trên các đường của mạng hiện K. Ta sẽ chứng minh định lý này bằng quy nạp theo m. Nếu m = 0 thì TK =  và quá trình p là rỗng. Nếu đường dài nhất của K chứa m+1 T-phần tử thì quá trình p được phân tích thành p' và p" mà p = p' p", trong đó đường dài nhất của p' chứa m T-phần tử và p" là quá trình cơ sở khác rỗng. Theo giả thiết quy nạp thì p' được hợp thành từ các quá trình cơ sở p1, p2, , pn. Vậy thì p = p1 p2 pn p". 42
4.5 Các quá trình và đồ thị các trường hợp Trong phần này chúng ta nghiên cứu mối quan hệ giữa các quá trình và đường đi trong đồ thị các trường hợp của một hệ mạng điều kiện - biến cố. Trước hết, ta chỉ ra rằng các quá trình cơ sở tương ứng với các cung trong đồ thị các trường hợp. Sau đó ta tìm các đường đi trong đồ thị mô tả các quá trình đơn. Ta sẽ thấy rằng tất cả các đường đi đó có thể biến đổi lẫn nhau nhờ “phân tách” hay ”hợp nhất” các cung của chúng. Bổ đề 4.19: Giả sử  là một hệ mạng điều kiện - biến cố an toàn. Quá trình p : K  là cơ sở khi và chỉ khi có một cung v = (c1, G, c2) trong   đồ thị các trường hợp  sao cho p( K) = c1, p(K ) = c2 và p(TK) = G. Chứng minh:   Nếu p : K  là cơ sở thì p( K) [ p(TK) > p(K ) là một bước trong .   Vậy thì, (p( K), p(TK), p(K )) là một cung trong đồ thị . Ngược lại, nếu (c1, G, c2) là một cung trong đồ thị  thì c1 [ G > c2. Ta chọn 2 mạng hiện K = (c1  c2, G ; F  (c1  c2  G) ). Thế thì ánh xạ id : K  là một quá trình cơ sở của hệ . Ví dụ 3.19: p = Hình 4.10. Mạng hiện cơ sở và đồ thị các trường hợp 43
Mỗi đường đi trong số 13 đường đi từ đỉnh {1,4} xuống đỉnh {3,6} đều tương ứng với quá trình p. Bổ đề này thiết lập sự tương ứng 1 - 1 giữa các quá trình cơ sở và các cung của đồ thị các trường hợp. Do vậy, ta định nghĩa: Định nghĩa 4.20: Giả sử  là một hệ mạng điều kiện - biến cố an toàn. 1) Nếu v là một cung trong  thì ta ký hiệu v là quá trình cơ sở tương ứng với v, xác định theo bổ đề trên. v được gọi là quá trình của cung v và v được gọi là cung của quá trình v. 2) Giả sử v1, v2, , vn là các cung của đồ thị  và giả sử w = v1 v2 vn là một đường đi trong . Thế thì, w = v1 v2 vn được gọi là quá trình của w còn w được gọi là đường đi của quá trình w. Mỗi đường đi của đồ thị các trường hợp tương ứng với đúng một quá trình. Song, nói chung, có nhiều đường đi tương ứng với cùng một quá trình (Ví dụ trên). Định nghĩa 4.21: Giả sử  là một hệ mạng điều kiện - biến cố và giả sử c1, c2, c3 C và G1, G2  E . 1) Nếu u1 = (c1, G1, c2) , u2 = (c2, G2, c3) và v = (c1, G1  G2, c3) là các cung trong đồ thị  thì đường đi u1u2 được gọi là phân tách của v và v được gọi là hợp thành của u1 và u2. 2) Giả sử w, w' là các đường đi trong đồ thị  , w' được gọi là hoán vị của w nếu tồn tại các đường đi w1, w2, w3, w4 sao cho w = w1 w2 w3 và w' = w1 w4 w3 và w4 là phân tách hoặc hợp nhất của w2. 3) Giả sử w1, w2, , wn là các đường đi trong đồ thị . (w1, w2, , wn) được gọi là một dãy hoán vị nếu với mỗi i = 1, 2, , n thì wi+1 là hoán vị của wi. Trong Ví dụ 3.19 ở trên ta có dãy 13 hoán vị. Định lý 4.20: Giả sử  là một hệ mạng điều kiện - biến cố và giả sử c1, c2, c3 C và hai tập con G1, G2  E không rỗng và rời nhau. 44
1. Nếu v = (c1, G1  G2, c3) là một cung trong đồ thị  thì tồn tại một phân tách của v có dạng với trường hợp c nào đó thuộc C. 2. Giả sử u1 = (c1, G1, c3) và u2 = (c3, G2, c2) là các cung trong đồ thị  và giả sử u1 u2 : K  là một quá trình của hệ . Thế thì: t1, t2 TK : (t1, t2) co (c1, G1  G2, c3) là một cung trong đồ thị . Chứng minh: 1. Suy trực tiếp từ Định lý 3.20. 2. t1, t2 TK : (t1, t2) co có một quá trình cơ sở p : K  sao cho   p( K) = c1, p(K ) = c2 và p(TK) = G1  G2 (c1, G1  G2, c3) là một cung trong đồ thị . Định lý 4.21: Hai đường đi w và w' tương ứng với cùng một quá trình khi và chỉ khi có một dãy hoán vị từ w tới w'. BÀI TẬP CHƯƠNG 4 4.1. Xác định các vùng của quan hệ tương tự sau đây: Hình 4.11. Một quan hệ tương tự 4.2. Chỉ ra các đường, nhát cắt, lát cắt trên mạng hiện dưới đây: Hình 4.12. Một mạng hiện 45
4.3. Giả sử K là một mạng hiện bị chặn và  là một hệ mạng điều kiện - biến cố. Hãy chỉ ra rằng ánh xạ p : K  là một quá trình khi và chỉ khi: 1) pK là đơn ánh và p(K) C và 2) t TK : p( t) = p(t)  p(t ) = p(t)  p là đơn ánh trên t và trên t . 4.4. Phân tách quá trình dưới đây thành hợp thành của một tập ít nhất các quá trình cơ sở: Hình 4.13. Một quá trình 46
Chương 5 HỆ MẠNG VỊ TRÍ - CHUYỂN Để nghiên cứu hệ mạng loại này, ta xét hệ thống sản xuất bao gồm một nhà sản xuất và hai nhà tiêu thụ sản phẩm với các ràng buộc như sau: 1. Mỗi lần sản xuất, nhà sản xuất làm ra được 3 sản phẩm. 2. Có một bộ đếm để đếm số lần sản xuất. 3. Kho của xưởng sản xuất chứa được nhiều nhất là 5 sản phẩm. 4. Tại mỗi thời điểm chỉ có thể cho một nhà tiêu thụ vào lấy hàng. 5. Mỗi lần lấy hàng, nhà tiêu thụ đều mua 2 sản phẩm. Quá trình sản xuất và tiêu thụ sản phẩm trên có thể mô tả bằng hệ mạng sau đây: Hình 5.1. Mô hình hệ thống sản xuất - tiêu thụ 5.1 Hệ mạng vị trí - chuyển Hệ mạng vị trí - chuyển là một trong những mô hình tốt để biểu diễn các hệ tương tranh, được định nghĩa như sau: Định nghĩa 5.1: Bộ sáu  = (P, T; F, W, K, M0) được gọi là một hệ mạng vị trí - chuyển (P/T - net) nếu: 1) Bộ ba (P, T; F) là một mạng Petri hữu hạn, phần tử của tập P được gọi là vị trí còn phần tử của tập T được gọi là chuyển. 2) W : F N \ {0}, là hàm gắn một trọng số dương vào mỗi cung của mạng. 47
3) K : P N  {}, là hàm cho dung lượng (có thể vô hạn) trên mỗi vị trí. 4) M0 : P N  {} là bộ đánh dấu đầu tiên của mạng phù hợp với dung lượng, nghĩa là: p P : M0(p) K(p). Dưới đây, ta đưa ra quy luật hoạt động của một hệ mạng vị trí - chuyển. Định nghĩa 5.2: 1. Ánh xạ M : P N {} được gọi là một bộ đánh dấu của hệ mạng  nếu: p P : M(p) K(p). 2. Giả sử M là một bộ đánh dấu. - Chuyển t T được gọi là M-kích hoạt nếu: p t : M(p) W(p, t) và p t : M(p) K(p) - W(t, p). - Một chuyển M-kích hoạt t hoạt động sẽ cho ta bộ đánh dấu kế tiếp M’ của M như sau: M ( p) W ( p,t) , nếu p t \ t M ( p) W (t, p) , nếu p t \ t M’(p) = , nếu p t  t M ( p) W ( p,t) W (t, p) các trường hợp còn lại. M ( p) Ta nói rằng chuyển t hoạt động và dẫn M tới M’. Ký hiệu: M [ t > M’. 3. Giả sử R(M) là tập nhỏ nhất các bộ đánh dấu thoả mãn: - M R(M) và - Nếu M1 R(M) và với chuyển t nào đó mà M1 [ t > M2 thì M2 R(M). Tập R(M) được gọi là tập các bộ đánh dấu đạt được từ bộ đánh dấu M. Trong biểu diễn đồ thị của một hệ mạng vị trí - chuyển, cung u F được gán nhãn W(u) nếu W(u) > 1. Cung không gán nhãn được hiểu là cung có trọng số bằng 1. Dung lượng tại vị trí p được biểu diễn bởi “k = K(p)"; nếu 48
dung lượng bằng  thì bỏ qua không cần viết. Bộ đánh dấu M được biểu diễn bởi số nguyên M(p) hoặc ký hiệu  viết trên mỗi vị trí p. Nếu dấu trên vị trí nào đó bằng 0 thì không cần viết. Ví dụ 5.3: Chuyển được kích hoạt và hoạt động: Hình 5.2. Hoạt động của một chuyển Chuyển không được kích hoạt: Hình 5.3. Các chuyển không hoạt động được Hiển nhiên, mỗi một hệ mạng điều kiện - biến cố có thể xem như là một hệ mạng vị trí - chuyển mà dung lượng của các vị trí và trọng số của các cung trên mạng bằng 1. Ngược lại, mỗi một hệ mạng vị trí - chuyển với dung lượng của các vị trí và trọng số của các cung bằng 1 hoạt động giống như một hệ mạng điều kiện - biến cố. Cần chú ý rằng, một hệ mạng điều kiện - biến cố liên quan tới một lớp các trường hợp còn một hệ mạng vị trí - chuyển chỉ nhận một bộ đánh dấu đầu tiên. Như một tổng quá hoá của các hệ mạng điều kiện - biến cố, bộ đánh dấu đầu tiên M có thể dẫn chuyển t tới tình trạng không an toàn nếu t bị mất tính M-kích hoạt chỉ vì các vị trí trong tập t không đủ năng lượng. 49
Định nghĩa 5.4: Hệ mạng vị trí - chuyển  = (P, T; F, W, K, M0) được gọi là an toàn nếu với mọi M R(M0) và với mọi t T : p t : M(p) W(p, t) p t : M(p) K(p) - W(t, p). Tương tự như đối với các hệ mạng điều kiện - biến cố, mỗi hệ mạng vị trí - chuyển có thể làm đầy đủ bằng cách thêm vào các vị trí mà hành vi của mạng không bị thay đổi nhưng tình trạng không an toàn sẽ bị loại trừ. Chẳng hạn, Hình 5.4. Thêm bù p' cho vị trí p Giả sử  = (P, T; F, W, K, M0) là một hệ mạng vị trí - chuyển. Hệ mạng ' nhận được bằng cách thêm vào các vị trí và các cung mới như sau: Với mỗi vị trí p không có bù ta thêm vào một vị trí mới p'. Với các cung (p, t) và (t, p) thuộc F ta thêm vào các cung mới (t, p') và (p', t) một cách tương ứng. Đồng thời W’(t, p') = W(p, t) và W’(p',t) = W(t, p). Dung lượng tại các vị trí mới K’(p') = K (p). Với các vị trí mới p' thì bộ đánh dấu đầu tiên được bổ sung: M0’(p') = K(p) - M0(p). Hiển nhiên, hệ mạng nhận được ' là an toàn vì với mỗi bộ đánh dấu đạt được M ta luôn có: M(p) + M(p') = K(p). Bộ đánh dấu M của mạng  và bộ đánh dấu M' của mạng ' tương ứng với nhau khi và chỉ khi thu hẹp của M' trên P là bằng M. Hiển nhiên, sự tương ứng này là 1 - 1. Với các bộ đánh dấu M của hệ mạng  và M' của hệ 50
mạng ' tương ứng nhau thì một chuyển t là M-kích hoạt trong  khi và chỉ khi t là M'-kích hoạt trong '. Hơn nữa, mọi dung lượng hữu hạn của các vị trí trong ' có thể thay bằng  mà không làm thay đổi hành vi của hệ mạng '. 5.2 Biểu diễn đại số cho các hệ mạng vị trí - chuyển Quy tắc hoạt động trên các hệ mạng vị trí - chuyển có thể đơn giản hoá nhờ biểu diễn đại số tuyến tính như sau. Giả sử  = (P, T; F, W, K, M0) là một hệ mạng vị trí - chuyển. 1) Với chuyển t T, ta xây dựng vectơ t : P Z như sau: W ( p,t) , nếu p t \ t W (t, p) , nếu p t \ t t(p) = , nếu p t  t W (t, p) W ( p,t) các trường hợp còn lại. 0 2) Xây dựng ma trận  : P T Z như sau: (p,t) = t(p). Ma trận  được gọi là biểu diễn đại số tuyến tính của hệ mạng vị trí - chuyển . Mỗi bộ đánh dấu M, dung lượng K của mạng có thể biểu diễn như các vectơ. Chẳng hạn, biểu diễn đại số tuyến tính của hệ mạng sản xuất - tiêu thụ ở đầu chương như sau: t1 t2 t3 t4 t5 K M0 p1 1 -1 1 1 p2 -1 1 1 p3 1 5 5 p4 3 -2 5 3 p5 1 -1 2 p6 1 -1 2 2 p7 -1 1 1 Phần tử (pi,tj) diễn tả sự thay đổi trong đánh dấu tại vị trí pi khi chuyển tj hoạt động. 51
Biểu diễn ma trận rất rõ ràng đối với các hệ mạng tinh khiết. Trong trường hợp này, các thành phần P, T, F và W có thể xác định ngược lại nhờ ma trận biểu diễn của hệ mạng . Nếu hệ mạng vị trí - chuyển  là an toàn thì hành vi của  sẽ được xác định một cách đầy đủ bởi ma trận  và vectơ MN. Với cách biểu diễn ma trận, ta tìm được công thức ngắn gọn cho quy luật hoạt động trên hệ mạng như sau. Định lý 5.1: Giả sử  là một hệ mạng vị trí - chuyển và M và M' là hai bộ đánh dấu của hệ mạng này. 1. Nếu chuyển t là M-kích hoạt thì: M [ t > M' M + t = M'. 2. Nếu hệ mạng  là tinh khiết thì: - Chuyển t là M-kích hoạt 0 M + t K - Hệ mạng  là an toàn M R(M0) : 0 M + t M + t K. Với các hệ mạng có dung lượng vô hạn tại các vị trí thì tính chất đơn điệu sau đây thoả mãn. Bổ đề 5.2: Giả sử  là một hệ mạng vị trí - chuyển mà các vị trí của nó đều có dung lượng vô hạn. Giả sử M1, M2 là hai bộ đánh dấu của mạng. 1. M1 [ t > M (M1 + M2) [ t > (M + M2) 2. M R(M1) (M + M2) R(M1 + M2). Chứng minh: 1. Điều này hiển nhiên trên cơ sở của định nghĩa. 2. Suy từ điều 1. Định nghĩa 5.4: Giả sử  là một hệ mạng vị trí - chuyển và U là tập con các chuyển tách được. Tập U được gọi là một bước trên hệ mạng  nếu: M R(M0) , t U : t là M -kích hoạt. Hiển nhiên, tập con các chuyển U là một bước khi và chỉ khi tập U là tách được và tồn tại M R(M0) : 0 M + t K. 52
5.3 Đồ thị phủ của hệ mạng vị trí - chuyển Thật là tuyệt nếu ta có một đồ thị hữu hạn biểu diễn trực tiếp các bộ đánh dấu đạt được của một hệ mạng vị trí - chuyển (hữu hạn). Điều này thật khó làm vì nói chung có nhiều vô kể các bộ đánh dấu đạt được khác nhau. Bởi vậy, ta chỉ lấy một đồ thị hữu hạn mà mỗi bộ đánh dấu đạt được hoặc được biểu diễn tường minh bằng một đỉnh của đồ thị hoặc được “phủ“ bởi một đỉnh. Đồ thị như thế được gọi là đồ thị phủ của hệ mạng. Ví dụ 5.5: Xét hệ mạng vị trí - chuyển sau đây. Hình 5.5. Biểu diễn đồ thị của một hê mạng vị trí - chuyển Từ bộ đánh dấu đầu tiên các chuyển hoạt động cho ta các dãy hoạt động vô hạn mà một phần của nó được thể hiện như đồ thị dưới đây. Hình 5.6. Đồ thị vô hạn thể hiện các dãy hoạt động trên một hê mạng vị trí - chuyển 53
Ta cần phải phủ đồ thị vô hạn này bằng một đồ thị hữu hạn nhưng vẫn phản ánh đầy đủ các hoạt động của hệ mạng đa cho. Mỗi đỉnh của đồ thị phủ như là một bộ đánh dấu của hệ mạng, một số đỉnh thực sự là các bộ đánh dấu đạt được còn những đỉnh khác phủ các bộ đánh dấu đạt được. Ý tưởng chủ đạo cho việc phủ các bộ đánh dấu xuất phát từ việc phân tích các dãy vô hạn các hoạt động và các bộ đánh dấu được sinh ra như thế nào. Giả sử M và M' là hai bộ đánh dấu đạt được của hệ mạng và M' R(M). Giả thiết thêm rằng: p P : M(p) M'(p) và M M’ (ta viết M Mi(p) nếu M'(p) > M(p). Dãy này sẽ được biểu diễn trong đồ thị phủ bằng một đỉnh phủ V với: V(p) = M(p) nếu M'(p) = M(p) và V(p) =  nếu M'(p) > M(p). Như vậy, ta đã hình thức hoá việc xây dựng đồ thị phủ. Đồ thị phủ cho hệ mạng vị trí - chuyển cho trong Hình 5.5 như sau: Hình 5.7. Đồ thị phủ của hê mạng vị trí - chuyển trong Hình 5.5 Từ đó, chúng ta đưa ra thuật toán xây dựng đồ thị phủ cho một hệ mạng vị trí - chuyển như sau. 54
Thuật toán 5.3 (Thuật toán xây dựng đồ thị phủ): Giả sử  = (P, T; F, W, K, M0) là một hệ mạng vị trí - chuyển mà ta cần phải xây dựng đồ thị phủ cho nó. Ta thực hiện các bước sau đây: 1) Xây dựng đồ thị ban đầu chỉ gồm một đỉnh V0 = M0, không có cung. 2) Giả sử V là đỉnh nào đó của đồ thị nhưng chưa có cung nào đi ra từ nó thì: 1. Nếu V kích hoạt chuyển t nào đó và V [ t > V' thì ta bổ sung đỉnh mới V' và cung mới (V, t, V') vào đồ thị. 2. Trên đường từ đỉnh V0 tới đỉnh V, nếu tồn tại đỉnh V' mà V' M1 [ t2 > M2 Mk-1 [ tk > Mk trên hệ mạng  tồn tại một đường đi V0 t1 V1 t2 Vk-1 tk Vk trong  mà M0 = V0 và Mi Vi , i = 1,2, , k. Chứng minh: Ta chứng minh bổ đề trên bằng quy nạp theo độ dài k. Nếu k = 0 , M0 = V0 là một đỉnh của  theo định nghĩa đồ thị phủ. Giả sử bổ đề đúng với mọi dãy hoạt động có độ dài không quá k-1. Ta phải chứng minh nó đúng với dãy hoạt động có độ dài k. Phần đầu của dãy hoạt động M0 [ t1 > M1 [ t2 > M2 Mk-1 [ tk > Mk đã có đường đi: V0 t1 V1 t2 Vk-1 mà Mi Vi , i = 1, 2, , k-1. Vì Mk-1 Vk-1 và tk là Mk-1-kích hoạt nên tk là Vk-1-kích hoạt. Theo cách xây dựng đồ thị phủ thì cung (Vk-1, tk, V) thuộc đồ thị phủ. Hơn nữa, Mk = Mk-1 + tk Vk-1 + tk V. Bổ đề được chứng minh xong. 55
Đồ thị phủ của các hệ mạng hữu hạn là hữu hạn. Do vậy có thể lưu trữ và sử dụng đồ thị phủ một cách dễ dàng trong máy tính. Định lý 5.5: Đồ thị phủ của một hệ mạng vị trí - chuyển là hữu hạn. Chứng minh: Ta chứng minh định lý bằng phản chứng. Giả sử đồ thị phủ của một hệ mạng vị trí - chuyển nào đó là vô hạn. Theo cách xây dựng thì từ mỗi đỉnh có số các cung đi ra không vượt quá số các chuyển trong hệ mạng, mà số các chuyển trong một hệ mạng là hữu hạn. Vậy thì đồ thị phải có ít nhất một đường đi vô hạn xuất phát từ đỉnh V0 = M0. Từ tập các đỉnh trên đường đi vô hạn này phải tách được một dãy con vô hạn mà trong nó có hai đỉnh V' và V, V' đứng trước V và V' V. Theo cách xây dựng đồ thị thì V đã trở thành -đỉnh. Trái với giả thiết đường đi vô hạn. Do vậy, đồ thị phủ thực sự có thể xây dựng được cho mọi hệ mạng vị trí - chuyển và nó là công cụ hữu hiệu để nghiên cứu các tính chất của những mạng này. 5.4 Một số tính chất cơ bản của hệ mạng vị trí - chuyển 5.4.1 Tính bị chặn Định nghĩa 5.5: 1. Vị trí p trong hệ mạng vị trí - chuyển  = (P, T; F, W, K, M0) được gọi là bị chặn nếu tồn tại số nguyên dương n sao cho với mọi bộ đánh dấu đạt được trong hệ mạng  đều thoả mãn: M n. 2. Hệ mạng  được gọi là bị chặn nếu tất cả các vị trí của nó đều bị chặn. Định lý 5.6: Giả sử  là hệ mạng vị trí - chuyển và  là đồ thị phủ của nó. 1. Vị trí p là bị chặn V  : V(p)  . 2. Hệ mạng  là bị chặn Đồ thị  không chứa -đỉnh. Chứng minh: 1) Chứng minh bằng phản chứng. Giả sử vị trí p bị chặn nhưng tồn tại đỉnh V  mà V(p) =  . Theo cách xây dựng đồ thị , lúc chọn V ta đã có: 56
V', V"  : V'(p) . . . > V''[ t > . . . V1[ t > . . . > V2[ t > . . . mà V'(p) < V''(p) < V1(p) < V2(p) Vậy vị trí p không bị chặn, trái với giả thiết. Điều ngược lại suy từ tính hữu hạn của đồ thị . 2) Suy từ 1). Tương ứng với hai tính chất trên ta có bài toán bị chặn đối với một vị trí nào đó và bài toán bị chặn đối với một hệ mạng vị trí - chuyển. Như vậy, bài toán bị chặn đối với một vị trí nào đó và bài toán bị chặn của một hệ mạng vị trí - chuyển là giải được nhờ thuật toán sau đây. Thuật toán 5.7: 1. Xây dựng đồ thị phủ  của hệ mạng vị trí - chuyển đã cho. 2. Duyệt toạ độ p của các đỉnh của đồ thị phủ  để xem có toạ độ nào bằng  không. Nếu không có thì vị trí p là bị chặn, ngược lại là không bị chặn. 3. Duyệt các đỉnh của đồ thị phủ  xem có đỉnh nào là -đỉnh không. Nếu không có thì hệ mạng  là bị chặn, ngược lại là không bị chặn. Ví dụ 5.6: Xét hệ mạng vị trí - chuyển sau đây. Hình 5.8. Một hệ mạng vị trí - chuyển Đồ thị phủ  được xây dựng theo thuật toán trên như sau: 57
Hình 5.9. Đồ thị phủ của hệ mạng vị trí - chuyển trong Hình 5.8 Hệ mạng  có hai vị trí p2 và p4 là không bị chặn. Vậy  không bị chặn. Chú ý: Trong đồ thị phủ của một hệ mạng vị trí - chuyển, một -đỉnh có thể sinh ra các -đỉnh khác (Ví dụ trên). 5.4.2 Tính sống Hệ mạng vị trí - chuyển thường được áp dụng trong các lĩnh vực mà ở đó số lượng và sự phân bố của các đối tượng chuyển động là rất quan trọng. Chẳng hạn, dữ liệu trong máy tính, hàng hoá trong kho, tài liệu trong một hệ thống hành chính, các công việc đang tiến hành ở một hệ thống sản xuất Trong các lĩnh vực như thế, mục đích chính là có được một tổ chức hợp lý cho phép thay đổi số lượng và sự phân bố của các đối tượng động nhưng hạn chế sự thay đổi trong một giới hạn nào đó. Trong những hệ như vậy, rất có thể xuất hiện các sự cố dưới dạng phong toả, gây nên ngừng trệ toàn bộ hay một phần hệ thống. Sự phong tỏa như thế là do quá thiếu hoặc quá thừa các đối tượng động. Trong biểu diễn mạng của hệ nói trên, các phần tử hoạt động (bộ vi xử lý, hãng vận tải, máy móc ) được biểu diễn như các chuyển còn các phần tử không hoạt động (bộ nhớ, kho ) được biểu diễn như các vị trí. Các đối tượng chuyển động được biểu diễn như các dấu (token). Vậy thì, sự phong tỏa có thể “nhìn thấy” như là không có chuyển nào được kích hoạt. Hệ mạng như thế là không sống. Định nghĩa 5.7: Giả sử  = (P, T; F, W, K, M0) là một hệ mạng vị trí - chuyển và t là một chuyển nào đó của nó. 58
1. Chuyển t được gọi là sống nếu: M R(M0) , M' R(M) : t là M'- kích hoạt. 2. Hệ mạng  được gọi là sống nếu mọi chuyển của nó đều là sống. Giả thuyết có vẻ hiển nhiên sau đây: “Thêm dấu vào bộ đánh dấu đầu tiên của một hệ mạng vị trí - chuyển sống thì sẽ được một hệ mạng vị trí - chuyển sống khác” là sai. Ví dụ 5.8: Xét hệ mạng vị trí - chuyển  sau đây. Hình 5.10. Hệ mạng vị trí - chuyển Hệ mạng  là sống, nhưng nếu thêm dấu vào vị trí p7 thì hệ mạng trở nên không sống. Tính sống không suy ra rằng mỗi bộ đánh dấu được tái sản xuất, nghĩa là: M1, M2 R(M0) : M2 R(M1). Thậm chí không đúng ngay cả khi dung lượng của các vị trí là hữu hạn (chẳng hạn đối với hệ mạng điều kiện - biến cố). Định nghĩa 5.9: Bộ đánh dấu của hệ mạng vị trí - chuyển N là sống nếu: t T , M' R(M0) : t là M'- kích hoạt. 59
Bổ đề 5.8: Hệ mạng vị trí - chuyển  là sống khi và chỉ khi tất cả các bộ đánh dấu đạt được là sống. Chứng minh: Hệ mạng  là sống t T : t là sống t T , M R(M0), M' R(M) : t là M'- kích hoạt M R(M0) : M là sống. Bài toán sống: Cho một hệ mạng vị trí - chuyển . Có hay không một thuật toán để sau một số hữu hạn bước có thể trả lời được hệ mạng  là sống hay không ? Bài toán đạt được: |P| Cho một hệ mạng vị trí - chuyển  và bộ đánh dấu M N . Có hay không một thuật toán để sau một số hữu hạn bước có thể khẳng định được là M R(M0) hay không ? Năm 1981 E. Mayr đã chứng minh rằng bài toán đạt được là giải được, mặc dầu trước đó có nhiều người đã nêu giả thuyết là bài toán này giải được nhưng chứng minh sai. Đây là bài toán trung tâm của lý thuyết mạng Petri vì nhiều bài toán khác tương đương với nó theo nghĩa, tính giải được hay không giải được của chúng được suy từ tính giải được hay không giải được của bài toán này. Định lý 5.9: Bài toán đạt được đối với một bộ đánh dấu nào đó và bài toán sống của một hệ mạng vị trí - chuyển là tương đương. Vậy bài toán sống cũng là giải được. 5.4.3 Bài toán R-bao hàm và bài toán R-tương đương Giả sử có một lớp các hệ mạng vị trí - chuyển có cùng tập vị trí (hay các tập vị trí của chúng đẳng cấu với nhau). Có hay không một thuật toán để sau một số hữu hạn bước có thể khẳng định được đối với hai hệ mạng 1 và 2 thuộc lớp trên là: 1. Tập các bộ đánh dấu đạt được của chúng có bao hàm nhau hay không? Có nghĩa là: R(M1)  R(M2) hay không ? – Bài toán R-bao hàm. 60
2. Tập các bộ đánh dấu đạt được của chúng có bằng nhau hay không ? Có nghĩa là: R(M1) = R(M2) hay không ? – Bài toán R-tương đương. Hiển nhiên, nếu bài toán 1 giải được thì bài toán 2 cũng giải được. Bài toán thứ 10 của Hilbert: Năm 1900 tại Hội nghị Toán học Quốc tế lần thứ 3 tổ chức ở Pari, Hilbert - nhà toán học vĩ đại người Đức đã đưa ra 23 bài toán. Đó là những vấn đề lớn của toán học thời đó mà ông muốn gửi lại cho thế hệ sau. Những bài toán này đã trở nên nổi tiếng với tên gọi “các bài toán Hilbert”. Cho đến nay, người ta đã giải được 12 bài toán, 8 bài giải một phần còn 3 bài toán là chưa giải được. Trong số các bài toán đã giải được có bài toán thứ 10, được phát biểu như sau: Có hay không một thuật toán để sau một số hữu hạn bước có thể khẳng định được phương trình đa thức: f(x1, x2, , xn) = 0 với các hệ số hữu tỷ có nghiệm hữu tỷ hay không ? M. Hack và Rabin đã đưa ra bài toán trung gian về bao hàm của các đồ thị của các đa thức với hệ số nguyên không âm như sau: Bài toán trung gian: Giả sử f là một đa thức với các hệ số nguyên không âm. Ký hiệu: n+1 g(f) = {(x1, x2, , xm, z) N 0 z f(x1, x2, , xn)} và gọi là đồ thị của đa thức f. Bài toán phát biểu như sau: Có hay không một thuật toán để sau một số hữu hạn bước có thể khẳng định được với hai đa thức đã cho f1, f2 có cùng số biến với các hệ số nguyên không âm, thoả mãn bao hàm thức: g(f1)  g(f2) hay không ? Bài toán thứ 10 của Hilbert được J. Robinson và nhiều nhà toán học biến đổi tương đương thành các bài toán khác. Mãi đến năm 1972, A. 61
Mitiasevich, 27 tuổi, nghiên cứu sinh của Đại học Tổng hợp Saint Peterbourg (Nga) đã chứng minh rằng bài toán thứ 10 của Hilbert là không giải được nhờ sử dụng dãy số Fibonacci quen thuộc. Từ kết quả này, ta cũng chỉ ra được là bài toán trung gian là không giải được. Để dẫn bài toán trung gian về các bài toán R-bao hàm và R-tương đương, Rabin đã xem hệ mạng như một máy trừu tượng để tính toán yếu các đa thức. Máy tính yếu của đa thức f có nghĩa là: đối với một vectơ đầu vào tuỳ ý (y1, y2, , yn) thì kết quả trên đầu ra của máy tính sẽ là một số bất kỳ z mà 0 z f(y1, y2, , yn). Thế thì, máy tính yếu là không tất định theo nghĩa: thay cho kết quả duy nhất tương ứng với một vectơ đầu vào xác định y, máy có thể đưa ra một số bất kỳ không vượt quá f(y1, y2, , yn). Tính không tất định của máy nhận được từ tính không tất định của mạng Petri. Mỗi đa thức đều có dạng: k m j1 m j 2 m jn f(x1, x2, , xn) = c j x1 x2 xn j 1 với các hệ số cj nguyên không âm. Vậy để xây dựng hệ mạng tính toán yếu cho đa thức f tổng quát cần xây dựng mạng mô hình cho các phép toán x1 + x2 , c.x và x1.x2 rồi ghép các mạng trên theo dạng công thức của đa thức. Định lý 5.10: Bài toán R-bao hàm và bài toán R-tương đương là không giải được. Phương hướng chứng minh: Đối với hai đa thức tuỳ ý f và h có cùng số biến, có thể xây dựng các hệ mạng vị trí - chuyển  và ' mà: g(f)  g(h) R()  R('). Từ bài toán trung gian suy ra tính không giải được của bài toán R-bao hàm. Còn bài toán R-tương đương suy từ bài toán R-bao hàm bằng cách: từ hai mạng có cùng số vị trí có thể xây dựng hai mạng 1' và 2' mà: R(1)  R(2) R(1') = R(2'). Vậy bài toán R-tương đương là không giải được. 62
5.4.4 Ngôn ngữ của hệ mạng vị trí - chuyển Giả sử  = (P, T; F, W, K, M0) là một hệ mạng vị trí - chuyển. Giả sử, M1, M2, , Mn R(M0) , t1, t2, , tk T mà: M0 [ t1 > M1 [ t2 > > Mk-1 [ tk > Mk là một dãy hoạt động trên hệ mạng vị trí - chuyển . Khi đó,  = t1 t2 tk là một từ trên T được sinh ra bởi dãy hoạt động trên.  Ta ký hiệu là: M0 Mk . Định nghĩa 5.10:  * Tập hợp L() = {    T , Mk R(M0) : M0 Mk} được gọi là ngôn ngữ sinh bởi hệ mạng vị trí - chuyển . Cặp (R(M0), L()) mô tả hành vi tuần tự của hệ mạng vị trí - chuyển . Các kết quả nghiên cứu đã chỉ ra rằng: Lớp các ngôn ngữ sinh bởi các hệ mạng vị trí - chuyển rộng hơn lớp các ngôn ngữ chính quy, hẹp hơn lớp các ngôn ngữ sinh bởi các văn phạm tuỳ ý và không so sánh được với lớp các ngôn ngữ phi ngữ cảnh. Riêng lớp ngôn ngữ sinh bởi các hệ mạng điều kiện - biến cố là nằm trọn trong lớp các ngôn ngữ chính quy. Định nghĩa 5.11: Hai hệ mạng vị trí - chuyển 1 và 2 được gọi là tương đương ngôn ngữ nếu và chỉ nếu: L(1) = L(2). Bài toán tương đương ngôn ngữ: Có hay không một thuật toán để sau một số hữu hạn bước có thể khẳng định được đối với hai hệ mạng vị trí - chuyển đã cho là tương đương ngôn ngữ hay không ? Định lý 5.11: Bài toán tương đương ngôn ngữ là không giải được. Bài toán này có thể giải được ở một số lớp hệ mạng có các tính chất cụ thể nào đó. Đây là vấn đề mở và vẫn đang được tiếp tục nghiên cứu. 63
Bây giờ ta xét mối quan hệ giữa lớp ngôn ngữ sinh bởi các hệ mạng vị trí - chuyển và lớp ngôn ngữ sinh bởi các hệ mạng điều kiện - biến cố. Định lý 5.12: Lớp ngôn ngữ sinh bởi các hệ mạng vị trí - chuyển bao hàm thực sự lớp ngôn ngữ sinh bởi các hệ mạng điều kiện - biến cố. 5.5 Một vài ứng dụng của hệ mạng vị trí - chuyển Trong phần này ta xét một vài ứng dụng của hệ mạng vị trí - chuyển. 5.5.1 Hệ điều hành Trong hệ điều hành một số quá trình có thể đọc hoặc ghi vào một miền của bộ nhớ chính. Chẳng hạn, xét cấu hình gồm 2 quá trình ghi và 4 quá trình đọc. Ta xây dựng hệ mạng vị trí - chuyển sau đây phục vụ công việc đó. Hình 5.11. Tổ chức quyền truy nhập vào vùng nhớ cho 6 quá trình Hệ mạng vị trí - chuyển trên tổ chức quyền truy nhập vào bộ nhớ cho 6 quá trình. Nhiều nhất 3 quá trình đọc có thể cùng truy nhập vào bộ nhớ. Khi bộ nhớ đang bị thay đổi bởi một quá trình ghi nào đó thì các quá trình khác không thể truy nhập được. 5.5.2 Mô hình gửi-nhận tin Chúng ta mô hình hoá một hệ thống gửi-nhận tin bao gồm một người gửi tin và một người nhận tin. Cả hai sẽ dừng các hành động của mình khi đã đi tới trạng thái kết thúc. Mô hình đầu tiên được xây dựng như sau: 64
Hình 5.12. Một hệ mạng vị trí - chuyển mô hình gửi/nhận tin Mô hình này không được phù hợp lắm vì người nhận có thể đi tới trạng thái dừng trong khi người gửi chưa đi tới trạng thái dừng hoặc kênh thông tin vẫn chưa rỗng. Để loại bỏ tình huống này, ta thêm vào kênh thứ hai mà nó có thể mang thông tin “dừng” từ người gửi. Hơn nữa, một kênh bù được bổ sung sẽ tạo khả năng kiểm tra kênh thông tin có rỗng hay không. Hình 5.13. Hệ mạng vị trí - chuyển mô hình gửi-nhận tin được thêm kênh 65
Hệ thống gửi-nhận tin này được nhúng vào môi trường điều khiển các hoạt động của hệ. Khi người gửi và người nhận đi tới trạng thái dừng của mình, họ báo hiệu điều đó cho môi trường. Cả hai vẫn có thể hoạt động trở lại. Hình 5.14. Hệ mạng vị trí - chuyển của mô hình gửi-nhận tin thêm điều khiển môi trường Hệ thống gửi-nhận tin này có được các tính chất sau đây: 1) Trong hệ thống, người gửi có thể là “dừng”, “sẵn sàng gửi” hoặc vừa mới “gửi xong” còn người nhận có thể là “dừng”, “sẵn sàng nhận” hoặc vừa mới “nhận xong”. 2) Kênh thông tin chứa được nhiều nhất là n tin. 3) Người gửi (hoặc người nhận) là “dừng” khi và chỉ khi anh ta gửi một tín hiệu tương ứng tới môi trường. Anh ta chỉ có thể ra khỏi trạng thái này nhờ tín hiệu từ môi trường. 4) Nếu người gửi đang ở trạng thái “dừng” thì anh ta không thể ra khỏi trạng thái này cho đến khi người nhận đi tới trạng thái “dừng”. 5) Quyết định của người nhận liệu có nhận tin hay ở trạng thái “dừng” phụ thuộc vào cách ứng xử của người gửi. Nhờ vậy mà không xảy ra xung đột. 66
6) Người nhận chỉ có thể “dừng” khi kênh thông tin rỗng và người gửi đang “dừng”. BÀI TẬP CHƯƠNG 5 5.1. Chỉ ra sự giống nhau và khác nhau giữa hệ mạng điều kiện - biến cố và hệ mạng vị trí - chuyển. 5.2. Xây dựng đồ thị phủ cho hệ mạng vị trí - chuyển dưới đây: Hình 5.15. Một hệ mạng vị trí - chuyển 5.3. Tìm ngôn ngữ sinh bởi hệ mạng vị trí - chuyển cho trong Hình 5.15. 67
Chương 6 BẢNG CHỮ CÁI TƯƠNG TRANH VÀ NGÔN NGỮ VẾT Bảng chữ cái thông thường sinh ra ngôn ngữ các từ thì bảng chữ cái tương tranh sinh ra ngôn ngữ mà thành phần của nó là tập các từ. Mỗi một tập các từ như vậy được gọi là một vết. 6.1 Vết và ngôn ngữ vết 6.1.1 Bảng chữ cái tương tranh Giả sử A là một bảng chữ cái. Định nghĩa 6.1: 1. Một quan hệ nhị nguyên p đối xứng và không phản xạ trên bảng chữ cái A được gọi là quan hệ độc lập trên A. a, b A , (a, b) p (b, a) p a b. 2. Bảng chữ cái tương tranh là một cặp (A, p), trong đó A là một bảng chữ cái và p là một quan hệ độc lập trên A. Ký hiệu: A = (A, p) là một bảng chữ cái tương tranh. Ví dụ 6.2: Bảng chữ cái A = {a,b,c,d,e,f} và quan hệ độc lập p = {(a,b), (a,c), (a,e), (b,c), (c,d), (c,f), (d,e), (d,f)}. Hình 6.1. Bảng chữ cái tương tranh Ví dụ 6.3: Trên cơ sở dữ liệu D có một tập các giao tác O. Trên các giao tác này có môt thứ tự bộ phận < chỉ thứ tự thực hiện của chúng. 68
Ta có thể biểu diễn tập các giao tác trên bằng một bảng chữ cái tương tranh O = (O, p), trong đó quan hệ độc lập p được xác định như sau: o1, o2 O : (o1, o2) p  ((o1 < o2)  (o2 < o1)). Như vậy, bảng chữ cái hữu hạn là tập các giao tác và hai giao tác là độc lập với nhau nếu chúng không sắp thứ tự với nhau. Chúng ta còn trở lại ví dụ này để điều khiển tương tranh trên các giao tác. Giả sử A = (A, p) là một bảng chữ cái tương tranh. Quan hệ =p được định nghĩa như sau: * * x, y A : x =p y x1, x2 A , (a, b) p , x = x1abx2  y = x1bax2. Theo Ví dụ 6.2 ở trên ta có: abde =p bade =p baed =p bead =p * * Quan hệ p  A A được định nghĩa là quan hệ tương đương nhỏ * nhất trên A chứa quan hệ =p . Với mọi x, y A*, x và y được gọi là p-tương đương nếu và chỉ nếu x p y. Dễ thấy rằng, đối với bảng chữ cái tương tranh A = (A, p) thì: 1. Quan hệ p là bao đóng phản xạ bắc cầu của quan hệ =p , nghĩa là: * p = (=p) . * 2. Nếu x, y A , x p y thì: a A : a(x) = a(y) – số lần xuất hiện của a trong x và y là bằng nhau. Từ đó suy ra: |x | = |y |. * Với mọi x A , ta ký hiệu [x]p là lớp tương đương của quan hệ p chứa x. Để ngắn gọn []p được ký hiệu là 1. Trong ví dụ ở trên thì: [abde]p = {abde , bade , abed , baed , bead}. 6.1.2 Vết và ngôn ngữ vết Khái niệm vết được A. Mazurkiewicz định nghĩa như sau. 69
Định nghĩa 6.4: Giả sử A = (A, p) là một bảng chữ cái tương tranh. 1) Mỗi một lớp tương đương của quan hệ p được gọi là một vết trên A. 2) Một tập các vết được gọi là một ngôn ngữ vết trên A. Các từ trong một vết t có cùng độ dài. Do vậy, nếu t = [x]p thì độ dài của vết t được định nghĩa bằng độ dài của từ đại diện, nghĩa là: |t| = |x|. Ưu điểm chính của vết là có thể biểu diễn chúng bằng các từ. Ký hiệu p là tập tất cả các vết trên A. Bây giờ, ta xây dựng một số phép toán cơ bản trên vết và ngôn ngữ vết. Định nghĩa 6.5: Giả sử A = (A, p) là một bảng chữ cái tương tranh. 1. Nếu t1, t2 là các vết; t1 = [x1]p và t2 = [x2]p thì hợp thành của t1 và t2 là vết: t1 ◦ t2 = [x1.x2]p. 2. Nếu T1, T2 là các ngôn ngữ vết thì hợp thành của T1 và T2 là ngôn ngữ vết: T1 ◦ T2 = { t1 ◦ t2  t1 T1  t2 T2 }. 3. Giả sử T là một ngôn ngữ vết và n 0. Luỹ thừa bặc n của T là một ngôn ngữ vết, ký hiệu Tn được định nghĩa như sau: T0 = {} (ký hiệu  chỉ ngôn ngữ vết rỗng) và Tn = T ◦ Tn-1. 4. Lặp của ngôn ngữ vết T là ngôn ngữ vết T * =  Tn . n 0 Chú ý: * 1) Dễ thấy rằng nếu x1, x2, y1, y2 A , x1 p x2  y1  y2 thì x1y1 p x2y2. Do đó, định nghĩa của hợp thành vết là hoàn toàn đúng đắn. Không nhầm lẫn giữa hợp thành của vết và phép ghép các từ của vết. Chẳng hạn, với bảng chữ cái tương tranh như trong ví dụ trên và t1 = [ab]p và t2 = [cd]p thì t1 ◦ t2 = [abcd]p = t1 t2  {bead} - nhiều hơn phép ghép từ một phần tử. 0 1 Ta chọn ngôn ngữ vết T = {[a,b]p} thì T = {}, T = T, T2 = {abab, aabb, abba, baba, bbaa, baab}, n n n * k k với n 0 thì T = {[a b ]p} và T = {[a b ]p  k 0}. 70
2) Phép hợp thành của vết có tính chất kết hợp: t1, t2, t3 p : t1 ◦ ( t2 ◦ t3) = (t1 ◦ t2) ◦ t3. Vậy với mỗi bảng chữ cái tương tranh A = (A, p) thì bộ ba (p , ◦ , ) là * monoid thương của monoid (A , . , ) đối vói quan hệ tương đương p. Ta còn có các kết quả sau đây: Định lý 6.1: Giả sử A = (A, p) là một bảng chữ cái tương tranh và các vết t, t', * t'', t''' p ; a, b A và u, v, w, u', v' A . 1. [u]p =  u =  2. [uvw]p = [uv'w]p [v]p = [v']p 3. [uav]p = [u'av']p  a(x) = b(x) [uv] = [u'v'] 4. t’◦ [a]p = t" ◦ [b]p  a b thì: - (a, b) p - s p sao cho t' = [b]p◦ s và t'' = [a]p◦ s 5. t = [a]p ◦ t''  t' = [a]p ◦ t''' ( t = t' t'' = t''') Một số trường hợp đặc biệt sau đây liên quan đến đặc thù của quan hệ độc lập. Định lý 6.2: Giả sử A = (A, p) là một bảng chữ cái tương tranh. * 1) Nếu p =  thì t p : t = {x} , x A . 2) Nếu p = A A \ I thì: * x, y A : [x]p = [y]p a A : a(x) = a(y). 6.1.3 Xấp xỉ ngôn ngữ từ bằng ngôn ngữ vết Ngôn ngữ vết có thể dùng để xấp xỉ ngôn ngữ từ. Định nghĩa 6.6: Giả sử A = (A, p) là một bảng chữ cái tương tranh và K là một ngôn ngữ trên bảng chữ cái A.  1. Ngôn ngữ vết tồn tại của K trên A, ký hiệu bởi [K]p là ngôn ngữ vết { t p t  K }. 71
 2. Ngôn ngữ vết phổ dụng của K trên A, ký hiệu bởi [K]p là ngôn ngữ vết { t p t  K}.  3. Ngôn ngữ vết phù hợp của K, ký hiệu bởi [K]p là ngôn ngữ vết [K]p nếu   [K]p = [K]p và không xác định trong các trường hợp khác.  Vậy thì, ngôn ngữ vết tồn tại [K]p bao gồm các vết có chung với ngôn  ngữ K ít nhất một từ, còn ngôn ngữ vết phổ dụng [K]p tạo bởi các vết chỉ chứa các từ trong K. Hay viết một cách khác:  [K]p = { t p x t : x K} – xấp xỉ trên của ngôn ngữ K,  [K]p = { t p x t : x K} – xấp xỉ dưới của ngôn ngữ K. Hình 6.2. Các ngôn ngữ vết xấp xỉ của ngôn ngữ Chú ý rằng, với mọi bảng chữ cái tương tranh A = (A, p) thì:   *  *  * [A]p = [A]p = [A]p và [A ]p = [A ]p = [A ]p. * * Bởi vậy, ([A]p) = [A ]p = p. Ví dụ 6.7: Giả sử A = (A, p) là một bảng chữ cái tương tranh với bảng chữ cái A = {a, b} và quan hệ độc lập p = {(a, b)}. 1) Tập tất cả các vết trên A là: * * p = { t  A  m, n 0 : t = { x A  a(x) = m , b(x) = n }}. 2) Lấy ngôn ngữ K = {ab}*{ba}* thì: 72
 * * [K]p = { t  A  m 0 : t = { x A  a(x) = b(x) = m }} và  [K]p = { , {ab, ba}}.   Vậy thì [K]p [K]p . Suy ra, [K]p không xác định. 3) Lấy K = {a}*{b}{a}*{b}{a}* thì:  * * [K]p = { t  A  m 0 : t = { x A  a(x) = m , b(x) = 2}} và   [K]p = [K]p =[K]p . Bây giờ ta xét một số tính chất cơ bản của ngôn ngữ vết. Định lý 6.3: Giả sử A = (A, p) là một bảng chữ cái tương tranh và các ngôn ngữ K, L  A*. 1. K =  [K] =  2. [K*] = ([K])* *  3. K = A [K] = p 4. K  L [K]  [L] 5. [K] ◦ [L] = [K.L] 6. [K]  [L] = [K  L] 7. [K  L]  [K]  [L] . Định lý 6.4: Giả sử A = (A, p) là một bảng chữ cái tương tranh và các ngôn ngữ K, L  A*. 1. K =  [K] =  2. K  L [K]  [L] 3. [K]  [L]   [K  L] 4. [K]  [L]  = [K  L] 5. [K.L]  [K] ◦ [L] *  6. K = A [K] = p . Định lý 6.5: Giả sử A = (A, p) là một bảng chữ cái tương tranh và các ngôn ngữ K, L  A*. 1. [K]  [K]  *  2. [K] = p \ [A \ K]  *  3. [K] = p \ [A \ K] 73
4. [K \ L]  [K] \ [L] 5. [K \ L]  [K] \ [L]. Ví dụ 6.8: Giả sử bảng chữ cái tương tranh A = (A, p) với A = {a, b} và quan hệ độc lập p = {(a, b)}. 1) [{ab}] = {{ab, ba}}  {{ba, ab}} = [{ba}] trong khi đó {ab}  {ba}. 2) [{ab}]  [{ba}] = {{ab, ba}}   = [] = [{ab}  {ba}]. * *  * 3) Do ab p ba và ab A \ {ba} nên [A \ {ba}] = p, nhưng A \ {ba} A*. 4) [{ab}] =  trong khi đó {ab} . 5) [{ab}] =    = [{ba}] nhưng mà {ab}  {ba}. 6) [{a}] [{b}] = {ab, ba}   = [{ab}] = [{a}.{b}]. 7) [{ab}  {ba}] = [{ab, ba}] = {{ab, ba}}   =    = [{ab}]  [{ba}]. 8) Nếu lấy K = {ab, aabb, baab, abba, baba, bbaa} thì abab K*. Do vậy, [aabb] [K*]. Nhưng vì [K] =  nên [aabb] [K*]   =  = ([K])*. 6.2 Dạng chuẩn của vết Một vết có thể phân tách thành hợp thành của nhiều vết con. Đặc tính ấy được dùng để chứng minh hàng loạt tính chất của vết và ngôn ngữ vết. Tuy nhiên, sự phân tách ấy là không duy nhất. Bởi vậy, ta cần tìm một dạng phân tách “chuẩn” cho các vết, mà các vết con của nó có các tính chất quý báu thường gặp trong thực tế. Định lý 6.6: Mỗi vết t p , t  đều có một phân tách duy nhất t = t1 ◦ t2 ◦ ◦ tm , m 1 sao cho: 1. ti  , i = 1, 2, , m 2. ti = [ui]p , i = 1, 2, , m và mỗi chữ cái trong ui chỉ xuất hiện một lần và hai chữ cái trong ui là độc lập với nhau. 3. i = 1, 2, , m-1 , nếu ti = [ui]p và ti+1 = [ui+1]p thì mỗi chữ cái trong ui+1 không độc lập với một chữ cái nào đó trong ui . 74
Định lý trên đã định nghĩa dạng chuẩn của vết. Theo định lý trên thì mỗi vết đều có thể phân tách một cách duy nhất thành một số ít nhất các thành phần “tương tranh cực đại”. Mỗi thành phần được hiểu như một khối tương tranh trong bài toán điều khiển. Cách phân tách này cho ta một biểu diễn duy nhất đối với mọi vết t và ta gọi là dạng chuẩn của vết t. Ví dụ 6.9: 1) Xét bảng chữ cái tương tranh như ở Ví dụ 6.2. t = [abccdef]p = [abc]p◦ [cd]p◦ [e]p◦ [f]p . 2) Giả sử A được cho dưới dạng đồ thị dưới đây. Hình 6.3. Biểu diễn đồ thị vô hướng của một bảng chữ cái tương tranh t = [adcbbed]p = [adbcbed]p = [abdbced]p = [ab]p◦ [db]p◦ [c]ơ ◦ [ed]p. Bây giờ chúng ta xây dựng thuật toán tìm dạng chuẩn của vết khi biết từ đại diện của vết này. Thuật toán 6.7 (Tìm dạng chuẩn của vết) Phân tích thuật toán: Giả sử t là vết mà ta cần tìm dạng chuẩn của nó, t = [w]p . Khi đó, từ w trở thành đầu vào của thuật toán. Giả sử l = |w| và bảng chữ cái A = {a1, a2, , an}. Thuật toán sẽ xây dựng phân tách t = t1 ◦ t2 ◦ ◦ tm bằng cách xây dựng các từ u1, u2, , um mà ti = [ui]p , i = 1, 2, , m thoả mãn các tính chất của dạng chuẩn. 75
Thuật toán sử dụng các biến xâu u(1), u(2), , u(m) mà u(i) chứa các tiền tố của ui. Trước tiên, các biến u(1), u(2), , u(m) được gán xâu rỗng . Mỗi một chữ cái aj A có một biến trỏ nguyên q(j) để chỉ ra rằng nếu aj xuất hiện thì nó sẽ được nối vào giá trị hiện tại của u(q(j)). Ban đầu các biến trỏ q(1), q(2), , q(m) được gán giá trị bằng 1. Điều này có nghĩa là chữ cái nào xuất hiện đầu tiên đều được đưa vào khối thứ nhất. Để xây dựng phân tách của vết t, thuật toán sẽ đọc từ đại diện w từng chữ cái một từ trái sang phải. Giá trị của các tiền tố u(1), u(2), , u(m) và các biến trỏ q(1), q(2), , q(m) được cập nhật như sau: Giả sử hiện thời thuật toán đang đọc thành phần thứ k của w, 1 k l mà nó chính là chữ cái aj trong bảng chữ cái A. Thế thì: 1. aj được nối thêm vào giá trị hiện tại của u(q(j)) 2. Với mỗi chữ cái ai trong A khác aj, không tương tranh với aj và q(i) q(j) thì giá trị của biến trỏ q(i) được đặt bằng q(j) +1. 3. Giá trị của q(j) được tăng thêm 1. Bước 2. và 3. đảm bảo rằng những chữ cái ai không tương tranh với aj cũng như chính aj chỉ có thể xuất hiện trong các khối đứng sau đó. Sau khi thực hiện các bước 1. – 3. với thành phần thứ k được đọc, thuật toán chuyển đầu đọc tới thành phần thứ k+1 của từ đại diện w. Khi đã đọc và xử lý xong thành phần thứ l của từ w, thuật toán chọn m là số i lớn nhất mà u(i)  và kết quả của thuật toán sẽ là các từ u(1), u(2), , u(m). Thuật toán: Đầu vào: Bảng chữ cái tương tranh A = (A, p) và từ w A*. Đầu ra: Các từ u(1), u(2), , u(m). Khai báo: Giả sử l = |w|, n = A và A = {a1, a2, , an}. Giả sử k là biến nguyên trên {0, 1, , l}, q là mảng nguyên trên {1, 2, , l+1} có độ dài n . i, j là các biến nguyên trên {1, 2, , n}, u là mảng các xâu trên (A  {})* có độ dài l và m là biến nguyên trên {1, 2, , l}. Tính toán: 1) Với mỗi i = 1, 2, , n đặt q(i)  1 2) Với mỗi k = 1, 2, , l đặt u(k)   76
3) k  0 4) k  k + 1 5) Chọn j mà w(k) = aj 6) u(q(j))  u(q(j)).aj 7) Với mọi i = 1, 2, , n mà i j , q(i) q(j) và (ai, aj) p thì đặt q(i)  q(j) + 1 8) Đặt q(j)  q(j) + 1 9) Nếu k < l thì chuyển lên bước 4) 10) Chọn m mà u(m)  nhưng u(m+1) =  hoặc m = l 11) Dừng Ví dụ 6.10: Minh hoạ của thuật toán trên với bảng chữ cái tương tranh đã cho ở Ví dụ 6.2. k adcbbed u(1) u(2) u(3) u(4) u(5) q1 q2 q3 q4 q5 j 0 adcbbed 1 1 1 1 1 abcde 1 dcbbed a 2 1 2 2 2 1 b acde 2 cbbed a d 3 1 3 3 2 4 b acd 3 bbed a d c 4 1 4 4 4 3 b acde 4 bed ab d c 4 2 4 4 4 2 b acde 5 ed ab d c 4 3 4 4 4 2 b acde 6 d ab db c e 5 5 5 4 5 5 d abce 7 ab db c ed 5 5 5 5 5 4 abce Định lý 6.8: Với bảng chữ cái tương tranh A = (A, p) và từ w A* thì dạng chuẩn của vết [w]p được Thuật toán 6.7 xây dựng trong thời gian O(|w|). Chứng minh: Từ thuật toán ta có các quan sát sau đây: 1) Các bước 1), 2), 3) và 10) thực hiện một lần. 77
2) Các bước từ 4) đến 9) được thực hiện l lần. 3) Các bước 3), 4), 6), 8) và 9) có độ phức tạp thời gian không đổi. 4) Các bước 1), 5) và 7) có độ phức tạp thời gian tuyến tính với n và 5) Các bước 2) và 10) có độ phức tạp thời gian tuyến tính với l. Vậy độ phức tạp thời gian tổng thể là O(n.l). Nhưng với bảng chữ cái hữu hạn A thì n là hằng số, vậy suy ra kết quả trên. Một số ứng dụng thực tế của dạng chuẩn của vết: Dạng chuẩn của vết cho ta phương án tối ưu khi thực hiện một quá trình xảy ra trên một hệ thống nào đó. 1) Trở lại với Ví dụ 6.3, trên cơ sở dữ liệu D ta có bảng chữ cái tương tranh O = (O, p). Mỗi quá trình tuần tự xảy ra trên tập các giao tác của cơ sở dữ liệu D là một từ nào đó w O*, mà các giao tác xuất hiện trong w thỏa mãn thứ tự bộ phận <. Với các giao tác độc lập (không sắp thứ tự) với nhau thì ta có thể xử lý chúng một cách đồng thời. Áp dụng thuật toán tìm dạng chuẩn cho vết [w] ta có một phương án tối ưu thực hiện quá trình tương ứng với w. 2) Giả sử  = (B, E: F, c0) là một hệ mạng điều kiện - biến cố nào đó. Khi đó, E = (E, q), với q là quan hệ tách được trên E, là một bảng chữ cái tương tranh. Áp dụng thuật toán tìm dạng chuẩn của vết đối với mỗi từ thuộc ngôn ngữ L() sinh bởi hệ mạng , ta nhận được phương án tối ưu thực hiện quá trình tương ứng với từ này. Hơn nữa, ngôn ngữ vết V() = L() / biểu diễn hành vi tương tranh của hệ mạng . Kết quả này cũng có thể áp dụng cho các hệ mạng vị trí - chuyển. 6.3 Biểu diễn đồ thị định hướng của vết 6.3.1 Định nghĩa đồ thị phụ thuộc Trong phần này ta sẽ xét sự tương ứng giữa vết và đồ thị định hướng. Định nghĩa 6.11: Giả sử A = (A, p) là một bảng chữ cái tương tranh. * Giả sử x = a1a2 an , (n 0) là một từ thuộc A với các chữ cái a1, a2, , an thuộc A. Đồ thị phụ thuộc (d - đồ thị) của x trên A, ký hiệu bởi D(x) là một đồ 78
thị định hướng phi chu trình với các đỉnh được gán nhãn (V, E, A, l), trong đó: 1) V = {1, 2, , n} 2) Với mọi 1 i n , l(i) = ai và 3) E  V V sao cho với mọi 1 i n : (i, j) E (i < j)  (ai, aj) p. Ví dụ 6.12: Bảng chữ cái tương tranh A = (A, p) đã cho được biểu diễn bằng đồ thị vô hướng sau đây: Hình 6.4. Biểu diễn đồ thị vô hướng của bảng chữ cái tương tranh Quan hệ phụ thuộc d = A A \ p. Chọn từ x = dbcee thì đồ thị phụ thuộc D(x) có dạng: Hình 6.5. Đồ thị phụ thuộc của một từ Đồ thị phụ thuộc là phi chu trình. Để thuận tiện cho việc xây dựng đồ thị phụ thuộc, ta đưa ra định nghĩa đệ quy cho nó như sau. Định nghĩa 6.13: 1) D() là đồ thị rỗng (không đỉnh, không cạnh). 79