1. Kiến thức trọng tâm
Chủ đề này gồm các bài từ Bài 14 đến Bài 16: thuật toán tìm kiếm tuần tự, thuật toán tìm kiếm nhị phân và thuật toán sắp xếp. Chủ đề giúp em hiểu máy tính giải quyết vấn đề như thế nào.
Thuật toán là dãy các bước rõ ràng, thực hiện theo thứ tự để giải quyết một vấn đề. Khi con người giao việc cho máy tính, máy tính thực hiện đúng các bước của thuật toán để tìm ra kết quả. Thuật toán càng tốt thì máy tính giải quyết vấn đề càng nhanh và chính xác.
Tìm kiếm là công việc thường gặp: tìm một cuốn sách trong thư viện, tìm tên bạn trong danh sách lớp, tìm từ trong từ điển. Thuật toán tìm kiếm tuần tự kiểm tra lần lượt từng phần tử từ đầu đến khi tìm thấy. Thuật toán tìm kiếm nhị phân áp dụng cho dãy đã sắp xếp, mỗi lần loại bỏ một nửa dãy nên nhanh hơn nhiều.
Sắp xếp là việc xếp các phần tử theo thứ tự tăng dần hoặc giảm dần, ví dụ xếp điểm số từ thấp đến cao, xếp tên học sinh theo thứ tự bảng chữ cái. Sắp xếp giúp việc tìm kiếm sau đó dễ dàng hơn.
2. Ví dụ minh họa
Tình huống: Em cần tìm tên bạn "An" trong danh sách 100 học sinh đã xếp theo thứ tự bảng chữ cái. Nên dùng cách nào?
Lời giải: Vì danh sách đã sắp xếp, em dùng thuật toán tìm kiếm nhị phân: so sánh "An" với tên ở giữa danh sách. Nếu tên ở giữa đứng sau "An" theo bảng chữ cái, em chỉ tìm trong nửa đầu; nếu đứng trước, em chỉ tìm trong nửa sau. Mỗi lần tìm, số tên cần xét giảm một nửa nên rất nhanh. Nếu danh sách chưa sắp xếp, em phải dùng tìm kiếm tuần tự, kiểm tra lần lượt từng tên.
3. Ghi nhớ
- Thuật toán là dãy các bước rõ ràng để giải quyết một vấn đề.
- Tìm kiếm tuần tự: kiểm tra lần lượt từng phần tử từ đầu dãy.
- Tìm kiếm nhị phân: chỉ dùng cho dãy đã sắp xếp, mỗi lần loại bỏ một nửa dãy.
- Sắp xếp giúp dữ liệu có thứ tự và tìm kiếm dễ dàng hơn.