TAILIEUCHUNG - Bài giảng Phân tích và thiết kế giải thuật: Chương 3 - PGS.TS. Dương Tuấn Anh

Chương 3 giới thiệu về chiến lược giảm để trị trong phân tích và thiết kế giải thuật. Các nội dung chính trong chương này gồm có: Chiến lược giảm để trị, sắp thứ tự bằng phương pháp chèn, các giải thuật duyệt đồ thị, sắp xếp tôpô, giải thuật sinh các hoán vị từ một tập. | Chương 3 Chiến lược giảm-để-trị (Decrease-and-conquer) Nội dung Chiến lược giảm-để-trị Sắp thứ tự bằng phương pháp chèn Các giải thuật duyệt đồ thị Sắp xếp tôpô Giải thuật sinh các hoán vị từ một tập 1. Chiến lược thiết kế giải thuật giảm-để-trị (Decrease-and-conquer) Kỹ thuật thiết kế giải thuật giảm-để-trị lợi dụng mối liên hệ giữa lời giải cho một thể hiện của một bài toán và lời giải cho một thể hiện nhỏ hơn của cùng một bài toán. Có ba biến thể của chiến lược này. Giảm bởi một hằng số (decrease by a constant) Giảm bởi một hệ số (decrease by a factor) Giảm kích thước của biến (variable size decrease) Sắp thứ tự bằng phương pháp chèn (insertion sort) là một thí dụ điển hình của chiến lược giảm-để-trị. Chiến lược thiết kế giải thuật giảm-để-trị (tt.) Giải thuật tìm ước số chung lớn nhất của 2 số theo công thức gcd(m,n) = gcd(n, m mod n) cũng là thí dụ của chiến lược giảm-để-trị theo lối giảm kích thước của biến. Algorithm Euclid(m,n) /* m,n : two nonnegative integers m and n */ while n0 do r := m mod n; m:= n; n:= r endwhile return m; Thí dụ: m = 60 và n = 24 m = 60 và n = 24 m = 24 và n = 12 m = 12 và n = 0 Vậy 12 là ước số chung lớn nhất Chiến lược thiết kế giải thuật giảm-để-trị (tt.) Tại mỗi bước của giải thuật duyệt đồ thị theo chiều sâu trước (DFS) hay duyệt theo bề rộng trước (BFS), giải thuật đánh dấu đỉnh đã được viếng và tiến sang xét các đỉnh kế cận của đỉnh đó. Hai giải thuật duyệt đồ thị này đã áp dụng kỹ thuật giảm-bớt-một (decrease-by-one), một trong 3 dạng chính của chiến lược Giảm-để-trị. 2. Sắp thứ tự bằng phương pháp chèn Ý tưởng : Xét một ứng dụng của kỹ thuật “giảm để trị” vào việc sắp thứ tự một mảng a[0n-1]. Theo tinh thần của kỹ thuật, ta giả sử rằng bài toán nhỏ hơn: sắp thứ tự một mảng a[0n-2] đã được thực hiện. Vấn đề là phải chèn phần tử a[n-1] vào mảng con đã có thứ tự a[0n-2]. Có hai cách để thực hiện điều này. - Một là ta duyệt mảng con đã có thứ tự từ trái sang phải cho đến khi tìm thấy phần tử đầu tiên lớn

• Kỹ thuật lập trình
• Thiết kế giải thuật
• Phân tích giải thuật
• Chiến lược giảm để trị
• Phương pháp chèn
• Giải thuật duyệt đồ thị
• Sắp xếp tôpô
• Phân tích thiết kế giải thuật
• Kỹ thuật thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ thuật phân tích thiết kế giải thuật
• Bài giảng phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Cắt tỉa Alpha Beta
• Phương pháp thiết kế thuật giải
• Thuật toán chính xác
• Thuật toán gần đúng
• Bước thiết kế một thuật giải
• Giải thuật quay lui
• Giải thuật tham lam
• Quy hoạch động
• Phân tích thiết kế thuật toán
• Phân tích thuật toán
• Thiết kế thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Giải thuật xấp xỉ
• Bài toán che phủ đỉnh
• Bài toán NP đầy đủ
• Phân tích thiết kế giải thuật chương 37
• Phân tích thuật giải
• Thiết kế thuật giải
• Chiến lược thiết kế thuật giải
• Biểu diễn thuật giải
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Chia để trị
• Tiêu chuẩn đánh giá giải thuật
• Phương pháp đánh giá giải thuật
• Giải thuật nâng cao
• Kỹ thuật phân tích giải thuật
• Hệ thống thông tin
• Giải thuật hình học
• Giải thuật so khớp chuỗi
• Single Source Shortest Paths
• Phân tích thiết kế giải thuật chương 10
• Giải bài toán các đường đi ngắn nhất
• Biểu diễn các đường đi ngắn nhất
• Kỹ thuật mã hóa
• Cây khung nhỏ nhất
• Giải thuật tổng quát
• Giải thuật của Kruskal
• Giải thuật của Prim
• Phân tích thiết kế thuật toán
• Công nghệ thông tin
• Bài giảng Giải thuật
• Kỹ thuật phân tích và thiết kế giải thuật
• Giải thuật đơn giản
• Phương pháp thiết kế giải thuật
• Phương pháp chia để trị
• Phương pháp quy hoạch động
• Mô tả công việc
• Mô tả công việc ngành IT
• Mô tả công việc Trưởng phòng thiết kế đồ họa
• Trưởng phòng thiết kế đồ họa
• Thiết kế đồ họa
• Quy trình thiết kế
• Bản vẽ kỹ thuật
• Ý tưởng thiết kế
• Giải trình thiết kế
• Đào tạo nhân viên thiết kế
• Kỹ thuật tối ưu hóa chương trình
• Mức thiết kế một chương trình
• Kỹ thuật tinh chế mã
• Kỹ thuật tối ưu hóa rẽ nhánh
• Bài Giảng điện tử
• Dương Tuấn Anh
• Thuật toán chương trình
• Kỹ thuật lập trình
• bài toán giải thuật
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• Giải thuật đệ quy
• Thiết kế giải thuật đệ quy
• Đệ quy tuyến tính
• Đệ quy nhị phân