Đồ án, luận văn, do an, luan van

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

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

Đồ 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).

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

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

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

Bạn cần xây dựng mạng máy tính bằng cách kết nối từng cặp máy. Cần chọn một số kết nối để mạng liên thông; nhưng không phải tất cả các cặp: Mỗi kết nối tốn một chi phí (tiền bảo trì) Mạng với chi phí nhỏ nhất là gì?

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

Đường đi ngắn nhất trên DAG Hình: Đồ thị phi chu trình G và biểu diễn dạng tuyến tính của nó. 169 ▶ Xét nút D của đồ thị, cách duy nhất để đi từ S đến D là phải qua B hoặc C. ▶ Vậy, để tìm đường đi ngắn nhất từ S tới D ta chỉ phải so sánh hai đường: dist(D) = minfdist(B) + 1; dist(C) + 3g

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

Mệnh đề (Giả thuyết Euler, 1769) Phương trình a4 + b4 + c4 = d4 không có nghiệm khi a; b; c; d là số nguyên dương. Năm 1988, Noam Eikies đã chứng minh là sai với phản ví dụ a = 95800; b = 217519; c = 414560; d = 422481 9 / 37Mệnh đề Phương trình 313(x3 + y3) = z3 không có nghiệm nguyên dương. Mệnh đề này cũng sai nhưng phản ví dụ nhỏ nhấ...

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

Yêu cầu chung : Các yêu câu được viết theo từng hàm Hàm giải cho kết quả bài toán đồng thời hiển thị các bước trung gian Các hàm đều phải có chú thích Viết chương trình chính ứng dụng các hàm để giải toàn bộ bài toán Ứng dụng giải các ví dụ và bài tập trong giáo trình

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

1. Phân phối nhị thức 1.1 Định nghĩa Phép thử xảy ra n lần, xác suất xảy ra biến cố A là p, khi đó biến ngẫu nhiên X có phân phối nhị thức. Ký hiệu: X~B(n,p) Ví dụ 1.1 Biết xác suất một người có thời gian sử dụng Interner trong ngày hơn 6 tiếng là 0,1587, gọi Y là biến ngẫu nhiên chỉ số người có thời gian sử dụng Internet trong ngày hơn 6 tiếng ...

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

3.3 QUY NẠP TOÁN HỌC Các phương pháp chứng minh cơ sở: • Chứng minh trực tiếp, chứng minh gián tiếp, chứng minh phản chứng, chứng minh từng trường hợp, chứng minh tương đương Chứng minh bằng quy nạp • Là kĩ thuật sử dụng để chứng minh các mệnh đề phổ quát trên tập các số nguyên dương, x P(x) với x  Z+. • Bao gồm 2 bước: 1) Bước cơ sở: chỉ...

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

CÁC HỆ THỨC TRUY HỒI Một số bài toán đếm không thể giải được bằng kĩ thuật đếm thông thường • Có thể giải bằng cách tìm mối quan hệ, gọi là các hệ thức truy hồi CÁC HỆ THỨC TRUY HỒI Hệ thức truy hồi đối với dãy số {an} là phương trình biểu diễn an qua một hay nhiều số hạng đứng trước nó, cụ thể là a0, a1, ., an-1 với mọi số nguyên n  n0 ,t...

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