Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chương 8: Giải thuật, Vũ Hữu Kỳ Anh - Coggle Diagram
Chương 8: Giải thuật
- Nguyên lý Von Neumann: Máy tính xử lý thông tin theo dãy lệnh lưu trữ trong bộ nhớ
- Quy trình xử lý: Bài toán -> Giải thuật -> Chương trình -> Ngôn ngữ máy -> Thực thi
- Xác định bài toán: Làm rõ dữ liệu đầu vào (Input) và đầu ra (Output)
- Định nghĩa giải thuật: Khái niệm từ Al-Khwarizmi (825), là dãy hữu hạn các thao tác theo trình tự xác định để đạt kết quả
- Selection Sort (Lựa chọn): Tìm phần tử nhỏ nhất đổi chỗ về đầu, lặp lại
- Insertion Sort (Chèn): Chèn lần lượt từng phần tử vào vị trí đúng trong dãy đã sắp xếp
- Bubble Sort (Nổi bọt): Duyệt từ phải sang trái, so sánh cặp kề nhau để đẩy phần tử nhỏ nhất lên
- Sequential Search (Tuần tự): Duyệt từng phần tử từ đầu đến cuối dãy
- Binary Search (Nhị phân): Dãy phải sắp xếp trước, so sánh phần tử giữa để thu hẹp phạm vi
- Khái niệm: Chương trình con gọi lại chính nó
- Cấu trúc: Trường hợp suy biến (điểm dừng) và Phần đệ quy
- Ví dụ bài toán: Tính n!, Bài toán Tháp Hà Nội
- Đầu vào / Đầu ra: Nhận dữ liệu vào và trả về kết quả
- Tính hữu hạn: Phải dừng sau một số hữu hạn bước
- Tính xác định: Thao tác chặt chẽ, cùng 1 đầu vào chỉ ra 1 kết quả
- Tính hiệu quả: Đơn giản, dễ cài đặt, thực hiện nhanh, tiết kiệm bộ nhớ
- Ngôn ngữ tự nhiên: Liệt kê các bước bằng văn bản
- Lưu đồ (Flowchart): Dùng khối hình học chuẩn và mũi tên chỉ hướng
- Giả mã (Pseudocode): Kết hợp cấu trúc điều khiển, ngôn ngữ tự nhiên và toán học
- Mô-đun hóa: Chia bài toán lớn thành các bài toán con
- Tinh chỉnh từng bước: Chuyển từ Ngôn ngữ tự nhiên -> Giả mã -> Ngôn ngữ lập trình
- Đo lường thời gian thực hiện theo kích thước đầu vào n
- Không phụ thuộc phần cứng hay hệ điều hành
- Thứ tự tăng dần: O(1) < O(log2 n) < O(n) < O(n log2 n) < O(n^2) < O(2^n) < O(n!)
- Quy tắc tính: Quy tắc cộng, Quy tắc nhân, Quy tắc bỏ hằng số
-