计算思维

计算机专业导论笔记

计算机、计算与计算思维

从小白鼠试毒引出计算思维

问题

小白鼠实毒：有1000瓶水，小白鼠只要尝一点带毒的水24小时内就会死亡，至少需要多少只小白鼠才能在24小时内鉴别出哪瓶水有毒？

背后的思维模式

• 1000瓶水编号：0-999（这是十进制，无法继续）使用转换思维 ：转换成二进制
• 确立十位二进制的方式表达：运用了递推思维
• 多种含义用01串表达，这是0和1的思维
• 同样一串数字可以表达不同的含义，这是理解计算机思维的关键

计算思维是运用科学计算的基础概念去求解问题、设计系统和理解人类行为。（周以真）本博客在2025年也提到过《computational thinking》

• 此外，这道题如果用二分法求解，时间不够，因为这是串行使用，如果是并行使用二分法，完全可以。（串行并行也是一种计算机思维））
• 这里也涉及到符号变换、逻辑推理思维。

枚举-计算-验证

机器计算需要用指令表达规则，通过CPU执行指令，存储器保存程序。机器计算的复杂性可以通过算法的复杂性来衡量，算法的复杂性取决于基本步骤的重复次数。 以下这张图也说明了机器级的程序如何执行：

这张图对应的现实中的例子如无人机，自动化程度更高，里面是有一个芯片的，这个芯片就是CPU和存储器。程序在存储器中，被CPU读取然后一条一条的执行；这就是机器级的程序的例子，以单一的加法或减法进行编程，后来出现了用语句/函数表达规则，即高级语言程序。

注意，高级语言程序是独立于具体机器的。

然后就是算法,比如无人机群如何协同和控制，是用一种计算规则：算法。

以上，就是去理解机器如何自动计算的说明。

在机器级的程序中，了解到其复杂性低，提出问题：机器能在有限时间内完成计算吗 ？在计算机领域，有限时间会涉及到算法和算法的复杂性（执行算法时间的长短）;

能在有限时间内解决的问题是可求解问题，反之称之为难以求解的问题。

难以求解的问题需要引入随机因素和近似解来求解。如何解决和研究算法，回归到开头标题：枚举-计算-验证 。在此基础上，才会考虑优化。

计算与社会

第一次工业革命以蒸汽机发明为代表，第二次是电力，第三次计算机和互联网，目前的历史进程已经处于第四次工业革命时期，属于第二次信息技术革命，人工智能、物联网等为代表。

发展趋势：

• 计算微型化（芯片越来越小，如植入人体、嵌入各种设备中，万物可计算）；
• 计算大型化（IBM-BlueGene,如我国的天河计算机，多个芯片组成大型计算；飞机设计前的仿真模拟）；
• 计算网络化（人机物互联，三维世界的互联）；
• 计算智能化（理解自然语言，人工智能自主完成复杂功能）。

计算机的发展：

• 早期冯诺伊曼计算机，单机，程序放在外存上，如何被装载到内存，如何被CPU执行；
• 后来发展为多机并行，多个CPU，多个磁盘阵列，怎么运用；
• 然后是云计算，把大量计算节点变成虚拟运算节点提供给多个用户；
• 互联网+高端机械群，群体协作控制，数据收集实施汇聚。

计算机的理论模型：图灵机

历史背景

Alan Turningopen in new window 于1937年发表论文，提出图灵机模型概念；后来冯诺伊曼根据此概念设计出世界上第一台电子计算机；

1950年，Turning 发表了划时代文章《机器能思考吗》，成为人工智能的开山之作；

1966年，计算机界设计最高荣誉奖：图灵奖。

图灵机基本操作 & 计算概念

什么是计算？图灵的观点

计算是计算者（人或机器）对一条两端可无限延长的纸带上的一串0或1，执行指令，一步一步地改变纸带上的0或1，经过有限步骤最后得到一个满足预先规定的符号串的变换过程。

以上，也是关于数据、指令、程序及程序/指令自动执行的基本思想。

基本操作如下：

图灵机的运行示例

图灵机模型: