读算法简史：从美索不达米亚到人工智能时代05天气预报

1. 天气预报

1.1. 自古以来，生命就与变幻莫测的天气息息相关

• 1.1.1. 在很多情况下，只要能提前一天得知天气情况，人类就可以避免灭顶之灾
  
• 1.1.2. 公元前2000年，准确预测天气是众神的特权
  

1.2. 大约在公元前650年，巴比伦人曾尝试通过观察云的形成来更精确地预测天气
1.3. 在公元前340年左右，希腊哲学家亚里士多德撰写了《气象论》(Meteorologica)，这是第一部论述天气本质的重要著作
1.4. 《伊勒苏斯的泰奥弗拉斯图斯论风与天气征象》(Theophrastus of Eresus on Winds and On Weather Signs)，其中收录有关于天气的传说
1.5. 两部书都错得很彻底
1.6. 英国于1854年成立了气象局
1.7. 1860年美国气象局也开始运行
1.8. 气象部门从边远地区收集气象数据，并根据这些信息发布天气预报

• 1.8.1. 预测方法相当初级
  

1.9. 20世纪初

• 1.9.1. 美国气象局局长克利夫兰·阿贝(Cleveland Abbe)指出，地球的大气层本质上是多种气体的混合物
  
• 1.9.2. 挪威科学家威廉·皮叶克尼斯(Vilhelm Bjerknes)提出了一种预测天气的两步法
  
  
  
  • 1.9.2.1. 第一步，测量天气的当前状态
    
  • 1.9.2.2. 第二步，用一组方程来预测大气未来的气压、温度、密度、湿度和风速
    
  • 1.9.2.3. 利用图表将观测结果转化为对未来情况的估计
    
  • 1.9.2.4. 皮叶克尼斯的迭代法是一个突破，但其方法的准确性受到图表的限制
    
  
  

2. 数值预报

2.1. 刘易斯·弗莱·理查德森

• 2.1.1. Lewis Fry Richardson
  
• 2.1.2. 1881年出生于英国纽卡斯尔
  
• 2.1.3. 在纽卡斯尔大学和剑桥大学国王学院学习科学
  
• 2.1.4. 一个几乎没有气象学经验的人
  
  
  
  • 2.1.4.1. 理查德森投身于一项开发和测试天气预报数值算法的任务
    
  • 2.1.4.2. 理查德森的实验以不可违背的物理定律为基础
    
  
  

2.2. 算法

• 2.2.1. 测量每个单元格的初始天气情况
  
• 2.2.2. 对于每一个时间步骤，重复以下操作
  
  
  
  • 2.2.2.1. 对于每个单元格，重复以下操作
    

    2.2.2.1.1. 根据单元格和其相邻单元格前一个时间步骤中的状态计算单元格的状态
    

    2.2.2.1.2. 处理完所有单元格后停止重复
    

    
    
  • 2.2.2.2. 当所有时间步骤都处理完毕后，停止重复
    
  
  
• 2.2.3. 输出完成的预报
  
• 2.2.4. 模拟
  
  
  
  • 2.2.4.1. simulation
    
  • 2.2.4.2. 通过计算来预测现实世界的物理系统是如何随时间变化的
    
  • 2.2.4.3. 支配模拟的方程是现实世界天气情况动力学的模型(model)
    
  
  

2.3. 算法极其不准确，而且非常不切实际，因为需要做大量的计算

• 2.3.1. 唯一的出路是借助高速的计算机器
  

3. ENIAC

3.1. 第一台可运行的通用计算机是第二次世界大战期间在宾夕法尼亚大学被设计和制造的

• 3.1.1. 建造ENIAC的目的是计算火炮弹道表，但它是一个成熟的通用计算机
  
  
  
  • 3.1.1.1. 是可编程的，尽管用的是电线和插头
    
  
  
