Hi các bạn! DL again. Chắc ai tham gia vào các chương trình đào tạo về lập trình hay đam mê công nghệ thông tin chắc chắn đều nghe qua cụm từ "giải thuật (thuật toán) và cấu trúc dữ liệu". Vậy nó là gì và có tác dụng gì đối với người lập trình? Thì qua bài viết này mong rằng các bạn sẽ hiểu rõ hơn về cấu trúc dữ liệu và giải thuật và sau đó sẽ đi chuyên sâu hơn qua loạt Series về giải thuật xuyên suốt thời gian sắp tới.
Khái quát về Series giải thuật và cấu trúc dữ liệu:
- Series này tham khảo trên "Bài giảng cấu trúc dữ liệu và giải thuật" - của TS. Nguyễn Duy Phương, ngoài ra Series còn tham khảo trên một số tài liệu khác và được cải biên theo ngôn ngữ của Sinh Viên :v
- Series sử dụng ngôn ngữ C/C++, Java và Python 3 để trình bày (Hai ngôn ngữ thông dụng dùng trong các kì thi ACM/ICPC)
- Series sẽ cố gắng nắm bắt đầy đủ 4 tiêu chí mà các thầy cô cần:
- Định nghĩa được.
- Hiểu và đánh giá quy chế hoạt động.
- Biểu diễn bằng ngôn ngữ máy.
- Ứng dụng được.
Giải thuật là gì?
Theo wiki thì: "Thuật toán (Algorithm) , còn gọi là giải thuật, là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán trước."
Còn theo mình thì Thuật toán (hay giải thuật) nó là cách bạn giải quyết (cho ra kết quả đúng) một "bài toán có kết quả" thì đó gọi là thuật toán.
Ví dụ như: Bạn cần sắp xếp tăng dần các số tự nhiên ngẫu nhiên thì có một cách đó là "đưa các con số bé đưa lên đầu dãy số" và đưa ra kết quả thì trong lập trình đó được gọi là giải thuật.
Một bài toán có nhiều cách làm (nhiều giải thuật) nhưng tùy thuộc vào bài toán mà ta chọn cách đỡ mất thời gian nhất. Trong Series sẽ đề cập chủ yếu về các giải thuật cổ điển như: sắp xếp nổi bọt, sắp xếp nhanh, tìm kiếm nhị phân, sinh, đệ quy,...
Cấu trúc dữ liệu là gì?
Một cách dễ hiểu là: Cấu trúc dữ liệu (Data Struct) là Cách bạn biểu diễn dữ liệu hay tổ chức nó trên máy để dễ dàng và thuận tiện cho việc áp dụng giải thuật và giải quyết bài toán. (Phần này sẽ được trình bày chi tiết hơn trong các bài đăng sau)
Ví dụ: Bạn tìm đường từ nhà đến trường thì bạn có thể sử dụng bản đồ, thì cái bản đồ chính là một loại dữ liệu được cấu trúc theo dạng hình ảnh trên giấy. Và nó hỗ trợ cho bạn việc tìm đường nhanh hơn. (Lưu ý cho vd này: Ví dụ trên đây chỉ là để bạn dễ hiểu hơn thôi ^^, chứ để tổ chức dữ liệu trên máy sẽ rất khác với cách tổ chức ngoài đời. Vì cách tổ chức này phục vụ cho việc máy hiểu.)
Tổng kết:
Giải thuật: là cách giải quyết bài toán.
Cấu trúc dữ liệu: là cách tổ chức dữ liệu của bài toán.