• Bài giảng Toán rời rạc - Bài 15: Kỹ thuật Hàm sinh - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 15: Kỹ thuật Hàm sinh - Trần Vĩnh Đức

    Định nghĩa Ta ký hiệu [xn]G(x) là hệ số của xn trong hàm sinh G(x) = g0 + g1x + g2x2 + ·· · : Có nghĩa rằng [xn]G(x) = gn: 3 / 26Bài tập Tìm hệ số của xn trong hàm sinh (1 − x)c : 4 / 26Lời giải Ta có (1 − x)c = (1 + x + x2 + · · · )c: Hệ số của xn trong hàm sinh trên chính là số nghiệm nguyên không âm của phương trình

    pdf26 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 474 | Lượt tải: 0

  • Bài giảng Toán rời rạc - Bài 16: Công thức truy hồi - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 16: Công thức truy hồi - Trần Vĩnh Đức

    Ví dụ Một quần thể vi trùng có số lượng cá thể tăng gấp đôi sau mỗi giờ. Nếu thoạt đầu có 5 cá thể hỏi sau 5 giờ số lượng của chúng là bao nhiêu? Ví dụ Xét một cầu thang với n bậc thang. Có bao nhiêu cách để đi lên cầu thang nếu chúng ta có thể leo lên 1 bậc hoặc 2 bậc trong mỗi bước? Ví dụ Có bao nhiêu xâu nhị phân độ dài n không chứa hai...

    pdf45 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 541 | Lượt tải: 0

  • Bài giảng Toán rời rạc - Bài 21: Luồng trên mạng - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 21: Luồng trên mạng - Trần Vĩnh Đức

    Mô hình bài bài toán Đồ thị có hướng biểu diễn mạng đường ống, dầu có thể được chuyển qua đường ống này ▶ Mục tiêu là chuyển dầu từ s đến t, nhiều nhất có thể. Mạng Định nghĩa Một mạng được định nghĩa là bộ G = (V; E; s; t; c), ở đây ▶ (V; E) là một đồ thị có hướng; ▶ s; t 2 V, gọi là đỉnh nguồn và đỉnh đích; và ▶ c là một hàm gắn trên mỗi...

    pdf42 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 507 | Lượt tải: 0

  • Bài giảng Toán rời rạc - Bài 22: Bài tập Luồng trên mạng - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 22: Bài tập Luồng trên mạng - Trần Vĩnh Đức

    Tìm tập đỉnh phủ tối tiểu của đồ thị hai phần Tập đỉnh phủ là một tập đỉnh C ⊆ V sao cho mọi cạnh của đồ thị đều có ít nhất một đầu mút trong C. Phủ bàn cờ ▶ Cho bàn cờ n × n đã bị xóa đi một số ô. ▶ Tìm thuật toán để xác định xem liệu có thể phủ kín bàn cờ này bằng các quân dominos biết rằng mỗi quân domino chỉ phủ đúng hai ô trên bàn cờ.

    pdf19 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 338 | Lượt tải: 0

  • Bài giảng Toán rời rạc - Bài 3: Quy nạp - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 3: Quy nạp - Trần Vĩnh Đức

    Nguyên lý quy nạp Xét vị từ P(n) trên N. Nếu ▶ P(0) đúng, và ▶ với mọi n 2 N; (P(n) ) P(n + 1)) cũng đúng, thì P(n) đúng với mọi n 2 N. Chứng minh. ▶ Bước cơ sở: P(0) đúng. ▶ Bước quy nạp: Ta sẽ chứng minh: với mọi n ≥ 0, mệnh đề P(n) ) P(n + 1) đúng. Thật vậy, giả sử P(n) đúng, với n là một số nguyên bất kỳ.

    pdf37 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 299 | Lượt tải: 0

  • Bài giảng Toán rời rạc - Bài 4: Đồ thị - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 4: Đồ thị - Trần Vĩnh Đức

    Định nghĩa Một đồ thị G là một cặp có thứ tự G = (V; E), ở đây V là một tập, còn E là tập với các phần tử là các tập con hai phần tử của V. Các phần tử của V được gọi là các đỉnh, còn các phần tử của E gọi là các cạnh của G. Ví dụ Xét đồ thị G = (V; E) trong đó V = fa; b; c; d; zg E = ffa; bg; fa; dg; fb; zg; fc; dg; fd; zgg:

    pdf57 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 318 | Lượt tải: 0

  • Bài giảng Toán rời rạc - Bài 9: Đồ thị phẳng - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 9: Đồ thị phẳng - Trần Vĩnh Đức

    Định nghĩa Một đồ thị được gọi là phẳng nếu ta có thể vẽ nó trên mặt phẳng mà không có cạnh nào cắt nhau. Hình vẽ như thế gọi là một biểu diễn phẳng của đồ thị. Euler chứng minh rằng mọi biểu diễn phẳng của một đồ thị đều chia mặt phẳng thành cùng số miền như nhau. Định lý (Công thức Euler) Cho G là một đồ thị phẳng liên thông với e cạnh và ...

    pdf36 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 615 | Lượt tải: 0

  • Bài giảng Toán rời rạc - Bài 17: Tìm kiếm trên đồ thị (Version 0.4) - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 17: Tìm kiếm trên đồ thị (Version 0.4) - Trần Vĩnh Đức

    Dùng ma trận kề có hiệu quả? ▶ Có thể kiểm tra có cạnh nối giữa cặp đỉnh bất kỳ chỉ cần một lần truy cập bộ nhớ. ▶ Tuy nhiên, không gian lưu trữ là O(n2) 5 / 57Biểu diễn đồ thị dùng danh sách kề ▶ Dùng một mảng Adj gồm jVj danh sách. ▶ Với mỗi đỉnh u 2 V, phần tử Adj[u] lưu trữ danh sách các hàng xóm của u. Có nghĩa rằng: Adj[u] = fv 2 V j ...

    pdf57 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 307 | Lượt tải: 0

  • Bài giảng Toán rời rạc - Bài 17: Tìm kiếm trên đồ thị (Version 0.5) - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 17: Tìm kiếm trên đồ thị (Version 0.5) - Trần Vĩnh Đức

    Đồ thị Một đồ thị xác định bởi một tập đỉnh (còn gọi là nút) V và bởi các cạnh E giữa các cặp đỉnh được chọn. ▶ Đồ thị có thể vô hướng: cạnh e = fu; vg ▶ hoặc có hướng e = (u; v).

    pdf58 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 261 | Lượt tải: 0

  • Bài giảng Toán rời rạc - Bài 18: Đường đi trên đồ thị (Version 0.2) - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 18: Đường đi trên đồ thị (Version 0.2) - Trần Vĩnh Đức

    Tìm kiếm theo chiều rộng (Breadth-First Search) Chia đồ thị thành các mức: ▶ S là mức có khoảng cách 0. ▶ Các đỉnh có khoảng cách tới S bằng 1. ▶ Các đỉnh có khoảng cách tới S bằng 2 Ý tưởng thuật toán: Khi mức d đã được xác định, mức d + 1 có thể thăm bằng cách duyệt qua các hàng xóm của mức d

    pdf52 trang | Chia sẻ: thuyduongbt11 | Ngày: 11/06/2022 | Lượt xem: 310 | Lượt tải: 0