Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chương 8: GIẢI THUẬT - Coggle Diagram
Chương 8: GIẢI THUẬT
8.2. Giải thuật
8.2.1. Khái niệm giải thuật
Nguồn gốc thuật ngữ Algorithm (Al-Khwarizmi)
Dãy hữu hạn thao tác xác định
Ví dụ: Giải thuật Euclid (tìm UCLN)
8.2.2. Các tính chất của giải thuật
Đầu vào (Input)
Đầu ra (Output)
Tính hữu hạn
Tính xác định
Tính hiệu quả
8.2.3. Cách diễn đạt giải thuật
Ngôn ngữ tự nhiên
Lưu đồ (sơ đồ khối)
Bắt đầu/Kết thúc
Khối Input/Output
Khối điều kiện
Khối thao tác
Giả mã (pseudocode)
8.2.4. Thiết kế giải thuật
Mô-đun hóa bài toán
Tinh chỉnh từng bước
Ngôn ngữ tự nhiên -> Giả ngôn ngữ -> Ngôn ngữ lập trình
Ví dụ: sắp xếp dãy tăng dần
8.2.5. Đánh giá giải thuật
Tiêu chí đánh giá
Thời gian thực hiện
Dung lượng bộ nhớ
Độ phức tạp tính toán O(g(n))
O(1) - hằng số
O(log2n) - logarit
O(n) - tuyến tính
O(nlog2n)
O(n^k) - đa thức
O(2^n), O(n!) - hàm mũ
Quy tắc xác định độ phức tạp
Quy tắc cộng
Quy tắc nhân
Quy tắc bỏ hằng số
8.2.6. Một số giải thuật cơ bản
Sắp xếp lựa chọn (Selection sort)
Sắp xếp chèn (Insertion sort)
Sắp xếp nổi bọt (Bubble sort)
Tìm kiếm tuần tự (Sequential search)
Tìm kiếm nhị phân (Binary search)
Giải thuật đệ quy
Trường hợp suy biến
Phần đệ quy
Ví dụ: n! và Tháp Hà Nội
8.1. Phương pháp giải quyết vấn đề bằng máy tính
Nguyên lý Von Neumann
Quy trình: Bài toán -> Giải thuật -> Chương trình -> Ngôn ngữ máy -> Máy thực hiện