《计算与人工智能概论》计算与人工智能概述

计算与人工智能概论计算与人工智能概述

计算的概念1PART1.1.1什么是计算什么是计算？在计算机科学领域，计算是根据设定的规则将一串编码转换成另一串编码的过程。例如：加法问题，输入一对数值，输出是该对数值的和。排序问题，排序计算对每个输入表都赋予一个输出表，而输出表的数据项与输入表一样，只是输出表的数据项是按照升序或降序排列的。在数学领域，计算是抽象数学思想在具体数据上的应用，例如用数字进行加、减、乘、除的运算。1.1.1什么是计算什么是计算？在计算机科学领域，计算是根据设定的规则将一串编码转换成另一串编码的过程。例如：加法问题，输入一对数值，输出是该对数值的和。排序问题，排序计算对每个输入表都赋予一个输出表，而输出表的数据项与输入表一样，只是输出表的数据项是按照升序或降序排列的。在数学领域，计算是抽象数学思想在具体数据上的应用，例如用数字进行加、减、乘、除的运算。1.1.1什么是计算计算的历史1.1.1什么是计算可计算问题计算模型之一：图灵机（Turingmachine）阿兰·麦席森·图灵于1936年在其发表的论文《论可计算数及其在判定问题中的应用》中，针对可计算边界问题提出了一种抽象的计算模型——图灵机图灵将逻辑中的任意命题用图灵机来表示和计算，并按照规则推导出结论，其结果是——可计算函数等价子图灵机能计算的函数图灵机的提出证明了通用计算理论，肯定了计算机实现的可能性，同时它给出了计算机应有的主要架构，这为计算机的诞生和发展提供了理论基础可计算边界问题：哪些问题是可计算的，哪些问题是不可计算的？求解思路：为计算建立一个数学模型，称之为计算模型，然后证明，凡是这个计算模型能够解决的问题，就是可计算的问题。1.1.2图灵机基本原理图灵机的基本原理是用机器来模拟人们用纸笔进行数学运算的过程。图灵机将一个无限长的带子作为无限存储，它有一个读写头，能在带子上读、写和左右移动。图灵机开始运作时，带子上只有输入串，其他地方都是空白，如果需要保存信息，则其可以将相关信息写在带子上。为了读取已经写下的信息，它可以将读写头往回移动到这个信息所在的位置。机器不停地计算，直到产生输出为止。1.1.2图灵机图灵机执行计算的具体案例利用图灵机执行“1+2=3”的计算。先定义读头读到“+”之后，依次移动读头两次并读取格子中的数据；接着读头进行计算，最后把计算结果写入第二个数据的下一个格子里，1.1.3什么是计算机冯·诺依曼体系结构输入设备输出设备程序运行1.1.3什么是计算机计算机系统：硬件层+操作系统层+应用软件层硬件系统软件操作系统应用软件工具软件语言处理系统数据库管理系统政务软件娱乐软件学习软件1.1.3什么是计算机计算机硬件传统“计算机器”多样化的“计算机器”，各种设备的“大脑”系统在探索最短路径的过程中，首先需要从键盘输入机器人所处环境的地图，然后由操作系统将地图数据传送到内存，由中央处理器对数据进行运算并获得结果，最后在显示器上输出寻找到的最短路径。1.1.3什么是计算机计算机硬件中央处理器是计算机的核心硬件，它往往以处理器芯片的形式存在。在现实生活中，各类处理器芯片无处不在，多样化的计算机控制着各种机械设备运行。交通中的汽车、平衡车等，日常生活中的冰箱、洗衣机等智能家居设备，都与处理器芯片紧密相关。1.1.3什么是计算机计算机软件硬件有形，而软件无形。计算机软件多种多样。它可以是计算机系统中的各类程序，也可以是用户与硬件之间的接口程序，还可以是运行在硬件上的各种程序的总称智能终端应用软件软件供应商网上商城商品供应商1.1.3什么是计算机计算机是什么?认知世界的工具各种机器的大脑各种软件的载体创建虚拟世界的工具计算的工具1.1.4算法、计算机语言与程序算法、计算机语言与程序之间的关系1.1.4算法、计算机语言与程序高级语言源程序及其编译过程示意-以智能机器人寻路计算两点间距离为例求智能机器人在环境中行走的最短路径时，需要重复不断地求出当前位置与下一位置之间的距离。假设已知机器人已经行走的距离为2cm，机器人还需要往前走4cm，那么机器人总共需要行走的路径长度为多少呢？算法、计算机语言与程序之间的关系1.1.4算法、计算机语言与程序从二进制机器语言到计算机语言计算机语言的发展1.1.4算法、计算机语言与程序问题求解策略与算法用两种不同的算法解决求解机器人行走的最短距路径问题针对最短距路径求解问题，我们可以将其抽象为一个组合优化问题，即：机器人从起点走到终点的过程中，有n个节点需要访问，按怎样的次序访问，才能使机器人访问路径的“权值和”最小？遍历算法基本思想：利用遍历算法求解最短距路径时，可以把复杂的路径分解求解，把可能短的每一条路径通过穷举法列举出来，再比较得出最短距路径，该最短距路径即为问题的解。时间复杂性：O(n!)。贪心算法基本思想：利用贪心算法求解最短距路径时，从某一个节点开始，每次选择一个节点，直到所有节点都被选完。时间复杂性：多项式量级O(n3)。贪心算法牺牲了结果的精度（即求得的不一定是最优解），但换来了时间上可观的节约，如将算法复杂度直接降到多项式量级O(n3)。1.1.4算法、计算机语言与程序问题求解策略与算法用两种不同的算法解决求解机器人行走的最短距路径问题遍历算法流程图贪心算法流程图什么是计算思维？2PART1.2.1计算思维的概念计算思维的概念周以真教授在美国计算机权威期刊《CommunicationsoftheACM》杂志上给出，并定义的计算思维（ComputationalThinking）：计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。计算思维教学改革宣言2013年2006年教育部高等学校大学计算机课程教学指导委员会发表旨在大力推进以计算思维为切入点的计算机教学改革宣言。教育与科学思维；计算机教育与计算思维；人才培养与计算思维教学改革；构建多方位、立体化人才培养平台。CMU计算机系主任/学术事务副校长NSF信息学部主任微软研究院副总裁哥伦比亚大学数据科学研究院主任1.2.1计算思维的概念计算思维的概念计算思维是人类应具备的第三种思维理论思维:假设/预设定义/性质/定理证明.---推理和演绎实验思维:实验观察发现、推断与总结.---观察与归纳计算思维:设计,构造与计算.---设计与构造计算思维关注的是人类思维中有关可行性、可构造性和可评价性的部分当前环境下，理论与实验手段在面临大规模数据的情况下，不可避免地要用计算手段来辅助进行。1.2.2问题求解方法Google计算思维计算思维（CT）是一个有着诸多特点和要求的问题解决过程。可用于解决人文科学、数学和科学等各种学科的问题。不但能了解各学科之间的关联，同时也能够体会到课外生活与课堂内的知识之间的联系。分解：把数据、过程或问题分解成更小的、易于管理的部分。模式识别：观察数据的模式、趋势和规律。抽象：识别模式形成背后的一般原理。算法设计：为解决某一类问题撰写一系列详细步骤1.2.2问题求解方法计算思维与计算机科学的区别1.2.2问题求解方法计算思维案例1：分解分解：分解就是把大问题拆解成小问题，把复杂问题拆解成简单问题，把新问题拆分成老问题。对于一块大蛋糕，如果不切开，吃起来是非常困难的。使用工具把它分成一小块一小块来吃，一小块也不可能一次吃完，还要一口一口吃。1.2.2问题求解方法计算思维案例2：模式识别模式识别：寻找问题内或者子问题之间的模式、规律或者趋势。简单来说，就是找规律。一个苹果的价格是3元，3个苹果是9元，即单价乘上数量，现在知道一个梨子是4元，5个梨子多少钱？模式：单价*数量=总价1.2.2问题求解方法计算思维案例3：模式归纳模式发掘就是探索学科案例中蕴含的一些模式，并形成一套您独有的、借助模式识别方法进行问题研究的流程。1.2.2问题求解方法计算思维案例4：抽象抽象：指事物相关和重要的信息，它涉及从无关细节中分离出核心信息。抽象是计算思维的核心。1.2.2问题求解方法计算思维案例5：算法设计算法设计：完成某项任务的一系列指令，即解决问题的方案（步骤）。步骤中又包含分解，抽象，及模式识别，它就像一条线，串起计算思维在各个领域的应用。例如火星机器人着陆后，如何在无人控制情况下，实现自动寻路呢？1分解：在控制火星机器人翻越前面障碍的过程当中，机器人要左右移动，可以把它分解成左移或者是右移的动作。2模式：左移的模式与右移类似，左移设计好了，直接运用到右移即可。3抽象：机器人与障碍物的处理可以将机器人抽象成多边形，通过计算多边形之间是否重叠来判断其是否撞到障碍物导致游戏失败。4算法：实现程序，依次完成角色导入（即背景，、火星机器人、障碍图标等）、设定机器人初始位置、控制机器人上下移动、背景移动，设计碰撞检测算法等。1.2.3算法-计算系统的灵魂算法、数据和计算能力是人工智能的三大基石，其中算法是非常重要的一个部分。好的算法能节约很多资源，甚至能够完成一些不可能完成的任务。在任何应用领域，精心设计的算法都是解决大型问题最有效的方法。人工智能机器学习算法包括包括监督学习、无监督学习、半监督学习，强化学习、深度学习、迁移学习、强化学习等。人工智能机器学习算法分类人工智能之机器学习算法探索人工智能3PART1.3.1智能移动机器人路径规划智能移动机器人路径规划路径规划环境示意图本质智能移动机器人路径规划是一个集环境感知、动态决策与规划、行为控制与执行等多种问题于一体的综合人工智能例子，它融合了计算机技术、自动控制、传感器技术、信息处理以及人工智能等多学科知识，是目前科学技术发展最活跃的领域之一。问题描述：让一个智能机器人从迷宫的起点S出发，自动绕过迷宫内的障碍物，并使用最少的时间走到迷宫终点E。智能机器人：包含有机身、电源、传感器、微处理器、电机及驱动等部分，智能机器人利用传感器感知检测前方、左边、右边是否有障碍物，在电机控制下可以执行直行、左转、右转等运动及避障行为。环境地图：有起点与终点，有墙，有墙与墙之间的通道，外围有边界。问题描述1.3.1智能移动机器人路径规划计算思维首先是需要将问题分解成一系列较小可管理的问题过程。智能移动机器人路径规划问题可以分解为两个子问题：子问题1

