lOMoAR cPSD| 27879799 1/10/2011
Phầ n I – Giớ i thiệ u vệ Thuầ t toầ n Ch ươ ng 1.1 KHÁ I NIỆ M CƠ BÁ N 1 lOMoAR cPSD| 27879799 1/10/2011 1.1 Thuầ t toầ n lầ gì ? B i toÆn: sắp xếp ,
• Đầu v o: một dªy gồm n kh a a a1 2,..,an
• Đầu ra: một hoÆn vị c thứ tự của cÆc kh a đầu v o trong đ a '1 a '2 .. a 'n
Trường hợp cụ thể của b i toÆn • {14, 45, 68, 24, 54, 34}
• {Mike, Bob, Sally, Jill, Jan}
• Chœng ta chỉ quan t m đến cÆc thuật toÆn ch nh xÆc v hiệu quả, v dễ c i đặt 1.2.1 Tì nh 1.2.1 Tì nh chì nh chì nh xầ c xầ c
• Thuật toÆn 3. Duyệt to n bộ:
• Thu ậ t toÆn 1 . Ch ọ n b ộ phim s ớ m nh ấ t trong L m khng trøng
duyệt 2n tập con của n bộ phim
v ớ i cÆc b ộ phim đ ª ch ọ n tr ướ c đ . L ặ p l ạ i cho đế n khi khng
trong L. Chọn ra tập con n o c số th ể ch ọ n thŒm.
lượng phần tử lớn nhất.
Đảm bảo thu được kết quả tối ưu
Thuật toÆn chạy rất chậm, vd n =20 th số tập con l 220
• Thu ậ t toÆn 2 . Ch ọ n b ộ phim c th ờ i gian chi ế u ng ắ n nh ấ t
trong L m khng trøng v ớ i cÆc b ộ phim đ ª ch ọ n tr ướ c. L ặ p l ạ i
• Thuật toÆn 4. Thuật toÆn tối
cho đế n khi khng ch ọ n thŒm đượ c.
ưu: sắp xếp cÆc lịch chiếu phim
theo thứ tự kh ng giảm thời gian
kết thœc. Lần lượt xem xØt cÆc
phim trong danh sÆch đª sắp
xếp, bổ sung v o danh sÆch xem
bộ phim đang xØt nếu n kh ng CuuDuongThanCong.com 2 lOMoAR cPSD| 27879799 1/10/2011
chồng lŒn cÆc bộ phim đª c trong danh sÆch xem.
• C những b i toÆn m kh ng tồn
tại thuật toÆn ch nh xÆc để giải! 1.2.1 Tì nh chì nh xầ c
• Ph n biệt giữa thuật toÆn ch nh xÆc v kh ng ch nh xÆc: đưa ra một v dụ thuật toÆn m thuật toÆn cho kết quả sai (phản v dụ).
• Chứng minh t nh đœng đắn của thuật toÆn: kh khăn hơn nhiều.
• B i tập. T m cÆc phản v dụ cho cÆc thuật toÆn giải b i toÆn h nh tr nh du lịch tối ưu. 3 lOMoAR cPSD| 27879799 1/10/2011 CuuDuongThanCong.com 4 lOMoAR cPSD| 27879799 1/10/2011 Cho n đo vầ t tro ng lướ ng nho trướ c
• Sắp xếp cÆc đồ vật theo thứ tự tăng trọng lượng • Lần lượt
xØt cÆc đồ vật theo thứ tự n y, chọn đồ
vật đang xØt v o tœi nếu n vẫn c thể chứa thŒm 5 lOMoAR cPSD| 27879799 1/10/2011 1.4 Biệ u diệ n thuầ t toầ n
• Cần biểu diễn cÆc bước thực hiện tuần tự của thuật toÆn một cÆch cụ thể. • Biểu diễn bằng: • Ng n ngữ tự nhiŒn • Giả ng n ngữ (pseudocode) • Lưu đồ • )
Ng n ngữ lập tr nh cụ thể (C/C++, java, CuuDuongThanCong.com 6 lOMoAR cPSD| 27879799 1/10/2011 7