Học cấu trúc dữ liệu và giải thuật luôn được xem là bộ môn rất quan trọng đối với bất cứ sinh viên công nghệ thông tin nào. Để có thể làm tốt những công việc trong tương lai bạn phải nắm vững nó càng chắc càng tốt. Sau đây, chúng ta sẽ cùng tìm hiểu chi tiết hơn về môn học này.
1. Cấu trúc dữ liệu và giải thuật là gì?
Cùng tìm hiểu lần lượt định nghĩa của hai khái niệm “cấu trúc dữ liệu” và “giải thuật” nhé.
1.1. Cấu trúc dữ liệu (Data structure)
Khi dữ liệu được lưu trữ, tổ chức một cách logic mà qua đó bạn có thể được sử dụng và quản lý một cách hiệu quả thì người ta gọi đó là cấu trúc dữ liệu. Ví dụ khi bạn tháo một thiết bị điện tử nào đó và đặt chúng theo thứ tự khi được tháo ra. Sau đó lắp lại theo thứ tự ngược lại thì cũng gọi là cấu trúc dữ liệu.
Nguyên tắc khi sử dụng dữ liệu vào sau sẽ được lấy ra trước là nguyên tắc của một loại cấu trúc dữ liệu khi hoạt động. Tùy vào từng trường hợp mà ta có rất nhiều loại cấu trúc dữ liệu khác nhau và mỗi loại sẽ có những ưu nhược điểm riêng.
Không có một cấu trúc dữ liệu nào được gọi là hoàn hảo. Tùy vào từng trường hợp cụ thể, ta sẽ ứng dụng cấu trúc khác nhau sao cho hiệu quả mang lại là tối ưu nhất.
1.2. Giải thuật (Algorithms)
Giải thuật hay còn gọi là thuật toán, trong tiếng Anh là Algorithms. Nó có nghĩa là tập hợp các thao tác, các bước để giải quyết một vấn đề gì đó hiệu quả hơn.
Ví dụ, khi bạn nấu cơm sẽ bao gồm các bước là: Lấy gạo – vo gạo – đong nước – đặt vào nồi – cắm điện – bật nút – đợi cơm chín. Các bước này chính là giải thuật nấu cơm. Tương tự trong lập trình có nhiều giải thuật hay còn gọi là thuật toán khác nhau giúp giải quyết các vấn đề trong lập trình.
2. Tầm quan trọng của việc học cấu trúc dữ liệu và giải thuật
Ta có thể thấy không chỉ các ngôn ngữ lập trình như Java, PHP, Python,… mà bất kể bạn dùng ngôn ngữ nào, bạn đều cần biết về cấu trúc dữ liệu và giải thuật để giải quyết vấn đề. Ngôn ngữ chỉ là một công cụ, còn cấu trúc dữ liệu và giải thuật là phương pháp. Do đó, cấu trúc dữ liệu và giải thuật đóng một vai trò rất quan trọng trong lập trình.
Có một thực tế là trong quá trình tuyển dụng, một trong những yếu tố đầu tiên nhà tuyển dụng xem xét chính là kỹ năng về cấu trúc dữ liệu và giải thuật, sau đó mới đến ngôn ngữ lập trình mà bạn có thể sử dụng. Và đương nhiên, bạn sẽ phải nắm vững cả 2 yếu tố trên để có thể đáp ứng được yêu cầu của công việc.
Chính vì thế việc học cấu trúc dữ liệu và giải thuật là vô cùng quan trọng trong những ngành này. Tương lai ngoài viết code ra, bạn còn có thể trở thành người thiết kế phần mềm hoặc team leader quản lý dự án nếu kiên trì tập luyện và không ngừng nâng cao kỹ năng của mình.
Vì vậy, các bạn sinh viên đang theo học công nghệ thông tin không thể bỏ qua môn học bổ ích này. Việc nghiên cứu và học cấu trúc dữ liệu và giải thuật sẽ giúp ích rất nhiều trong công việc của bạn ở hiện tại và tương lai.
Nói về “ác mộng” của 80% sinh viên CNTT : Cấu trúc dữ liệu và giải thuật, chúng tôi sẽ giới thiệu 10 cuốn sách kinh điển trong mảng này, tất nhiên không xếp theo thứ tự hơn-kém vì theo chúng tôi, mỗi cuốn sách đều cover các topic rất tốt. Chúng tôi đưa ra 10 đại diện, không có nghĩa là bạn phải đọc tất cả. Chỉ cần ngấm hết tinh hoa trong 2 cuốn, trình giải thuật của bạn đã khá hơn rất nhiều dev chuyên nghiệp rồi!
Để hỗ trợ độc giả trong công tác tìm kiếm, mỗi đại diện được chúng tôi đề cập đều đi kèm với một tập source code tương ứng.
#1 Data Structures and Algorithms Made Easy – Narasimha Karumanchi
Cuốn này giải thích các cấu trúc dữ liệu kèm theo source code C/C++. Độc giả có thể test song song với đọc. Nếu bạn thích Java? Hãy chọn phiên bản “Data Structures and Algorithm Made Easy by Java”. Cuốn này giải thích các khái niệm cấu trúc dữ liệu xuyên suốt 21 chương với các chủ đề như: Recursion & Backtracking, Linked Lists, Stacks, Queues, Trees, Priority Queues, Heaps, String Algorithms, Algorithms Design Technique… Nó cũng đưa ra nhiều phương pháp tiếp cận khác nhau cho mỗi vấn đề, nhờ đó, độc giả dễ dàng hình dung và phân tích được các giải thuật tương ứng cho từng bài toán.
Ngôn ngữ sử dụng: C/C++
Source Code: //github.com/careermonk/DataStructuresAndAlgorithmsMadeEasy
#2 Data Structures and Algorithm in Java, 2nd Edition – Robert Lafore
Cuốn này giải thích các concept ở mức căn bản nhất. Kèm theo đó là các gợi ý về solution cho mỗi project ở từng chương. Cuốn này đã từng được sử dụng làm giáo trình cho một khóa học “Cấu trúc dữ liệu và giải thuật”. Các topic ở những cuốn sách kiểu này thường không khác nhau nhiều, vẫn là các cấu trúc dữ liệu quen thuộc : Stack, queue, heaps, hashtable…..
Ngôn ngữ sử dụng: Java
Source code: //www.informit.com/store/data-structures-and-algorithms-in-java-9780672324536
#3 The Algorithm Design Manual, 2nd Edition – Steven S. Skiena
Cuốn sách này sẽ giúp cho buổi phỏng vấn của các bạn trơn tru hơn.
Một người thiết kế thuật toán tốt sẽ nắm được những nguyên lý thiết kế cơ bản, kèm theo đó là các cấu trúc dữ liệu, dynamic programming, depth first search, backtracking và tìm kiếm heuristic… Cuốn sách này sử dụng Pseudocode. Từ Pseudocode, ta có thể chuyển qua bất kỳ ngôn ngữ nào. Khía cạnh lịch sử liên quan đến việc áp dụng các giải thuật xảy ra trong chiến tranh thế giới cũng được đề cập trong cuốn này với một góc nhìn khá thú vị.
The Algorithm Desgin Manual đã được Steve Yegge đề xuất cho các ứng viên phỏng vấn tại Google.
Ngôn ngữ sử dụng: C/Pseudocode
Source code: //www3.cs.stonybrook.edu/~algorith/book/programs/
#4 Introduction to Algorithm, 3rd edition – Thomas H.Cormen
Cuốn này cover một phạm vi khá rộng trong cấu trúc dữ liệu, bên cạnh đó, mỗi topic đều được viết rất sâu. Introduction to Algorithm phù hợp với tất cả đối tượng – từ sinh viên chưa tốt nghiệp cho đến chuyên gia…
Pseudocode cũng được sử dụng để trình bày các ý tưởng trong cuốn sách này. Các chủ đề thuộc giải thuật hiện đại như lý thuyết đồ thị, giải thuật đa luồng đều được đề cập rất chi tiết.
Introduciton to Algorithm cũng là một bí kíp cần được tu luyện tử tế trước khi đi phỏng vấn
Ngôn ngữ sử dụng: Pseudocode
Source code: //notebookbft.files.wordpress.com/2015/10/clrs-solution-collection.pdf
#5 Algorithm, 4th Edition – Robert Sedgewick, Kevin Wayne.
Cuốn này được sử dụng rộng rãi tại các trường đại học trên toàn thế giới. Nó thống kê các thuật toán quan trọng đang được áp dụng rộng rãi cũng như đề cập một cách hết sức chi tiết tới các thuật toán và cấu trúc dữ liệu áp dụng cho công việc tìm kiếm, sắp xếp, xử lý đồ thị và xử lý xâu ký tự, Tác giả Robert Sedgewick và Kevin Wayne cũng duy trì một cổng thông tin điện tử cung cấp source code tương ứng. Trong tài liệu này, ngôn ngữ lập trình được sử dụng là Java.
Ngôn ngữ sử dụng: Java
Source code: //algs4.cs.princeton.edu/home/
Bạn hãy cùng Techmaster nghiên cứu cuốn này tại đây
#6 Elements of Programming Interviews in Java: The Insiders’ Guide – Adnan Aziz, Tsung-Hsien Lee, Amit Prakash
The Elements of Programming Interviews hỗ trợ rất hiệu quả cho các buổi phỏng vấn. Tác giả cuốn này phát hành 2 bản, một bản cho ngôn ngữ C và một bản cho Java.
Các hướng dẫn trong quyển này bắt đầu với các giải thuật kiểu vét cạn, sau đó phân tích và đi đến những lựa chọn tối ưu hơn. Tất cả các vấn đề đều được phân loại dựa theo độ khó và các trường hợp liên quan trong thực tế, kèm theo đó là những gợi ý hữu ích, nhờ vậy bạn dễ dàng hiểu và áp dụng các giải thuật này trong công việc thường nhật. Cuốn sách này cũng mô phỏng được một phần những khó khăn bạn sẽ gặp phải trong các buổi phỏng vấn.
Ngôn ngữ: Java/C++
Source code: //elementsofprogramminginterviews.com/solutions
#7 Programming Pearls, 2nd Edition – Jon Bentley
Ngôn ngữ lập trình được sử dụng ở đây là ngôn ngữ C.
“Những viên ngọc của lập trình” – Programming Pearls là một bộ sưu tập các vấn đề kinh điển và khá phổ biến trong giới lập trình: thuật toán sắp xếp, tìm kiếm, kiểm thử phần mềm, bài toán tối ưu, …..Mỗi vấn đề đều kèm theo hướng dẫn và các bài phân tích hết sức chi tiết.
Ngôn ngữ: C
#8 Algorithms in C, 3rd Edition – Robert Sedgewick
Đây là một bộ 2 cuốn sách. Chúng được coi như nguồn tài nguyên quý giá dành cho các nhà nghiên cứu, các developer và thậm chí là cả sinh viên ngành CNTT.
Cuốn đầu tiên giới thiệu các ý niệm cơ bản liên quan tới cấu trúc dữ liệu và giải thuật.
Cuốn thứ 2 tập trung vào các thuật toán đồ thị với trên 2000 bài tập thực hành. Đi kèm với khối lượng bài tập khổng lồ đó là các hướng dẫn và sample code mẫu mực của tác giả.
Ngôn ngữ: C
Source code:
//www.cs.princeton.edu/~rs/Algs3.c1-4/code.txt
//www.cs.princeton.edu/~rs/Algs3.c5/code.txt
#9 The Art of Computer Programming, 1st Edition – Donald E. Knuth
Đây là một tập hợp đồ sộ các giải thuật và phân tích được tổ chức thành 3 phần:
Phần 1 gồm các kiến thức nền liên quan đến toán học và những cấu trúc dữ liệu căn bản. Phần 2 dành cho semi-numerical algorithm. Phần cuối cùng giống như một cuốn bí kíp toàn tập về các kỹ thuật tìm kiếm và sắp xếp.
“Nếu bạn là một lập trình viên cứng, hãy đọc cuốn sách này và gửi CV ngay cho tôi nếu bạn hiểu tất cả mọi thứ trong đó” – Bill Gates
Ngôn ngữ: Pseudocode
Source code: //www-cs-faculty.stanford.edu/~uno/programs.html
#10 Hacker’s Delight 2nd Edition by Henry S. Warren
Bí kíp này sẽ tổng hợp các mẹo liên quan tới kỹ thuật, giải thuật. Mục tiêu chính là giúp bạn lập trình linh hoạt hơn, từ đó nâng cao hiệu suất công việc. Các tricks được trình bày “chi tiết đến từng bit”. Cuốn sách này cũng chứa một chương trình tối ưu hóa cho máy tính RISC.
Ngôn ngữ: C
Source code: //www.hackersdelight.org/hdcodetxt.zip
Via Techtalk.vn