将数学和CS应用于日常生活--D.Knuth和R.Tarjan的轶事

此订阅源当前的文章如下所示。订阅此订阅源中所有可用内容的更新，或单击此处查看原始文章。

在2020年虚拟世界海德堡桂冠论坛(HLF)的第二天，罗伯特·恩德雷·塔詹(Robert Endre Tarjan)和唐纳德·埃尔文·努斯(Donald Ervin Knuth)就数学、计算机科学和艺术进行了畅所欲言的对话。

Donald Knuth是1974年ACM A.M.Turing奖的获奖者，获奖者是“因为他对算法的分析和编程语言的设计做出了重大贡献，特别是因为他通过他以这个标题连续系列的著名书籍对”计算机编程艺术“的贡献，而Robert Tarjan则因”为许多图论和几何问题设计了近乎最优的算法以开发和利用支持高效算法的数据结构“而获得了1982年的纳瓦林纳奖，并因贡献了几项惊人的深度和优雅的算法分析”和1986年与约翰·E·霍普克罗夫特(John E.Hopcroft)合著的“图灵奖”而获得了纳瓦林纳奖(The Nevanlinna Award)，该奖项的获得者是约翰·E·霍普克罗夫特(John E.Hopcroft)，他为许多图论和几何问题设计了近乎最优的算法，用于开发和利用支持高效算法的数据结构，在算法和数据结构的设计和分析方面取得基本成就。“。

塔詹是努斯在斯坦福大学的学生，他们在一起的历史在他们充满活力的玩笑中得到了展示。这场对话产生了许多有趣的轶事，比如努斯在担任助理教授时对塔詹的健康状况的担忧。Knuth谈到Tarjan时说，“我还记得…。我很担心你，因为你在高速公路上开车的时候脑子里在证明定理，我怕你会出车祸。“。记住孩子们，不要一边算术一边开车。

Knuth还谈到了他在本科时担任凯斯理工学院篮球队经理的时间。在他大三的时候，他创建了一个流程，以便在训练和比赛期间更好地保存每个篮球运动员的统计数据。然后，他使用打孔卡，将这些数据输入到一台IBM 650计算机中，为球队教练生成战略建议。这个系统似乎取得了成功--他们开始使用Knuth系统的那一年赢得了比前一年更多的比赛。IBM甚至录制了一段关于努斯系统的短片，名为《电子教练》，你可以在YouTube上观看。

Knuth走在了他的时代前列-现代NBA球队依靠详细的数据分析来更好地了解他们的球员和竞争对手；事实上，在2013-2014赛季，NBA在每个NBA体育场都安装了SportVu运动跟踪摄像头。这些SportVu摄像头以每秒25帧的速度监控每个球员和篮球的运动，生成有关每场篮球比赛中发生的一切的数据。Nba球队，包括最著名的休斯顿火箭，已经使用这些分析来重新定义比赛的方式。虽然三分球是最难投的，但它们的期望值比两分远的投篮要高(因为两者之间的投篮百分比差异微乎其微)，增加了球员之间的间距(这使得防守变得更加困难)，并增加了获得进攻篮板的可能性(因为错过三分球往往会反弹到离篮筐更远的地方)。意识到这一点，NBA球队每个赛季的投篮命中率都越来越高。在1979-1980赛季，也就是三分线引入NBA的第一年，圣地亚哥快船队以场均6.6次三分命中率(3PA)领先联盟。去年，休斯顿火箭打破了这一数字，尝试了nba历史上最多的三分，场均出手45.4次。

这就是说，当Knuth有了使用计算机更好地理解篮球比赛的新想法时，他确实做得很好。在彭博社发布的这段视频中，你可以更多地了解一位nba现代数据科学家的工作，这段视频介绍了费城76人的高级研究员伊万娜·塞里奇(Ivana Seric)。

Knuth将数学和计算机科学应用到其他领域并不止步于此。努斯也是一位成就斐然的管风琴演奏家，几年前，他创作了一首为管风琴创作的多媒体作品《幻想曲启示录》(Fantasia Apoalyptica)。在“启示录”中，克努斯使用了一些数学和算法方法来生成旋律。在他的网页上，克努斯说：

“我一度想，我可能有足够的时间来充分理解音乐理论，这样我就可以试着把这一理论教授给电脑。”但最终我得出的结论是，几乎完全手工创作这件作品会更好，只使用我的台式机来帮助组织工作。因此，它绝对不是“计算机音乐”，尽管我确实自称是一名计算机科学家。

