人工智能通识课件 第2章 计算思维

人工智能通识第2章计算思维提纲2.1计算与计算思维2.2初识计算思维2.3计算思维的理解2.4计算思维的具体呈现提纲2.1计算与计算思维2.2初识计算思维2.3计算思维的理解2.4计算思维的具体呈现人工计算是指人类通过将数据与运算符结合，按照特定的计算规则进行计算，从而获得结果。例如，加减乘除算术运算；对数、指数、微积分等复杂函数的运算。人类不断地学习新的函数及其计算方法，并利用这些知识解决各种实际问题，得出正确的计算结果。3+4=78÷(2

2)=2算术运算

正态分布函数计算计算机器自动计算是针对某些计算规则设计出简单的机械操作流程，让机器能够重复并自动完成计算任务，本质上是让机器代替人类，自动按照既定规则执行计算。计算机的出现，实现了机器自动计算，使得许多复杂计算能够高效、准确地完成。帕斯卡的加法机

巴贝奇差分机

计算机计算图灵奖获得者、著名数据库专家JimGray观察并总结人类自古以来，在科学研究上先后历经了实验、理论、计算和数据四种范式。实验理论计算数据计算实验手段以物理、化学等自然科学为代表，强调通过观察和总结的“实证思维”；通过“实验”再现社会或自然现象，通过“观察”和“归纳”发现其中的规律。计算理论手段以数学学科为代表，主要特征是推理和演绎的“逻辑思维”；通过“定义”限定研究对象，利用“公理”和“定理”表达对象的性质或规律，并通过“证明”来验证公理和定理的正确性，是揭示社会或自然现象及其规律的重要方法。计算计算手段以计算机科学和人工智能为代表，突出以设计和构造为核心的“计算思维”；通过设计计算算法、构建计算系统，对大规模数据进行自动化分析和处理，从而揭示社会与自然现象及其规律。计算数据手段培养数据思维，树立以数据为中心的问题求解范式；从数据中发现问题、形成结论，挖掘未知的模式和有价值的信息。计算思维图灵奖得主艾兹赫尔·迪杰斯特拉（EdsgerDijkstra）曾指出：“人们所使用的工具不仅影响着人们的思维方式和习惯，更在深层次上塑造了人们的思维能力”。计算思维海量数据各学科研究计算科学计算思维基于计算机科学跨学科结合计算思维2006年，华人学者周以真首次系统性地提出并定义了计算思维（ComputationalThinking）的概念计算思维是指（无论是人还是机器）以计算机能够高效执行的方式来表述问题、表达解决方案的思维过程，它是一种像读、写、算一样，所有人都应具备的基本思维能力。建立在理解计算过程能力与限制的基础上，由人设计并通过机器执行。理解计算机的思维如何运用计算思维提纲2.1计算与计算思维2.2初识计算思维2.3计算思维的理解2.4计算思维的具体呈现计算思维的内涵和价值通过两个典型示例来展示计算思维的内涵及其独特价值第一个示例是现代计算机的设计理念第二个示例是算法的设计思路现代计算机的设计理念计算机的本质是通过程序来控制物理运动，从而实现各种计算任务的。早期的机械计算机试图用更加复杂的机械结构来解决复杂的问题。乔治·布尔克劳德·香农康拉德·楚泽现代计算机的设计理念现代计算机的设计理念XYX与Y（X∧Y）X或Y（X∨Y）X的非（¬X）00001010111001011110现代计算机的设计理念德国力学工程师，通过工程实践证明布尔代数可完成十进制运算和复杂控制逻辑贡献简单，大量复制简单模块设计逻辑人类第一台可编程计算机Z1，一台由电动机驱动齿轮组工作的机械计算机发明现代计算机的设计理念逻辑运算和控制过程可转化为等价开关电路形式，奠定现代数字电路路设计基础现代计算机是这种特殊数字电路的实现在布尔代数和算术运算间搭起逻辑电路桥梁模块化、等价性现代计算机的设计理念模块化就是通过少量简单的基础模块，搭建出各种复杂的功能体系。现代计算机的设计理念等价性计算机及其相关产品之所以容易实现模块化，主要还依赖于等价性这一重要思想。计算任务基础算术运算逻辑运算算法的设计思路算法是为了解决特定问题而设计的一组有序、明确、可执行的步骤或规则。是求解问题的步骤，既不依赖具体的程序设计语言，也不依赖具体的执行环境（包括硬件和操作系统）。递归（Recursive）在算法设计中，较核心的是一种自顶向下、先全局后局部的逆向思考方式递推

（Iterative）人类习惯的自底向上、从小到大的正向思维方式切换思路算法的设计思路递推递推是人类最为本能的正向思维方式，特点是从小到大，由局部到整体，由易到难，顺着已有的经验逐步向前推进。算法的设计思路递推（正向逐步计算）递归（逐层拆解+反向回推）从最小数开始正向依次相乘;掌握方法后，可延申计算100!先逐层向下拆解，找到最简基准；再从底向上反向推导得到结果12345

