Thuật toán PRIM

Đăng bởi - Vào
Cho đồ thị vô hướng có trọng số G=(V,E), với hàm trọng số w: E → R (R là tập các số thực). Tìm một MST(Minimal Spanning Tree: cây khung tối tiểu) của G: T=(VT, ET).

Mã giả







Hướng dẫn giải tay



Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

[DATABASE] Tìm mọi khóa của lược đồ quan hệ

Đăng bởi - Vào
Hình ảnh
  Cách thực hiện: Gọi K là tập khóa cần tìm B1. Tìm tập nguồn N và Tính N + F Nếu N + F  = Q +  thì suy ra lược đồ quan hệ chỉ có một khóa duy nhất là N và kết thúc thuật toán Ngược lại, qua bước 2 B2. Tìm tập trung gian TG Nếu TG =   thì lược đồ quan hệ có 1 khóa là tập nguồn N và kết thúc thuật toán Ngược lại, nếu TG ≠   thì tìm tất cả tập con khác rỗng X i  của tập TG Lấy từng X i  hợp với N => N ∪ X i  TH1 : Nếu (N ∪ X i ) + F  = Q +  thì (N ∪ X i ) là khóa, loại tính toán đối với các tập con khác của TG có chứa X i  ; thêm khóa vào tập K TH2 : Nếu (N ∪ X i ) + F  ≠ Q +  thì  (N ∪ X i ) không là khóa B3. Kết luận:  Khóa của lược đồ quan hệ là tập K ------------ Giải thích: N là tập thuộc tính nguồn (chứa những thuộc tính chỉ xuất hiện ở vế trái của các phụ thuộc hàm; các thuộc tính không xuất hiện ở cả vế trái và vế phải của phụ thuộc hàm) TG là tập thuộc t...
Xem chi tiết »

[DATABASE] Phủ tối thiểu của tập phụ thuộc hàm

Đăng bởi - Vào
Hình ảnh
Cách thực hiện: B1. Phân rã PTH sao cho VP chỉ còn 01 thuộc tính B2. Loại các thuộc tính dư thừa ở VT (không xét PTH mà VT có 01 thuộc tính) Bỏ thuộc tính ở VT khi và chỉ khi bao đóng của các thuộc tính còn lại chứa thuộc tính ở VP B3. Loại bỏ các PTH dư thừa ( không xét PTH mà thuộc tính ở VP chỉ xuất hiện một lần) B3.1: Tìm bao đóng của VT B3.2: Nếu bao đóng của VT chứa thuộc tính ở VP thì nó là PTH dư thừa, ngược lại nó không là PTH dư thừa ------------ Ví dụ : Cho lược đồ quan hệ Q=(A, B, C, D) và PTH F={AB → CD, B → C, C → D}  Tìm phủ tối thiểu?  B1. Phân rã PTH sao cho vế phải chỉ còn một thuộc tính F={AB → C, AB → D, B → C, C → D}  B2. Bỏ các thuộc tính dư thừa ở vế trái B → C, C → D : không xét vì vế trái chỉ có một thuộc tính Xét AB → C A + F-{AB → C}    = A, không chứa C nên B không thừa B + F-{AB  → C}   = BCD, chứa C nên A thừa Loại thuộc tín...
Xem chi tiết »

[SOFTWARE TESTING] - Tổng hợp lí thuyết

Đăng bởi - Vào
Hình ảnh
Hình 1. Sơ đồ tổng quan kiến thức về kiểm thử phần mềm 1. Các tài liệu trong test process - Test plan : là tài liệu mô tả về: scope, approach, schedule, resources - Test case : trình bày những thông tin cho kiểm thử một hạng mục. Tùy theo tổ chức sẽ có những custom phù hợp với tổ chức của mình nhưng vẫn đảm bảo gồm các thành phần: ID Test case description Pre-conditions Test case procedure Actual output Expected output Result (pass/fail) Note 1 test case luôn có 3 loại: Normal, Abnormal, Boundary - Bug report: Mô tả bug khi execute test cases -> Giúp dev tái hiện lại con bug một cách dễ dàng. Gồm các thành phần: ID Bug Description Environment: Browser, devices,... Các bước tái hiện: Pre-conditions Step to reproduce Actual output Expected output Mức độ nghiêm trọng (s everity - con bug ảnh hưởng như thế nào tới hệ thống) Critical: dừng ứng dụng (crash app) Serious: thiếu chức năng/chức năng không work Normal: chức năng không work nhưng vẫn có giải pháp khắc phục tạm thời để nó hoạ...
Xem chi tiết »