另一方面，我确实在一些地方手动应用了一些算法。例如，一个令人难以忘怀的旋律，取自最早幸存的古希腊音乐之一，出现了十次。我每次都使用David Kraehenbuehl的算法，每次都是不同的，这一算法在“娱乐与游戏精选论文”第22章中有描述。(见“音乐中的随机性”。)。

数学方法也被用来产生短暂出现的变化的图案，以及用于以色列十二个部落和新耶路撒冷“珍珠门”下的十二颗珍贵珠宝的某些旋律。如果这些方法没有成功，我就会手工改变结果。幸运的是，我不必这么做；算法方法在这些情况下确实给出了令人满意的结果。“。

库恩斯的不同兴趣促使塔尔扬提出了一个令人信服的问题：“有人说，任何以科学为名的领域都不是科学，所以我可能会问你，计算机科学是一门科学，还是工程学的一个分支，数学的一个分支，还是一门艺术--但让我以一种更个人化的方式来问这个问题…。.你认为自己是艺术家、科学家、数学家、工程师、哲学家，还是某种组合？“。

努斯回答说，他意识到艺术不仅代表美术，而且还代表人造或由人类制造的东西(与自然相对)。他将科学定义为“我们理解得足够好，足以向计算机解释的东西”，而“艺术就是一切”。他接着说，当我们学到更多关于某事的科学知识时，我们的大脑“保持领先几个跳跃，这就是艺术”。

最后，克努斯被问到是否对学生有什么建议。努斯的反应是呼应了莱斯利·兰波特(Leslie Lamport)在HLF早些时候提出的建议，即要经常写信。然而，Knuth告诫说，不要“太受时尚东西的影响”。不要因为你必须写论文，或者因为你认为你必须给别人留下深刻印象，而你个人对…并不真正感兴趣，所以不要写论文。这是写论文的最糟糕的理由。“。

塔尔扬补充说，“你必须弄清楚自己的道路是什么，然后沿着它走下去。我遇到过的最好的学生要么是和他们一起来的，要么就是带着他们自己发展出来的想法结束的。“。显然，这两个人都成功地找到了自己的道路，并走上了自己的道路。点击此处观看Tarjan和Knuth在YouTube上的完整对话。

计算在抗击新冠肺炎大流行中能起到什么作用？世界协调时2020-09-24 15：58哈里·道格拉斯(Khari Douglas)

计算机技术如何影响全球健康，特别是新冠肺炎大流行？2018年ACM计算奖获得者和计算社区联盟(CCC)理事会成员Shweak Patel在2020年虚拟海德堡桂冠论坛(HLF)的第二天谈到了这个问题。帕特尔是一名企业家，也是华盛顿大学计算机科学系的首席教授，他因“对可持续发展和健康方面的创造性和实用性传感系统做出的贡献”而获得2018年大奖。

在他的演讲中，Patel强调了计算技术在医疗保健方面的一些使用案例：例如，人工智能通过读取X射线和放射扫描提高了筛查和诊断能力，而移动电话的无处不在使其成为健康传感和护理点诊断的绝佳选择。

帕特尔和他的同事们已经开发了许多创新的健康应用程序，这些应用程序旨在与标准手机一起使用。BiliCam就是一个这样的例子，这是一款可以使用智能手机摄像头监测婴儿黄疸的应用程序。另一个是Osteoapp，它从智能手机发出声音，导致骨骼振动。然后，这款应用程序可以判断由此产生的振动频率是否表明骨骼结构健康或不健康。

帕特尔还开发了一款名为CoughSense的应用程序，该程序通过手机麦克风监控用户的咳嗽。这款应用程序已经被用来监测结核病患者的康复情况，并确保他们没有患上继发性感染。帕特尔说，他的研究生已经开始将这项咳嗽监测技术应用到COVID患者身上。点击此处阅读更多关于他在移动咳嗽监测系统方面的工作。

其他技术解决方案，如接触者追踪，在与COVID的战斗中可能是有价值的。为了了解病毒是如何传播的，我们将需要处理大量的公共卫生数据，部署和解读快速检测，并对个人进行跟踪和跟踪，帕特尔提到华盛顿大学独立的全球卫生研究中心--美国卫生指标与评估研究所(IHME)在捕获全球卫生数据以帮助改善政策和决策方面所做的工作。IHME在其网站上有大量与COVID大流行相关的数据和预测。