5!=1×2×3×4×5

5!=4!×54!=3!×43!=2!×32!=1!×21!=1算法的设计思路递归好处每一步只需解决当前的问题解决问题的过程可以完全复用递归前提子问题与原问题形式一样必须有清晰的终止条件算法的设计思路上台阶问题：从第1级台阶（起点）出发，每次可以向上攀登1级或2级，直到到达第20级台阶（终点）。请问共有多少种不同的攀登方法?算法的设计思路一种解法：归纳出一般性规律推导出台阶数n和走法数F(n)之间的关系式

无法通过数学归纳法直接推导出来只有走法的总数，没有攀登的具体方法算法的设计思路递归解法F(20)F(18)F(19)F(16)F(17)F(17)F(18)算法的设计思路递归解法归纳起来，这种关系可以表示为：必须有初始条件F(1)和F(2)：有了F(1)和F(2)，就可以逐步推算出F(3)，继而依次推算到F(20)=10946F(n)=F(n-1)+F(n-2)著名的斐波那契数列到达第1级台阶只有一种走法，即F(1)=1到达第2级台阶有两种方式，即F(2)=2提纲2.1计算与计算思维2.2初识计算思维2.3计算思维的理解2.4计算思维的具体呈现计算思维具体内涵包括：对计算思维的10种不同理解理解1：自动执行。计算机能够自动执行离散步骤的计算过程。理解理解2：正确性。计算机求解问题的正确性可以比特精准地定义并分析。理解3：通用性。计算机能够求解任意可计算问题。理解4：构造性。人们能够构造聪明的方法让计算机有效地解决问题。理解5：复杂度。这些聪明的方法（称为算法）具备时间/空间复杂度。对计算思维的10种不同理解理解6：抽象化。少数精心构造的计算抽象可产生成千上万种应用系统。理解理解7：模块化。多个模块有条理地组合成为计算系统。理解8：无缝衔接。计算过程在计算系统中流畅地执行。理解9：连通性。很多问题涉及用户/数据/算法的连接体，而非单体。理解10：协议栈。连接体的节点之间通过协议栈通信交互。提纲2.1计算与计算思维2.2初识计算思维2.3计算思维的理解2.4计算思维的具体呈现计算思维的4种具体呈现逻辑思维算法思维系统思维网络思维关注计算过程的正确性、通用性，以及能够机械地自动执行关注计算过程的巧妙性，体现为构造性和复杂度关注计算过程的实用性，体现为抽象化、模块化和无缝衔接如何将逻辑思维、算法思维、系统思维推广到网络计算过程，体现为连通性与协议栈2.4.1逻辑思维主要用来回答计算机科学的一个根本性问题：计算过程可以用来解决哪些问题？（1）计算过程可以用来解决哪些问题？这些问题称为可计算问题。（2）是否存在不可计算的问题？（3）是否存在一种通用的计算机？什么是通用计算机？通用又是何含义？2.4.1逻辑思维计算过程：在计算机上通过操作数字符号实现信息转换的过程。最基本理论模型是布尔逻辑，而当需要考虑系统状态时，最基础的理论模型则是图灵机。计算机科学中的逻辑思维主要围绕布尔逻辑和图灵机展开。布尔逻辑图灵机2.4.1逻辑思维主要用来回答计算机科学的一个根本性问题：计算过程可以用来解决哪些问题？（1）计算过程能够解决图灵可计算的问题。（2）存在任何计算过程都无法解决的问题，即不可计算问题。（3）存在通用计算机，即某些计算机具备能够模拟其他任何合理定义的计算机的能力，这种能力被称为通用性。2.4.1逻辑思维布尔逻辑是一种仅处理两种取值（通常是真（True）或假（False））的逻辑体系。在计算机应用中，布尔逻辑主要体现为针对单比特的运算。2.4.1逻辑思维命题逻辑研究命题之间的逻辑关系，以及由逻辑联结词构成的复合命题的真值规律。命题是一个具有确定真值（真或假）的陈述句，用1表示“真”，用0表示“假”。今天下雨了北京师范大学在北京2+2=52.4.1逻辑思维命题逻辑命题逻辑由用符号表示的原子命题和各种逻辑联结词组成。任何命题都对应着一个布尔函数，如下所示，即它把n个变量的取值映射到某个具体的函数值。如果把所有变量的全部可能取值及其对应的函数值逐一列出，每一行表示一种变量的取值情况，这个表就称为该布尔函数的真值表。2.4.1逻辑思维谓词逻辑又称一阶逻辑，是在命题逻辑的基础上发展而来的。不仅能够表达更复杂的断言，还引入了谓词和量词（全称量词

和存在量词

