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

LÊ MINH HOÀNG

􀁝􀁝􀁝􀂒􀁞􀁞􀁞

BÀI GIẢNG CHUYÊN ĐỀ: GIẢI THUẬT VÀ LẬP TRÌNH

Bài giảng chuyên đề

Đại học Sư phạm Hà Nội, 1999-2002

Try not to become a man of success

but rather to become a man of value.

Albert Einstein

􀁝 i 􀁞

MỤC LỤC

PHẦ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