Chuyển tới nội dung

cấu trúc dữ liệu và giải thuật sách | Tanggiap

  • bởi

“Bất kì một chương trình máy tính nào cũng cần thuật toán/ giải thuật (algorithms). Không thuật toán, không chương trình nào hết!”

Câu nói đánh giá vô cùng đúng về vai trò cũng như giá trị của thuật toán/giải thuật đối với mỗi lập trình viên. Vậy thuật toán là gì? Tại sao thuật toán lại quan trọng như vậy? Chúng ta nên học thuật toán từ những nguồn nào là tốt nhất?,… Những thắc mắc này của bạn sẽ có ngay đáp án sau khi bạn đọc xong bài viết này.

Let’s go!

Thuật toán là gì?

Thuật toán (algorithms) có thể hiểu đơn giản là tập hợp các bước để hoàn thành một nhiệm vụ. Một số ví dụ rất cơ bản về thuật toán xung quanh bạn như: bạn có thể có một thuật toán để đi từ nhà đến trường, để làm bánh mỳ xá xíu thật ngon hoặc một thuật toán để tìm thấy những gì bạn tìm kiếm trong một cửa hàng tạp hóa nhanh nhất.

Trong khoa học máy tính khái niệm này cũng tương tự như vậy, thuật toán là một tập hợp các bước để chương trình máy tính hoàn thành một nhiệm vụ.

Tại sao thuật toán lại quan trọng với lập trình viên như vậy?

Câu trả lời rất đơn giản, học thuật toán giúp chúng ta giải quyết vấn đề một cách tốt hơn, nâng cao tư duy lập trình.

Như ví dụ mình đã nêu ở trên bạn có thể thấy rằng thuật toán ở khắp nơi quanh ta từ những vấn đề nhỏ tới vấn đề lớn. Chính vì thế thuật toán thì cũng có thuật toán đơn giản và thuật toán phức tạp.

Một số lĩnh vực trong lập trình chỉ cần những thuật toán đơn giản những cũng có những lĩnh vực cần sử dụng rất nhiều thuật toán phức tạp như: render đồ hoạ, mã hoá dữ liệu, driver, machine learning, data mining. Phải nắm vững các thuật toán này thì bạn mới có thể làm việc trong lĩnh vực đó.

Đối với mỗi lập trình viên việc giỏi thuật toán cũng giúp bạn tìm ra hướng giải quyết vấn đề nhanh hơn, viết code mạch lạc hơn. Nắm vững thuật toán, cấu trúc dữ liệu, bạn sẽ ước tính được độ phức tạp của code, đánh giá code chạy nhanh hay chậm, có scalable hay không.

Trích lời trong bài viết Thuật toán là gì? Học thuật toán làm quái gì?, có thể khẳng định thế này:

“Có một sự thật rằng, đa phần các sản phẩm phần mềm ngày nay thành công mà không cần hay sử dụng rất ít thuật toán bên trong nó. Tuy nhiên những sản phẩm có hàm lượng thuật toán cao, trí tuệ lớn, thật sự tạo ra sự khác biệt và thành công lớn hơn những sản phẩm bình thường. Sản phẩm như Google thành công vì có thuật toán tìm kiếm mạnh mẽ bậc nhất thế giới. Sản phẩm như Facebook hay Youtube cũng phải sử dụng nhiều thuật toán như tìm kiếm, gợi ý người dùng, gợi ý nội dung, … Nhưng thuật toán lại không phải yếu tố cốt lõi quyết định thành công của sản phẩm này. Do đó, việc học thuật toán, sự quan trọng của thuật toán phụ thuộc vào sản phẩm, ứng dụng mà bạn làm. Dù có giỏi hay không giỏi thuật toán, bạn vẫn có thể thành công nếu vận dụng đúng kỹ năng, hiểu biết của mình vào lĩnh vực mà bạn làm. Cá nhân tôi luôn khuyên và nhắn nhủ các bạn lập trình viên hãy luôn học và rèn luyện thuật toán. Với tôi, thuật toán giúp bạn rèn luyện tư duy giải quyết vấn đề, cùng với suy nghĩ về việc luôn tối ưu và làm sản phẩm một cách tối ưu và tổng quát. Có những lúc, thực sự bế tắc trong công việc (không chỉ là lập trình), tôi vẫn thường vào làm 1 số bài tập thuật toán để khai thông và thúc đẩy sự suy nghĩ. Sau đó tôi thấy mình minh mẫn và giải quyết công việc cũ 1 cách thuận lợi hơn.”