）。断言是一个会传回“真”或“假”的函数。李明是大学生张帅是大学生命题p命题q如果用谓词Stu(x)表示x是大学生断言Stu(李明)断言Stu(张帅)不相关相似2.4.1逻辑思维图灵机现代计算机的运作原理正是基于图灵机的思想。人们普遍认为，任何可计算的问题都可以用图灵机来实现。这一观点被称为丘奇-图灵论题（Church-TuringHypothesis），即所有人类能够用纸和笔完成的计算，本质上都可以由图灵机来完成。丘奇-图灵论题是否绝对成立，至今尚无定论。2.4.2算法思维高德纳（DonaldErvinKnuth）的算法定义一个算法是一组有穷的规则，它给出求解特定类型问题的操作序列，并具备5个特征。2.4.2算法思维算法范式：算法设计的基本方法论分治范式（DivideandConquerParadigm）动态规划范式（DynamicProgrammingParadigm）贪心范式（GreedyParadigm）随机化范式（RandomizationParadigm）2.4.2算法思维4种常用的分析算法复杂度的渐进记号O记号：假设f和g都是从非负整数映射到非负整数的函数。如果存在一个常数c>0，使得对于任意的n，f(n)≤c·g(n)，则称f(n)=O(g(n))。例如：10n+5=O(n)，100n2+n=O(n2)，10nlogn-n=O(n2)。O记号反映了函数随着n的增长其增长的速度快慢，而忽略掉之间可能存在的常数倍的差异。2.4.2算法思维

例如：10n=o(n2)，10nn2=o(n!)，100n=o(1.1n)。2.4.2算法思维4种常用的分析算法复杂度的渐进记号Ω记号：假设f和g都是从非负整数映射到非负整数的函数。如果存在一个常数c>0，使得对于任意的n，f(n)≥c·g(n)，那么就称f(n)=Ω(g(n))。例如：0.1n-8=Ω(n)，n2-106=Ω(n2)，10n-10=Ω(n)。2.4.2算法思维4种常用的分析算法复杂度的渐进记号Θ记号：假设f和g都是从非负整数映射到非负整数的函数。如果f(n)=O(g(n))且f(n)=Ω(g(n))，则称f(n)=Θ(g(n))。例如：10n-8=Θ(n)，10n2+100n=Θ(n2)。可以看出，f(n)=Θ(g(n))中的g(n)往往可以通过删除f(n)中的较小项和最大项的常数获得。2.4.3系统思维核心要义是通过抽象，将不同模块组合成一个系统，使计算过程能够无缝执行。计算系统计算抽象模块化无缝衔接2.4.3系统思维计算系统是计算模型、计算逻辑、算法和程序的实用载体和具体实现。主要提供三方面的功能提供资源为所支持的计算过程的执行提供硬件、软件、数据资源提供接口为用户开发和使用应用程序提供抽象化的接口（编程抽象）忠实执行将程序转化为系统能够理解的步骤序列，比特精准地执行每一步2.4.3系统思维计算抽象数据抽象也称数据类型，是某一类数据及其操作。控制抽象控制多个步骤如何组合起来实现计算过程。例如，文件是一种特殊的数据抽象例如，表达式5×3+3=18中先乘除后加减，可以使用括号强制规定优先级2.4.3系统思维计算抽象模块抽象用于刻画系统的子系统（模块）单元，通常同时包含数据抽象与控制抽象。比如，函数是程序设计语言中较常见的模块抽象。a=5b=10temp=aa=bb=tempprint(f"a={a},b={b}")defswap(a,b):returnb,aa=5b=10a,b=swap(a,b)print(f"a={a},b={b}")2.4.3系统思维模块化模块化是在计算系统的设计与理解中对抽象化方法的应用。其核心是将系统视为由若可组合的部件（即模块或子系统）构成，并围绕三大架构问题展开。系统由哪些模块组成模块如何连接与协作计算过程如何在模块间流动2.4.3系统思维模块化抽象化和模块化的核心在于信息隐藏原理。XYWZAB&&两个与非门级联而成的组合电路系统2.4.3系统思维无缝衔接要求计算机系统在运行过程中各模块和步骤顺畅衔接，信息和计算能够无障碍过渡，不出现阻塞或中断。分层与组合设计计算过程分为程序、指令、时钟多层周期，逐层循环运行。宽进严出输入端兼容误差与噪声，输出端执行严格控制。完备指令规则提供完整指令与细节，覆盖全部场景，实现程序自动运行。瓶颈导向优化紧盯系统性能瓶颈定向优化，随系统变化持续迭代。2.4.4网络思维网络思维是强调连通性和协议栈的思维方式2.4.4网络思维连通性通过网络的名字空间和网络拓扑刻画：名字空间名字空间用于规定网络节点的命名及其合法使用规则，也可用于命名其他实体（如边、消息、操作等）。11010819xxxxxxxx1X属地北京市海淀区出生日期19××年××月××日顺序号校验码2.4.4网络思维连通性通过网络的名字空间和网络拓扑刻画：网络拓扑网络拓扑描述了网络中节点间可能的连接方式及实际使用的连接形式。常见的网络拓扑主要包括静态网络和动态网络两种类型。（