tailieunhanh - Bài giảng Phân tích thiết kế giải thuật: Chương 3 - Trịnh Huy Hoàng

Bài giảng Phân tích thiết kế giải thuật: Chương 3 của Trịnh Huy Hoàng bao gồm những nội dung về kỹ thuật tối ưu hóa chương trình (các mức thiết kế một chương trình, các kỹ thuật tối ưu hóa chương trình như kỹ thuật tinh chế mã, kỹ thuật tối ưu hóa rẽ nhánh, kỹ thuật tối ưu hóa các vòng lặp tối ưu hóa chương trình bằng bảng truy cập, tối ưu bằng cách giảm thiểu gọi chương trình con). | Chương 3: Kỹ thuật tối ưu hóa chương trình Trịnh Huy Hoàng Khoa Công nghệ thông tin Đại học Sư phạm TPHCM Nội dung Các mức thiết kế một chương trình Các kỹ thuật tối ưu hóa chương trình Kỹ thuật tinh chế mã Kỹ thuật tối ưu hóa rẽ nhánh Kỹ thuật tối ưu hóa các vòng lặp Tối ưu hóa chương trình bằng bảng truy cập Tối ưu bằng cách giảm thiểu gọi chương trình con Các mức thiết kế một chương trình Đặc tả bài toán Thiết kế cấu trúc hệ thống Cấu trúc dữ liệu và thuật toán Tinh chế mã (tối ưu hóa chương trình) Tính độ phức tạp của thuật toán Lưu ý Trước khi viết chương trình: + Không nên mã hóa 1 chương trình ngay khi chỉ mới có ý tưởng đầu tiên mà phải xem xét tất cả các mức thiết kế có thể để chọn ra 1 thiết kế làm tăng tốc nhanh nhất với phí tổn ít nhất. + Nên thử nhiều mức thiết kế khác nhau bằng cách giải quyết bài toán trên nhiều mặt từ đó chọn được 1 thiết kế tối ưu về không gian và thời gian. Kỹ thuật tinh chế mã Ta có thể tối ưu chương trình về mặt thời gian hoặc không gian (rất khó thực hiện được cả hai), nếu muốn tối ưu cả hai khía cạnh trên thì ta phải thay đổi thuật toán. Ở chương này ta xét các kỹ thuật tối ưu chương trình về mặt cấu trúc, tìm 1 thuật giải có độ phức tạp tốt nhất có thể. Ví dụ 1: Viết chương trình tính tổng S=1+x/1!+x2/2!+ +xn/n! s=1; for(i=1;i Kỹ thuật tối ưu hóa rẽ nhánh Qui tắc 1: Sắp xếp biểu thức điều kiện dạng A1 and A2 and An theo xác suất sai của các điều kiện Aigiảm dần Qui tắc 2: Sắp xếp biểu thức điều kiện dạng A1 or A2 or An theo xác suất đúng của các điều kiện Ai giảm dần Ví dụ: Cho 2 dãy số nguyên A, B lần lượt có số phần tử là m và n. A=B? if ((m=n)&& Chua(a,b) && Chua(b,a) printf(“Hai day bang nhau”); else printf(“Hai day khong bang nhau”); Ví dụ: Nhập số tự nhiên n, nếu n là số có 1 trong các tính chất (lẻ, nguyên tố, chính phương, hoàn hảo) thì thực hiện S1, ngược lại S2. if . | Chương 3: Kỹ thuật tối ưu hóa chương trình Trịnh Huy Hoàng Khoa Công nghệ thông tin Đại học Sư phạm TPHCM Nội dung Các mức thiết kế một chương trình Các kỹ thuật tối ưu hóa chương trình Kỹ thuật tinh chế mã Kỹ thuật tối ưu hóa rẽ nhánh Kỹ thuật tối ưu hóa các vòng lặp Tối ưu hóa chương trình bằng bảng truy cập Tối ưu bằng cách giảm thiểu gọi chương trình con Các mức thiết kế một chương trình Đặc tả bài toán Thiết kế cấu trúc hệ thống Cấu trúc dữ liệu và thuật toán Tinh chế mã (tối ưu hóa chương trình) Tính độ phức tạp của thuật toán Lưu ý Trước khi viết chương trình: + Không nên mã hóa 1 chương trình ngay khi chỉ mới có ý tưởng đầu tiên mà phải xem xét tất cả các mức thiết kế có thể để chọn ra 1 thiết kế làm tăng tốc nhanh nhất với phí tổn ít nhất. + Nên thử nhiều mức thiết kế khác nhau bằng cách giải quyết bài toán trên nhiều mặt từ đó chọn được 1 thiết kế tối ưu về không gian và thời gian. Kỹ thuật tinh chế mã Ta có thể tối ưu chương trình về mặt thời gian hoặc không

• Kỹ thuật lập trình
• 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
• 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
• Kỹ thuật thiết kế giải 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
• Phân tích thuật toán
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Phân tích thiết kế 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
• 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
• Tiêu chuẩn đánh giá giải thuật
• Phương pháp đánh giá giải thuật
• 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
• 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
• Thuật toán sắp xếp
• Phân tích thuật toán sắp xếp
• Thuật toán tìm kiếm
• Phân tích thuật toán tìm kiếm
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• 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 giải thuật
• Hệ thức truy hồi
• Độ phức tạp giải thuật
• Phân tích giải thuật lặp
• Phân tích giải thuật đệ quy
• 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
• Quy hoạch động
• Biểu diễn thuật giải
• Phân tích 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
• 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ị
• Giải thuật quay lui
• 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 sắp xếp
• Chương trình sắp xếp
• Cấu trúc dữ liệu
• Giải thuật lưu trữ ngoài
• 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
• Hình học tính toán
• Giải thuật thô sơ
• Kỹ thuật quét
• Tính đúng đắn
• Kỹ thuật mã hóa
• Giải thuật đệ quy
• Thiết kế giải thuật đệ quy
• Đệ quy tuyến tính
• Đệ quy nhị phân