• 3.1.2. ENIAC与巴贝奇的分析机一样处理十进制数字
  
  
  
  • 3.1.2.1. 体量巨大，重量约为27吨，占地面积超过1500平方英尺
    
  
  

3.2. ENIAC的建造工作开始于1943年

• 3.2.1. 年轻而精力充沛的埃克特被任命为总工程师
  
• 3.2.2. 成熟的莫希利担任埃克特的顾问
  
• 3.2.3. 戈德斯坦是项目经理兼数学家
  

3.3. 约翰·莫希利

• 3.3.1. 莫希利1907年出生于辛辛那提
  
• 3.3.2. 于1980年去世
  

3.4. 普雷斯伯·埃克特

• 3.4.1. 埃克特不是一个优秀的学生，但他是一个卓越的实用工程师
  
• 3.4.2. 曾在雷明顿·兰德公司及其后续公司工作，直到1995年去世
  

3.5. 赫尔曼·戈德斯坦

• 3.5.1. Herman Goldstine
  
• 3.5.2. 弹道制表工作的负责人
  
• 3.5.3. 密歇根大学的数学教授
  

3.6. 位于马里兰州阿伯丁试验场附近的弹道研究实验室(Ballistic Research Laboratory，BRL)雇用了100名有数学头脑的女研究生来进行精确且耗时的计算

• 3.6.1. ENIAC的程序员选取自为BRL工作的数学家队伍
  
• 3.6.2. 凯瑟琳·麦克纳尔蒂［Kathleen McNulty，婚后改姓莫希利和安东内利(Antonelli)］、​（贝蒂）琼·詹宁斯(Jean Jennings)，婚后改姓巴蒂克(Bartik)］、​（弗朗西丝）贝蒂·霍尔伯顿［Betty Holberton，婚后改姓斯奈德(Snyder)］、马林·威斯考夫［Marlyn Wescoff，婚后改姓梅尔策(Meltzer)］、弗朗西丝·比拉斯［Frances Bilas，婚后改姓斯宾塞(Spence)］和露丝·利希特曼［Ruth Lichterman，婚后改姓泰特尔鲍姆(Teitelbaum)］
  

3.7. ENIAC于1945年建造完成

• 3.7.1. 在1秒钟内就完成了5000个数字的求和
  
• 3.7.2. 庆祝晚宴
  
  
  
  • 3.7.2.1. 晚宴只招待高级官员和电子工程师
    
  • 3.7.2.2. ENIAC的女性程序员没有收到邀请
    

    3.7.2.2.1. 50年后，ENIAC的程序员们才得到了一点认可，她们本应得到更多
    

    
    
  
  

3.8. ENIAC是为弹道计算设计的，但它的第一次操作运行更像是为了更高级的目的

• 3.8.1. 首次运行是为曼哈顿计划做秘密计算
  
• 3.8.2. 将ENIAC用于设计氢弹所需的计算
  
• 3.8.3. 曼哈顿计划和ENIAC团队之间得以建立起持续的联系
  
  
  
  • 3.8.3.1. 对历史上最强大的算法之一进行测试成为可能
    
  
  

3.9. 1947年，ENIAC被转移到其所有者的所在地——位于阿伯丁的BRL设施
3.10. 1944年8月莫希利和埃克特提出了一种改进的设备——EDVAC（电子离散变量自动计算机）
3.11. 约翰·冯·诺伊曼

• 3.11.1. 1903年出生于匈牙利布达佩斯
  
• 3.11.2. 在18岁之前就完成了自己的第一篇研究论文
  
• 3.11.3. 能讲一口流利的英语、德语和法语，拉丁语和希腊语也还凑合
  
• 3.11.4. 1931年被任命为普林斯顿大学教授
  
  
  
  • 3.11.4.1. 和爱因斯坦一起，成为普林斯顿高等研究院(Institute for Advanced Study，IAS)的一员
    
  
  
• 3.11.5. 参与了曼哈顿计划，协助设计第一颗原子弹
  
