TAILIEUCHUNG - Bài giảng Phân tích và thiết kế thuật toán: Bài 5 - Hà Đại Dương

"Bài giảng Phân tích và thiết kế thuật toán - Bài 5: Chia để trị" thông qua bài học này người học nắm chắc kiến thức về lược đồ chung và bài toán áp dụng của chia để trị; nhân số nguyên (lớn), nhân ma trận, dãy con lớn nhất, tính lũy thừa, hoán đổi phần tử của mảng. | 2 2 2017 Phân tích và Thiết kế THUẬT TOÁN Hà Đại Dương duonghd@ Web duonghd Bài 5 - Chia để trị tiếp PHÂN TÍCH VÀ THIẾT KẾ THUẬ TOÁN NỘI DUNG I. Giới thiệu II. Lược đồ chung III. Bài toán áp dụng IV. Bài tập 1 2 2 2017 III. Bài toán áp dụng 5. Nhân số nguyên lớn Bài toán Nhân 2 số nguyên lớn x y có n chữ số x x n 1 x n 2 .x1 x0 y y n 1 y n 2 . y1 y 0 z x y z 2 n 1 z 2 n 2 .z1 z 0 Quá quen Đến mức không cần phải thắc mắc về tính tối ưu của nó Cách thức vẫn làm quá quen Độ phức tạp O n2 III. Bài toán áp dụng 5. Nhân số nguyên lớn Ý tưởng Chia để trị Đặt a x n 1 x n 2 .x n 2 b x n 2 1 x n 2 2 .x 0 c y n 1 y n 2 . y n 2 d y n 2 1 y n 2 2 . y 0 Khi đó x a 10 n 2 b y c 10 n 2 d Và z x y a 10n 2 b c 10n 2 d a c 10n a d b c 10n 2 b d III. Bài toán áp dụng 5. Nhân số nguyên lớn Ý tưởng Chia để trị x y có độ dài bằng nhau và độ dài có dạng 2m nếu Có 1 chữ số làm trực tiếp Có n chữ số Tích của nó có thể biểu diễn qua tích của 4 số nguyên có độ dài n 2 chữ số z a c 10n a d b c 10n 2 b d và các phép cộng dịch phải 2 2 2 2017 III. Bài toán áp dụng 5. Nhân số nguyên lớn Ý tưởng Chia để trị z a c 10n a d b c 10n 2 b d Gọi T n là thời gian thực hiện phép nhân 2 số nguyên có độ dài n thì T n 4T n 2 O n O n là thời gian thực hiện các phép cộng và dịch phải Giải công thức truy hồi trên ta được T n O n 2 Chưa nhanh hơn nếu không chia để trị III. Bài toán áp dụng 5. Nhân số nguyên lớn Ý tưởng Năm 1962 nhà toán học người Nga Anatoly Alexeevitch Karatsuba Karatsuba đã tối ưu thời gian thực hiện phép nhận 2 số nguyên có n chữ số như sau Khi đó T n 3T n 2 O n Giải phương trình đệ qui ta được T n O nlog23 O III. Bài toán áp dụng Karatsuba x y n 5. Nhân số nguyên lớn Thuật toán Karatsuba If n 1 Return x y Else a x n-1 . . . x n 2 b x n 2-1 . . . x 0 c y n-1 . . . y n 2 d y n 2-1 . . . y 0 U Karatsuba a c n 2 V Karasuba b d n 2 W Karatsuba a b c d n 2 Return U 10n W-U-V 10n 2 V 3 2 2 2017 III. Bài toán áp dụng 6. Nhân ma trận III. Bài toán áp dụng 6. Nhân ma .

• Kỹ thuật lập trình
• Phân tích và thiết kế thuật toán
• Chia để trị
• Nhân số nguyên
• Nhân ma trận
• Dãy con lớn nhất
• Hoán đổi phần tử của mảng
• Phân tích thiết kế thuật toán
• Đề thi Phân tích thiết kế thuật toán
• Câu hỏi Phân tích thiết kế thuật toán
• Ôn tập Phân tích thiết kế thuật toán
• Thuật toán tham lam
• Trình diễn thuật toán
• Phân tích thiết kế giải thuật
• Thiết kế thuật toán
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Bài giảng Phân tích và thiết kế thuật toán
• Phân tích thuật toán
• Phân tích Top down
• Đánh giá thuật toán
• Bài giảng đánh giá thuật toán
• Bài giảng thiết kế thuật toán
• Phân tích đệ quy
• Thuật toán đệ quy
• Phân tích toán học
• Bài toán sắp xếp
• Sắp xếp chèn
• Bài giảng Phân tích thuật toán
• Tính chất cơ bản của thuật toán
• Độ phức tạp của thuật toán
• Ước lượng tiệm cận
• Ngôn ngữ lập trình
• Tự học lập trình
• Lập trình máy tính
• Tìm kiếm tuần tự
• Xem xét phân bố khóa
• Tìm kiếm nhị phân
• Kỹ thuật Greedy
• Bài toán tối ưu tổ hợp
• Bài toán trả tiền của ATM
• Phương pháp khử đệ quy
• Phương trình đệ quy
• Thuật toán hoán vị
• Số nghịch thế
• Bảng nghịch thế
• Đánh giá bằng công cụ toán học
• Công cụ toán học sơ cấp
• Đánh giá bằng thực nghiệm
• Quy hoạch động
• Bài toán quy hoạch động
• Bài toán con
• Phương pháp giải bài toán trên máy tính
• Phương pháp trực tiếp
• Phương pháp gián tiếp
• Tìm kiếm cục bộ
• Bài toán cây phủ tối thiểu
• Bài toán người giao hàng
• Chuỗi lũy thừa
• Dùng hàm sinh giải hệ thức truy hồi
• Hàm sinh của dãy xác suất
• Bài toán cơ sở
• Nhân số nguyên lớn
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Thiết kế giải thuật
• Định nghĩa B Tree
• Các phép toán trên B Tree
• Giải thuật nâng cao
• Kỹ thuật phân tích giải thuật
• Kỹ thuật thiết kế giải thuật
• Hệ thống thông tin
• Công nghệ thông tin
• Độ phức tạp thuật toán
• Phương pháp tham lam
• Phương pháp chia để trị
• Thuật toán đồ thị cơ bản
• Bài giảng Phân tích thuật toán Phần 1
• Khái niệm thuật toán
• Cấu trúc dữ liệu
• Sắp xếp dữ liệu
• Đề thi học kỳ
• Lược đồ giản thuật
• Ý tưởng chia để trị
• Bài toán tìm kiếm nhị phân
• Bài toán tô màu đồ thị
• Biểu diễn đồ thị
• Tổng quan đồ thị
• Bài toán đồ thị
• Bài giảng Phân tích thuật toán Phần 2
• Chiến lược vét cạn
• Chiến lược chia để trị