Bài giảng Toán rời rạc - Chương 2, Phần 2: Bài toán tồn tại - Nguyễn Đức NghĩaCỏc số Ramsey Xét một cách tô màu (tuỳ ý) các cạnh của K7. Rõ ràng hoặc là tìm đợc ít nhất một cạnh của K7 đợc tô màu đỏ, hoặc là tất cả các cạnh của nó đều đợc tô bởi màu xanh. Nếu có cạnh tô màu đỏ thì rõ ràng ta có K2 đỏ. Còn nếu tất cả các cạnh đều tô bởi màu xanh thì ta có K7 xanh. Vậy số 7 có tính chất (2,7)-Ramsey, và vì thế R(2,7) ? 7. Nh...
108 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 388 | Lượt tải: 0
Bài giảng Toán rời rạc - Chương 2, Phần 1: Bài toán tồn tại - Nguyễn Đức NghĩaCỏc số Ramsey Từ phân tích ở trên ta thấy 6 có tính chất (3,3)-Ramsey, và mọi số n<6 đều không có tính chất này. Vậy 6 là số nhỏ nhất có tính chất (3,3)-Ramsey. Định nghĩa 3. Số Ramsey R(i,j) là số nguyên dơng nhỏ nhất có tính chất (i,j)-Ramsey. Chẳng hạn, từ kết quả vừa trình bày ở trên, ta có R(3,3) = 6. Ví dụ. Tìm R(2,7) - số nguyên dơng n...
103 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 402 | Lượt tải: 0
Bài giảng Toán rời rạc - Chương 1: Bài toán đếm - Nguyễn Đức NghĩaLiNoReCoCo Example Find all solutions to an = 3an−1+2n. Which solution has a1 = 3? Notice this is a 1-LiNoReCoCo. Its associated 1-LiHoReCoCo is an = 3an−1, whose solutions are all of the form an = α3n. Thus the solutions to the original problem are all of the form an = p(n) + α3n. So, all we need to do is find one p(n) that works. If the extr...
178 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 357 | Lượt tải: 0
Bài giảng Toán rời rạc - Phần 1: Lý thuyết tổng hợp - Nguyễn Đức NghĩaMột số loại ánh xạ hay dùng Toàn ánh: Ánh xạ f từ X vào Y được gọi là toàn ánh (surjection) nếu mỗi phần tử của Y đều là ảnh của ít nhất một phần tử nào đó của X qua ánh xạ f. yY, xX: y = f(x). Song ánh: Ánh xạ f từ X vào Y được gọi là song ánh (bijection, one to one) hay còn gọi là tương ứng 1-1(one-to-one correspondence), sánh, nếu nó ...
91 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 543 | Lượt tải: 0
Bài giảng Toán rời rạc - Giới thiệu môn học - Nguyễn Đức NghĩaỨng dụng: Lý thuyết tập hợp (Set Theory) Có phải số lượng số nguyên là nhiều hơn số lượng số nguyên dương? Có phải số lượng số nguyên là nhiều hơn số lượng số thực? Ví dụ 5: Bài toán người du lịch (The Traveling Salesman Problem) Có ứng dụng quan trọng trong Thiết kế mạch (circuit design) Hướng lộ trên mạng (network routing) và nhiều bài t...
33 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 396 | Lượt tải: 0
Bài giảng Phương pháp tính - Phương trình vi phân - Nguyễn Hồng LộcCác phương pháp tìm nghiệm gần đúng của phương trình vi phân thường đòi hỏi các điều kiện được cho tại một thời điểm ban đau nào đó. 9 Đối vói phương trình vi phân bậc hai, ta can 2 giá trị y(x0) và y'(x0). 9 Tuy nhiên, nhiều bài toán trong thực tế cho thấy điều kiện của hàm can tìm được cho tại nhiều thời điêrn khác nhau, vấn đề này dẫn tói việc...
29 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 437 | Lượt tải: 0
Bài giảng Phương pháp tính - Đạo hàm và tích phân - Nguyễn Hồng LộcCông thức Simpson b Dê tính gần đúng tích phân / f(x)dx ta chia [a, b] thành 2 đoạn bang bằng đa thức nội suy Newton tiến bậc 2 đi qua 3 điếm (a. f(a)), (xi, f(xi)) và (b, f(b)) xuất phát từ nút (a. f(a)) Vạy p2(x) = f(a) + f[a,xi](x - a) + f[a,Xi, b](x - a)(x - X1) I'b p2(x)dx = fb f(a) + f[a,xi](x - a) + f[a,xi, b](x - a)(x - X1)ỜX Dổi biến X ...
18 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 479 | Lượt tải: 0
Bài giảng Phương pháp tính - Nội suy và xấp xỉ hàm - Nguyễn Hồng LộcDặt vần đê Việc xây dựng một đa thức đi qua các điểm nội suy cho trưóc trong trưòng hợp n lớn là rất khó khăn và khó ứng dụng. Một trong những cách khắc phục là trên từng đoạn liên tiếp của các nút nội suy ta xây dựng những đa thức bậc thấp, đa thức đơn giản nhất là bậc l.tuy nhiên khi nối các đa thức bâc 1 lại vói nhau thì đồ thị tông quát lại mấ...
35 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 440 | Lượt tải: 0
Bài giảng Phương pháp tính - Hệ phương trình tuyến tính - Nguyễn Hồng LộcPhương pháp Gauss-Seidel có thế xem là 1 biến dang của phương pháp lặp Jacobi, nhưng khác phương pháp Jacobi ỏ chỗ: khi tính thành phần thứ / của vécto lặp thì ta sử dung ngay những thành phần xjm\ xịm\ ., x)"i vừa tính dược. Ví dụ ( 6xi + 2x2 — 3x3 = 8 2xỵ -I- 7X2 + 3x3 = 9 3xi 4- 2X2 4- 8X3 = 7 Sử dụng phương pháp Gauss-seidel,vói x(°) = (0....
78 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 357 | Lượt tải: 0
Bài giảng Phương pháp tính - Phương trình phi tuyến - Nguyễn Hồng LộcHãy thực hiện bôn lân lặp cho môi hàm g>(x). k = 1, 2, 3. 4 xác định ỏ trên vói cùng giá trị lặp ban đầu Xo = 1 và so sánh kết quả vói nhau. Hàm nào cho chúng ta dãy lặp hội tụ về nghiệm tốt hon? Giải. Vói Xọ = 1 ta có n Xn ểì(xn) g3(*n) giM 1 *1 1.1892 1.2247 1.1547 1.1429 2 X2 1.0801 0.9937 1.1164 1.1245 3 *3 1.1497 1.2286 1.1261 1.1241 4 X4 1.10...
79 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 436 | Lượt tải: 0