• 3.11.6. 1945年6月，冯·诺伊曼撰写了一份101页的报告，题为《EDVAC报告书初稿》(First Draft of a Report on the EDVAC)
  
  
  
  • 3.11.6.1. 详细描述了EDVAC的新设计
    
  • 3.11.6.2. 没有提及机器的发明者莫希利和埃克特
    
  
  
• 3.11.7. 冯·诺伊曼是EDVAC第一份报告的唯一作者，人们广泛认为他是该设计的鼻祖
  
• 3.11.8. 于1957年去世，终年53岁
  
  
  
  • 3.11.8.1. 冯·诺伊曼的讣告是斯塔尼斯瓦夫·乌拉姆撰写的
    
  
  

3.12. ENIAC（电子数值积分计算机）是由两位大学教授约翰·莫希利(John Mauchly)和普雷斯伯·埃克特(Presper Eckert)设计的

• 3.12.1. 在命运的捉弄下，大部分功劳都被算在了世界著名数学家约翰·冯·诺伊曼(John von Neumann)头上
  

4. 阿塔纳索夫-贝瑞计算机

4.1. Atanasoff-Berry Computer，ABC
4.2. ABC是由艾奥瓦州立大学的教授约翰·阿塔纳索夫(John Atanasoff)和他的学生克利福德·贝瑞(Cliff ord Berry)发明的，这种计算机就是电子计算机
4.3. ABC不是可编程的，且缺乏决策能力
4.4. ENIAC比ABC先进得多，且包含许多创新特性
5. 蒙特卡洛

5.1. 斯塔尼斯瓦夫·乌拉姆

• 5.1.1. Stanislaw Ulam
  
• 5.1.2. 1909年出生在一个富裕的波兰犹太家庭
  
• 5.1.3. 主攻数学，毕业于乌克兰利沃夫理工学院(Lviv Polytechnic Institute)，获得博士学位
  
• 5.1.4. 1935年，他在华沙遇到了约翰·冯·诺伊曼
  
• 5.1.5. 1939年，他永久移居美国，勉强躲过了欧洲爆发的第二次世界大战
  
• 5.1.6. 于1984年在新墨西哥州的圣菲去世
  

5.2. 坎菲尔德纸牌

• 5.2.1. 单人纸牌游戏
  
• 5.2.2. 使用普通的52张纸牌
  
• 5.2.3. 一次可以发一张纸牌，纸牌根据游戏规则和玩家的决定在牌堆之间移动
  
• 5.2.4. 游戏的目标是最终只剩下4个牌堆
  
  
  
  • 5.2.4.1. 每个牌堆应该包含同一花色的所有纸牌
    
  
  

5.3. 乌拉姆想知道，他玩这个游戏获胜的概率有多大？

• 5.3.1. 计算获胜概率的一个方法是列出所有可能的纸牌序列，然后算一下能够获胜的纸牌序列的百分比
  

5.4. 乌拉姆算法

• 5.4.1. 把获胜计数设为零
  
• 5.4.2. 重复以下步骤
  
  
  
  • 5.4.2.1. 取一副新纸牌
    
  • 5.4.2.2. 重复以下步骤
    

    5.4.2.2.1. 随机抽一张牌
    

    5.4.2.2.2. 以最佳方式移这张牌
    

    5.4.2.2.3. 当纸牌全部抽完后停止重复
    

    
    
  • 5.4.2.3. 如果游戏赢了，那么在获胜计数上加1
    
  • 5.4.2.4. 在玩过很多次游戏后停止重复
    
  
  
• 5.4.3. 在玩过很多次游戏后停止重复
  
• 5.4.4. 洛斯阿拉莫斯的纸牌玩家们将这种新算法命名为蒙特卡洛方法，取自摩纳哥著名赌场的名字
  

5.5. 在制造核弹的过程中，乌拉姆负责计算中子（原子中心的无电荷粒子）穿过屏蔽材料距离的问题

