G.O.S.S.I.P 阅读推荐 2023-12-27 高德纳频道

Donald E. Knuth（他给自己起的中文名叫做高德纳），大名鼎鼎的《计算机程序设计艺术》（The Art of Computer Programming）作者，图灵奖得主，TeX之父。高老爷子今年85岁，依然还在活跃（大家都等着他完成皇皇巨著《计算机程序设计艺术》的剩余部分），作为斯坦福的退休教职工，每年应邀发表圣诞演说，为此斯坦福还专门开设了一个Donald E. Knuth Lectures相关页面，里面不仅有老爷子最近几年的视频，也把当年的一些珍贵的古老视频（上世纪80年代开始）都收录了进来：

https://online.stanford.edu/donald-e-knuth-lectures

那么，你觉得老爷子每年圣诞演讲会讲什么？和大部分的老专家不太一样，老爷子虽然姓高，但是德高望重的他没有什么高屋建瓴高瞻远瞩的架子，只是讲最基本的算法问题。2018年的圣诞演讲，他回顾了自己在2000年发表的一篇短论文Dancing links（https://arxiv.org/abs/cs/0011047 居然是在2000年就提交到了arXiv上）：

实际上dancing links就是我们熟知的双向链表的基本操作（如上图），但是基于这个操作，可以玩出很多花样，一些著名的精确覆盖问题（exact cover problem）例如数独（sudoku）就可以基于此高效解决。老爷子自己在2018年也说，大家可能觉得他健忘了，2000年讲过的东西又拿出来讲一遍？而在2023年，这个演讲又深入了一层，名字叫做Dancing cells，虽然老人家现在说话有点不太利索，但是思维还是很敏捷，在2023年还能给大家在线上推导算法，我们这帮年轻人又有什么借口躺平呢？

鉴于网络访问的issue，特地搬运了2023年的视频给大家看，可能你会有点没耐心看完，如果看完的读者欢迎给我们留言讲讲观后感！当然也可以访问一下高德纳教授的主页，非常有趣的名字——Computer Musings

https://www-cs-faculty.stanford.edu/~knuth/musings.html

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2023-12-27 高德纳频道