Cấu trúc dữ liệu và giải thuật - Day 1
Cấu trúc dữ liệu và giải thuật - Day 1
Nền tảng cần thiết:
1. Cốt lõi của một chương trình máy tính bao gồm: Đầu vào, thuật toán và đầu ra của dữ liệu.
2. Các khai báo kiểu dữ liệu, các thư viện chuẩn của ngôn ngữ đó.
3. Cách giải quyết vấn đề và giải bài toán trên giấy: Phân tích chia nhỏ vấn đề để giải quyết từng cái dựa vào các giải thuật; các yêu cầu, cách tổ chức dữ liệu, các đối tượng tham gia, các yêu cầu có code đã làm trước đó không. Sau đó, viết trình tự xử lý từng thuật toán.
4. Nắm vững kiến thức nền.
Thuật toán - thuật giải:
Thuật toán là tập hợp các bước (hữu hạn) để giải quyết vấn đề, các bước này phải rõ ràng và có khả năng thực thi được.
Thuật toán - "xác định, hữu hạn, đúng"; "đầu vào/đầu ra, tính hiệu quả, tính tổng quát"
Các phương pháp biểu diễn thuật toán:
- Ngôn ngữ tự nhiên: liệt kê từng bước bằng chữ: Khá dài dòng, nên viết vắn tắt để tổng quát hiểu vấn đề
- Lưu đồ khối:
- Mã giả: (pseudo-code): Sử dụng từ khóa vay mượn từ ngôn ngữ lập trình (if, else, for, while): kết hợp với ngôn ngữ tự nhiên để giải thuật.
Sau khi có mã giả ta có thể ánh xạ sang bất kì ngôn ngữ nào.
Độ phức tạp của thuật toán:
Một thuật toán hiệu quả được đánh giá trên:
- Tốc độ thực thi
- Tính chính xác
- Đơn giản, dễ hiểu, dễ bảo trì
- Mức phổ dụng
- Chi phí sử dụng tài nguyên, bộ nhớ, CPU...
Phương pháp đánh giá:
- Dựa vào thời gian thuật toán chạy cho đến khi ra kết quả:
Code được biên dịch từ trên xuống dưới, từ trái qua phải.
Ta đặt timer vào trên và dưới đoạn code cần đo, sau đó tính toán thời gian thực hiện.
- Dựa vào các phép toán thực hiện: phép so sánh, phép gán...
- Độ phức tạp của một hằng số là một hằng số (nhỏ)
- Đoạn chương trình nối tiếp dùng nguyên tắc cộng
- Đoạn chương trình có lồng nhau dùng phương pháp nhân
- Độ phức tạp trong bảng trên tăng từ trên xuống dưới.
- Cần tránh viết thuật toán với độ phức tạp 2*n hoặc n!.
Ví dụ:
Yêu cầu: - Xác định số phép gán, số phép so sánh trong từng thuật toán.
- Tính độ phức tạp của thuật toán trong từng bài.
Nền tảng cần thiết:
1. Cốt lõi của một chương trình máy tính bao gồm: Đầu vào, thuật toán và đầu ra của dữ liệu.
2. Các khai báo kiểu dữ liệu, các thư viện chuẩn của ngôn ngữ đó.
3. Cách giải quyết vấn đề và giải bài toán trên giấy: Phân tích chia nhỏ vấn đề để giải quyết từng cái dựa vào các giải thuật; các yêu cầu, cách tổ chức dữ liệu, các đối tượng tham gia, các yêu cầu có code đã làm trước đó không. Sau đó, viết trình tự xử lý từng thuật toán.
4. Nắm vững kiến thức nền.
Thuật toán - thuật giải:
Thuật toán là tập hợp các bước (hữu hạn) để giải quyết vấn đề, các bước này phải rõ ràng và có khả năng thực thi được.
Thuật toán - "xác định, hữu hạn, đúng"; "đầu vào/đầu ra, tính hiệu quả, tính tổng quát"
Các phương pháp biểu diễn thuật toán:
- Ngôn ngữ tự nhiên: liệt kê từng bước bằng chữ: Khá dài dòng, nên viết vắn tắt để tổng quát hiểu vấn đề
- Lưu đồ khối:
Vòng lặp while: Kiểm tra trước, thực thi sau
Vòng lặp Do-while: thực thi trước, kiểm tra sau
Vòng For(BT1,BT2,BT3) <câu lệnh>
Sau khi có mã giả ta có thể ánh xạ sang bất kì ngôn ngữ nào.
Độ phức tạp của thuật toán:
Một thuật toán hiệu quả được đánh giá trên:
- Tốc độ thực thi
- Tính chính xác
- Đơn giản, dễ hiểu, dễ bảo trì
- Mức phổ dụng
- Chi phí sử dụng tài nguyên, bộ nhớ, CPU...
Phương pháp đánh giá:
- Dựa vào thời gian thuật toán chạy cho đến khi ra kết quả:
Code được biên dịch từ trên xuống dưới, từ trái qua phải.
- Dựa vào các phép toán thực hiện: phép so sánh, phép gán...
- Độ phức tạp của một hằng số là một hằng số (nhỏ)
- Đoạn chương trình nối tiếp dùng nguyên tắc cộng
- Đoạn chương trình có lồng nhau dùng phương pháp nhân
- Độ phức tạp trong bảng trên tăng từ trên xuống dưới.
- Cần tránh viết thuật toán với độ phức tạp 2*n hoặc n!.
Ví dụ:
Yêu cầu: - Xác định số phép gán, số phép so sánh trong từng thuật toán.
- Tính độ phức tạp của thuật toán trong từng bài.
Nhận xét
Đăng nhận xét