• 5.5.1. 一个乒乓球随意向随机摆放的100万个木柱飞去
  
  
  
  • 5.5.1.1. 这个球平均能飞多远？
    
  • 5.5.1.2. 有那么多可能的路径，谁能回答出这个问题呢？
    
  
  

5.6. 乌拉姆算法不仅适用于纸牌游戏，也适用于中子扩散问题

• 5.6.1. 中子的运动轨迹和屏蔽材料原子的位置可以用随机数表示
  
• 5.6.2. 将大量随机试验所得结果的平均值计算出来，就可以估计出现实世界中典型的中子穿透距离
  

5.7. 1949年，梅特罗波利斯和乌拉姆发表了第一篇关于蒙特卡洛方法的论文

• 5.7.1. 这种方法现已成为计算机模拟的主要方法
  
• 5.7.2. 科学家使用该方法，通过随机抽取大量案例来估计复杂物理事件的可能结果
  
• 5.7.3. 如今，蒙特卡洛方法已经成为物理、生物、化学、工程、经济、商业和法律等诸多领域中推测性研究的必备方法
  

6. 计算机预测

6.1. IAS计算机，是冯·诺伊曼对计算机界的献礼

• 6.1.1. 机器从1952年一直运行到1958年
  
• 6.1.2. 冯·诺伊曼将IAS计算机的计划分发给了多个研究小组和公司
  
• 6.1.3. IAS计算机成为全世界计算机的蓝图
  
• 6.1.4. 冯·诺伊曼还思考了哪些任务可以交给计算机承担
  

6.2. 冯·诺伊曼从美国海军处获得了一笔资金，建立了第一个计算机气象学研究小组
6.3. 20世纪五六十年代，由于算法的改进、电脑性能的进步和天气监测站数量的增加，天气预报的准确性稳步提高
7. 混沌理论

7.1. Chaos theory
7.2. 爱德华·洛伦兹

• 7.2.1. 于1917年出生在康涅狄格州
  
• 7.2.2. 差异源于模拟输入中的一个非常小的差异
  
  
  
  • 7.2.2.1. 第一次运行时，就大气层状态，洛伦兹输入的数字保留了小数点后六位
    
  • 7.2.2.2. 第二次运行中，他只保留了三位
    
  
  
• 7.2.3. 洛伦兹意识到他看到的不只是模拟的产物
  
  
  
  • 7.2.3.1. 这一模拟准确地模仿了现实世界的现象
    
  
  
• 7.2.4. 在2008年去世
  

7.3. 混沌理论(Chaos theory)表明，许多现实世界中的物理系统对其初始条件非常敏感

• 7.3.1. 初始状态的微小变化会导致后期结果出现重大差异
  
• 7.3.2. 这个思想被概括为一个流行的称呼：​“蝴蝶效应”​
  

7.4. 混沌理论为数值天气预报的时间范围设定了一个界限

• 7.4.1. 对当前情况建模时的小误差可能会导致后期预测结果上的大误差
  

7.5. 可以准确预测的时间范围看似是无法延长的，直到爱德华·爱泼斯坦(Edward Epstein)的出现
7.6. 爱德华·爱泼斯坦

• 7.6.1. Edward Epstein
  
• 7.6.2. 于1931年出生在纽约布朗克斯
  
• 7.6.3. 在斯德哥尔摩大学担任访问学者期间，他发表了一篇论文，概述了一种可以减轻蝴蝶效应的算法
  
• 7.6.4. 理查德森提出的数值天气预报依赖于单一的模拟来预测天气
  
  
  
  • 7.6.4.1. 模拟从测量当前的条件开始，逐个单元格、逐个时间步骤地计算天气如何演变
    
  
  