机器人对地图的“记忆”子问题2探索机器人在环境中行走时可能面对的情况以及该采取的行动

子问题1地图的构建与表示机器人对环境的记忆子问题2智能移动机器人遇到的状况机器人的行动

左边有墙，前边没有墙左边没墙左边有墙，前边也有墙智能移动机器人路径规划问题分解问题分解1.3.1智能移动机器人路径规划人（蒙上眼睛）机器人靠墙行走靠墙行走用手搜索用红外避障传感器感知双手配合用两个红外避障传感器模式识别是要观察找出问题的模式、趋势和规律。人寻路：用两只手配合并沿着墙壁探索路线的时候，我们能够在各种状况下（如拐角）很好地做出相应的判断，并顺利找到出口机器人寻路：将红外传感器嵌入机器人，作为机器人的“双臂”，用以感知检测前方、左边、右边是否有障碍物智能移动机器人寻路与人寻路相似之处模式识别1.3.1智能移动机器人路径规划模式挖掘（抽象）即探寻模式形成背后的一般原理，寻找一类问题的一般方法。地图构建将地图划分成网格，蓝色格子代表墙壁，白色格子代表路地图抽象把地图转换为数学形式，用1和0分别定义蓝色格子和白色格子机器人状态行为抽象机器人感知探测不同状态时对应执行不同动作地图构建地图抽象机器人状态行为抽象抽象1.3.1智能移动机器人路径规划算法设计即为解决某一类问题撰写一系列详细的指令。以智能移动机器人寻路左手定则的算法流程为例：检测左侧是否有墙：如果没有则左转，如果有则执行②；检测前方是否有墙；如果没有则直行，如果有则执行③；检测右侧是否有墙；如果没有则右转，如果有则左转；直到移动机器人到达目的终点，完成任务。智能移动机器人寻路（左手定则）算法设计1.3.2人工智能历史图灵测试图灵测试是区分人与人工智能设备的一个测试，测试中要求一个人和一台拥有智能的机器设备在互不相知的情况下，进行随机的提问交流，如果超过3成的测试者没有发现对方是机器设备，就代表这台设备拥有“人类智能”。聊天机器人尤金.古斯特曼清华大学语音与语言实验中心(CSLT)研发的作诗机器人“薇薇”1.3.2人工智能历史图灵测试和人工智能的关系“全部智能行为”对应的集合和“全部人类行为”集合之间有相交部分也有不同之处。全部智能行为和全部人类行为之间的交集（如猴妈妈分桃）即可通过图灵测试。猴妈妈拥有部分智能行为，可以将一堆桃子较为公平的分给3个儿子，但她并不具有全部人类行为，但我们可以说其拥有智能并可通过图灵测试。类似的机器人拥有某一项智能行为，比如自然语言处理、图像识别等，并不一定要拥有全部人类行为，但仍可通过图灵测试。因此，主流的人工智能是以解决人脑能解决的问题为目标，注重解题能力，而不在乎解题行为是否和人类相似。1.3.2人工智能历史人工智能领域关键事件时间轴1.3.3人工智能相关研究人工智能近10年“十大人工智能研究热点”人工智能涉及计算机科学、电子、自动控制、机械、心理学、伦理学、哲学和语言学等多个学科，几乎涵盖自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，它的终极目标是使机器拥有像人类一样的智力，可以替代人类实现学习、推理、思考、规划等多种功能。从应用的角度看，人工智能的研究主要集中在以下几个方面：机器人、语音识别、模式识别、自然语言处理、专家系统、计算机视觉、计算智能、自动程序设计、智能控制与智能规划等。AMiner评选出的近10年“十大人工智能研究热点”1.3.3人工智能相关研究1.3.3人工智能相关研究人工智能研究案例在航天领域，人工智能已经成为中国航天的“探路者”，例如火星探测器。“天问一号”使用了基于计算机视觉、自然语言处理、机器学习、语音识别等技术的人工智能技术。人脸检测的任务就是判断给定的图像上是否存在人脸，如果人脸存在，就给出全部人脸所处的位置及其大小。1.3.3人工智能相关研究人工智能研究案例AlphaGo的实现原理给胜率高的点分配更多的计算力任意时间算法，计算越多越精确1、选取2、展开3、评