Toán Rời Rạc(Chương III: Bài Toán Đếm) - Nguyễn Huy Long

Đăng nhập / Đăng ký

• ViOLET.VN
• Bài giảng
• Giáo án
• Đề thi & Kiểm tra
• Tư liệu
• E-Learning
• Kỹ năng CNTT
• Trợ giúp

Thư mục

Các ý kiến mới nhất

xcv...

sao file không có dung lượng...

Đánh giá cuối học kì I - Tiếng Việt 5...

Ôn tập cuối học kì I (Tiết 5) - Tiếng...

Ôn tập cuối học kì I (Tiết 3) - Tiếng...

Ôn tập cuối học kì I (Tiết 2) - Tiếng...

Ôn tập cuối học kì I (Tiết 1) - Tiếng...

ÔN TẬP  SỐ THẬP PHÂN...

KNTT-ÔN TẬP CÁC PHÉP TÍNH SỐ THẬP PHÂN-TIẾT 4...

KNTT-ÔN TẬP CÁC PHÉP TÍNH SỐ THẬP PHÂN-TIẾT 2...

KNTT-ÔN TẬP CÁC PHÉP TÍNH SỐ THẬP PHÂN-TIẾT 1...

BAI 50 EM LÀM ĐƯỢC NHỮNG GÌ...

CHU VI HÌNH TRÒN...

Sao tôi tải bài mà không được?...

Thành viên trực tuyến

29 khách và 3 thành viên

buithi duyen

Trần minh kết

Nguyễn Hoài Vũ

Tìm kiếm theo tiêu đề

Đăng nhập

Tên truy nhập Mật khẩu Ghi nhớ   Quên mật khẩu ĐK thành viên

Quảng cáo

Tin tức cộng đồng

5 điều đơn giản cha mẹ nên làm mỗi ngày để con hạnh phúc hơn

Tìm kiếm hạnh phúc là một nhu cầu lớn và xuất hiện xuyên suốt cuộc đời mỗi con người. Tác giả người Mỹ Stephanie Harrison đã dành ra hơn 10 năm để nghiên cứu về cảm nhận hạnh phúc, bà đã hệ thống các kiến thức ấy trong cuốn New Happy. Bà Harrison khẳng định có những thói quen đơn...

Hà Nội công bố cấu trúc định dạng đề minh họa 7 môn thi lớp 10 năm 2025

23 triệu học sinh cả nước chính thức bước vào năm học đặc biệt

Xem tiếp

Tin tức thư viện

Chức năng Dừng xem quảng cáo trên violet.vn

Kính chào các thầy, cô! Hiện tại, kinh phí duy trì hệ thống dựa chủ yếu vào việc đặt quảng cáo trên hệ thống. Tuy nhiên, đôi khi có gây một số trở ngại đối với thầy, cô khi truy cập. Vì vậy, để thuận tiện trong việc sử dụng thư viện hệ thống đã cung cấp chức năng...

Khắc phục hiện tượng không xuất hiện menu Bộ công cụ Violet trên PowerPoint và Word

Thử nghiệm Hệ thống Kiểm tra Trực tuyến ViOLET Giai đoạn 1

Xem tiếp

Hướng dẫn sử dụng thư viện

Xác thực Thông tin thành viên trên violet.vn

Sau khi đã đăng ký thành công và trở thành thành viên của Thư viện trực tuyến, nếu bạn muốn tạo trang riêng cho Trường, Phòng Giáo dục, Sở Giáo dục, cho cá nhân mình hay bạn muốn soạn thảo bài giảng điện tử trực tuyến bằng công cụ soạn thảo bài giảng ViOLET, bạn...

Bài 4: Quản lí ngân hàng câu hỏi và sinh đề có điều kiện

Bài 3: Tạo đề thi trắc nghiệm trực tuyến dạng chọn một đáp án đúng

Bài 2: Tạo cây thư mục chứa câu hỏi trắc nghiệm đồng bộ với danh mục SGK

Bài 1: Hướng dẫn tạo đề thi trắc nghiệm trực tuyến

Lấy lại Mật khẩu trên violet.vn

Kích hoạt tài khoản (Xác nhận thông tin liên hệ) trên violet.vn

Đăng ký Thành viên trên Thư viện ViOLET

Tạo website Thư viện Giáo dục trên violet.vn

Hỗ trợ trực tuyến trên violet.vn bằng Phần mềm điều khiển máy tính từ xa TeamViewer

Xem tiếp

Hỗ trợ kĩ thuật

• (024) 62 930 536
• 0919 124 899
• hotro@violet.vn

Liên hệ quảng cáo

• (024) 66 745 632
• 096 181 2005
• contact@bachkim.vn

Tìm kiếm Bài giảng

Đưa bài giảng lên Gốc > THCS (Chương trình cũ) > Toán >

• Toán Rời Rạc(Chương III: Bài Toán Đếm)
• Cùng tác giả
• Lịch sử tải về

Toán Rời Rạc(Chương III: Bài Toán Đếm)

• 
• 
• 
• 
• 
• 
• 0 / 0
• 

