Bài giảng Cây nhị phân

Chương 1: CÁC KHÁI NIỆM CƠ BẢN1.1 MỘT SỐ KHÁI NIỆM• Trung tâm quảng bá (Center, Broadcast Center), nhà cung cấp dữ liệu (NCCDL-Data Provider): Trung tâm có các kênh phát thông tin quảng bá tới các thiết bị thu dữ liệu. • Thiết bị thu dữ liệu (TBTDL - User): Thu dữ liệu phát ra từ NCCDL và dùng các khoá bí mật của nó để giải mã dữ liệu thu được. • Thông điệp hay bản tin (Message): Là thông tin hoặc đoạn thông tin được NCCDL gửi đến TBTDL qua các kênh quảng bá. • Khoá thời...
Nội dung trích xuất từ tài liệu:
Bài giảng Cây nhị phânChương 1: CÁC KHÁI NIỆM CƠ BẢN1.1 MỘT SỐ KHÁI NIỆM• Trung tâm quảng bá (Center, Broadcast Center), nhà cung cấp dữ liệu (NCCDL-Data Provider): Trung tâm có các kênh phát thông tin quảng bá tới các thiết bị thu dữ liệu.• Thiết bị thu dữ liệu (TBTDL - User): Thu dữ liệu phát ra từ NCCDL và dùng các khoá bí mật của nó để giải mãdữ liệu thu được.• Thông điệp hay bản tin (Message): Là thông tin hoặc đoạn thông tin được NCCDL gửi đến TBTDL qua cáckênh quảng bá.• Khoá thời gian tồn tại ít (Short-lived key-session key): Là khóa được duy trì trong một phiên truyền dữ liệu gọi tắt là khoá phiên.• Khoá thời gian tồn tại dài (long- lived key): Là khoá tồn tại trong thời gian dài của hệ thống, gọi tắt là khoá thời giandài hay khoá “dài”.• Bộ khoá nhái: Là bộ khoá mà kẻ gian đã (dùng phương pháp nào đó,ví dụ thám khoá) thuđược từ tập khoá của một số TBTDL.• Thiết bị thu bất hợp pháp (Traitor): Là TBTDL làm rò rỉ khoá hoặc TBTDL sử dụng bộ khoá nhái để giải mãbản tin nhận được từ NCCDL. 11.1.1 Các ký hiệu:• N: Tập tất cả các TBTDL, |N|=n.• u1,..., un: ký hiệu các TBTDL.• R: Tập các TBTDL bất hợp pháp, |R|=r.• P: Tập các TBTDL hợp pháp, P=N-R.• K: Khoá phiên.• L: Khoá “dài”.• M: Thông điệp hay bản tin.• CM: Bản mã của thông điệp M.• tM: Bản tin thử nghiệm.• Lu i tập các khoá “dài” của TBTDL ui, i=1, 2,…, n.• | Lu i |: số lượng các khoá “dài” của TBTDL ui.• Si: Tập các TBTDLdùng chung một khoá “dài” Li.• Si,j = Si – Sj: chứa các TBTDL thuộc phần bù của tập Si so với tập Sj.Các TBTDL trong tập Si,j dùng chung khoá “dài” Li,j. 21.1.2 Vấn đề mã hoá1.1.2.1 Khái niệm hệ mã hoá Mã hóa là quá trình chuyển những thông tin nhận biết được thành nhữngthông tin “khó” nhận biết được1.1.2.2 Phân loại mã hoá Các hệ thống mã hoá trong máy tính thuộc một trong hai loại sau: • Mã hoá với khoá đối xứng (Symmetric-key Encryption) • Mã hoá với khoá công khai (Public-key Encryption)1.1.3. Khái niệm “phủ”Cho một họ các tập con khác rỗng S = { S1, S2, ..., SW}, Sj ⊆ N, j=1,…,w.Cho tập khác rỗng P ⊆ N; phủ của tập P là tập Si 1 , Si 2 ,…, Si t ,{i1,i2,..., it} ⊆ {1,..., w} và thoả mãn điều kiện: tP= U S ij S i j ∩ S i k = φ , ∀ ij ≠ i k j= 1Kích thước của một phủ là số lượng các tập con tạo nên phủ đó.Ví dụ ở đây, kích thước của phủ P là t. 31.2 KHÁI NIỆM “KHUNG PHỦ TẬP CON” Giới thiệu “khung phủ tập con” ( Subset Cover Framework – SCF) đượcdùng trong phương pháp phát hiện thiết bị thu làm lộ khoá bí mật. wTrong SCF, có giải thuật xác định các tập con S1, S2, ..., Sw ⊂ N, US i = N. i =1 Mỗi tập Si có khoá “dài” Li. Mỗi u ∈ Si đều tính được Li từ tập khoá Lu của mình. Tập P phải được phân mhoạch thành các tập con rời rạc Si 1 , Si 2 ,…, Si m sao cho: P = US ij j=1Các khoá “dài” tương ứng với các tập Si 1 , Si 2 ,…, Si m là Li 1 , Li 2 , ..., Li m .Lưu ý: Các TBTDL u ∈ Si j sử dụng chung khoá “dài” Li j , j = 1, 2,..., mSCF sử dụng hai giải thuật mã hoá E và F:• Giải thuật E: {0,1}*→{0,1}*, mã hoá khóa phiên K, lần lượt với từngkhoá “dài” Li 1 , Li 2 , ..., Li m , nhận được các bản mã: E(K, Li 1 ), E(K, Li 2 ), ..., E(K, Li m ).• Giải thuật F : {0,1}*→ {0,1}*, mã hoá thông điệp M sử dụng khóa phiênK, nhận được bản mã: Fk(M). 41.3 CÂY NHỊ PHÂNa. Khái niệm cây Cây là đồ thị đơn, vô hướng, liên thông và không có chu trình.b. Khái niệm cây nhị phân Cây nhị phân là cây có hai dạng nút: Nút ngoài: nút lá, không có con. Nút trong: có chính xác hai con là con trái và con phải. Cây nhị phân đầy đủ là cây nhị phân, trong đó tất cả các lá có cùngkhoảng cách tới gốc. Số lượng các lá trong cây nhị phân đầy đủ (có chiều cao k) là h = 2k. Cha chung thấp nhất của hai nút (kể cả lá) a, b là nút giao nhau giữađường đi từ a tới gốc và từ b tới gốc.c. Tính chất cây nhị phân1) Cây nhị phân có r lá, thì có chiều cao ít nhất là ⎡log 2 (r )⎤2) Thuộc tính rẽ nhánh 5 Chương 2: PHƯƠNG PHÁP DÒ TÌM THIẾT BỊ THU BẰNG “KHUNG PHỦ TẬP CON”2.1 Khái niệm lưu v ...