虽然这种数据收集可以被证明是有价值的，但也不是没有缺点。在问答过程中，一位年轻的研究人员向帕特尔询问了大规模收集医疗数据的伦理挑战。帕特尔回应说，安全和隐私是至高无上的，研究人员需要考虑他们正在收集什么数据--有时研究人员可能在没有明确计划使用特定数据的情况下收集数据，但帕特尔认为，我们应该只收集对你试图实现的特定结果有价值的数据，而不是我们正在对这些数据做什么。我们不能只是收集一些东西，然后再想办法处理它--我们需要知道这些数据是否真的像我们认为的那样。此外，研究人员应该考虑这些数据的价值是否超过了对隐私的担忧。透明度也非常重要。需要让用户清楚地知道数据是如何处理的，以及它将用于什么。

去年，我有机会在计算研究协会(CRA)CCC的官方播客--全球催化计算播客上采访了Shweak Patel。请在这里收听这一集，了解更多关于他是如何开始从事计算机科学的，以及他对创业精神、团队建设和智能医疗系统未来的想法。

点击此处观看Shwatak Patel在Virtual HLF 2020上的完整演示文稿。有关研究人员如何使用计算来适应和帮助这些时代的更多信息，请参见CCC的更多系列帖子。我们希望您现在或将来都能找到对您有帮助的东西。

作为虚拟技术海德堡桂冠论坛(HLF)第一天的一部分，获得2017年美国机械工程师协会(ACM)图灵奖的大卫·A·帕特森(David A.Patterson)分享了一篇题为《架构创新加速人工智能》的演讲。帕特森获得了2017年度ACM AM图灵奖，他的获奖理由是“开创了一种系统的、定量的方法来设计和评估计算机架构，对微处理器行业产生了持久的影响”。

首先，帕特森简要概述了人工智能的历史：它从自上而下的方法开始，在这种方法中，程序员会试图用机器的适当逻辑来描述所有规则，但其他研究人员认为这是不可能的，而是主张一种自下而上的方法，即你向机器提供数据，机器自己学习，即机器学习，事实证明这是非常成功的。机器学习的一种类型是深度神经网络(DNN)，它产生了人工智能最近的许多进展。

驱动DNN的算法并不新鲜，那么目前是什么改变了这些系统的可行性呢？如今，我们可以访问更多的数据和速度更快的机器，从而使DNN能够高效地进行自我训练。不幸的是，摩尔定律-由英特尔联合创始人戈登·摩尔在20世纪70年代提出的观察，如果今天1美元能买到1000个晶体管，那么大约两年后1美元就能得到2000个晶体管-已经放缓了。用来与计算机速度一对一跟踪的晶体管的数量，这样每两年左右你就可以使计算机的速度翻一番，但这种关系不再成立。帕特森说，我们目前预测的每个芯片的晶体管数与实际相差15倍。因此，我们需要想出新的方法来提高计算速度和增强机器学习系统的能力。

当前克服这些限制的方法是领域特定体系结构(Domain Specific Architecture，DSA)，它做了一些很好的事情，但不擅长任意程序。帕特森说，“五十年的通用建筑设计经验可能不适用。”如果你是这个领域的一家公司，你会做什么？

帕特森分享了一个近代史上的例子：2013年，谷歌计算出，如果1亿用户开始每天在CPU上使用DNN 3分钟，他们将需要将数据中心的大小增加一倍，因此他们启动了一个紧急项目，目标是使现有CPU和GPU的性能提高10倍。在15个月内，他们从创意转变为硬件和软件。谷歌设计的TPUv1拥有约80倍的2015英特尔CPU和30倍的NVIDIA CPU的性能/瓦，因为它们使用的是8位整数数据而不是32位浮点数据，并且它们放弃了通用CPU/GPU功能，从而节省了面积和能源。

TPUv1用于ML推理，接下来Google创建了TPUv2，它是为进行ML训练而设计的，这需要更多的计算、更多的内存和更大的数据。谷歌决定在TPUv2芯片中内置四个核心间互联(ICI)链路，每个链路都以每秒500千兆位的速度运行。因此，这些链路的速度大约是传统数据中心网络中链路速度的五倍，而成本仅为传统数据中心网络的十分之一。最终，他们创建了TPUv3，进一步提高了系统性能。

这就是说，使特定于领域的体系结构发挥作用，如果我们想要继续改进ML系统，我们将需要继续开发新的和改进的DSA。最近发布的GPT-3(生成性预训练变形金刚)神经网络模型因能够成功模仿人类语言而备受关注。正如帕特森所说，最大的突破就是比GPT-2大100倍。与GPT-3的1750亿个参数相比，GPT-2只有15亿个参数。在机器学习中，你的数据集的大小和你的计算机的速度；因此，计算机架构师将在人工智能的未来发挥至关重要的作用。

