Thư viện tài liệu, ebook tham khảo dành cho học sinh, sinh viên

Khẳng định Giả sử B chứa n phần tử và phủ tối ưu gồm k tập. Thuật toán tham lam sẽ dùng nhiều nhất k ln n tập. Tỉ suất của thuật toán tham lam I Tỉ lệ giữa nghiệm của thuật toán tham lam và nghiệm tối ưu thay đổi theo dữ liệu vào nhưng luôn nhỏ hơn ln n. I Có một số input tỉ lệ rất gần với ln n. I Ta gọi tỉ lệ lớn nhất là tỉ suất của thuật t...

64 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 809 | Lượt tải: 0

Tính chất Với mọi đường đi của DAG, các đỉnh xuất hiện theo thứ tự topo. procedure dag-shortest-paths(G; l; s) Input: DAG G = (V; E); độ dài các cạnh fle : e 2 Eg; đỉnh s 2 V Output: Với mỗi đỉnh u đến được từ s, dist(u) được đặt bằng khoảng cách từ s tới u. for all u 2 V: dist(u) = 1 prev(u) = nil dist(s) = 0 Sắp topo các đỉnh của G f...

52 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 961 | Lượt tải: 0

Câu hỏi 2 Ta sẽ tiếp tục thế nào khi đã tìm được một thành phần liên thông mạnh? Mệnh đề Nếu C và D là các thành phần liên thông mạnh, và có một cạnh từ một đỉnh trong C tới một đỉnh trong D, vậy thì số post lớn nhất trong C phải lớn hơn số post lớn nhất trong D. Khi ta tìm thấy một thành phần liên thông mạnh và xóa nó khỏi đồ thị G, vậy th...

58 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 981 | Lượt tải: 0

Câu hỏi 2 Ta sẽ tiếp tục thế nào khi đã tìm được một thành phần liên thông mạnh? Mệnh đề Nếu C và D là các thành phần liên thông mạnh, và có một cạnh từ một đỉnh trong C tới một đỉnh trong D, vậy thì số post lớn nhất trong C phải lớn hơn số post lớn nhất trong D. Khi ta tìm thấy một thành phần liên thông mạnh và xóa nó khỏi đồ thị G, vậy th...

57 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 759 | Lượt tải: 0

Định lý Cho c1; c2; : : : ; ck là các số thực. Giả sử phương trình kr − c1rk−1 − · · · − ck = 0 có k nghiệm phân biệt r1; r2; : : : ; rk. Khi đó dãy ⟨an⟩ là nghiệm của hệ thức truy hồi an = c1an−1 + c2an−2 + · · · + ckan−k nếu và chỉ nếu an = α1r1n + α2r2n + · · · + αkrkn trong đó αi là các hằng số. Ví dụ Tìm nghiệm của hệ thức truy hồi ...

45 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 2768 | Lượt tải: 0

Bài tập ▶ Ta cần $15 để đóng góp cứu trợ đồng bào vùng bão lụt. ▶ Có 20 sinh viên tham gia đóng góp. ▶ Biết rằng 19 người đầu tiên sẽ góp $1 hoặc không, người thứ 20 sẽ góp $1 hoặc $5 (hoặc không góp). ▶ Hãy dùng hàm sinh để tính số cách quyên góp $15. Bài tập Hãy tính số cách để lấy 25 quả bóng giống nhau từ 7 chiếc hộp biết rằng hộp đầu t...

26 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 712 | Lượt tải: 0

Bài tập Có bao nhiêu cách để lấy n quả thỏa mãn ba yêu cầu sau đây? ▶ Nhiều nhất 2 quả cam. ▶ Số táo là tùy ý. ▶ Số chuối phải chia hết cho 3. 41 / 51Với n = 4 quả 1. 0 quả cam, 1 quả táo, 3 quả chuối 2. 0 quả cam, 4 quả táo, 0 quả chuối 3. 1 quả cam, 0 quả táo, 3 quả chuối 4. 1 quả cam, 3 quả táo, 0 quả chuối 5. 2 quả cam, 2 quả táo, 0 q...

51 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 687 | Lượt tải: 0

Đếm bằng hai cách 1. Định nghĩa S. 2. Chứng minh jSj = n (một cách đếm). 3. Chứng minh jSj = m (một cách đếm khác). 4. Kết luậ Chứng minh ▶ S = các bộ bài gồm n quân chọn từ n quân đỏ và 2n quân đen trên bàn.

48 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 748 | Lượt tải: 0

Nhắc lại tương đương logic :P _ Q ≡ P ) Q 33 / 34Chứng minh Ta chứng minh bằng phản chứng. Xét u có bậc ra cao nhất và u không là vua. Vậy tồn tại v thỏa mãn: 1. v ! u, và 2. Với mọi w: :(u ! w) | {z } w!u hoặc :(w ! v) | {z } v!w Khẳng định 2 tương đương với Nếu u ! w vậy v ! w. Kết hợp với khẳng định 1 ta được outdeg(v) ≥ outdeg(u...

34 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 752 | Lượt tải: 0

Định lý (Dirac) Nếu G là một đồ thị với n ≥ 3 đỉnh thỏa mãn: bậc của mỗi đỉnh ít nhất bằng n/2, khi đó G là đồ thị Hamilton. Chứng minh. ▶ Với hai đỉnh không kề nhau bất kỳ u và v ta có deg(u) + deg(v) ≥ n/2 + n/2 = n ▶ Suy ra, G thỏa mãn các điều kiện của định lý Ore, vì thế nó có chu trình Hamilton. Bài tập ▶ Hãy chỉ ra rằng các điều kiệ...

24 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 946 | Lượt tải: 0