intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Toán rời rạc: Bài 5 - TS. Nguyễn Văn Hiệu

Chia sẻ: Le Xuan Manh | Ngày: | Loại File: PDF | Số trang:61

Thêm vào BST
Báo xấu
115
lượt xem 11
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giới thiệu bài toán liệt kê, phương pháp sinh, phương pháp quay lui là những nội dung chính được trình bày trong bài 5 "Bài toán liệt kê" thuộc bài giảng Toán rời rạc. Đây là tài liệu tham khảo hữu ích cho các bạn chuyên ngành Toán học.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Bài 5 - TS. Nguyễn Văn Hiệu

  1. BÀI 5 BÀI TOÁN LIỆT KÊ Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
  2. 5.1. Giới thiệu Nội dung  5.1. Giới thiệu  5.2. Phương pháp sinh  5.3. Phương pháp quay lui Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2
  3. 5.1. Giới thiệu Mục đích  Đưa ra danh sách tất cả các cấu hình có thể có Bản chất  Xác định một thuật toán để theo đó có thể lần lượt xây dựng được tất cả các cấu hình đang quan tâm. Nguyễn Văn Hiệu, 2012, Discrete Mathematics 3
  4. 5.1. Giới thiệu Nguyên tắc  Không được lặp lại một cấu hình  Không được bỏ sót một cấu hình Lưu ý  Chỉ giải với bài toán chưa có phương pháp giải  Phương pháp Sinh  Phương pháp quay lui Nguyễn Văn Hiệu, 2012, Discrete Mathematics 4
  5. 5.2. Phương pháp sinh Thường sử dụng  Giải bài toán liệt kê tổ hợp Điều kiện  Xác định được một thứ tự.  Có cấu hình đầu tiên  Có cấu hình cuối cùng  Xác định được thuật toán để xây dựng cấu hình kế tiếp Nguyễn Văn Hiệu, 2012, Discrete Mathematics 5
  6. 5.2. Phương pháp sinh Bản chất Chú thích Generating_method(…) {  Stop = =1, là cấu hình ; cuối cùng stop = islastconfigure(…);  Stop == 0, chưa phải while (stop==0) { là cấu hình cuối cùng ; }  là } thuật toán sinh cấu hình tiếp theo trên thứ tự đã xác định trước Nguyễn Văn Hiệu, 2012, Discrete Mathematics 6
  7. 5.2. Phương pháp sinh Ví dụ  Liệt kê dãy nhị phân có độ dài n.  Liệt kê các tập con k phần tử của tập n phần tử.  Liệt kê các hoán vị của tập n phần tử Nguyễn Văn Hiệu, 2012, Discrete Mathematics 7
  8. 5.2. Phương pháp sinh Ví dụ 1: Liệt kê các dãy nhị phân có độ dài n Bước 1: Xác định thứ tự Dãy nhị phân được biểu diễn: b = (b1 b2 … bn ) thỏa mản bi €{0,1}  Định nghĩa thứ tự từ điển: b = (b1 b2 ... bn) và *b = (*b1 *b2 ... *bn) thứ tự b < *b, nếu q(b) < q(*b) Nguyễn Văn Hiệu, 2012, Discrete Mathematics 8
  9. 5.2. Phương pháp sinh Ví dụ 1: Liệt kê các dãy nhị phân có độ dài n Bước 2: Cấu hình đầu và cuối  Khi n = 4 phần tử, có 24 dãy nhị phân được liệt kê Nguyễn Văn Hiệu, 2012, Discrete Mathematics 9
  10. 5.2. Phương pháp sinh Ví dụ 1: Liệt kê các dãy nhị phân có độ dài n Bước 2: b q(b) b q(b) 0000 0 1000 8 0001 1 1001 9 0010 2 1010 10 0011 3 1011 11 0100 4 1100 12 0101 5 1101 13 0110 6 1110 14 0111 7 1111 15 Nguyễn Văn Hiệu, 2012, Discrete Mathematics 10
  11. 5.2. Phương pháp sinh Bước 3: xác định thuật Thuật toán toán  Tìm i từ bên phải: 0000 0001 bi = 0.  Gán lại bi = 1 và 0001 0010 bj = 0 với mọi j> i. 0011 0100 i= n; 0111 1000 while (i>=1 && b[i]==‘1’) b[i--] = ‘0’; b[i] = ‘1’; Nguyễn Văn Hiệu, 2012, Discrete Mathematics 11
  12. 5.2. Phương pháp sinh Nguyễn Văn Hiệu, 2012, Discrete Mathematics 12
  13. 5.2. Phương pháp sinh Nguyễn Văn Hiệu, 2012, Discrete Mathematics 13
  14. 5.2. Phương pháp sinh Ví dụ 1: Liệt kê các dãy nhị phân có độ dài n Kết quả Chương trình Result Source Code Nguyễn Văn Hiệu, 2012, Discrete Mathematics 14
  15. 5.2. Phương pháp sinh Ví dụ 2 Liệt kê các tập con k phần tử của tập n phần tử Chuẩn bị  Ánh xạ tập n phần tử vào tập X = {1,2,…,n}  Mỗi tập con k phần tử của X được biểu diễn bởi bộ có thứ tự gồm k thành phần: a = (a1 a2 a3 ..... ak ) thỏa mản 1≤ a1< a2 < a3
  16. 5.2. Phương pháp sinh Ví dụ 2 Liệt kê các tập con k phần tử của tập n phần tử Bước 1: Xác định thứ tự  Định nghĩa thứ tự từ điển: a = (a1 a2 a3 ...ak) và b = (b1 b2 b3 ... bk) thứ tự a < b, nếu tồn tại j (1≤ j≤ k): a1 = b1,...,aj-1= bj-1, aj < bj Nguyễn Văn Hiệu, 2012, Discrete Mathematics 16
  17. 5.2. Phương pháp sinh Ví dụ 2: Liệt kê các tập con k phần tử của tập n phần tử Bước 2: { 1,2,3 } Cấu hình đầu { 1,2,4 } { 1,2,5 }  Các tập con 3 phần tử { 1,3,4 } Cách sinh của tập 5 phần tử { 1,3,5 } {1,2,3,4,5} { 1,4,5 }  𝑪𝟑 5 = 10 { 2,3,4 } { 2,3,5 } { 2,4,5 } { 3,4,5 } Cấu hình cuối Nguyễn Văn Hiệu, 2012, Discrete Mathematics 17
  18. 5.2. Phương pháp sinh Bước 3: xác định Thuật toán thuật toán n=5, k=3  Giả sử a = (a1...ak ) không là cuối cùng. i= 1 2 3  B1: Tìm vị trí i đầu tiên từ a = {1, 4, 5 } n-k+i = 3 4 5 bên phải của dãy: ai ≠ n-k+i.  B2: Thay ai bởi ai + 1.  B3: Thay aj bởi ai - i +j, { 2, , } { 2, 3, 4} với j = i+1,...,k Nguyễn Văn Hiệu, 2012, Discrete Mathematics 18
  19. 5.2. Phương pháp sinh Thuật toán Code  Giả sử a = (a1...ak ) không là cuối cùng. B1:  B1: Tìm vị trí i đầu tiên từ i=k; bên phải của dãy: while (a[i]==n-k+i) i-- ; ai ≠ n-k+i. B2:  B2: Thay ai bởi ai + 1. a[i]= a[i] + 1;  B3: Thay aj bởi ai - i +j, B3: với j = i+1,...,k for (j=i+1;j
  20. 5.2. Phương pháp sinh Nguyễn Văn Hiệu, 2012, Discrete Mathematics 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2