Từ điển Thuật toán và Cấu trúc Dữ liệu (Dictionary of Algorithms and Data Structures)

 (xlinux.nist.gov)
3 điểm bởi GN⁺ 2023-09-30 | 1 bình luận | Chia sẻ qua WhatsApp
  • Từ điển trực tuyến tổng hợp và sắp xếp thuật toán, các kỹ thuật thuật toán, cấu trúc dữ liệu, các bài toán điển hình và các định nghĩa liên quan
  • Bao gồm các mục thuật toán như những hàm phổ biến như Ackermann's function
  • Bao gồm các mục bài toán điển hình như traveling salesman, Byzantine generals
  • Một số mục cung cấp liên kết đến triển khai (implementation) và thông tin bổ sung, các mục được sắp xếp theo chỉ mục dựa trên lĩnh vực (area) và loại (type)
  • Loại trừ một số lĩnh vực cụ thể như business data processing, AI, graphics và tập trung vào thuật toán và cấu trúc dữ liệu "tổng quát (general)"

Tổng quan về trang web và đơn vị vận hành

  • Được lưu trữ bởi Software and Systems Division thuộc Information Technology Laboratory của NIST
  • Việc phát triển từ điển bắt đầu vào năm 1998 dưới sự biên tập của Paul E. Black
  • Có dạng từ điển, bao quát thuật toán, các kỹ thuật thuật toán, cấu trúc dữ liệu, các bài toán điển hình và các định nghĩa liên quan

Cấu thành các mục nội dung

  • Các mục thuật toán bao gồm những hàm phổ biến như Ackermann's function
  • Các mục bài toán bao gồm traveling salesman, Byzantine generals
  • Một số mục cung cấp liên kết đến triển khai (implementation) và thông tin bổ sung
  • Trang chỉ mục liệt kê các mục theo lĩnh vực (area) và loại (type)
  • two-level index có dung lượng tải xuống toàn bộ chỉ bằng 1/20 trang này

Hướng dẫn sử dụng

  • Cấm sử dụng cho mục đích gian lận (cheat), giáo viên cần hỗ trợ thì được hướng dẫn liên hệ
  • Đề xuất, chỉnh sửa và ý kiến được hướng dẫn gửi cho Paul Black

Phạm vi không bao gồm

  • Hiện tại chưa bao gồm các thuật toán chuyên biệt cho các lĩnh vực sau
    • business data processing, communications, operating systems hoặc distributed algorithms
    • programming languages, AI, graphics, numerical analysis
  • Phạm vi được giới hạn vì chỉ riêng thuật toán và cấu trúc dữ liệu "tổng quát (general)" cũng đã đủ khó để bao quát

