Lập trình và Giải thuật

Tài liệu có kết cấu gồm 4 phần, bao gồm: Bài toán liệt kê, cấu trúc dữ liệu và giải thuật, quy hoạch động, các thuật toán trên đồ thị. Tài liệu là tài liệu học tập cho sinh viên ngành Toán - Tin đồng thời là tài liệu tham khảo hữu ích cho các ngành liên quan. Tham khảo nội dung tài liệu để bổ sung các kiến thức cần thiết cho bản thân.
Nội dung trích xuất từ tài liệu:
Lập trình và Giải thuậtLÊ MINH HOÀNG Bài giảng chuyên đề Đại học Sư phạm Hà Nội, 1999-2002 Lời cảm ơnTôi muốn bày tỏ lòng biết ơn đối với những người thầy đã chỉ dạy tận tình trong những năm thángđầy khó khăn khi tôi mới bước vào học tin học và lập trình. Sự hiểu biết và lòng nhiệt tình của cácthầy không những đã cung cấp cho tôi những kiến thức quý báu mà còn là tấm gương sáng cho tôinoi theo khi tôi đứng trên bục giảng cũng với tư cách là một người thầy.Cuốn tài liệu này được viết dựa trên những tài liệu thu thập được từ nhiều nguồn khác nhau, bởicông sức của nhiều thế hệ thầy trò đã từng giảng dạy và học tập tại Khối Phổ thông chuyên Toán-Tin, Đại học Sư phạm Hà Nội, còn tôi chỉ là người tổng hợp lại. Qua đây, tôi muốn gửi lời cảm ơntới các đồng nghiệp đã đọc và đóng góp những ý kiến quí báu, cảm ơn các bạn học sinh - nhữngcon người đã trực tiếp làm nên cuốn sách này.Do thời gian hạn hẹp, một số chuyên đề tuy đã có nhưng chưa kịp chỉnh sửa và đưa vào tài liệu.Bạn đọc có thể tham khảo thêm trong phần tra cứu. Rất mong nhận được những lời nhận xét và gópý của các bạn để hoàn thiện cuốn sách này. Tokyo, 28 tháng 4 năm 2003 Lê Minh Hoàng i MỤC LỤCPHẦN 1. BÀI TOÁN LIỆT KÊ ................................................................................. 1 §1. NHẮC LẠI MỘT SỐ KIẾN THỨC ĐẠI SỐ TỔ HỢP......................................................................2 1.1. CHỈNH HỢP LẶP..............................................................................................................................................2 1.2. CHỈNH HỢP KHÔNG LẶP...............................................................................................................................2 1.3. HOÁN VỊ ...........................................................................................................................................................2 1.4. TỔ HỢP..............................................................................................................................................................3 §2. PHƯƠNG PHÁP SINH (GENERATION) ..........................................................................................4 2.1. SINH CÁC DÃY NHỊ PHÂN ĐỘ DÀI N .........................................................................................................5 2.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ............................................................................................................6 2.3. LIỆT KÊ CÁC HOÁN VỊ ..................................................................................................................................8 §3. THUẬT TOÁN QUAY LUI ................................................................................................................12 3.1. LIỆT KÊ CÁC DÃY NHỊ PHÂN ĐỘ DÀI N..................................................................................................12 3.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ..........................................................................................................13 3.3. LIỆT KÊ CÁC CHỈNH HỢP KHÔNG LẶP CHẬP K ....................................................................................15 3.4. BÀI TOÁN PHÂN TÍCH SỐ ...........................................................................................................................16 3.5. BÀI TOÁN XẾP HẬU .....................................................................................................................................18 §4. KỸ THUẬT NHÁNH CẬN.................................................................................................................24 4.1. BÀI TOÁN TỐI ƯU.........................................................................................................................................24 4.2. SỰ BÙNG NỔ TỔ HỢP ..................................................................................................................................24 4.3. MÔ HÌNH KỸ THUẬT NHÁNH CẬN...........................................................................................................24 4.4. BÀI TOÁN NGƯỜI DU LỊCH ........................................................................................................................25 4.5. DÃY ABC ........................................................................................................................ ...