- Donald Knuth trong bài giảng Giáng sinh 2024 tại Stanford đã nói về strong components và weak components của đồ thị có hướng, đồng thời chọn thuật toán strong components của Tarjan là thuật toán ông yêu thích nhất
- Khi co mỗi strong component thành một đỉnh, ta thu được một DAG không chu trình, và thuật toán hoạt động theo luồng tìm sink strong component rồi loại bỏ nó
- Ở đây, weak component không phải là thành phần liên thông khi bỏ qua hướng, mà là một phép phân hoạch tổng quát hơn, gộp lại các strong components để tạo thành linear order
- Thuật toán Tarjan phân biệt tree arc, back arc, loop, forward arc, cross arc trong quá trình DFS, đồng thời thu được cả strong components lẫn sắp xếp topo của chúng
- Điều Knuth nhấn mạnh là sức hấp dẫn không chỉ nằm ở thủ tục mà còn ở cấu trúc dữ liệu sâu sắc được bố trí sao cho đúng lúc có thể truy cập chính xác thông tin cần để ra quyết định
Điểm khởi đầu của bài giảng và cuốn sách mới của Knuth
- Phần cập nhật đầu bài giảng xoay quanh cuốn sách mới Constraint Satisfaction
- Ông đã gửi bản thảo nội bộ cho nhà xuất bản vào ngày hôm trước, và hiện cũng đã có thể đặt trước
- Có thể sẽ khó in xong trước Giáng sinh, và ngày phát hành chính thức có vẻ là 3 tháng 2
- Trong sách ghi là in vào tháng 1, và đây là dự án lớn của Knuth trong 5 năm qua
- Nội dung chi tiết hơn về chủ đề lần này, Strong Components and Weak Components, có trong pre-fascicle 12A
- Hiện bộ sách đang ở volume 4 Fascicle 7, còn các fascicle trước đó đã được xuất bản bìa cứng dưới dạng volume 4A và 4B
- Phần này về sau sẽ trở thành một phần ba đầu tiên của volume 4C
- Phụ đề của bài giảng gần như là “Which algorithm do you love the most?”
- Knuth nói rằng ông thường không thích câu hỏi buộc phải chọn “thuật toán yêu thích”, nhưng trong trường hợp này câu trả lời rõ ràng là thuật toán strong components của Tarjan
- Khi học thủ tục này vào năm 1973, ông lần đầu hiểu rằng cấu trúc dữ liệu cũng có thể “sâu sắc” như định lý hay thuật toán
Khác biệt giữa strong component và weak component
- Đồ thị có hướng gồm các đỉnh và các mũi tên có hướng
- Nếu hai đỉnh u, v đều đi tới được nhau thì chúng thuộc cùng một strong component
- Các đỉnh nằm trong chu trình đều thuộc cùng một strong component
- Một đỉnh có thể tự tạo thành một strong component riêng, dù có nhiều đường đi vào từ nơi khác nhưng không thể đi ra ngoài
- Weak component theo cách dùng của Knuth khác với undirected component khi bỏ qua hướng
- Ông cho rằng thành phần liên thông khi bỏ qua hướng nên được gọi là “undirected component”
- Weak component là khái niệm phân hoạch lại DAG thu được sau khi co các strong components, sao cho toàn bộ trở thành một thứ tự tuyến tính
- Nếu co mỗi strong component thành một “super vertex” thì ta được đồ thị không có chu trình
- Có thể xem nó như một thứ tự bộ phận (partial order)
- Nếu co tiếp theo weak components thì sẽ thành total order hoặc linear order
- Khái niệm này cũng liên hệ trực tiếp với sắp xếp topo
- Nếu một đỉnh x trong mọi topological sorting luôn đứng trước y thì hai đỉnh thuộc các weak component khác nhau
- Nếu trong một cách sắp xếp thì x đứng trước y, còn trong cách khác thì y đứng trước x, thì chúng thuộc cùng một weak component
- Knuth liên hệ điều này với mutual incomparability
Lịch sử của khái niệm và thuật toán
- Khái niệm weak component xuất hiện trong quá trình trao đổi thư từ giữa Knuth, Ron Graham và một giáo sư được ghi là Mazkin về một bài toán khác
- Trong lá thư Mazkin gửi Graham ngày 28 tháng 2 năm 1970 đã có nội dung về việc phân hoạch để thu được total order
- Tháng 12 năm 1970, Knuth viết cho Graham rằng cả ba người đều đã chứng minh được kết quả tổng quát hơn bằng những cách tiếp cận khác nhau
- Knuth quyết định đưa Mazkin vào làm đồng tác giả, nhưng ngay sau đó nhận tin Mazkin đột ngột qua đời vì đau tim
- Bài báo liên quan được đăng năm 1972 trên Discrete Mathematics volume 2 number 1
- Khi đó Discrete Mathematics là một tạp chí mới ra mắt, và chưa ai đoán được sau này nó sẽ đăng nhiều bài báo xuất sắc đến vậy
- Thuật toán strong components của Tarjan được đăng năm 1972 trên SIAM Journal on Computing volume 1 number 2
- Khi ấy Tarjan còn là nghiên cứu sinh, và bài báo đó là công bố thứ 6 trong danh mục publication của ông
- Knuth đọc bài báo này vào tháng 1 năm 1973 và từ đó rất yêu thích thuật toán
- Sách giáo khoa thuật toán của Aho, Hopcroft, Ullman cũng trình bày rất tốt thuật toán Tarjan
- Hopcroft trong kỳ nghỉ sabbatical tại Stanford đã chung văn phòng với Tarjan và cùng nghĩ ra nhiều thuật toán
- Hopcroft đã có ý tưởng về thuật toán biconnected components cho undirected graph, còn Tarjan áp dụng ý tưởng tương tự cho strong components của directed graph
- Sách của Shimon Even bàn về low point trong thuật toán Tarjan
- Có vẻ như để tìm component thì cần low point, còn để tính low point lại phải biết component, và Tarjan đã tháo gỡ được vòng luẩn quẩn đó
Cách tìm strong components bằng DFS
- Knuth ví việc duyệt đồ thị như thám hiểm hang động
- Mỗi room là một vertex, và danh sách các room khác có thể đi tới từ đó là các outgoing arc
- Máy tính không nhìn hình vẽ mà chỉ dựa vào danh sách vertex và danh sách arc để duyệt
- Phương pháp duyệt cơ bản là depth-first search
- Đi sâu theo một outgoing arc chưa từng xem
- Khi không còn chỗ để đi tiếp thì quay lại vị trí trước đó
- Khi gặp một vertex đã thăm thì xác định loại arc đó
- Trong DFS, arc được chia thành năm loại
- tree arc: arc trong cây DFS được tạo khi lần đầu phát hiện một vertex mới
- back arc: arc quay trở lại một ancestor
- loop: arc trỏ vào chính nó và không ảnh hưởng đến strong components
- forward arc: arc hướng tới một descendant
- cross arc: arc hướng tới một vertex không phải ancestor cũng không phải descendant
- Mỗi khi phát hiện một strong component, thuật toán tìm sink component của phần đồ thị còn lại
- Một DAG hữu hạn luôn có ít nhất một sink
- Ta loại bỏ sink strong component đó rồi tiếp tục tìm trong phần đồ thị còn lại
- Trong quá trình này, thuật toán vừa tìm strong components vừa thu được topological sort của chúng
- Hiệu năng được mô tả là rất nhanh
- Với M arc và N vertex, trong trường hợp xấu nhất số lần truy cập bộ nhớ vào cỡ 5M + 17N
- Con số này đã tính cả những việc như kiểm tra cuối danh sách arc hay cập nhật pointer
Weak components, bản cải tiến và triển khai
- Thuật toán weak components cũng có thể chạy cùng lúc với quá trình tìm strong components
- Nó tận dụng việc strong components được phát hiện từ phải sang trái, tức từ sink trở đi
- Khi một strong component mới xuất hiện ở bên trái, cần xác định nó sẽ gộp với các weak components hiện có như thế nào
- Việc xác định weak component phụ thuộc vào source và sink bên trong mỗi component
- Mọi sink của một weak component phải có arc tới mọi source của weak component kế tiếp
- Đây là điều kiện cần và đủ để tồn tại các weak components
- Khi lập trình, chỉ cần theo dõi source cũng có thể cập nhật được
- Năm 1974, Tarjan công bố một bài báo thuật toán dài 3 trang về việc tìm weak components trên Information Processing Letters volume 3 number 1
- Knuth đã tổng hợp nội dung này trong pre-fascicle 12A của mình
- Việc duy trì cấu trúc dữ liệu đủ tốt để bảo đảm worst-case linear time không hề đơn giản
- Dijkstra cũng từng xử lý bài toán strong components
- Chương 25 trong sách của Dijkstra có tiêu đề “Finding the maximal strong components in a directed graph”
- Dijkstra cũng dùng cấu trúc loại bỏ dần sink strong component, nhưng chưa đi tới được sự đơn giản hóa bằng low point của Tarjan
- Lời giải của Dijkstra đưa thêm bốn array mới để theo dõi cấu trúc
- Gần đây, Knuth và Tarjan đã xem lại các thuật toán cũ để tạo ra định nghĩa tốt hơn và bản cải tiến
- Họ chỉnh sửa dựa trên ý tưởng từ thập niên 1970 của Kurki-Suonio, nhưng bài báo gốc có một fallacy
- Họ giảm số lần truy cập từ khoảng 7 lần mỗi arc xuống còn khoảng 5 lần
- Một số field được gộp lại để tạo thành dạng phức tạp hơn nhưng nhanh hơn, và Knuth đùa rằng đây không phải “premature optimization” mà là “post-mature optimization”
- Phần triển khai được cung cấp dưới dạng chương trình CWEB
- Ông nhắc đến các tên chương trình Tarjan strong and weak và Tarjan strong
- Đầu vào là graph theo định dạng Stanford GraphBase
- Knuth nói sẽ sắp xếp lại các chương trình trên website để dễ tìm hơn, đồng thời sửa tình trạng chưa được cập nhật từ sau năm 2022
- Stanford GraphBase có một ví dụ directed graph dùng khoảng 1.000 category trong thesaurus của Roget làm vertex, còn quan hệ synonym hoặc antonym làm arc
1 bình luận
Ý kiến trên Hacker News
Khi ghé thăm San Francisco vào năm 2022, lúc đang đi dạo quanh khuôn viên Stanford và sắp bước ra sau khi đi qua hành lang yên tĩnh, trống vắng của các tòa nhà mùa hè, tôi tình cờ nhìn thấy văn phòng của Knuth
Nó nhỏ đến mức đáng ngạc nhiên so với danh tiếng của ông, nên tôi phải nhìn lại, nhưng ngược lại lại khiến tôi cảm thấy đó là một không gian rất hợp với tính cách giản dị của ông
https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
Tôi cũng có không phải một mà là hai tấm séc thưởng. Chỉ là những lỗi in nhỏ, nhưng việc có hai tài liệu này thực sự rất tuyệt
Chắc sẽ không ai lạm dụng đâu, nhưng nếu biết ảnh văn phòng của mình bị đăng lên mà mình không hề hay biết thì tôi sẽ thấy khá rợn người
Tôi đọc TAOCP 4A và 4B lúc rảnh và thực sự rất xuất sắc, cực kỳ đáng đọc
Với đa số lập trình viên thì có thể không quá thực dụng, nhưng cách Knuth thiết kế và giải thích thuật toán thì đáng kinh ngạc và độc nhất vô nhị
Đặc biệt, phần hiện thực Dancing Links trong 4B đã được cập nhật đáng kể kể từ bài báo nổi tiếng đó, và đây là một cấu trúc dữ liệu tinh xảo, đẹp mắt mà cũng rất nhanh. Ở tuổi ngoài 80 mà vẫn còn ghê gớm như vậy
Khi tính chi phí cần thiết cho quy mô của chúng tôi, con số lên tới hàng chục triệu USD, trong khi toàn bộ ngân sách hạ tầng của Route 53 chỉ ở mức vài chục nghìn USD. Ở biên mạng, chúng tôi tái sử dụng các máy chủ CloudFront bị hỏng ổ cứng làm máy chủ tên miền, máy chủ API cũng rất đơn sơ, và cả nhóm chỉ khoảng 6 người. Cách làm kiểu AWS là “cố đến cùng”: gần như không tiêu tiền, giảm rủi ro phía dưới, và hoàn thành thật nhanh
Vì vậy, chúng tôi không thể xin hàng chục triệu USD cho packet scrubber, mà việc giao hàng cũng sẽ rất lâu và có thể khiến chúng tôi phụ thuộc quá nhiều vào một nhà cung cấp cụ thể
Ban đầu, chúng tôi quyết định vận hành các máy chủ tên miền của Route 53 trên một dải IP chuyên dụng để có mức cô lập nhất định, và bằng các liên kết mạng chuyên dụng có thể tránh để hạ tầng khác của Amazon bị ảnh hưởng. Nhưng điều đó không giải quyết được chuyện các khách hàng Route 53 vẫn cùng chung số phận với nhau, và kế hoạch thực tế chỉ là kiểu “nếu có sự cố thì hãy lọc thật tốt bằng các công cụ mạng và hệ thống sẵn có”
Đầu mùa hè năm đó, tôi đang đọc bản fascicle mới nhất liên quan tới 4A của Knuth và bị cuốn vào các thuật toán tổ hợp, thì một đêm chợt “lóe lên” ý tưởng rằng nếu tạo ra rất nhiều máy chủ tên miền ảo, ta có thể gán cho mỗi khách hàng một tổ hợp gồm bốn máy chủ tên miền ảo là duy nhất. Mức độ chồng lặp cũng có thể được kiểm soát, và tôi nhanh chóng tính ra rằng với khoảng 2.000 máy chủ tên miền, có thể bảo đảm bất kỳ hai khách hàng nào cũng không chia sẻ quá hai máy chủ. Thử nghiệm cho thấy miền vẫn phân giải tốt ngay cả khi hai máy chủ tên miền không thể truy cập, nhưng từ mức đó trở lên thì sẽ có vấn đề, nên con số này rất quan trọng
Thuật toán tìm kiếm đệ quy để gán IP được truyền cảm hứng trực tiếp từ một thuật toán trong 4A, và còn cung cấp thêm hai chiều cô lập độc lập đối với miền của khách hàng. Khách hàng nhận bốn máy chủ tên miền từ bốn “stripe” độc lập, tương ứng với các tên miền cấp cao nhất khác nhau dùng trong tên máy chủ tên miền như co.uk, com, net, org. Vì vậy, nếu một trong các tên miền cấp cao nhất đó gặp sự cố như lỗi DNSSEC, thì cũng chỉ ảnh hưởng đến một máy chủ tên miền
Ngoài ra, chúng còn đến từ bốn “braid” độc lập, nên có thể bảo đảm rằng không có hai máy chủ tên miền nào cùng dùng chung một tuyến mạng cụ thể hay cùng phần cứng vật lý. Dù đã biết về tổ hợp học từ nền tảng thống kê và mật mã học, có lẽ tôi đã không thể nghĩ ra thiết kế này nếu chưa đọc 4A
Chưa từng có giải pháp nào khiến tôi phấn khích đến vậy. Về cơ bản, nó cung cấp mức cô lập có thể chứng minh được ở cấp IP mạng giữa các miền khách hàng mà hầu như không cần thêm chi phí hạ tầng. Đó là toán học. Không hoàn toàn miễn phí, vì chúng tôi phải dùng 2.000 địa chỉ IP anycast, và còn phải đăng ký 512 miền do cách nhiều tên miền cấp cao nhất yêu cầu đăng ký máy chủ tên miền và glue record. Quá trình làm việc với các nhà đăng ký khá thú vị, nhưng cuối cùng chúng tôi vẫn làm được
Chúng tôi đặt tên cách này là Shuffle Sharding, và nó gần với một khám phá hơn là một phát minh. Nhiều hệ thống đa thuê dùng phân bổ ngẫu nhiên sẽ có được một dạng shuffle sharding nào đó, và các kỹ thuật lọc mạng như Stochastic Fair Blue cũng tạo hiệu ứng tương tự bằng băm theo thời gian. Nhưng tôi chưa từng thấy đúng cách làm này với mức độ kiểm soát như chúng tôi có thể áp dụng, và nó còn có thể mở rộng thành shuffle sharding lồng nhau theo kiểu đệ quy để cô lập ở nhiều tầng hơn, không chỉ người gọi mà cả người gọi của người gọi trong các mẫu “gọi thay”
Vài năm sau, với lòng biết ơn, tôi đã trực tiếp đến xem bài giảng Giáng sinh của Knuth và ngồi ở hàng đầu. Vì không biết điều gì sẽ truyền cảm hứng cho mình, đến giờ tôi vẫn đọc mọi thứ Knuth công bố. Kể cả các bản nhạc organ
Vì thế tôi cho rằng sách của Knuth thực sự đáng ngạc nhiên ở tính thực dụng đối với lập trình viên. Chúng mở rộng tư duy và đào sâu hiểu biết; còn mong gì hơn nữa
Bài báo Dancing Links gốc là một trong những bài tôi thích nhất. Những câu như “Quá trình này khiến các biến con trỏ trong cấu trúc dữ liệu toàn cục thực hiện một điệu nhảy được biên đạo tinh vi” cho thấy tình yêu thuật toán của Knuth rõ mồn một
Tôi đang dùng nó để tạo ô chữ, theo cách các từ ngang và dọc tạo thành một exact cover của lưới
Tôi tò mò liệu thuật toán cập nhật có dùng ít bộ nhớ hơn không
Tôi ước tính bài toán lớn này có khoảng 100 triệu nghiệm, và ngay cả khi tìm được 100 nghiệm mỗi giây thì cũng mất khoảng mười ngày mới xong
Bài toán tôi đang làm là đếm số cách trong ‘Fancy Tetris Houten Puzzel’ mà các mảnh cùng màu đều nối liền với nhau bằng cách chia sẻ ít nhất một cạnh
Tôi cũng đang cân nhắc các thuật toán khác ít nhạy cảm với bộ nhớ hơn để giải bài toán exact cover này
Tôi hỏi từ góc nhìn của người mới chỉ gần đây mới bắt đầu đọc các tài liệu về khoa học máy tính
Vài năm trước khi đến San Francisco, tôi đã ngạc nhiên khi biết Donald Knuth không chỉ vẫn còn sống mà còn tiếp tục giảng thường niên ở Stanford
Đêm đó, khi tìm đến đúng tòa nhà trong khuôn viên trường và trực tiếp xem ông nói về một chủ đề gần như không thể theo kịp, là một kỷ niệm tôi sẽ còn nhớ rất lâu. Donald Knuth thật sự là một huyền thoại
Một thành viên trong nhóm tôi tháng trước đã tìm ra lỗi trong Seminumerical Algorithms và nhận được tấm séc thưởng trị giá 1 hexadecimal dollar, kèm theo bản in email gốc có chú thích viết tay
Điều truyền cảm hứng nhất ở Donald Knuth đối với tôi là sự tận tâm và kỷ luật kéo dài suốt nhiều thập kỷ
Với một người cứ liên tục đổi dự án, ngôn ngữ và bản phân phối, tôi thật sự có rất nhiều điều để học từ ông
Trang phục rất sắc nét và sống động, trông như y phục truyền thống/dân gian từng được mặc ở một ngôi làng xưa; nhưng tôi không rõ là kiểu Iran, kiểu Slav hay đâu đó ở giữa
Có ai đoán chính xác hơn không?
Ký ức của tôi khá mơ hồ, và có thể còn liên quan đến vợ ông nữa. Có vẻ ông mặc nó khá thường xuyên trong các buổi nói chuyện từ giữa thập niên 2010 trở đi, nên chắc hẳn ở đâu đó có giải thích
Năm 2012 tôi từng ở cạnh Knuth khi ông định trèo lên bệ cửa sổ để xem đuốc Olympic đi vào quảng trường trước Manchester Town Hall. Tôi đã nói chuyện với ông, và trong khoảnh khắc còn đưa tay ra vì sợ ông ngã ra ngoài cửa sổ, nhưng rồi không sao cả. Ông để lại cho tôi cảm giác là một người đầy tò mò, với những câu hỏi và trí tuệ tỏa sáng, và trông trẻ hơn tuổi
Cả hai chúng tôi khi đó đều đang tham dự sự kiện kỷ niệm 100 năm ngày sinh Alan Turing, và tôi rất ngạc nhiên khi thấy trong cùng một căn phòng có Knuth, Gary Kasparov, Fred Brooks, Vint Cerf cùng nhiều nhân vật lớn của khoa học máy tính khác. Đến giờ nghỉ trưa, đuốc Olympic đi vào quảng trường bên ngoài, và ông không thể cưỡng lại mà phải đi xem. Có vẻ ông là người duy nhất thực sự hào hứng với chuyện đó
Tối hôm ấy ông diễn thuyết trong bữa tiệc, và sau này khi 4B vừa ra mắt, tôi gặp lại ông ở Manchester; khi nhờ ông ký sách, ông mơ hồ nhận ra tôi từ sự kiện trước đó
Tôi kể câu chuyện này vì tôi nghĩ chiếc áo của ông gợi lên một tâm hồn còn dung hòa và hiếu kỳ hơn nhiều. Tôi chắc chắn đã thấy bằng chứng của điều đó ở những nơi khác nữa
Vì vậy có thể tình cảm của ông với trang phục truyền thống Sami bắt nguồn từ đó
[0]: https://youtu.be/jB0aeePskBg
https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...
Vừa kiểm tra thì ông 87 tuổi. Donald Knuth sinh ngày 10 tháng 1 năm 1938
Wow
Knuth vẫn thật đáng kinh ngạc
Tuy vậy, việc ở Stanford mà không ai lo nổi phần thu âm tương xứng với tầm vóc của tài liệu này thì thật rất bất ngờ và đáng thất vọng. Nghe như thể ai đó thu bằng máy ghi âm bỏ túi trong túi áo
Không phải tôi nói về giọng già nua của Knuth; chỉ cần nghe đoạn ông dừng lại để nhận câu hỏi từ khán giả là sẽ thấy chất lượng âm thanh tệ đến mức nào
Những video như thế này khiến tôi nhớ vì sao ngay từ đầu mình lại yêu máy tính
Việc ông vẫn còn sắc sảo như vậy khá đáng kinh ngạc. Tiếc là hồi tôi còn là sinh viên đại học hơn 20 năm trước, ông đã không còn giảng dạy nữa
Tôi thích cách ông xử lý câu hỏi: https://youtu.be/Hi8r_63LGyg?t=827
Ông dành thời gian để hiểu người ta đang hỏi gì, rồi trả lời rất rõ ràng