Nhấn vào đây để tải về Báo tài liệu có sai sót Nhắn tin cho tác giả (Tài liệu chưa được thẩm định) Nguồn: Nguyễn Tất Thành Người gửi: Nguyễn Huy Long Ngày gửi: 19h:58' 01-09-2013 Dung lượng: 1.5 MB Số lượt tải: 332 Số lượt thích: 0 người BÀI TOÁN ĐẾMCHƯƠNG 3Nội dungGiới thiệu bài toán đếm.Các nguyên lý đếm cơ bản.Nguyên lý bù trừ.Nguyên lý Dirichlet.Hoán vị.Chỉnh hợp.Tổ hợp.1. Giới thiệu bài toán đếmViệc đếm các đối tượng có những tính chất nào đó là một bài toán quan trọng trong Toán Rời Rạc.Giải quyết tốt bài toán đếm giúp ta giải nhiều bài toán khác nhau trong đánh giá độ phức tạp tính toán của các thuật toán và tìm xác suất rời rạc của các biến cố.1. Giới thiệu bài toán đếmPhương pháp chung để giải bài toán đếm được dựa trên các nguyên lý đếm cơ bản (nguyên lý cộng, nguyên lý nhân).Một số bài toán đếm phức tạp hơn được giải bằng cách qui về các bài toán con để sử dụng được các nguyên lý đếm cơ bản.Vấn đề ta quan tâm là sự phân bố của các phần tử vào một tập hợp hữu hạn.2. Các nguyên lý đếm cơ bảnNguyên lý cộngNguyên lý nhân2.1. Nguyên lý cộngGiả sử để làm công việc A có 2 phương pháp hoàn toàn độc lập nhau: - Phương pháp thứ nhất có n cách làm - Phương pháp thứ hai có m cách làmKhi đó số cách làm công việc A là n + m2.1. Nguyên lý cộngVí dụ 1: Xét việc chọn nhân sự đi dự họp:Giả sử cần chọn hoặc một cán bộ hoặc một SV tham gia buổi họp. Hỏi có bao nhiêu cách chọn nhân sự nếu có 37 cán bộ và 63 SV ?Giải:Gọi cách chọn thứ nhất là chọn một cán bộ từ tập cán bộ  ta có 37 cách. Gọi cách chọn thứ hai là chọn một SV từ tập SV  ta có 63 cách. Vì tập cán bộ và tập SV là rời nhau nên theo nguyên lý cộng, ta có số cách chọn nhân sự là 37 + 63 = 100 cách2.1. Nguyên lý cộngVí dụ 2: Xét quá trình chọn bài thực hành:Một sinh viên có thể chọn bài thực hành từ 1 trong 3 danh sách có số bài tương ứng là: 23, 15 và 19 bài. Vì 3 danh sách này rời nhau nên theo nguyên lý cộng, sinh viên có tổng cộng 23+15+19=57 cách chọn bài thực hành.Ví dụ 3: An có 3 áo tay dài và 5 áo tay ngắn. Để chọn 1 cái áo thì An có mấy cách ?2.2. Nguyên lý nhânGiả sử để làm công việc A cần thực hiện 2 bước:- Bước 1 có n cách làm- Bước 2 có m cách làmKhi đó số cách làm công việc A là n x m2.2. Nguyên lý nhânVí dụ 1: Cho sơ đồ đường đi sau:Từ A đến B có 3 đường điTừ B đến C có 2 đường điVậy từ A đến C có bao nhiêu đường đi ?Có 3x2 = 6 con đường đi từ A đến C2.2. Nguyên lý nhânVí dụ 2: Người ta ghi nhãn cho những chiếc ghế trong một giảng đường bằng một chữ cái (trong 26 chữ cái) và một số nguyên dương không vượt quá 100. Có nhiều nhất bao nhiêu chiếc ghế có thể được ghi nhãn khác nhau?Quy tắc nhân chỉ ra rằng có 26x100=2600 cách khác nhau để gán nhãn cho một chiếc ghế. Như vậy nhiều nhất ta có thể gán nhãn cho 2600 chiếc ghế.2.2. Nguyên lý nhânVí dụ 3: Có bao nhiêu xâu nhị phân có độ dài n ?Mỗi 1 bit trong n bit của xâu nhị phân có thể chọn bằng hai cách: hoặc bằng 0 hoặc bằng 1. Bởi vậy theo quy tắc nhân có tổng cộng 2n xâu nhị phân khác nhau có độ dài bằng n2.2. Nguyên lý nhânVí dụ 4: Giá trị của biến k bằng bao nhiêu sau khi chương trình sau được thực hiện?k := 0for i := 1 to n for j := 1 to m for e := 1 to p k := k+1Kết quả: k = n x m x p3. Nguyên lý bù trừTrong một số bài toán đếm phức tạp hơn, các giải pháp tiến hành thường không độc lập nhau, nghĩa là có thể có vài cách làm áp dụng được cho các giải pháp.Khi đó, ta áp dụng nguyên lý bù trừ.3. Nguyên lý bù trừNguyên lý bù trừ: Cho A và B là hai tập hữu hạn. Khi đó: |A∪B| = |A| + |B| – |A∩B|ABA∩B3. Nguyên lý bù trừVí dụ 1: Lớp có 25 SV giỏi tin học, 13 SV giỏi toán và 8 SV giỏi cả toán và tin học. Hỏi lớp có bao nhiêu SV ? Giải:Gọi A tập là tập các SV giỏi Tin học, B là tập các SV giỏi toán. Khi đó A∩B là tập SV giỏi cả toán và tin học. Do vậy ta có: |A∪B| = |A| + |B| – |A∩B|Hay Số SV của lớp = 25 + 13 – 8 = 303. Nguyên lý bù trừVí dụ 2. Có bao nhiêu số nguyên