4 bộ sách huyền thoại về thuật toán

1. Cuốn sách “The design and Analysis of computer Algorithms”

Cuốn sách này được viết bởi nhóm tác giả Alfred V. Aho , John E. Hopcroft , Jeffrey D. Ullman và được xuất bản đầu tiên năm 1974.

Đây là cuốn sách huyền thoại giúp bạn hiểu biết về các khái niệm cơ bản của thuật toán – trung tâm của khoa học máy tính. Nó giới thiệu các cấu trúc dữ liệu cơ bản và kỹ thuật lập trình thường được sử dụng trong các thuật toán hiệu quả.

Các thuật toán đó bao gồm việc sử dụng danh sách, ngăn xếp đẩy xuống, hàng đợi, cây và biểu đồ. Các chương sau đi sâu vào các thuật toán sắp xếp, tìm kiếm và vẽ đồ thị, các thuật toán khớp chuỗi và thuật toán nhân số nguyên Schonhage-Strassen. Cung cấp nhiều bài tập được phân loại ở cuối mỗi chương.

2. Cuốn sách Introduction to Algorithms

Introduction to Algorithms là một cuốn sách về lập trình máy tính của Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest và Clifford Stein .

Cuốn sách này đã được sử dụng rộng rãi làm sách giáo khoa cho các khóa học thuật toán tại nhiều trường đại học và thường được trích dẫn làm tài liệu tham khảo cho các thuật toán trong các bài báo được xuất bản. Chính vì thế đây là một nguồn học thuật toán rất chất lượng cho bạn.

Trong lời nói đầu, các tác giả viết về cách cuốn sách được viết để trở nên toàn diện và hữu ích trong cả môi trường giảng dạy và chuyên nghiệp. Mỗi chương tập trung vào một thuật toán và thảo luận về các kỹ thuật thiết kế và các lĩnh vực ứng dụng của nó.

Thay vì sử dụng một ngôn ngữ lập trình cụ thể, các thuật toán được viết bằng mã giả . Các mô tả tập trung vào các khía cạnh của chính thuật toán, các thuộc tính toán học của nó và nhấn mạnh hiệu quả.

3. Bộ sách The Art of Computer Programming

The Art of Computer Programming là một bộ sách toàn diện của Donald Knuth bao trùm rất nhiều chủng loại giải thuật lập trình và những phân tích về các thuật toán này.

The Art of Computer Programming tập 1 nói về các thuật toán cơ bản gồm các chương như “Các khái niệm cơ bản” và “Cấu trúc thông tin”.

Tập 2 tác giả nói về các thuật toán tổng hợp với các chương về số ngẫu nhiên và số học.

Tập 3 là tập dành riêng cho thuật toán sắp xếp và tìm kiếm – có thể nói rằng đây là cuốn sách hàng đầu thế giới nói về thuật toán yêu cầu cao này. Sang tập 4A tác giả viết về thuật toán kết hợp.

Dự đinh trong tương lai tác giả sẽ phát hành các tập sách mới nói về các chủ đề tiếp theo như tập 4B – Thuật toán kết hợp với hai chương tìm kiếm kết hợp và Đệ quy. Tập 5 – Thuật toán cú pháp (tính đến năm 2017 , ước tính phát hành vào năm 2025) với chương 9 – Quét từ điển (cũng bao gồm tìm kiếm chuỗi và nén dữ liệu ) và chương 10 – Kỹ thuật phân tích cú pháp. Tập 6 tác giả sẽ nói về Lý thuyết về ngôn ngữ không ngữ cảnh và cuối cùng tập 7 là về kỹ thuật biên dịch.

Đây là nguồn tài nguyên tốt nhất cho các bài toán thuật toán điển hình trong hầu hết các khóa học C và C ++ truyền thống. Những người xem và thích lập trình như toán học ứng dụng ắt hẳn sẽ thấy hụt hẫng khi bỏ qua những cuốc sách này.

4. Cuốn Cấu trúc dữ liệu và giải thuật của thầy Đinh Mạnh Tường

Sách này trình bày các cấu trúc dữ liệu (CTDL) và thuật toán. Các kiến thức về CTDL và thuật toán đóng vai trò quan trọng trong việc đào tạo sinh viên IT. Cuốn sạch đựơc hình thành trên cơ sở các bài giảng về CTDL và thuật toán mà thầy đã đọc nhiều năm tại khoa Toán-Cơ-Tin học và khoa Công nghệ thông tin Đại học khoa học tự nhiên, Đại học quốc gia Hà Nội.

