Bạn đang xem: Giải toán rời rạc nguyễn đức nghĩa

’"“'+ a y'' (5)Cônc thức (5) còn gọi là klìíỉi triển nhị tlìức Ne'ĩon và các hệ số tổ hợp còn đượcgọi là những lìệ sốnììị ĩììức.Chẳng hạn, căn cứ vào trong dòng cuối của tam giác Pascal form size 8 (đã tính ngơi nghỉ trên), taphện đirợc:ú ' + V)* - / + 8.v"v + 28.r
V + 5 6 . ' + 7().v‘v" + 56,r
V’ -r 28.r"/ + /Tliôngthường, công thức (5) được gặp dướidạng đa thức một ẩn:(x + 1 )" = c l x ” + c l x"-' + ... + c r ' A- + c;: (6)Rất các đẳng thức về hệ số tổ hợp được suy từ bỏ (6). Chảng hạn, trong (6) chọn A' =1 tađược:c : + c ! , + ... + c ;r' + c = 2" ^ (7)tức là dìm được công dụng đã biết (thí dụ 3, mục 1.4,1); số các tập nhỏ của một /?-tậpbằng 2", còn nếu chọn ,v = -1 ta được:cỉ: - c ; , + ...+ (-ir c :: - 0 (8)tức là số các tập con chẵn (có số phần tử là số chán) bằng các số tập bé lẻ cùng bằng
Nhiều đặc điểm của thông số tổ hợp hoàn toàn có thể thu được tự (6) bằng cách lấy đạo hàm hoặctích phan theo A' nhì vế của đẳng thức này một số hữu hạn lần, sau đó gán mang đến .r nhữnggiá trị rứa Ihể. Chẳng hạn, cốne thức dưới đây thu được bằns cách lấy đạo hàm nhị vếth eo với sau đ ó trong đ ẳ n g thức Ihu đư ợc để X - :/72"-' = n c : + ( / 7 - i ) c , : + ... + C ;;-' .Còn công thức dưới đây thu được bằng cách lấy tích phân nhị vế theo X và tiếp nối trongđẳng thức thu được để A' = 1:(« + i)2' - ' = { « + i) c : +

Xem thêm: Cách học giỏi hóa cho người mất gốc, 6 bước để học tốt môn hóa nếu bạn bị mất gốc

Giáo trình Toán rời rộc - Nguyễn Đức Nghĩa, Nguyễn sơn Thành nhằm ra mắt các kỹ năng cơ bạn dạng trong tía lĩnh vực có tương đối nhiều ứng dụng của toán rời rộc rạc là: định hướng tổ hợp, kim chỉ nan đồ thị và hàm đại số logic.

NGUYỄN ĐỨC NGHĨA - NGUYỄN TÔ THÀNH----------GIÁO TRÌNHTOÁN RỜI RẠCNXB ĐẠI HỌC QUỐC GIA HÀ NỘI -2009Lời nói đầu
Toán rời rốc là m ột nghành của toán học phân tích các đối tượng rời rạc. Chúng ta sẽ áp dụng công cố của toán rời rộc rạc khi đề nghị đếm các đối tượng, khi nghiên cứu quan hệ giữa những tập rời rạc, khi phân tích các quy trình hữu hạn. M ột giữa những nguyên nhân hầu hết làm nâng tầm đặc biệt của toán rời rộc là việc cất giữ cùng xử lý thông tin trên m áy tính bản chất là các quy trình rời rạc. Cuốn sách này nhầm trình làng các kiến thức cơ bạn dạng trong ba lĩnh vực có khá nhiều ứng dụng của toán rời rộc là: triết lý tổ hợp, kim chỉ nan đồ thị cùng hàm đại số logic. Ngôn từ cuốn sách được trình diễn thành cha phần. Phần I trình diễn các vấn đề của kim chỉ nan tổ hòa hợp xoay xung quanh 4 việc cơ bản: việc đếm , vấn đề tồn tại, vấn đề liệt kê và vấn đề tối ưu tổ hợp. Nội dung của phần 1 không phần lớn giúp nâng cao tư duy toán, mà còn khiến cho quen với bốn duy thuật toán trong việc giải q u y ết những vấn đề thực tế, đổng thời cũng rèn luyện kỹ thuật lập trình giải các bài toán tổ hợp. Phần II kể đến triết lý đổ thị - một cấu tạo rời rạc tìm kiếm được những ứng dụng rộng rãi trong nhiều nghành nghề của khoa học kỹ thuật với đời sống. Vào phần này sau phần ra mắt các quan niệm cơ bủn, những bài toán ứng dụng quan trọng của triết lý đồ thị như bài toán cây khung nhỏ dại nhất, bài toán đưòìig đi ngán nhất, câu hỏi luồng cực lớn trong m ạng... Và mọi thuật toán để giải quyết và xử lý chúng đã có được trình bày cụ thể cùng với vấn đề phân tích cùng hướng dẫn thiết đặt chươiig trình bên trên m áy tính. Phần III tương quan đến lý thuyết hàm đại số ngắn gọn xúc tích là cơ sở để nắm bắt những vấn để phức hợp của nghệ thuật m áy tính. Sau phần trình bày các quan niệm cơ bản, phần này đi sâu vào việc tối thiểu hoá những hàm đại số lôgic và m ô tả m ột số thuật toán quan trọng để xử lý vấn đề đặt ra như thuật toán Q uine - M c
C mùi hương 1. M làm việc đầu 1.1 M ô hình xử lý thông tin và hàm đại số lôgic 1.2 những hàm đại số lôgic sơ cung cấp 1.3 Biểu diễn những hàm đại số lôgic qua hệ tuyển, hội, lấp định 1.4 biểu diễn tối thiểu của hàm đại số lôgic Chương 2. D ạng tuyển chuẩn chỉnh tắc của hàm đại sò lògic 2.1 những khái niệm cơ phiên bản 2.2 D ạng tuyển chuẩn chỉnh tắc thu gọn 2.3 Dạng tuyển chuẩn tắc nghẽn với dạng tuyển chuẩn chỉnh tắc tối thiểu Chương 3. T huật toán kiếm tìm dạng tuyển chuẩn tác về tối thiểu 3.1 để ý m ở đẩu 3.2 Tim dạng tuyển chuẩn tắc thu gọn 3.3 Tim dạng tuyển chuẩn tắc buổi tối thiểu 3.4 Sơ đồ tối thiểu261263 263 265 266 269 271 271 273277 277 278 282 285Tài liệu tham khảo289VI