Chuyên đề Toán cao cấp

Cuốn giáo trình Toán cao cấp (Phần I: Đại số tuyến tính; Phần II: Giải tích) nhằm phục vụ cho sinh viên khối kinh tế học và nghiên cứu các phương pháp toán ứng dụng trong kinh tế. Kiến thức toán cao cấp đã trở thành một phần kiến thức không thể thiếu được để sinh viên có thể hiểu được các tài liệu kinh tế hiện nay. Để nắm được những kiến thức cơ bản của toán học và biết vận dụng những phương pháp cơ bản của toán vào nghiên cứu kinh tế đòi hỏi sự nỗ lực...
Nội dung trích xuất từ tài liệu:
Chuyên đề Toán cao cấp Bài toán liệt kê 1 MỤC LỤC §0. GIỚI THIỆU...................................................................................................................................... 2 §1. NHẮC LẠI MỘT SỐ KIẾN THỨC ĐẠI SỐ TỔ HỢP....................................................................... 3 I. CHỈNH HỢP LẶP ...........................................................................................................................................3 II. CHỈNH HỢP KHÔNG LẶP...........................................................................................................................3 III. HOÁN VỊ ......................................................................................................................................................3 IV. TỔ HỢP.........................................................................................................................................................3 §2. PHƯƠNG PHÁP SINH (GENERATE) ............................................................................................ 5 I. SINH CÁC DÃY NHỊ PHÂN ĐỘ DÀI N.......................................................................................................6 II. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ........................................................................................................7 III. LIỆT KÊ CÁC HOÁN VỊ .............................................................................................................................9 §3. THUẬT TOÁN QUAY LUI ............................................................................................................. 12 I. LIỆT KÊ CÁC DÃY NHỊ PHÂN ĐỘ DÀI N...............................................................................................13 II. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ......................................................................................................14 III. LIỆT KÊ CÁC CHỈNH HỢP KHÔNG LẶP CHẬP K ..............................................................................15 IV. BÀI TOÁN PHÂN TÍCH SỐ .....................................................................................................................16 V. BÀI TOÁN XẾP HẬU.................................................................................................................................18 §4. KỸ THUẬT NHÁNH CẬN.............................................................................................................. 22 I. BÀI TOÁN TỐI ƯU ......................................................................................................................................22 II. SỰ BÙNG NỔ TỔ HỢP...............................................................................................................................22 III. MÔ HÌNH KỸ THUẬT NHÁNH CẬN .....................................................................................................22 IV. BÀI TOÁN NGƯỜI DU LỊCH...................................................................................................................23 V. DÃY ABC ....................................................................................................................................................25 Lê Minh Hoàng Bài toán liệt kê 2 §0. GIỚI THIỆU Trong thực tế, có một số bài toán yêu cầu chỉ rõ: trong một tập các đối tượng cho trước có bao nhiêu đối tượng thoả mãn những điều kiện nhất định. Bài toán đó gọi là bài toán đếm cấu hình tổ h ợp . Trong lớp các bài toán đếm, có những bài toán còn yêu cầu chỉ rõ những cấu hình tìm được thoả mãn điều kiện đã cho là những cấu hình nào. Bài toán yêu cầu đưa ra danh sách các cấu hình có thể có gọi là bài toán liệt kê tổ hợp. Để giải bài toán liệt kê, cần phải xác định được một thuật toán để có thể theo đó lần lượt xây dựng được tất cả các cấu hình đang quan tâm. Có nhiều phương pháp liệt kê, nhưng chúng cần phải đáp ứng được hai yêu cầu dưới đây: • 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 Có thể nói rằng, phương pháp liệt kê là phương kế cuối cùng để giải được một số bài toán tổ hợp hiện nay. Khó khăn chính của phương pháp này chính là sự bùng nổ tổ hợp. Để xây dựng 1 tỷ cấu hình (con số này không phải là lớn đối với các bài toán tổ hợp - Ví dụ liệt kê các cách xếp n≥13 người quanh một bàn tròn) và giả thiết rằng mỗi thao tác xây dựng mất khoảng 1 giây, ta phải mất quãng 31 năm mới giải xong. Tuy nhiên cùng với sự phát triển của máy tính điện tử, bằng phương pháp liệt kê, nhiều bài toán tổ hợp đã tìm thấy lời giải. Qua đó, ta cũng nên biết rằng chỉ nên dùng phương ph ...