- Donald Knuth กล่าวถึง strong components และ weak components ของกราฟมีทิศทางในการบรรยายคริสต์มาสปี 2024 ที่ Stanford และยกให้อัลกอริทึม strong components ของ Tarjan เป็นอัลกอริทึมที่เขารักที่สุด
- เมื่อย่อ strong component ให้เป็นจุดยอดเดียว จะได้ DAG ที่ไม่มีวงจร และอัลกอริทึมทำงานในรูปแบบการค้นหา sink strong component แล้วนำออก
- ในที่นี้ weak component ไม่ใช่องค์ประกอบเชื่อมต่อที่ได้จากการละทิศทาง แต่เป็น partition ที่ทั่วไปกว่า ซึ่งจัดกลุ่ม strong components อีกครั้งให้กลายเป็น linear order
- อัลกอริทึมของ Tarjan แยกแยะ tree arc, back arc, loop, forward arc, cross arc ระหว่าง DFS และได้ทั้ง strong components กับ การเรียงลำดับเชิงทอพอโลยี ของมันไปพร้อมกัน
- เสน่ห์ที่ Knuth เน้นไม่ได้อยู่แค่ขั้นตอนเท่านั้น แต่อยู่ที่ โครงสร้างข้อมูลเชิงลึก ที่จัดวางให้เข้าถึงข้อมูลสำหรับการตัดสินใจที่จำเป็นได้ในจังหวะที่พอดี
จุดเริ่มต้นของการบรรยายและหนังสือเล่มใหม่ของ Knuth
- ช่วงต้นของการบรรยายเล่าความคืบหน้าที่สอดคล้องกับหนังสือเล่มใหม่ Constraint Satisfaction
- เขาส่งต้นฉบับภายในให้สำนักพิมพ์เมื่อวันก่อนหน้า และเปิดให้สั่งจองล่วงหน้าได้แล้ว
- อาจพิมพ์ให้เสร็จก่อนคริสต์มาสได้ยาก และวันวางจำหน่ายอย่างเป็นทางการดูเหมือนจะเป็นวันที่ 3 กุมภาพันธ์
- ในหนังสือระบุว่าพิมพ์ในเดือนมกราคม และเป็นโปรเจกต์หลักของ Knuth ตลอด 5 ปีที่ผ่านมา
- รายละเอียดเพิ่มเติมของหัวข้อครั้งนี้ Strong Components and Weak Components อยู่ใน pre-fascicle 12A
- หนังสือปัจจุบันคือ volume 4 Fascicle 7 และ fascicle ก่อนหน้าออกเป็นปกแข็งในชื่อ volume 4A และ 4B
- เนื้อหานี้มีกำหนดจะเป็นหนึ่งในสามส่วนแรกของ volume 4C ในอนาคต
- หัวข้อย่อยของการบรรยายใกล้เคียงกับ “Which algorithm do you love the most?”
- โดยปกติ Knuth ไม่ชอบคำถามให้เลือก “อัลกอริทึมที่ชอบที่สุด” แต่ในกรณีนี้เขาบอกว่า อัลกอริทึม strong components ของ Tarjan คือคำตอบที่ชัดเจน
- เมื่อได้เรียนรู้ขั้นตอนนี้ในปี 1973 เขาเข้าใจเป็นครั้งแรกว่าโครงสร้างข้อมูลก็สามารถ “ลึกซึ้ง” ได้ เช่นเดียวกับทฤษฎีบทหรืออัลกอริทึม
ความแตกต่างระหว่าง strong component กับ weak component
- กราฟมีทิศทางประกอบด้วยจุดยอดและลูกศรที่มีทิศทาง
- ถ้าจุดยอดสองจุด u, v ไปถึงกันและกันได้ ทั้งคู่จะอยู่ใน strong component เดียวกัน
- จุดยอดที่อยู่ในวงจรทั้งหมดจะรวมอยู่ใน strong component เดียวกัน
- จุดยอดที่มีเส้นทางเข้ามาจากหลายที่ แต่ไม่สามารถออกไปข้างนอกได้ อาจเป็น strong component เดี่ยวของตัวเองได้
- weak component ในความหมายที่ Knuth ใช้ ต่างจาก undirected component ที่ได้จากการละทิศทาง
- เขาเห็นว่าควรเรียกองค์ประกอบที่เชื่อมต่อกันเมื่อไม่สนใจทิศทางว่า “undirected component”
- weak component คือแนวคิดที่ partition DAG ซึ่งได้จากการย่อ strong components อีกครั้ง เพื่อให้ภาพรวมกลายเป็นลำดับแบบเส้นตรง
- เมื่อลด strong components แต่ละอันให้เป็น “super vertex” หนึ่งจุด จะได้กราฟที่ไม่มีวงจร
- สามารถมองสิ่งนี้เป็น partial order ได้
- หากย่อต่อจนถึง weak components จะได้ total order หรือ linear order
- เชื่อมโยงโดยตรงกับการเรียงลำดับเชิงทอพอโลยี (topological sorting) ด้วย
- ถ้า x อยู่ก่อน y เสมอในการทำ topological sorting ทุกแบบ ทั้งสองจะอยู่คนละ weak component
- ถ้าในการเรียงแบบหนึ่ง x อยู่ก่อน y แต่ในการเรียงอีกแบบ y อยู่ก่อน x ได้ ทั้งสองจะอยู่ใน weak component เดียวกัน
- Knuth เชื่อมสิ่งนี้กับ mutual incomparability
ประวัติของแนวคิดและอัลกอริทึม
- แนวคิด weak component เกิดขึ้นระหว่างที่ Knuth, Ron Graham และศาสตราจารย์ที่เขียนชื่อว่า Mazkin แลกเปลี่ยนจดหมายกันเกี่ยวกับปัญหาอื่น
- ในจดหมายที่ Mazkin ส่งถึง Graham เมื่อวันที่ 28 กุมภาพันธ์ 1970 มีเนื้อหาเกี่ยวกับการได้ total order ด้วย partition
- ในเดือนธันวาคม 1970 Knuth เขียนถึง Graham ว่าทั้งสามคนพิสูจน์ผลลัพธ์ที่ทั่วไปกว่าด้วยแนวทางที่ต่างกัน
- Knuth ตัดสินใจใส่ Mazkin เป็นผู้เขียนร่วม แต่ไม่นานหลังจากนั้นได้รับข่าวว่า Mazkin เสียชีวิตกะทันหันด้วยอาการหัวใจวาย
- บทความที่เกี่ยวข้องตีพิมพ์ใน Discrete Mathematics volume 2 number 1 ในปี 1972
- ตอนนั้น Discrete Mathematics เป็นวารสารที่เพิ่งเริ่มต้น และไม่มีใครคาดคิดว่าจะมีบทความยอดเยี่ยมมากมายเพียงใดตีพิมพ์ในภายหลัง
- อัลกอริทึม strong components ของ Tarjan ตีพิมพ์ใน SIAM Journal on Computing volume 1 number 2 ในปี 1972
- ตอนนั้น Tarjan เป็นนักศึกษาปริญญาโท และบทความดังกล่าวเป็นลำดับที่ 6 ในรายชื่อผลงานตีพิมพ์ของเขา
- Knuth อ่านบทความนี้ในเดือนมกราคม 1973 และเริ่มชอบอัลกอริทึมนี้
- ตำราอัลกอริทึมของ Aho, Hopcroft, Ullman ก็อธิบายอัลกอริทึมของ Tarjan ไว้อย่างดี
- Hopcroft ใช้ปี sabbatical ที่ Stanford โดยนั่งสำนักงานร่วมกับ Tarjan และคิดค้นอัลกอริทึมหลายอย่าง
- Hopcroft มีไอเดียอัลกอริทึมสำหรับ biconnected components ของ undirected graph และ Tarjan นำไอเดียคล้ายกันไปใช้กับ strong components ของ directed graph
- หนังสือของ Shimon Even กล่าวถึง low point ของอัลกอริทึม Tarjan
- Tarjan แก้สถานการณ์ที่ดูเหมือนเป็นวงวนว่า หากจะหา component ต้องมี low point และหากจะคำนวณ low point ก็ต้องรู้ component
วิธีหา strong components ด้วย DFS
- Knuth เปรียบการสำรวจกราฟกับการสำรวจถ้ำ
- แต่ละ room คือ vertex และรายการ room อื่นที่ไปได้จากแต่ละ room คือ outgoing arc
- คอมพิวเตอร์ไม่ได้เห็นภาพ แต่สำรวจจากรายการ vertex และรายการ arc เท่านั้น
- วิธีสำรวจพื้นฐานคือ depth-first search
- เดินลึกเข้าไปตาม outgoing arc ที่ยังไม่เคยดู
- เมื่อไม่มีที่ให้ไปต่อ ก็ย้อนกลับไปตำแหน่งก่อนหน้า
- เมื่อเจอ vertex ที่เคยเยี่ยมชมแล้ว ก็วินิจฉัยชนิดของ arc นั้น
- ใน DFS arc แบ่งเป็นห้าประเภท
- tree arc: arc ของ DFS tree ที่สร้างขึ้นเมื่อพบ vertex ใหม่เป็นครั้งแรก
- back arc: arc ที่ย้อนกลับไปยัง ancestor
- loop: arc ที่ไปหาตัวเอง และไม่ส่งผลต่อ strong components
- forward arc: arc ที่มุ่งไปยัง descendant
- cross arc: arc ที่มุ่งไปยัง vertex ที่ไม่ใช่ทั้ง ancestor และ descendant
- ทุกครั้งที่อัลกอริทึมค้นพบ strong component จะเป็นการหา sink component ของกราฟที่ยังเหลืออยู่
- finite DAG จะมี sink เสมอ
- ดำเนินการโดยนำ sink strong component ออก แล้วหาอีกครั้งในกราฟที่เหลือ
- ในกระบวนการนี้จะได้ strong components และ topological sort ของมันไปพร้อมกัน
- มีการนำเสนอว่าประสิทธิภาพเร็วมาก
- สำหรับ arc จำนวน M เส้นและ vertex จำนวน N จุด กรณีแย่ที่สุดมี memory access อยู่ที่ระดับ 5M + 17N
- เป็นตัวเลขที่รวมงานอย่างการตรวจจุดสิ้นสุดของรายการ arc และการอัปเดต pointer แล้ว
Weak components, เวอร์ชันปรับปรุง และการติดตั้งใช้งาน
- อัลกอริทึม weak components สามารถดำเนินไปพร้อมกับกระบวนการหา strong components ได้
- ใช้ข้อเท็จจริงที่ว่า strong components ถูกค้นพบจากขวาไปซ้าย กล่าวคือเริ่มจาก sink
- เมื่อ strong component ใหม่เข้ามาทางซ้าย จะตัดสินว่าควรรวมกับ weak components เดิมอย่างไร
- ในการตัดสิน weak component, source และ sink ภายในแต่ละ component มีความสำคัญ
- sink ทั้งหมดของ weak component หนึ่งต้องมี arc ไปยัง source ทั้งหมดของ weak component ถัดไป
- เงื่อนไขนี้เป็นเงื่อนไขจำเป็นและเพียงพอสำหรับการมี weak components
- เมื่อตั้งโปรแกรม สามารถอัปเดตได้โดยติดตามเฉพาะ source
- Tarjan เผยแพร่บทความอัลกอริทึม 3 หน้าเพื่อหา weak components ใน Information Processing Letters volume 3 number 1 เมื่อปี 1974
- Knuth สรุปเนื้อหานี้ไว้ใน pre-fascicle 12A ของเขา
- การรักษา data structure ให้เพียงพอเพื่อรับประกัน worst-case linear time ไม่ใช่เรื่องง่าย
- Dijkstra ก็กล่าวถึงปัญหา strong components เช่นกัน
- บทที่ 25 ในหนังสือของ Dijkstra กล่าวถึง “Finding the maximal strong components in a directed graph”
- Dijkstra ใช้โครงสร้างที่ค่อย ๆ ลบ sink strong component ออก แต่ยังไม่ไปถึงการทำให้ low point ง่ายขึ้นแบบ Tarjan
- วิธีแก้ของ Dijkstra นำ array ใหม่สี่ชุดมาใช้เพื่อติดตามโครงสร้าง
- Knuth และ Tarjan เพิ่งกลับมาดูอัลกอริทึมเดิมอีกครั้ง และสร้างนิยามที่ดีขึ้นกับเวอร์ชันปรับปรุง
- แก้ไขโดยอิงไอเดียของ Kurki-Suonio ในทศวรรษ 1970 แต่บทความต้นฉบับมี fallacy อยู่
- ลดการเข้าถึงจากระดับ 7 ครั้งต่อ arc ในวิธีเดิม เหลือระดับ 5 ครั้ง
- รวม field บางส่วนให้เป็นรูปแบบที่ซับซ้อนกว่าแต่เร็วกว่า และพูดติดตลกว่าไม่ใช่ “premature optimization” แต่เป็น “post-mature optimization”
- การติดตั้งใช้งานมีให้ในรูปแบบ โปรแกรม CWEB
- มีการกล่าวถึงชื่อโปรแกรม Tarjan strong and weak, Tarjan strong
- อินพุตคือ graph ในรูปแบบ Stanford GraphBase format
- Knuth บอกว่าจะจัดระเบียบโปรแกรมบนเว็บไซต์ให้ค้นหาได้ง่ายขึ้น และแก้สถานะที่ไม่ได้อัปเดตมาตั้งแต่ปี 2022
- Stanford GraphBase มีตัวอย่าง directed graph ที่ใช้หมวดหมู่ thesaurus ของ Roget ประมาณ 1,000 หมวดเป็น vertex และใช้ความสัมพันธ์ synonym หรือ antonym เป็น arc
1 ความคิดเห็น
ความคิดเห็นบน Hacker News
ตอนที่ไปเยือน San Francisco ในปี 2022 ระหว่างเดินชมแคมปัส Stanford ผมบังเอิญเห็น ห้องทำงานของ Knuth ตอนกำลังจะเดินออกผ่านโถงทางเดินของอาคารฤดูร้อนที่เงียบและว่างเปล่า
เมื่อเทียบกับชื่อเสียงแล้ว มันเล็กจนน่าประหลาดใจจนต้องหันกลับไปดูอีกครั้ง แต่กลับรู้สึกว่าเป็นพื้นที่ที่เข้ากับบุคลิกเรียบง่ายของเขาเป็นอย่างดี
https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
ผมมีเช็คเงินรางวัลไม่ใช่แค่ใบเดียว แต่สองใบด้วย แม้จะเป็นแค่การพิมพ์ผิดเล็ก ๆ แต่การได้มีเอกสารสองชิ้นนี้ไว้ถือว่าเจ๋งมากจริง ๆ
คงไม่มีใครเอาไปใช้ในทางไม่ดีหรอก แต่ถ้ารู้ว่ารูปห้องทำงานของผมถูกโพสต์ขึ้นมาโดยที่ผมไม่รู้ ผมคงรู้สึกขนลุกพอสมควร
ช่วงเวลาว่างผมกำลังอ่าน TAOCP 4A และ 4B อยู่ และมันยอดเยี่ยมมาก เลยขอแนะนำอย่างยิ่ง
สำหรับโปรแกรมเมอร์ส่วนใหญ่ มันอาจไม่ได้ใช้งานได้จริงนัก แต่วิธีที่ Knuth ออกแบบและอธิบายอัลกอริทึมนั้นน่าทึ่งและมีเอกลักษณ์มาก
โดยเฉพาะการอิมพลีเมนต์ Dancing Links ใน 4B ได้รับการปรับปรุงครั้งใหญ่หลังบทความวิจัยอันโด่งดัง และเป็นโครงสร้างข้อมูลที่ประณีตและงดงาม อีกทั้งยังเร็วมากด้วย แม้อายุ 80 กว่าแล้วก็ยังสุดยอด
พอคำนวณต้นทุนที่จำเป็นสำหรับสเกลของเราแล้วได้ออกมาเป็นหลายสิบล้านดอลลาร์ แต่ทั้งงบโครงสร้างพื้นฐานของ Route 53 อยู่ระดับหลักหมื่นดอลลาร์เท่านั้น ที่ edge เรานำเซิร์ฟเวอร์ CloudFront ที่ฮาร์ดดิสก์เสียกลับมาใช้เป็น nameserver และ API server ก็เรียบง่าย ทีมมีประมาณ 6 คน แนวทาง “กัดไม่ปล่อย” แบบ AWS คือใช้เงินให้น้อยที่สุด ลดความเสี่ยงด้านล่าง และทำให้เร็ว
ดังนั้นเราจึงขอเงินหลายสิบล้านดอลลาร์เพื่อซื้อ packet scrubber ไม่ได้ อีกทั้งของกว่าจะมาถึงก็ใช้เวลานาน และอาจทำให้พึ่งพา vendor รายใดรายหนึ่งมากเกินไป
ช่วงแรกเราตัดสินใจรัน nameserver ของ Route 53 บนช่วง IP เฉพาะเพื่อแยกออกระดับหนึ่ง และใช้ลิงก์เครือข่ายเฉพาะเพื่อไม่ให้โครงสร้างพื้นฐานอื่นของ Amazon ได้รับผลกระทบได้ แต่ก็ยังแก้ปัญหาที่ลูกค้า Route 53 ต้องร่วมชะตากันไม่ได้ และแผนจริง ๆ ก็ประมาณว่า “ถ้าเกิดปัญหา ก็กรองให้ดีมาก ๆ ด้วยเครื่องมือเครือข่ายและระบบที่มีอยู่”
ต้นฤดูร้อนปีนั้น ผมกำลังหมกมุ่นกับ combinatorial algorithms ระหว่างอ่าน fascicle ล่าสุดเกี่ยวกับ 4A ของ Knuth แล้วคืนหนึ่งก็เกิดไอเดีย “ปิ๊ง” ขึ้นมาว่า ถ้าสร้าง nameserver เสมือนจำนวนมาก ก็สามารถจัดชุด nameserver เสมือน 4 ตัวให้ลูกค้าแต่ละรายแบบไม่ซ้ำกันได้ ระดับการซ้อนทับกันก็ยังควบคุมได้ และคำนวณคร่าว ๆ ได้อย่างรวดเร็วว่า หากมี nameserver ประมาณ 2,000 ตัว จะรับประกันได้ว่าลูกค้าสองรายใด ๆ จะใช้ร่วมกันไม่เกิน 2 ตัว จากการทดลอง โดเมนยัง resolve ได้ดีแม้ nameserver สองตัวติดต่อไม่ได้ แต่ถ้ามากกว่านั้นจะเริ่มมีปัญหา ตัวเลขนี้จึงสำคัญ
อัลกอริทึมค้นหาแบบ recursive สำหรับจัดสรร IP ได้แรงบันดาลใจโดยตรงจากอัลกอริทึมใน 4A และยังให้มิติการแยกส่วนที่เป็นอิสระจากโดเมนลูกค้าเพิ่มอีกสองมิติ ลูกค้าจะได้รับ nameserver 4 ตัวจาก “stripe” อิสระ 4 ชุด ซึ่งสอดคล้องกับ top-level domain ต่างกันที่ใช้ในชื่อ nameserver (co.uk, com, net, org) ดังนั้นหากหนึ่งใน top-level domain เหล่านั้นมีปัญหา เช่น ความผิดพลาดเกี่ยวกับ DNSSEC ก็จะกระทบ nameserver เพียงตัวเดียว
นอกจากนี้ยังให้ออกมาจาก “braid” อิสระ 4 ชุด ทำให้รับประกันได้ว่า nameserver สองตัวใด ๆ จะไม่ใช้เส้นทางเครือข่ายหรือฮาร์ดแวร์ทางกายภาพร่วมกัน แม้ผมจะรู้ combinatorics จากพื้นฐานด้านสถิติและวิทยาการเข้ารหัสลับอยู่แล้ว แต่ถ้าไม่ได้อ่าน 4A ก็คงออกแบบแบบนี้ไม่ได้
ผมไม่เคยตื่นเต้นกับวิธีแก้ปัญหาไหนเท่านี้มาก่อน เพราะมันให้การแยกกันได้ในระดับ IP เครือข่ายระหว่างโดเมนลูกค้าแบบพิสูจน์ได้ โดยแทบไม่มีต้นทุนโครงสร้างพื้นฐานเพิ่มเติมเลย มันคือคณิตศาสตร์ แน่นอนว่าไม่ได้ฟรีสนิท เพราะต้องใช้ที่อยู่ anycast IP 2,000 รายการ และด้วยวิธีที่ top-level domain หลายแห่งกำหนดให้ต้องจดทะเบียน nameserver กับ glue record เราจึงต้องจดทะเบียนโดเมน 512 โดเมนด้วย ขั้นตอนจัดการกับ registrar ค่อนข้างสนุก แต่สุดท้ายก็ทำสำเร็จ
เราตั้งชื่อวิธีนี้ว่า Shuffle Sharding และมันใกล้เคียงกับการค้นพบมากกว่าการประดิษฐ์ขึ้น ระบบ multi-tenant จำนวนมากที่ใช้การจัดวางแบบสุ่มย่อมได้ shuffle sharding รูปแบบหนึ่งอยู่แล้ว และเทคนิคกรองเครือข่ายอย่าง Stochastic Fair Blue ก็ให้ผลคล้ายกันด้วย hashing ตามเวลา แต่ผมไม่เคยเห็นวิธีที่เหมือนกันซึ่งมีระดับการควบคุมเท่าที่เราสามารถนำมาใช้ได้ และมันยังขยายไปเป็น nested shuffle sharding แบบ recursive เพื่อแยกได้หลายระดับมากขึ้น ไม่ใช่แค่ผู้เรียก แต่รวมถึงผู้เรียกของผู้เรียกในแพตเทิร์น “เรียกแทน” ด้วย
หลายปีต่อมา ด้วยความขอบคุณ ผมไปชมปาฐกถาคริสต์มาสของ Knuth ด้วยตัวเองและนั่งแถวหน้า ทุกวันนี้ผมยังอ่านทุกอย่างที่ Knuth เผยแพร่ เพราะเราไม่รู้ว่าอะไรจะให้แรงบันดาลใจได้ รวมถึงเพลงออร์แกนของเขาด้วย
ดังนั้นผมมองว่าหนังสือของ Knuth ใช้งานได้จริงอย่างน่าทึ่งสำหรับโปรแกรมเมอร์ มันขยายวิธีคิดและทำให้ความเข้าใจลึกขึ้น จะต้องการอะไรมากกว่านั้นอีก
บทความวิจัย Dancing Links ต้นฉบับเป็นหนึ่งในบทความที่ผมชอบที่สุด ประโยคอย่าง “กระบวนการนี้ทำให้ตัวแปรพอยน์เตอร์ในโครงสร้างข้อมูลส่วนกลางเต้นรำอย่างประณีตตามท่าเต้นที่ออกแบบไว้” ทำให้เห็นความรักในอัลกอริทึมของ Knuth ชัดเจนมาก
ผมใช้มันสร้างปริศนาอักษรไขว้ โดยทำให้คำแนวนอนและแนวตั้งประกอบกันเป็น exact cover ของกริด
อยากรู้ว่าอัลกอริทึมที่ปรับปรุงแล้วใช้หน่วยความจำน้อยลงไหม
สำหรับปัญหาใหญ่นี้ คาดว่าน่าจะมีคำตอบประมาณ 100 ล้านแบบ และแม้จะหาได้ 100 แบบต่อวินาที ก็ต้องใช้เวลาประมาณสิบวันกว่าจะจบ
ปัญหาที่ผมกำลังทำคือการนับจำนวนกรณีใน ‘Fancy Tetris Houten Puzzel’ ที่ชิ้นส่วนสีเดียวกันทั้งหมดเชื่อมต่อกันโดยมีอย่างน้อยหนึ่งด้านติดกัน
ผมก็กำลังคิดถึงอัลกอริทึมอื่นที่ไวต่อการใช้หน่วยความจำน้อยกว่าสำหรับแก้ปัญหา exact cover นี้อยู่
ถามในฐานะคนที่เพิ่งเริ่มอ่านวรรณกรรมด้านวิทยาการคอมพิวเตอร์เมื่อไม่นานมานี้
เมื่อไม่กี่ปีก่อนตอนผมไป San Francisco ผมประหลาดใจที่รู้ว่า Donald Knuth ไม่เพียงยังมีชีวิตอยู่ แต่ยังบรรยายประจำทุกปีที่ Stanford ด้วย
คืนนั้นที่ผมเดินหาอาคารในแคมปัส แล้วได้นั่งดูเขาพูดเรื่องที่แทบตามไม่ทันด้วยตาตัวเอง จะยังอยู่ในความทรงจำไปอีกนาน Donald Knuth เป็น ตำนาน จริง ๆ
เพื่อนร่วมทีมของผมพบข้อผิดพลาดใน Seminumerical Algorithms เมื่อเดือนที่แล้ว และได้รับเช็ครางวัล 1 hexadecimal dollar พร้อมสำเนาอีเมลต้นฉบับที่มีหมายเหตุเขียนด้วยลายมือแนบมาด้วย
สิ่งที่สร้างแรงบันดาลใจให้ผมมากที่สุดจาก Donald Knuth คือ ความทุ่มเทและวินัย ที่ดำเนินมาตลอดหลายสิบปี
ในฐานะคนที่เปลี่ยนโปรเจกต์ ภาษา และดิสทริบิวชันไปเรื่อย ๆ ผมมีอะไรให้เรียนรู้จากเขาเยอะมาก
เสื้อผ้ามีสีสันสดใสและดูมีชีวิตชีวามาก เหมือนชุดประจำชาติ/พื้นเมืองที่คนในหมู่บ้านสมัยก่อนใส่กัน แต่ไม่แน่ใจว่าเป็นแบบอิหร่าน แบบสลาฟ หรืออยู่ตรงไหนระหว่างนั้น
มีใครพอเดาได้ดีกว่านี้ไหม?
ความทรงจำเลือน ๆ และอาจเกี่ยวข้องกับภรรยาของเขาด้วย ดูเหมือนเขาจะใส่บ่อยในการบรรยายตั้งแต่ช่วงกลางทศวรรษ 2010 เป็นต้นมา และน่าจะมีคำอธิบายอยู่ที่ไหนสักแห่ง
ผมเคยอยู่ข้าง ๆ Knuth ตอนปี 2012 ที่เขากำลังจะปีนขึ้นไปบนขอบหน้าต่าง เพื่อดูคบเพลิงโอลิมปิกเข้ามายังลานหน้า Manchester Town Hall ผมชวนเขาคุย และชั่วขณะหนึ่งก็ยื่นมือออกไปเพราะกลัวเขาจะตกออกไปนอกหน้าต่าง แต่เขาก็ไม่เป็นไร เขาให้ความรู้สึกว่าเป็นคนช่างสงสัย เปล่งประกายด้วยคำถามและสติปัญญา และดูอ่อนกว่าวัย
ตอนนั้นเราทั้งคู่กำลังเข้าร่วมงานฉลองครบรอบ 100 ปีชาตกาลของ Alan Turing และผมทึ่งมากที่ในห้องเดียวกันมีบุคคลระดับยักษ์ใหญ่ของวิทยาการคอมพิวเตอร์อย่าง Knuth, Gary Kasparov, Fred Brooks, Vint Cerf และคนอื่น ๆ อยู่ด้วย ตอนพักกลางวัน คบเพลิงโอลิมปิกเข้ามาที่ลานด้านนอก และเขาก็อดใจไม่ไหวต้องไปดู ดูเหมือนเขาจะเป็นคนเดียวที่ตื่นเต้นกับเรื่องนั้น
คืนนั้นเขาบรรยายในงานเลี้ยงอาหารค่ำ และภายหลังตอนที่ผมเจอเขาอีกครั้งที่ Manchester เมื่อเล่ม 4B เพิ่งตีพิมพ์ ผมขอให้เขาเซ็นหนังสือ เขาก็จำผมจากงานก่อนหน้าได้ลาง ๆ
เหตุผลที่เล่าเรื่องนี้ เพราะผมคิดว่าเสื้อของเขาสื่อถึงจิตใจที่ผสมผสานและช่างสงสัยมากกว่านั้นมาก และผมก็เห็นหลักฐานแบบนั้นชัดเจนจากที่อื่นด้วย
ดังนั้นความชอบต่อชุด Sami แบบดั้งเดิมอาจมาจากตรงนั้นก็ได้
[0]: https://youtu.be/jB0aeePskBg
https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...
ลองตรวจดูแล้ว เขาอายุ 87 ปี Donald Knuth เกิดวันที่ 10 มกราคม 1938
ว้าว
Knuth ยังคงน่าทึ่งเสมอ
แต่ก็น่าประหลาดใจและน่าผิดหวังมากที่ที่ Stanford ไม่มีใครดูแลเรื่อง การบันทึกเสียง ให้สมกับเนื้อหาระดับนี้ได้อย่างเหมาะสม ฟังเหมือนมีใครใช้เครื่องอัดเสียงในกระเป๋าอัดไว้
ผมไม่ได้หมายถึงเสียงของ Knuth ในวัยชรา แต่ลองฟังคุณภาพเสียงตอนที่เขาหยุดและรับคำถามจากผู้ชมก็พอ
วิดีโอแบบนี้ทำให้ผมนึกขึ้นได้ว่า แรกเริ่มเดิมทีทำไมผมถึงหลงรักคอมพิวเตอร์
น่าทึ่งมากที่เขายังเฉียบคมอยู่ น่าเสียดายที่ตอนผมเป็นนักศึกษาปริญญาตรีเมื่อราว 20 ปีก่อน เขาก็ไม่ได้ สอนบรรยาย แล้ว
ชอบวิธีที่เขารับมือกับคำถาม: https://youtu.be/Hi8r_63LGyg?t=827
เขาใช้เวลาทำความเข้าใจว่าถามอะไร แล้วตอบอย่างชัดเจนมาก