点击此处阅读帕特森2018年在HLF上的演讲，并查看帕特森的博客文章，内容是在该学科的旗舰会议上努力增加工业产品论文，进一步增强这里的学术界和产业界的协同效应。

大众演讲：计算如何改变我们的世界2020-09-22 17：49 UTC作者：海伦·赖特。

虽然计算研究协会的计算社区联盟(CCC)致力于促进计算社区的公益，但我们很少准备适合非计算机科学家公众的演讲。幸运的是，威斯康星大学麦迪逊分校(University of Wisconsin-Madison)的CCC主席马克·D·希尔(Mark D.Hill)最近为参与式学习与教学组织(Plato)准备了一场广受欢迎的普通听众演讲，该组织是一个高级组织，安排内容丰富的讲座、课程和实地考察，现在都是虚拟的。

希尔教授一小时的演讲以“计算如何改变我们的世界”(YouTube Video&；Slide PDF)命名为“计算如何改变我们的世界”(YouTube Video&；Slide PDF)。它讨论了，虽然计算已经改变了我们沟通、工作和娱乐的方式，但更大的影响正在酝酿之中。希尔教授洞察并讨论了即将出现的三个重要例子的影响：

Khari Douglas将在CCC博客上报道虚拟HLF 2020整个星期。请继续关注更多内容，并通过这里的直播观看节目。

虚拟世界·海德堡桂冠论坛论坛(HLF)2020今天(9月21日)通过直播拉开帷幕。作为当天节目的一部分，C·安东尼·R·霍尔爵士(Sir C.Antony R.Hoare)和莱斯利·兰波特(Leslie Lamport)都是AACM A.M.图灵奖的获得者，他们坐下来进行了对话，讨论了他们的职业生涯，并向观众中的年轻研究人员提供了建议。

兰波特在会议开始时问霍尔，他早年的学生时代是如何为他成为一名计算机科学家做好准备的。霍尔透露，由于勤奋好学，他被同学们昵称为“教授”，并提到英国逻辑学家、哲学家和作家伯特兰·罗素(Bertrand Russell)受到了主要影响。霍尔认为罗素的《婚姻与道德》一书非常引人入胜，后来又研读了罗素的《数学哲学导论》，霍尔还提到兰斯洛特·霍本的《数百万人的数学》是培养他对数学兴趣的早期影响。

在牛津大学默顿学院获得学士学位后，霍尔在英国皇家海军呆了两年，在那里他学习了俄语，并获得了俄罗斯口译员的资格。这项技能后来派上了用场，当时他翻译了俞敏洪编辑的一本名为《数学机器理论》的文章集。是啊。巴兹列夫斯基换取零用钱。

霍尔接着获得了牛津大学的统计学证书，因为哲学问题是“未来事件的概率陈述表达了什么样的知识”。随后，他参与了许多与统计和计算机编程相关的项目，包括快速排序算法(单击此处查看更多信息)，然后因其在1980年对编程语言的定义和设计做出的基本贡献而获得图灵奖。

在霍尔解释了他的背景之后，他和兰波特交换了角色，兰波特讨论了他是如何对计算机科学产生兴趣的。兰波特说，在对物理感兴趣之前，他一开始对数学感兴趣--直到他意识到自己“不够聪明，不足以成为一名物理学家”，所以他“只是获得了数学博士学位”。在学校时，他有兼职工作，编程，这导致了一份工作，设计操作系统，并最终做研究。

兰波特因对分布式和并发系统的理论和实践做出了根本性贡献而于2013年获得图灵奖，当他在ACM杂志上读到一篇关于他认为过于复杂的互斥算法的文章时，他开始研究并发性。作为回应，他提交了一篇带有两个过程解决方案的论文，但几周后，他收到了编辑的回信，指出他的算法中存在一个错误。解决这一问题的愿望驱使他创造了兰波特的烘焙算法，“意在通过互斥的方式提高多线程间共享资源使用的安全性。”

当被问及如何想出这个算法时，兰波特说，其他人认为互斥是一个数学或语言问题，但他认为这是一个物理问题：“你必须建造两个不会在同一物理时间做某事的物理设备。”同样，兰波特说，他从数学教育中学到的主要东西之一就是意识到“数学并不重要，重要的是表达的内容”，因此他认为数学“应该尽可能简单”。这种心态最终使他设计了一种称为TLA的时态逻辑，除了普通的数学运算外，它只使用了三个运算符：prim。

.