Tài liệu Tối ưu hoá lớp các thông tin có cấu trúc dạng cây nhị nguyên 1 và N chiều với thông tin chứa ở lá trên tập khoá hữu hạn bằng mô hình xử lý song song

ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ Trần Thị Ngọc Hà TỐI ƯU HOÁ LỚP CÁC THÔNG TIN CÓ CẤU TRÚC DẠNG CÂY NHỊ NGUYÊN 1 VÀ N CHIỀU VỚI THÔNG TIN CHỨA Ở LÁ TRÊN TẬP KHÓA HỮU HẠN BẰNG MÔ HÌNH XỬ LÝ SONG SONG LUẬN VĂN THẠC SĨ Hà Nội - Năm 2004 Luận văn tốt nghiệp Contents MỤC LỤC LỜI GIỚI THIỆU .............................................................................. 1 Chương l: ......................................................................................... 4 THUẬT TOÁN PHÂN RÃ LỚP THÔNG TIN CÓ CẤU TRÚC DẠNG CÂYNHỊ PHÂN MỘT CHIỀU VỚI THÔNG TIN CHỨA Ở LÁ TRÊN TẬP KHÓA HỮU HẠN ...................................................................... 4 1. Định nghĩa cây nhị phân một chiều với thông tin chứa Ở lá. ......................... 4 2. Hệ tiên dề và các quy tắc dẫn xuất trên TREE. ............................................. 6 2.1 Quy tắc dẫn xuất của TREE. ................................................................. 6 2.2 Hệ tiên đề của TREE trên tập khóa hữu hạn Ki(i=l, 2, ..., n-l). ........... 6 3. Cây chuẩn tắc một chiều trên tập khóa K. ................................................... 11 1.4 Bảng mã của cây trên tập khóa K. ...................................................... 23 1.5 Cây tối ưu một chiều trên tập khóa K. ............................................... 24 1.6 Thuật toán phân rã tìm cây nhị phân tối ưu trên tập khóa hữu hạn K. ................................................................................................................ 26 1.7 Ví dụ minh hoạ. .................................................................................... 30 Chương 2 ........................................................................................ 38 THUẬT TOÁN PHÂN RÃ LỚP THÔNG TIN CÓ CẤU TRÚC DẠNG CÂY NHỊ PHÂN N CHIỀU VỚI THÔNG TIN CHỨA Ở LÁ TRÊN TẬP KHÓA HỮU HẠN ..................................................................................... 38 2.1 Cây nhị phân n-chiều với thông tin chứa ở lá. .................................. 38 2.2 Hệ tiên đề và các quy tắc dẫn xuất trên TREE(n). ..................................... 40 2.2.1 Qui tắc dẫn xuất của TREE(n). ........................................................ 40 2.2.2 Hệ tiên đề của TREE(N) trên tập khóa hữu hạn Ki(n)(i=l, 2, ...,m). .................................................................................................................... 40 Trang 89 Luận văn tốt nghiệp 2.3 Dạng chuẩn tắc của cây nhị phân n-chiều. ................................................. 48 2.4 Bảng mã của cây n-chiều trên tập khóa K(n). ............................................ 72 2.5 Cây nhị phân n- chiều tối ưu. .................................................................... 73 2.6 Thuật toán phân rã xây dựng cây n-chiều tối ưu trên tập khóa hữu hạn K(n). ....................................................................................................................... 74 2.6.1 Thuật toán chuyển về cây n-chiều chuẩn tắc trên tập khoá hữu hạn Ki(n)(i=l, 2,..., m) (Thuật toán 2.l). ............................................................ 74 2.6.2 Thuật toán nối các cây n-chiều chuẩn tắc Nin  (Ki(n))T(i=l, ...,m) thành cây n-chiều chuẩn tắc Nn  (K(n))T (Thuật toán 2.2). ................... 74 2.6.3 Thuật toán phân rã tập khóa K(n) thành m tập con Kl(n), K2(n), ..., Km(n) (Thuật toán 2.3) ............................................................................... 75 2.6.4 Thuật toán chuyển về cây n -chiều tối ưu (Thuật toán 2.4). ........... 76 2.6.5 Thuật toán phân rã xây dựng cây n-chiều tối ưu trên tập khóa K(n). ............................................................................................................ 76 2.7 Ví dụ minh hoạ. ........................................................................................ 77 2.7.1 Ví dụ mô phỏng thuật toán chuyển về cây 2-chiều chuẩn tắc trên tập khóa hữu hạn Ki(2) (thuật toán 2.l). ................................................... 77 2.2.7 Ví dụ mô phỏng thuật toán nối các cây chuẩn tắc Ni2  (Ki( 2))T thành cây chuẩn tắc N2  (K(2))T (Thuật toán 2.3). .............................. 78 2.7.3 Ví dụ mô phỏng thuật toán chuyển cây 2 - chiều chuẩn tắc của T về cây tối ưu ( thuật toán 2.5) ........................................................................ 80 KẾT LUẬN ..................................................................................... 85 TÀI LIỆU THAM KHẢO: ................................................................ 87 PHỤ LỤC ....................................................................................... 88 Trang 90 Luận văn tốt nghiệp LỜI GIỚI THIỆU Khái niệm cây tìm kiếm nhị phân đóng vai trò rất quan trọng trong cấu trúc dữ liệu và trong lý thuyết thuật toán. Tuy nhiên, để khai thác tối đa ưu điểm của cây tìm kiếm nhị phân thì nhất thiết ta phải lưu trữ thông tin trên cây tìm kiếm nhị phân tối ưu (tức cây nhị phân có số đỉnh và độ cao nhỏ nhất trong tất cả các cây tương đương với nó). Hơn thế nữa, sau một thời gian sử dụng thì thông tin lưu trữ trên cây sẽ bị lạc hậu, khi đó ta phải đánh giá và tổ chức lại chúng, các thông tin lạc hậu sẽ bị loại bỏ. Như vậy, nhu cầu xây dựng cây nhị phân tối ưu luôn được đặt ra. Vấn đề đặt ra là làm thế nào để xây dựng cây nhị phân tối ưu? Đã có nhiều thuật toán xây dựng cây nhị phân tối ưu, tuy nhiên, các thuật toán này hoạt động dựa trên việc xét duyệt trên toàn bộ tập khóa, chính vì vậy khi tập khóa quá lớn nhất là khi tập khóa là vô hạn thì thời gian thực hiện thuật toán là rất lớn. Để khắc phục nhược điểm trên, trong luận văn này, ta áp dụng thuật toán phân rã để tìm cây nhị phân tối ưu và lưu trữ các thông tin đã được phân loại trong cây tối ưu đó. Thuật toán phân rã dựa trên việc chia nhỏ tập khóa hữu hạn ban đầu thành n tập khóa con (n tập hữu hạn). Sau đó áp dụng phương pháp tiên đề của H.Thiele để tìm cây nhị phân chuẩn tắc trên từng tập con đó. Công việc này có thể tiến hành đồng thời trên tất cả các tập khóa con vì vậy nó sẽ làm giảm đáng kể thời gian thực hiện thuật toán so với việc thực hiện thuật toán trên toàn tập khóa ban đầu. Tiếp theo, ta ghép nối các cây chuẩn tắc của từng tập con theo quy luật các khóa có giá trị tăng dần ta được cây chuẩn tắc trên toàn tập khóa ban đầu. Từ đó dùng thuật toán bẻ đôi cây chuẩn tắc ta được cây nhị phân tối ưu trên toàn tập khóa ban đầu. Thuật toán phân rã hoàn toàn không làm mất thông tin có ích, Cây nhị phân tối ưu thu được bằng thuật toán phân rã hoàn toàn giống với cây tối ưu thu được khi thực hiện trên toàn tập khóa ban đầu. Một vấn đề nữa đặt ra là: với cấu trúc cây nhị phân n-chiều thì liệu các kết quả trên có còn đúng không? Để trả lời câu hỏi này chúng tôi đã tổng quát hoá Trang 1 Luận văn tốt nghiệp bài toán trên cho cấu trúc cây nhị phân n-chiều. Tuy nhiên, cho đến nay, em mới chỉ giải quyết xong bài toán với cấu trúc cây nhị phân n-chiều với thông tin chứa ở lá. Điều thú vị là khi thay n = 1 ta thu lại được hoàn toàn những kết quả đã nghiên cứu với cấu trúc cây nhị phân một chiều với thông tin chứa ở lá. Luận văn gồm các chƣơng sau: Chƣơng 1: Thuật toán phân rã lớp thông tin có cấu trúc dạng cây nhị phân một chiều với thông tin chứa ở lá trên tập khóa hữu hạn. - Xây dựng các khái niệm: Cây nhị phân một chiều với thông tin chứa ở lá, hàm kết quả, sự tương đương giữa các cây nhị phân một chiều, dạng chuẩn của cây nhị phân một chiều, bảng mã của cây nhị phân, cây nhị phân một chiều tối ưu. Các qui tắc dẫn xuất và hệ tiên đề của cây nhị phân một chiều. - Các tính chất tương đương giữa các cây nhị phân một chiều, của dạng chuẩn tắc, của cây tối ưu và các bổ đề, các định lý cho phép kiểm tra tính tương đương giữa các cây nhị phân, biến đổi tương đương giữa các cây nhị phân. - Thuật toán chuyển về cây nhị phân một chiều chuẩn tắc, thuật toán nối các cây nhị phân một chiều chuẩn tắc, phân hoạch tập khóa ban đầu K thành n tập khóa con - Thuật toán chuyển về cây nhị phân một chiều tối ưu. - Thuật toán phân rã xây dựng cây nhị phân một chiều tối ưu. - Các ví dụ minh hoạ. Chƣơng 2: Thuật toán phân rã lớp thông tin có cấu trúc dạng cây nhị phân nchiều với thông tin chứa Ở lá trên tập khóa hữu hạn. - Xây dựng các khái niệm về: cây nhị phân n-chiều với thông tin chứa Ở lá, hàm kết quả, sự tương đương giữa các cây nhị phân n-chiều, dạng chuẩn của cây nhị phân n- chiều, cây nhị phân n-chiều tối ưu. Các qui tắc dẫn xuất và hệ tiên đề của cây nhị phân n-chiều. Trang 2 Luận văn tốt nghiệp - Các tính chất tương đương giữa các cây nhị phân n-chiều, của dạng chuẩn tắc, của cây tối ưu và các bổ đề, các định lý cho phép kiểm tra tính tương đương giữa các cây nhị phân n-chiều, biến đổi tương đương giữa các cây nhị phân nchiều. - Thuật toán chuyển về cây nhị phân n-chiều chuẩn tắc, thuật toán nối các cây nhị phân n-chiều chuẩn tắc tắc, phân hoạch tập khóa ban đầu K(n) thành in tập con Kl(n), K2(n), ..., Kn(n), thuật toán chuyển về cây nhị phân n-chiều tối ưu. - Thuật toán phân rã xây dựng cây nhị phân n-chiều tối ưu. - Các ví dụ minh hoạ. Kết luận: Tóm tắt lại những kết quả thu được của luận văn này. Tài liệu tham khảo. Phụ lục: Cài đặt chương trình mô phỏng thuật toán xây dựng cây nhị phân một chiều tối ưu cho lớp các thông tin có cấu trúc dạng cây nhị phân một chiều với thông tin chứa ở lá. Trang 3 Luận văn tốt nghiệp Chương l: THUẬT TOÁN PHÂN RÃ LỚP THÔNG TIN CÓ CẤU TRÚC DẠNG CÂY NHỊ PHÂN MỘT CHIỀU VỚI THÔNG TIN CHỨA Ở LÁ TRÊN TẬP KHÓA HỮU HẠN Nội dung của chương này gồm: - Các định nghĩa về: cây nhị phân một chiều với thông tin chứa Ở lá, hàm kết quả, sự tương đương giữa các cây nhị phân một chiều, dạng chuẩn của cây nhị phân một chiều, bảng mã của cây nhị phân, cây nhị phân một chiều tối ưu. Các qui tắc dẫn xuất và hệ tiên đề của cây nhị phân một chiều. - Các tính chất tương đương giữa các cây nhị phân một chiều, của dạng chuẩn tắc và các bổ đề, các định lý cho phép kiểm tra tính tương đương giữa các cây nhị phân, biến đổi tương đương giữa các cây nhị phân. - Thuật toán chuyển về cây nhị phân một chiều chuẩn tắc trên tập khóa hữu hạn, - Thuật toán nối các cây nhị phân một chiều chuẩn tắc, phân hoạch tập khóa ban đầu K thành n tập con K1, K2, ...Kn - Thuật toán chuyển về cây nhị phân một chiều tối ưu. - Thuật toán phân rã xây dựng cây nhị phân một chiều tối ưu. - Các ví dụ minh họa các thuật toán. 1. Định nghĩa cây nhị phân một chiều với thông tin chứa Ở lá. Giả sử D là tập không rỗng các Documents nào đó và mỗi phần tử của nó ta gọi là một thông tin, D được gọi là tập các thông tin. Tập K là tập hữu hạn các phần tử mà trên đó thỏa mãn quan hệ so sánh (tức là với mọi x, y y hoặc x K ta có : x > y). Không mất tính tổng quát ta xem K là tập các số tự nhiên. K được gọi là tập khóa của các cây nhị phân. Ta kí hiệu là cây rỗng và ta đặt D+ = D Giả sử các kí hiệu [ ] < > , D+ { }. K. Trang 4 Luận văn tốt nghiệp Định nghĩa l.1 (Định nghĩa đệ qui cây nhị phân một chiều với thông tin chứa ở lá) a. Mỗi phần tử d D gọi là một cây. b. Nếu T1, T2 là hai cây và k K, thì dãy kí hiệu k cũng là một cây. Dạng đồ thị của cây d như sau: k T1 T2 Tập tất cả các cây định nghĩa như trên ta kí hiệu qua TREE và gọi là tập các cây nhị phân một chiều với thông tin chứa ở lá trên tập khóa K (gọi tắt là câ y nhị phân).K là tập khoá của TREE. Mỗi đỉnh có khoá k được gọi là đỉnh trong của cây. Thông tin được chứa ở đỉnh ngoài ( tức là đỉnh không chứa khoá) còn gọi là lá. T 1 là cây con bên trái, T 2 là cây con bên phải. Định nghĩa 1.2 (Định nghĩa hàm đánh giá hay hàm kết quả) Ta kí hiệu " " " " để chỉ sự đồng nhất bằng nhau(không đồng nhất bằng nhau) giữa các cây nhị phân. Giả sử T là một cây nhị phân và l K. Ta định nghĩa hàm kết quả f từ tập TREE K vào D theo định nghĩa đệ quy của T như sau: a. Nếu cây nhị phân T d D thì f(T,l) = f(d,1) = d với mọi l b. Nếu cây nhị phân T k thì : f(T1,l) nếu 1 K. k f(T,1) = f(k,l) = f(T2) nếu 1 > k Định nghĩa 1.3 (Định nghĩa sự tương đương giữa hai cây nhị phân) Giả sử T1 , T2 TREE. Ta nói T 1 là tương đương với T 2 trên K( Kí hiệu T 1 (K) T2 ) khi và chỉ khi: f(T 1, l) = f(T2, l) với mọi 1 K. Từ định nghĩa trên ta thấy rằng: T 1 không tương đương với T 2 trên K (Ký hiệuT1 (K) T2) khi và chỉ khi tồn tại một khóa l0 Trang 5 K sao cho f(T 1, l0) f(T2, l0) Luận văn tốt nghiệp 2. Hệ tiên dề và các quy tắc dẫn xuất trên TREE. 2.1 Quy tắc dẫn xuất của TREE. Trước hết ta đưa vào khái niệm phương trình cây: Giả sử T1, T2 TREE và "=" là một kí hiệu không thuộc tập K D+ { [,],<,>} . Khi đó dãy kí hiệu T l = T2 gọi là một phương trình cây. Đặt EQU : {T1 = T2 | T1,T2 TREE}. EQU được gọi là tập tất cả những phương trình cây trên TREE. Giả sử X EQU và Tl= T2 EQU. Định nghĩa 1.4 (Định nghĩa dẫn được) Phương trình cây T 1 = T2 là dẫn được từ X( kí hiệu X ├ T1 = T2) khi và chỉ khi T1= T2 X hoặc T1 = T2 dẫn được từ các phần tử trong X bằng cách áp dụng một số hữu hạn lần các qui tắc dẫn xuất sau : Quy tắc 1 (R1): X ├ T =T với mọi T TREE. Quy tắc 2 (R2): Nếu X ├ T1= T2 thì X ├ T2= T1. Quy tắc 3 (R3): Nếu X ├ T1= T2 và X ├ T2 = T3 thì X ├ T1= T3 Quy tắc 4 (R4): Nếu X ├ T1= T1' thì X ├ k = k < T1', T2> Quy tắc 5 (R5): Nếu X ├ T2=T2' thì X ├ k = k < T1, T2'> 2.2 Hệ tiên đề của TREE trên tập khóa hữu hạn Ki (i=l, 2, ..., n-l). Do Ki hữu hạn nên trong Ki tồn tại phần tử bé nhất và phần tử lớn nhất mà ta kí hiệu tương ứng là k imin , kimax Hệ tiên đề của TREE trên tập khóa hữu hạn Ki là tập các phương trình cây sau: Tiên đề axi1: k, T3> = k là một tiên đề nếu kimin k < k’ kimax . Dạng đồ thị: k k’ T1 = T3 T2 Trang 6 k T1 T3 Luận văn tốt nghiệp Tiên đề axi2: k < k' , T3 > = k' > là một tiên đề nếu kimin k’ < k kimax . Dạng đồ thị: k k’ T1 = T3 k’ T1 T2 k T2 T3 Tiên đề axi3: k < T1, k' > = k là một tiên đề nếu kimin k k’ kimax . Dạng đồ thị: k = k’ T1 T2 Tiên đề axi4 : k T1 T3 k = T là một tiên đề với mọi T Dạng đồ thị: k = T T3 TREE và k T T Tiên đề axi5: k < T1, k' > = k’ là một tiên đề nếu kimin k < k’ kimax . Dạng đồ thị: k = k’ T1 T1 k’ T1 T2 T2 Tiên đề axi6(tiên đề max) k = T1 là một tiên đề nếu k > kimax Dạng đồ thị: k T1 = T2 Trang 7 T1 Ki Luận văn tốt nghiệp Tiên đề axi7(tiên đề min) k = T2 là một tiên đề nếu k < kimin Dạng đồ thị: k = T2 T1 T2 Đặt AXi = {axi1 , axi2 , axi3 , axi4 , axi5 , axi6 , axi7} và gọi AXi là hệ tiên đề trên tập khoá hữu hạn Ki (i= 1, ..., n-l). Một cách tổng quát, trong cây T l ta có thể thay cây con T 0 bởi cây T00 , Khi đó, ta sẽ được cây T 2 (ký hiệu T1T0T00T2). Như vậy, ký hiệu T 1T0T00T2 có nghĩa là T2 nhận được từ T l bằng cách thay cây con T 0 của Tl bởi T00 Giả sử X EQU ta có bổ đề sau: Bổ đề l.l: Nếu Tl , T0, T00 , T2 TREE, T1T0T00T2 và X ├ T0 = T00 thì X ├ T1 = T2 Thật vậy, ta sẽ chứng minh bổ đề 1 . 1 theo quy nạp từ định nghĩa 1 . 1 ta có các trường hợp sau: Trường hợp l: Nếu Tl d Khi đó T l = T0 T00 T2 d Hiển nhiên là X ├ T1 = T2 Trường hợp 2: Nếu Tl k < Tll, T12> , Khi đó ta có các trường hợp sau: Nếu Tl T2 thì bổ đề hiển nhiên đúng. Nếu Tl T0 và T00 Nếu Tl T2 , Tl T0 và T00 T2 Theo giả thiết ta có X ├ T0 = T00 X ├ T1 = T2 T2 giả sử ta đã có T 21 , T22 thoả mãn X ├ T11 = T21 (l) , X ├ T12= T22 (2) và T11T0T00T21 , T12T0T00T22 Ta cần chứng minh X ├ T1 = T2 Dễ thấy: T2 k < T21, T22> Từ ( 1 ) , áp dụng quy tắc R4 ta có X ├ k = k < T21 ,T22> (3). áp dụng R5 ta có : X ├ k = k < T21 ,T22> (4) . Từ (3) và (4) áp dụng R 3 ta có: X ├ k = k < T21 ,T22> hay X ├ T1 = T2 Bổ đề 1.1 đã được chứng minh. Định lý l.l: Giả sử T1, T2 TREE, nếu AX ├ T1 = T2 thì T1 Trang 8 (K)T2 Luận văn tốt nghiệp Thật vậy ta chứng minh định lý 1.1 bằng qui nạp theo chiều dài dẫn xuất của cây . Ta có các trường hợp sau: + Nếu Tl = T2 là axl, khi đó ta có: T l T2 k <[k' < Tll, T21>, T31> và k với k < k'. Với mọi l K ta có các trường hợp sau: Nếu l k < k' ta có: f(Tl, l) = f(k <[k' , T31>, l ) = f( k', , l ) = f(T ll, l) và f(T2, l) = f(k < T 21 , T3l>, l ) = f(T ll, l). Vậy ta có f(T l , l) f(T2, l) với mọi l K thỏa mãn l k < k'. Nếu k < l k' ta có: f(Tl, 1 ) = f( k <[k' , T31>, l ) = f(T2l, l). f(T2, 1 ) = f( k , 1 )= f(T31, 1 ) . vậy ta có f(T l , 1 ) = f(T2, l ) với mọi l K thỏa mãn k’ < l k'. Nếu l > k' ta có: f(Tl, l) = f(k <[k', , T31>, l ) = f(T 3l, l). f(T2, l ) = f(k , l ) = f(T 31, l ). vậy ta có f(T l, l ) = f(T2 ,1 ) với mọi l K thỏa mãn l > k'. Vậy ta có f(T l, l ) = f(T2, l ) Với mọi l K nếu Tl + Nếu Tl = T2 là ax2 , khi đó ta có: T l k < k', , T31> và T2 k' > với k > k'. Với mọi l Nếu l T2 là axl. K ta có các trường hợp sau: k'< k ta có: f(T1, l) = f( k < k' ,T31>, l ) = f( k' , l) = f(T ll , l > f(T2, l ) = f( k' > , l ) = f(T ll, l ). Vậy ta có f(T l, l ) = f(T2 , l ) với mọi l Nếu k'< l K thỏa mãn l k ta có: f(Tl, l) = f( k' , l ) = f(T 21, l). Trang 9 k'< k. Luận văn tốt nghiệp f(T2 , l) = f( k , l ) = f(T 21 , l) . Vậy ta có f(T l, l ) = f(T 2, l ) Với mọi l K thỏa mãn k' < l k. Nếu l > k ta có: f(Tl, l) = f(T31, l) và f(T2 , l) = f(k , l) = f(T31, l). vậy ta có f(T l , l) = f(T2, l) với mọi l K thỏa mãn l > k. Vậy ta có f(T l , l) = f(T2 , l) với mọi l K nếu T1 = T2 là ax2 + Nếu Tl = T2 là ax3, khi đó ta có: T 1 k > và T2 k Với k Nếu l k' k'. Với mọi l K ta có các trường hợp sau: k ta có: f(Tl , l ) = f(Tl1 , l ) và f(T2 , l) = f(Tl1 , l) . Vậy ta có f(T l , l) = f(T2, l) Với mọi l Nếu k' < l K thỏa mãn l k' k. K thỏa mãn k'< 1 k. k ta có: f(Tl , l) = f(Tl1 , 1 ) và f(T2 , l) = f(Tl1 , l). . Vậy ta có f(T l, l) = f(T2 , l) Với mọi l Nếu l > k ta có: f(Tl, l) = f( k', , l) = f(T 31, l) và f(T2 , l) = f(T31 , l). vậy ta có f(Tl, l) = f(T2 , l) với mọi l Vậy ta có f(T l , l) = f(T2 , l) Với mọi l + Nếu Tl = T2 là ax4 , khi đó ta có:T 1 Với mọi l K thỏa mãn l > k. K nếu Tl = T2 là ax3 k và T2 Tll với k > kmax K ta có: f(T l, l) = f(Tll, l) = f(T2 ,l) (Vì l kmax < k). Vậy ta có f(T l, l) = f(T2 , l) với mọi l K nếu Tl = T2 là ax4 + Nếu Tl = T2 là ax5 khi đó ta có:T l k và T2 T12 với k < kmin Với mọi l K ta có: f(Tl, l) = f(T12 , l ) = f(T2 , l) (vì k < kmin Vậy ta có f(T l, l) = f(T2 , l) với mọi l K nếu Tl = T2 là ax5 Trang 10 l) Luận văn tốt nghiệp Ngoài ra để chứng minh tính đúng đắn của định lý 1 ta cần chứng minh thêm rằng: các quy tắc dẫn xuất cũng bảo đảm tính tương đương. Thật vậy: Quy tắc l(Rl): X ├ T1 = T1 với mọi T1 f(Tl, l) = f(Tl, l) với mọi l TREE(n), hiển nhiên ta có: K. Quy tắc 2(R2): Nếu X ├ T1 = T2 thì X ├ T2 = T1 , hiển nhiên ta có: f(Tl , l) = f(T2 , l) Với mọi l K. Quy tắc 3(R3): Nếu X ├ T1 = T2 và X ├ T2 = T3 thì X ├ T1 = T3 hiển nhiên ta có: f(Tl, l) = f(T2, l) và f(T 2 , l) = f(T3 , l) với mọi l f(Tl, l) = f(T3 , l) K. Quy tắc 4(R4): Nếu X ├ T1 = T1’ (*) thì X ├ k = k Ta chứng minh f(k , l) = f(k < T l, T2>, l) với mọi l K. Thật vậy: *Nếu l k ta có: f( k , l) = f(Tl , l). f( k , l) = f(Tl, l). Theo (*) ta có: f(Tl, l) f(Tl, l). Vậy: f(k , l) = f( k , l). *Nếu l > k ta có: f(k , l) = f(k , l) : f( T2, l). vậy quy tắc R4 thỏa mãn định lý 1.1 . Quy tắc 5(R5): Nếu X ├ T2 = T2’ (**) thì X ├ k = k Ta chứng minh f( k , l) = f( k , l) Với mọi l K. Thật vậy: *Nếu l < k ta hiển nhiên có: f( k , l) = f( k < T l , T2’>, l) = f( T l, l). *Nếu l > k ta có: f( k , l) = f(T2, l). f( k < Tl’, T2>, l) = f(T 2’ , l). Theo (**) ta có: f(T 2 , l) = f( T2’ , l). vậy: f(k , l) = f( k , l)' vậy quy tắc R5 thỏa mãn định lý 1.1. Định lý 1.1 đã được chứng minh. Trang 11 Luận văn tốt nghiệp 3. Cây chuẩn tắc một chiều trên tập khóa K. Định nghĩa 1.5 (Định nghĩa cây chuẩn tắc ). Cây N TREE gọi là cây chuẩn tắc nếu N là một trong hai dạng sau : a. N d D. b. Nếu N d thì N k1 < d1, k2< d2,.....,ks, ds+1>....>> Dạng đồ thị của cây chuẩn tắc N: N k1 d1 k2 d1 ... ks Ở đây: k1< k2< ... < ks (ki di ds ds+1 K với i =l, 2, ..., s) và d 1, d2 ... ds D. di+1 (i=1,...,s) Nếu N, T TREE, N là dạng chuẩn tắc và N (K)T thì ta nói N là cây một chiều chuẩn tắc của T trên K. Định lý l.2 (tính duy nhất của dạng cây chuẩn tắc) Giả sử N1, N2 là 2 cây một chiều chuẩn tắc khi đó ta có: N1 N2 N1 N2 Chứng minh: Điều kiện đủ: Nếu N1 với mọi l N2 thì N1 N2 là hiễn nhiên đúng vì f(N1,l) = f(N2,l) K Điều kiện cần: Ta có 4 trường hợp sau: 1. N1 d1 , N2 e1 (với d1 , e1 D) Theo định nghĩa 3 ta có : N1 N2 khi f(N1,l) = f(N2,l) với mọi l Ta có : Trang 12 K (1) Luận văn tốt nghiệp f(N1,l) = f(d 1,l) = d 1 } theo (1) = > d 1 = e1 hay N1 N2 f(N2,l) = f(e1,l) = e1 Vậy N1 2. N1 N2 thì N1 d1 , N2 N2 k1 e1 k2 e2 ... ks Ở đây: k1< k2< ... < ks (ki di es es+1 K với i =l, 2, ..., s-1) và d i D. di+1 (i=1,...,s) Do N1 N2 nên N1 N2 vì f(N2,k1) =e1 = f(N1,k1) = d 1 f(N2, k2) = e2 = f(N1,k2) = d1 Mà giả thiết e1 Vậy N1 3. } = > e1 = e2 e2 (định nghĩa cây lệch phải) nên e1 = e2 là trái với giả thiết. N2 N1 k1 d1 N2 e1 k2 d2 ... ks ds ds+1 Chứng minh tương tự mục 2 ta có: Do N1 N2 nên N1 N2 vì f(N1,k1) =d1 = f(N2,k1) = e1 } = > d1 = d2 Trang 13 Luận văn tốt nghiệp f(N1, k2) = d 2 = f(N2,k2) = e1 Mà giả thiết d 1 Vậy N1 d2 (định nghĩa cây lệch phải) nên d 1 = d2 là trái với giả thiết. N2 4. N1 và N2 có các dạng sau: N1 k1 d1 N2 k2 l1 e1 d2 ... l2 e2 ... ks Với di, ej D. di di+1 lt ds , ej ds+1 ej+1 , (ki, kj) et et+1 K, i =1..s , j= 1..t ki+1 - ki > 0 , lj+1 -lj > 0 , i = 1..s-1 , j =1.. t-1 Nếu N1 { ` N2 thì ta chứng minh N1 tức là chứng minh N2 l1 = k1 , l2 = k2 , ... lt = ks (a) d1 = e1 , d2 = e2 , ... d s = et , ds+1 = et+1 và chứng minh: s=t (b) Bây giờ ta lần lượt chứng minh (a) và (b). * Chứng minh (a): Giả sử l1 k1 Xét trường hợp k1 < l1 . lấy m f(N1,k1) = f(N1,m) = d 1 f(N2,k1) = f(N2,m) = e1 } f(N1,k1+1) = f(N1,m+1) = d 2 f(N2,k1+1) = f(N2,m+1) = e1 K với k1=m ta có: = > d1 = e1 (1) } = > d2 = d1 (2) Từ (1) và (2) suy ra d 1 = d2 (vô lý) vì d 1 d2 = > kết luận k1 = l1 = > d 1 = e1 Trang 14 Luận văn tốt nghiệp Chứng minh tương tự ta có: { l2 = k2 , l3 = k3 , ... ls = ks d2 = e2 , d3 = e3 , ... ds = es * Chứng minh (b) tức chứng minh s = t: Giả sử s < t ( với trường hợp s > t) ta chứng minh tương tự) Vì s < t nên ks = ls < lt (3) N2 l1 e1 l2 e2 ... ls es ls+1 ls+1 lt et Với { ki K , i=1..t , l1< l2 < ... ở đây Ti (i=1,2) đã tồn tại cây lệch phải là R i (i=1,2) . Ta có AX ├ T = k T1 T2 áp dụng 2 lần bổ đề 1 ta được AX ├ T = k N1 * Với k kmin ta chọn ngay được cây N kmax và k phải thoả mãn: N2 (T N) và AX ├ T = N Trang 16 N1 hoặc N N2 là cây lệch Luận văn tốt nghiệp * Với k K tức ( kmin < k < kmax ) ta xét các trường hợp sau: 2.1 Nếu N1 d , N2 d . Ta chọn N = k < d, d > = > suy ra N là cây lệch phải và AX ├ T = N 2.2 Nếu N1 d , N2 k1...>> với k1 N là dạng lệch phải và AX ├ T = N b. Nếu k < k1 và d d1 thì chọn N k d k1 d1 ... kn Trang 17