Cấu trúc dữ liệu và giải thuật (Data Structure and Algorithms) là một trong những khối lượng kiến thức quan trọng nhất trong bất cứ chương trình học nào của sinh viên các ngành công nghệ thông tin. Bạn đã được nghe các bậc tiền bối ở đâu đó nói rằng, học lập trình bắt buộc phải học cấu trúc dữ liệu và giải thuật, điều này không hẳn nhưng lại là yếu tố tiên quyết để bạn đi được xa hơn trên con đường này. Đây là một khía cạnh kiến thức khó cho bất kỳ ai mới học nhưng lại là yếu tố cốt lõi trong mọi chương trình. Bạn có thể học một ngôn ngữ lập trình mới thành thạo trong chưa đầy một tháng nhưng để vận dụng nó tốt thì rất cần nắm vững các yếu tố đặc trưng của nó thể hiện ở các cấu trúc dữ liệu mà nó hỗ trợ, cách thức quản lý cấu trúc dữ liệu đó và các lớp giải thuật hỗ trợ sẵn có trong nó cũng như quan trọng hơn là cách thức để triển khai các thuật toán để giải quyết các vấn đề bằng ngôn ngữ lập trình đó.
Series “Cấu trúc dữ liệu và giải thuật cơ bản” này sẽ cung cấp cho bạn những kiến thức cơ sở nhất về các cấu trúc dữ liệu thường gặp như: mảng, con trỏ, ngăn xếp,…các lớp giải thuật cơ bản như: quay lui, đệ quy, quy hoạch động…cũng như phương pháp phân tích thiết kế, đánh giá các thuật toán để áp dụng trong các bài toán thực tế. Nội dung của series bao gồm:
Cấu trúc dữ liệu cơ bản
Cấu trúc dữ liệu là gì? Tổng quan về cấu trúc dữ liệu
Cấu trúc dữ liệu mảng và những vấn đề cần biết
Danh sách liên kết và các thao tác trên danh sách liên kết
Danh sách liên kết đơn, sự khác biệt giữa danh sách liên kết và mảng
Danh sách liên kết đôi và các đặc điểm
Danh sách liên kết vòng và ứng dụng
Ngăn xếp và các thao tác trên ngăn xếp
Cấu trúc dữ liệu hàng đợi và các thao tác cơ bản
Một số kiểu hàng đợi
Circular Queue và ứng dụng
Priority Queue (Hàng đợi ưu tiên)
Deque và các phép toán trên Deque
Bảng băm và ứng dụng của bảng băm
Các cấu trúc dữ liệu dạng cây
Cấu trúc dữ liệu cây và ứng dụng
Duyệt cây và thứ tự duyệt cây
Cây nhị phân và các kiểu cây nhị phân
Cây nhị phân tìm kiếm và các ứng dụng
Cây AVL và các thao tác cơ bản trên cây AVL
Splay Tree và ứng dụng
B-Tree và ứng dụng của B-tree
B+ tree và ứng dụng
Cây đỏ đen (Red-Black Tree) và ứng dụng
Cấu trúc dữ liệu Heap và các phép toán
Cấu trúc dữ liệu đồ thị
Cấu trúc dữ liệu đồ thị (Graph) và ứng dụng
Cây khung và cây khung nhỏ nhất trong đồ thị
Thuật toán Tarjan trong tìm thành phần liên thông mạnh
Thuật toán BFS – Tìm kiếm theo chiều rộng trên đồ thị
Thuật toán DFS – Tìm kiếm theo chiều sâu trên đồ thị
Biểu diễn đồ thị bằng ma trận kề và danh sách kề
Thuật toán tổng quan
Thuật toán là gì? Mối liên hệ giữa cấu trúc dữ liệu và thuật toán
Độ phức tạp tính toán
Phân tích thiết kế thuật toán
Thuật toán tham lam (Greedy Algorithms)
Thuật toán chia để trị (Divide and Conquer)
Quy hoạch động (Dynamic Programming)
Thuật toán quay lui (Back Tracking)
Đệ quy và ước lượng độ phức tạp đệ quy bằng định lý thợ (Master Theorem)
Các giải thuật tìm kiếm
Thuật toán tìm kiếm tuyến tính
Thuật toán tìm kiếm nhị phân
Tìm kiếm nội suy
Các giải thuật sắp xếp
Thuật toán sắp xếp nổi bọt (Bubble Sort)
Sắp xếp chọn (Selection Sort)
Thuật toán Insertion Sort (sắp xếp chèn)
Merge Sort (sắp xếp trộn)
Quick sort (sắp xếp nhanh)
Counting Sort (sắp xếp đếm)
Radix Sort (sắp xếp theo cơ số)
Bucket Sort (sắp xếp theo khối)
Heap Sort (sắp xếp vun đống)
Shell Sort (ứng dụng của sắp xếp chèn)
Các thuật toán đối sánh mẫu, tìm xâu con
Thuật toán Knuth-Morris-Pratt trong tìm kiếm xâu con
Thuật toán Boyer-Moore trong tìm kiếm xâu con
Thuật toán Rabin-Karp ứng dụng trong đối sánh mẫu
Thuật toán Wu-Manber trong đối sánh đa mẫu
Thuật toán Aho-Corasick trong đối sánh đa mẫu
Các thuật toán trên đồ thị
Thuật toán Dijkstra và các cách thực thi
Thuật toán Bellman-Ford cho đồ thị có trọng số âm
Thuật toán Floyd-Warshall cho đồ thị dầy
Thuật toán Johnson cho đồ thị thưa