第1章+前世今生--计算与计算机

第1章前世今生--计算与计算机学习目标理解计算和计算机器理解计算机科学和计算机科学中的经典问题熟悉计算机硬件和软件发展的历史和趋势了解计算机用户角色的转换了解系统程序员和应用程序员掌握计算机系统的概念掌握计算机系统的分层结构掌握计算机的特点、分类理解计算机对生活方式的改变了解计算机的应用领域内容提要认识计算机和计算机科学计算机的发展从计算工具到计算机计算机硬件发展计算机软件发展计算机系统及其抽象分层计算机的特点及分类计算机与社会什么是计算？1.1.1计算与计算机计算是“数据”在“运算符”的操作下，按“规则”进行的数据变换3+5=8hrrhrf22),(2hrrhrf22),(2hrrhrf22),(2各种计算“规则”越来越复杂，加减运算、对数运算、指数运算、微积分运算......除了学规则外，还要应用这些“规则”来求解各种问题“规则”可以学习，但是应用“规则”来求解问题有时却超出了人的计算能力…知道规则，很难（或者没有办法）通过人工计算得到结果化简，把复杂问题化简为简单规则的组合设计一种机器，代替人工计算用来帮助人们计算的机器称为计算机等式数目比未知数数目少；要求找出对所有等式都成立的整数组合问题？（1）哪些问题可以自动计算？哪些问题可以在有限时间、有限空间内自动计算？算法分析（2）如何低成本、高效地实现自动计算？构建计算机器（3）如何方便有效地利用计算机器进行计算。计算机的应用1.1.2计算机科学研究计算机器和可计算系统的理论方面的学科，包括：计算系统的硬件设计与构造、发现和提出新的问题、寻找新问题的求解算法、发现和设计使用计算机的新方式围绕如何构造各种计算机器和应用各种计算机器理解计算系统是如何工作的？理解如何利用计算系统来控制和处理现实世界的各种事物？计算思维（ComputationalThinking）Learning-Doing-Thinking1.1.3计算机科学中的经典问题经典问题往往以深入浅出的形式来表达深奥的科学规律和本质内容，在学科研究中常常用来辅助说明思想、原理、方法和技术哥尼斯堡七桥问题与图论哲学家就餐问题与资源管理汉诺塔问题与可计算性证比求易问题与并行计算TSP问题与组合爆炸问题两军问题与计算机网络图灵测试与人工智能Story1哥尼斯堡七桥问题与图论哥尼斯堡七桥问题与图论欧拉回路的判定规则：（1）如果通奇数桥的地方多于两个，则不存在欧拉回路；（2）如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；（3）如果没有一个地方是通奇数桥的，则无论从哪里出发，都能找到欧拉回路。CADB“七桥”是图论研究的开始，图论已广泛应用在计算学科、运筹学、控制论、信息论等学科中抽象是提取问题中最本质的东西，忽视问题非本质的东西哈密顿回路问题哈密顿回路：要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。1983141202131545679101112161718尚未找到图G是否存在哈密顿回路的充分必要条件Story2哲学家共餐问题与资源管理哲学家的生活进程可表示为：（1）思考问题；（2）饿了停止思考，左手拿起一只筷子（如果左侧哲学家已持有它，则等待）；（3）右手拿起一只筷子（如果右侧哲学家已持有它，则等待）；（4）进餐；（5）放下左手筷子；（6）放下右手筷子；（7）重新回到状态（1）思考问题；哲学家共餐问题与资源管理程序并发执行时进程同步的两个关键问题——死锁和资源耗尽：（1）按哲学家的生活进程，当所有的哲学家都同时拿起左手筷子时，则所有哲学家都将拿不到右手筷子，并处于等待状态，那么，哲学家都将无法进餐，最终饿死。（2）将哲学家的生活进程修改为当拿不到右手筷子时，就放下左手筷子。但是，可能在一个瞬间，所有的哲学家都同时拿起左手筷子，则自然拿不到右手筷子，于是都同时放下左手筷子，等一会，又同时拿起左手筷子，如此重复下去，则所有的哲学家都将无法进餐。操作系统必须彻底解决由于资源共享而产生的--竞争问题！Story3汉诺塔问题与可计算性在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。汉诺塔问题与可计算性BABCABCAACABC(a)(b)(c)(d)汉诺塔问题与可计算性n个碟子的汉诺塔问题需要移动的碟子数是n-1第一步为，第二步为1，第三步为。因此：2121121()2(1)12(2(2)1)12(2)212(0)2221222121nnnnhnhnhnhnh(1)hn(1)hn汉诺塔问题与可计算性●64个碟子的汉诺塔问题，需要移动的碟子数为：264－1＝18,446,744,073,709,551,615●如果每秒移动一次，一年有31,536,000秒，则僧侣们一刻不停地来回移动，也需要花费5849亿年的时间●假定计算机以每秒1000万个碟子的速度进行移动，则需要花费58,490年的时间。理论上可以计算的问题，实际上并不一定能行，这属于计算复杂性领域的研究内容。将可以在多项式时间内求解的问题看作是易解问题，可以在可接受的时间内实现问题求解；将需要指数时间求解的问题看作是难解问题，计算时间随着问题规模的增长而快速增长计算问题分为可计算（理论上可计算&时间上可计算）与不可计算从前，有一个酷爱数学的年轻国王艾述向邻国一位聪明美丽的公主秋碧贞楠求婚。公主出了这样一道题：求出48770428433377171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。国王回去后立即开始逐个数地进行计算，他从早到晚，共算了三万多个数，最终还是没有结果。国王向公主求情，公主将答案相告：233092827是它的一个真因子。国王很快就验证了这个数确能除尽48770428433377171这个数。公主说：“我再给你一次机会，如果这次你还求不出来，将来你只好做我的证婚人了。”Story4证比求易问题与并行计算证比求易问题与并行计算国王立即回国，向时任宰相的大数学家孔唤石求教，大数学家在仔细地思考后认为一个17位的数，其最小的一个真因子不会超过9位，于是，他给国王出了一个主意：按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立即将它通报全国，让每个老百姓用自己的编号去除这个数，除尽了就立即上报，赏金两万。经过宰相孔唤石的指点，国王最终求婚成功。证比求易问题●在计算复杂性领域中，一般认为求解一个问题往往比较困难，但验证一个问题相对来说就比较容易——证比求易。●求大整数S=48770428433377171的因子是个难解问题，但是验证a=223,092,871是不是大整数S的因子却很容易；●求一个线性方程组的解可能很困难，但是验证一组值是否是方程组的解却很容易。当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。就难解性问题而言，单纯地提高计算机系统的速度是远远不够的，而降低算法的复杂度的数量级才是最关键的。Story5TSP问题与组合爆炸TSP问题（又称货郎担问题、邮递员问题、售货员问题）是数学家克克曼于19世纪初提出的一个数学问题，是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。由于TSP问题有着貌似简单的表述、重要的应用、以及和其他NP完全问题的重要关系，它在近200年的时间里强烈地吸引着计算机科学工作者。TSP问题8abdc23571否18a→d→c→b→a6否23a→d→b→c→a5是11a→c→d→b→a4否23a→c→b→d→a3是11a→b→d→c→a2否18a→b→c→d→a1是否最短路径长度路径序号●10城市的TSP问题有大约180,000个可能解。●20城市的TSP问题有大约60,000,000,000,000,000个可能解。●50城市的TSP问题有大约1062个可能解，而一个行星上也只有1021升水。TSP问题对于具有n个顶点的TSP问题，可能的解有：(n-1)!/2个。组合爆炸●组合优化问题：寻找一个组合对象，比如一个排列或一个组合，这个对象能够满足特定的约束条件并使得某个目标函数取得极值。●无论从理论的观点还是实践的观点，组合优化问题都是计算领域中最难的问题，其原因是：（1）随着问题规模的增大，组合对象的数量增长产生组合爆炸；（2）还没有一种已知算法能在可接受的时间内，精确地求解绝大多数这类问题。Story6两军问题与计算机网络一支白军被围困在一个山谷中，山谷的两侧是蓝军。困在山谷中的白军人数多于山谷两侧的任一支蓝军，而少于两支蓝军的总和。若一支蓝军对白军单独发起进攻，则必败无疑；但若两支蓝军同时发起进攻，则可取胜。两支蓝军希望同时发起进攻，这样他们就要传递信息，以确定发起攻击的具体时间。假设他们只能派谴士兵穿越白军所在的山谷（惟一的通信信道）来传递信息，那么在穿越山谷时，士兵有可能被俘，从而造成消息的丢失。现在的问题是：如何通信，以便蓝军必胜。蓝军蓝军白军不存在使蓝军必胜的通信约定（协议）两军问题与计算机网络网络协议（简称协议），是为网络中的数据交换而建立的规则、标准或约定的集合互联网软件的分层结构计算机网络云服务Story7图灵测试与人工智能提问者回答者A回答者B“机器能思考吗？”人工智能分布式的控制系统将很多模式的识别和决策分配给了现场的控制设备，这些控制设备对生产过程所产生的数据以及背后的模式会有深刻的了解，进而做出代替人脑的智能判断我们虽然可以对语言进行准确的识别，但是人类表达中那些微妙语意，以及语言背后的情感和双关语是机器今天无法理解的，关于语意的识别需要构建更新的类似人脑的模式分辨方式和新的学习系统人工智能研究方向一在人工智能方面，有两个主要的研究方向：一种是采用传统的编程技术，使系统呈现智能的效果，而不考虑所用方法是否与人或动物机体所用的方法相同，这种方法叫工程学方法，这一方面的成果是极其显著的。包括科大讯飞的语音识别，还有IBM的人机大战的成功，都属于工程学的方法。人工智能研究方向二另一种是模拟法，与人类或生物机体所用的方法相同或类似：原则是编程者为每一个角色设计一个智能系统来进行控制，这个智能系统可能开始时候什么也不懂，就像出生婴儿一样，但是它能够快速学习，逐渐适应环境，甚至通过犯错不断吸取教训，下一次运行的时候就能改正，至少不会永远错下去……遗传算法和人工神经网络，都属于这个范畴。因为第一种工程学的方法会占用大量的计算资源，而当我们考察人脑的运行方式的时候，会发现它更接近模型法。其实在实时处理庞大的数据方面，虽然人脑略逊一筹，而且运行速度也比较慢，也不够精确，但是在识别、解释和根据模式做出反应方面，人脑却是当前的计算机根本无法代替的。而且整个大脑耗费的能源与一个20W的灯泡相当，所占体积也不足2L，但是在大规模计算机系统，99%的系统分给了供电和降温，仅用1%来处理信息。因此科学家们一直试图模拟人脑工作的芯片，IBM在这方面已经获得了关键突破，2014年8月，IBM对外宣称，他们开发的新一代芯片TrueNorth,采用模拟人脑结构中的神经突触内核，其芯片采用了54亿个晶体管。是传统PC处理的4倍以上，其效果相当于100万个神经元和2.56亿个突触。每一个结构都能使用一种名叫Crossbar的通信模式来存储处理，并向其他结构传输数据，每一个这样的内核都使用了事件驱动设计，也就是说它不会一直运行，只有在需要的时候次才会启动，从而使得芯片运行更节能。1.2计算机的发展了解历史可以了解技术的进步、解释为什么计算机是今天这