Sách bao gồm hai phần. Phần 1 nói về các CTDL, phần 2 nói về thuật toán. Nội dung cuốn sách mô tả CTDL và các thuật toán trong ngôn ngữ Pascal, vì tính sư phạm của nó.

Chương 1 trình bày các khái niệm cơ bản về thuật toán và phân tích thuật toán. Chương 2 trình bày các khái niệm CTDL, mô hình dữ liệu, kiểu dữ liệu trừu tượng (DLTT). Chương 3 trình bày các mô hình dữ liệu, danh sách và các phương pháp cài đặt danh sách (bởi mảng và bởi CTDL danh sách liên kết). Hai kiểu DLTT đặc biệt quan trọng là hàng và ngăn xếp (stack) cũng được xét trong chương này. Chương này cũng trình bày một số ứng dụng của danh sách, hàng, ngăn xếp trong thiết kế thuật toán. Chương 4 trình bày mô hình dữ liệu cây, các phương pháp cài đặt cây, cây nhị phân, cây tìm kiếm nhị phân và cây cân bằng. Chương 5 nói về mô hình dữ liệu tập hợp, các phương pháp cài đặt tập hợp, từ điển và cài đặt từ điển bởi bảng băm, hàng ưu tiên và cài đặt hàng ưu tiên bởi heap. Chương 6 đề cập đến phương pháp cài đặt các dạng bảng khác nhau. Các CTDL ở bộ nhớ ngoài (file băm, file chỉ số, B-cây) được trình bày trong chương 7.

Bonus về các khóa học về thuật toán

1. Thuật toán căn bản tại Tanggiap.net

Khóa học Thuật toán căn bản là tâm huyết của founder Tanggiap.net. Khóa học song ngữ Việt – Anh với phương pháp tiếp cận hiện đại và hệ thống hỗ trợ mạnh mẽ giúp các bạn giải quyết được các bài toán về tư duy.

Cấu trúc bài học sẽ đi từ cơ sở lý thuyết – đưa ra đề bài – tư duy – gợi ý – thực hành – chạy thử code. Rất dễ dàng cho người mới bắt đầu có thể làm quen và thực hành kỹ năng lập trình của mình. Bạn chắc hẳn sẽ thấy bất ngờ với chính bản thân mình sau khi hoàn thành 9 chương với 56 bài học thuật toán cơ bản trong khóa học này.

2. Chuỗi khóa học algorithms của Robert Sedgewick trên Coursera

Khóa học này được tạo bởi thầy Robert Sedgewick – Giáo sư Khoa học Máy tính của William O. Baker tại Princeton, nơi ông là chủ tịch sáng lập của Khoa Khoa học Máy tính và được cung cấp trên Coursena bởi Đại học Princeton – Đây là một trong tám trường đại học của Ivy League.

Nếu bạn không có trở ngại về ngoại ngữ và muốn học qua video thì khóa học này rất phù hợp cho bạn.

Khóa học này bao gồm các kiến thức về các thuật toán và cấu trúc dữ liệu, tập trung vào các ứng dụng và phân tích hiệu suất khoa học về các triển khai Java. Phần I bao gồm các cấu trúc dữ liệu cơ bản, sắp xếp và thuật toán tìm kiếm. Phần II tập trung vào các thuật toán xử lý đồ thị và chuỗi.

Bạn có thể tham gia khóa học theo đường dẫn mình để bên dưới đây:

Tổng kết

Như vậy, trong bài viết này mình đã giải đáp cho các bạn thuật toán là gì, tại sao nên học thuật toán và 4 cuốn sách huyền thoại về thuật toán chất lượng cho các bạn. Thuật toán là một trong những yếu tố quan trọng giúp bạn có thể giải quyết vấn đề tốt hơn và rèn luyện tư duy lập trình nhưng đó không phải là tất cả. Để trở thành một lập trình viên giỏi bạn cần nhiều yếu tố hơn như chăm chỉ luyện tập và học hỏi.

Tùy thuộc vào lĩnh vực vào bạn theo đuổi mà yêu cầu thuật toán mà bạn cần phải đạt sẽ là khác nhau. Chính vì thế nên dù bạn không giỏi thuật toán thì bạn đều có thể làm lập trình tốt tuy nhiên mình vẫn khuyến khích các bạn khi học tập hãy học thật tốt thuật toán.

Nguồn tham khảo: Tanggiap.net