Chỉ mục và ghi chú tham khảo

  • Các thuật ngữ có biến đứng trước như n-way, m-dimensional, p-branching được phân loại dưới mục k-
  • Có thể tìm các mục hữu ích trong A Glossary of Computer Oriented Abbreviations and Acronyms

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-09-30
Ý kiến trên Hacker News

  • Các bài viết liên quan trước đây:
    Dictionary of Algorithms and Data Structures (1998) - https://news.ycombinator.com/item?id=12758176 - tháng 10/2016 (18 bình luận)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=8905348 - tháng 1/2015 (4 bình luận)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=5525893 - tháng 4/2013 (15 bình luận)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2496539 - tháng 4/2011 (16 bình luận)
    Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2351074 - tháng 3/2011 (1 bình luận)

  • Tôi muốn thích tài liệu này, nhưng trong số những thứ tôi biết thì nó thiếu Fenwick tree và thuật toán/cấu trúc dữ liệu union-find
    Lần đầu tôi thấy Fenwick tree là ở đây: https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s
    union-find thì hình như tôi thấy ở đây: https://www.youtube.com/watch?v=PGZ64ob440I
    Nhưng theo trí nhớ thì đó là bản cài đặt bằng dictionary/hashmap chứ không phải mảng kích thước cố định

    • Có vẻ còn thiếu khá nhiều. Tôi tưởng Fenwick ít nhất cũng có dưới một tên khác, nhưng không thấy; còn việc không có union-find thì càng lạ hơn. Nó là một cấu trúc dữ liệu thật sự tuyệt vời và hữu ích, nên tôi cũng không nghĩ ra tên nào khác mà nó có thể bị giấu dưới đó
      Những thứ tôi nghĩ ra ngay mà không tìm thấy là phân rã căn bậc hai, heavy-light decomposition, và toàn bộ nhóm truy vấn giá trị nhỏ nhất trên đoạn (Range Minimum Query). Cá nhân tôi xếp truy vấn giá trị nhỏ nhất trên đoạn vào nhóm các bài toán tổng quát yêu thích nhất, và xét như một cụm kỹ thuật đáng dành thời gian tập trung thì tôi thấy nó thú vị hơn nhiều so với sắp xếp
      Cấu trúc dữ liệu union-find thường được trình bày bằng mảng cố định, vì như vậy phần phân tích thuật toán thú vị hơn. Nếu chi phí tra cứu vượt quá O(1), phần thú vị trong phân tích sẽ bị che lấp. Tất nhiên bản thân cấu trúc dữ liệu thì triển khai theo cách nào cũng hoạt động tốt
    • Vì đây là một bộ sưu tập hữu hạn nên gần như chắc chắn sẽ thiếu hầu hết mọi thứ. soft heap hay finger tree cũng không có, và nhiều cấu trúc dữ liệu thuần hàm mà Okasaki bàn tới cũng bị thiếu

  • Đây là tài liệu tuyệt vời, nhưng tôi mong các lớp cấu trúc dữ liệu và thuật toán tập trung hơn vào ứng dụng
    Tôi quan tâm nhiều hơn đến việc biết vì sao nó hữu ích và trong bối cảnh nào nên đem ra dùng, thay vì chỉ biết nó là gì

    • https://www.redblobgames.com/ là một tài liệu rất hay, cung cấp nhiều bối cảnh mà vẫn không né tránh các chi tiết kỹ thuật
    • Tôi từng viết một bài theo hướng tương tự. Không hẳn là về ứng dụng, mà là một hướng dẫn/cây quyết định để chọn cấu trúc dữ liệu hoặc cách tiếp cận thuật toán nào cho bài toán nào, dựa trên những gì tôi học được khi giải bộ bài Blind 75
      Tôi vẫn chưa phải chuyên gia nên đây không phải tài liệu có thẩm quyền, nhưng có thể sẽ thú vị: https://sebinsua.com/algorithmic-bathwater#what-kind-of-prob...
    • Theo kinh nghiệm của tôi, trong lớp học họ đã làm như vậy rồi. Trọng tâm là độ phức tạp thời gian/không gian của hàm cho trước và phần phân tích
    • Hình như Skiena từng có một bài giảng hay về chủ đề này
    • Biết được bối cảnh và lịch sử chắc chắn khiến mọi thứ thú vị hơn, và thường cũng giúp việc học

  • Một mục gây chú ý: Marlena
    https://xlinux.nist.gov/dads/HTML/marlena.html
    Có ai biết nó nghĩa là gì không?

  • Tôi không chắc một danh sách thuật toán xếp theo thứ tự alphabet có phải điểm khởi đầu tốt cho người học không
    Với người mới bắt đầu hoặc muốn nắm chắc chủ đề này, tôi nghĩ cuốn kinh điển này mới là chuẩn mực.[1]
    Nếu mục tiêu là trưởng thành thành lập trình viên và vượt qua phỏng vấn coding ở FAANG, đây có thể là đòn bẩy mạnh nhất
    [1] https://books.google.com/books/about/Introduction_To_Algorit...

    • Khả năng cao là không phải điểm khởi đầu. Nhưng với tư cách tài liệu tham khảo thì rất tuyệt

  • Tôi tự hỏi nên tìm kiếm ngược danh sách này như thế nào
    Ví dụ có lúc bạn có thể mô tả đại khái cách một thuật toán hoạt động nhưng không biết tên, và muốn biết nó có trong danh sách này không. Ngày nay có thể viết pseudocode rồi đưa cho ChatGPT hỏi tên, nhưng ngoài cách đó thì tôi không rõ

    • Vào Discord hỏi thì sẽ có người cho bạn biết

  • Giá mà họ nhận pull request. Những mục cơ bản như acceleration structure vẫn còn thiếu

  • Tài liệu này thật sự rất hay. Hy vọng nó sống sót qua những thứ như cắt giảm ngân sách, và nên được lưu trữ lại