• Câu hỏi trắc nghiệm Vật lý đại cương 1Câu hỏi trắc nghiệm Vật lý đại cương 1

    9.27 Bánh xe bán kính R lăn không trượt trên đường thẳng với vận tốc tịnh tiến của khối tâm v o (hình 9.2). Vận tốc của điểm C là: → a) v D v0 b) v c) → → = 2 v → → D 0 = v 2 D 0 . v d) → → = v 0 D → = 9.28 Bánh xe bán kính R lăn không trượt trên đường thẳng với vận tốc tịnh tiến của khối tâm (hình 9.2). Tính vận tốc của điểm A. v o ...

    pdf60 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 115 | 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

    Định lý (Luồng Nguyên) Nếu các khả năng thông qua là số nguyên, thì có tồn tại luồng cực đại nguyên. Chứng minh. Thuật toán Ford-Fulkerson kết thúc và luồng cực đại nó tìm được là luồng nguyên. Liên quan đến thuật toán Ford-Fulkerson ▶ Làm thế nào tính được lát cắt cực tiểu? Dễ thôi, xem chứng minh Định lý Max Flow-Min Cut. ▶ Làm thế nào đ...

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

  • Bài giảng Toán rời rạc - Bài 20: Quy hoạch động - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 20: Quy hoạch động - Trần Vĩnh Đức

    Tập độc lập trên cây ▶ Bài toán tìm tập độc lập lớn nhất được nhiều người tin rằng không có thuật toán hiệu quả để giải nó. ▶ Nhưng khi đồ thị là một cây thì bài toán có thể giải trong thời gian tuyến tính. Bài toán con Lấy một nút r bất kỳ làm gốc của cây. Mỗi nút u bây giờ sẽ xác định một cây con gốc u. Ta xét bài toán con: I(u) = kích th...

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

  • Bài giảng Toán rời rạc - Bài 19: Thuật toán tham lam - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 19: Thuật toán tham lam - Trần Vĩnh Đức

    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...

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

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

    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...

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

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

    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...

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

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

    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...

    pdf57 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 87 | 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

    Đị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 ...

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

  • 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

    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...

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

  • Bài giảng Toán rời rạc - Bài 14: Hàm sinh - Trần Vĩnh ĐứcBài giảng Toán rời rạc - Bài 14: Hàm sinh - Trần Vĩnh Đức

    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...

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