• 7.6.5. 爱泼斯坦的见解是将乌拉姆的蒙特卡洛方法应用于理查德森的数值模拟
  
  
  
  • 7.6.5.1. 爱泼斯坦提出要运行多次模拟，而不是一次
    
  • 7.6.5.2. 每次模拟都以随机扰动的初始条件开始
    
  • 7.6.5.3. 平均值把可能性的集合(ensemble)都考虑进去了
    

    7.6.5.3.1. 平均值走中间路线，是考虑周全的，而且是最有可能发生的那个情景
    

    
    
  
  
• 7.6.6. 在2008年去世
  

7.7. 爱泼斯坦算法

• 7.7.1. 测量当前的大气状况
  
• 7.7.2. 重复以下步骤
  
  
  
  • 7.7.2.1. 在当前条件中加入小的随机扰动
    
  • 7.7.2.2. 从这些初始条件开始执行数值预测
    
  • 7.7.2.3. 存储结果
    
  • 7.7.2.4. 当执行了足够多次的模拟后，停止重复
    
  
  
• 7.7.3. 输出平均后的预测结果
  

7.8. 爱泼斯坦算法的缺点是需要大量的计算

• 7.8.1. 进行8次蒙特卡洛模拟需要8倍于一次预测的计算机算力
  
• 7.8.2. 出于这个原因，爱泼斯坦的集合预报方法直到20世纪90年代初才投入使用
  
• 7.8.3. 欧洲中期天气预报中心(European Centre for Medium-Range Weather Forecasts)现在是基于51次独立的模拟进行预测
  

8. 长期预测

8.1. 晶体管(transistor)和集成电路(integrated circuit)分别发明于1947年和1958年，它们帮助计算机实现了小型化
8.2. 晶体管是一种电子开关，除了电子之外不包含任何其他可以运动的部分

• 8.2.1. 它体积小，功耗低，运行可靠，速度快得令人难以置信
  

8.3. 集成电路的发明让人们可以以不可思议的低成本制造大量的微型晶体管，以及它们之间的金属连接

• 8.3.1. 每个计算机芯片(computer chip)内部都有一个集成电路
  
• 8.3.2. 这些芯片就是现代计算机的物理构件
  

8.4. 摩尔定律

• 8.4.1. 1965年，英特尔(Intel)联合创始人戈登·摩尔(Gordon Moore)指出，他的工程团队能够使单个集成电路上的晶体管数量每18个月增加一倍
  
  
  
  • 8.4.1.1. 计算机的性能呈指数级增长
    
  • 8.4.1.2. 尽管性能提高了，计算机的体积、成本和功耗却大幅下降
    
  
  
• 8.4.2. 摩尔没有理由认为这种趋势不能延续到未来
  
  
  
  • 8.4.2.1. 成为该行业的路线图
    
  
  
• 8.4.3. 摩尔定律已被证明是现代最伟大的预言之一
  
  
  
  • 8.4.3.1. 该定律已经有效了半个多世纪
    
  
  
• 8.4.4. 摩尔定律是计算机强势崛起背后的驱动力
  
• 8.4.5. 摩尔定律也推动了算法数量的指数级增长
  

8.5. 2008年，都柏林大学的彼得·林奇(Peter Lynch)和IBM的欧文·林奇(Owen Lynch)在一部手机上重复运行了ENIAC最初的天气预报

• 8.5.1. 他们的程序名叫“PHONIAC”​，在一部普通的诺基亚6300型手机上运行
  
• 8.5.2. ENIAC用了24小时来完成单个预报
  
• 8.5.3. 诺基亚6300型手机用时不到1秒
  
• 8.5.4. ENIAC重27吨
  
• 8.5.5. 诺基亚6300型手机只有91克
  
• 8.5.6. 这就是摩尔定律在发挥作用
  

8.6. 曾经执行起来非常耗时的算法现在已经变成了常规操作

• 8.6.1. 算法研究的方式曾经看起来是纯理论的，现在完全是实用性的
  

《道德经》：上善若水。水善利万物而不争，处众人之所恶，故几于道。居善地，心善渊，与善仁，言善信，正善治，事善能，动善时。夫唯不争，故无尤。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！