计算机与计算思维

《计算机与计算思维》由会员分享，可在线阅读，更多相关《计算机与计算思维（56页珍藏版）》请在金锄头文库上搜索。

1、大学计算机基础上课信息第一大班：经济1114 讲课：周一 7、8节 周四1、2节 上机：周四 9、10节（19：0021：00） 第二大班: 经济1518 讲课：周一5、6节 周四5、6节 上机：周四7、8节机器安排1教师： 贾应智E-Mail: 交作业服务器：ftp:/202.117.207.198用户名：student 口令：ctec2大学计算机基础3计算意义与计算思维 计算科学方法概论 可计算性与计算过程 计算思维的跨学科交 融 计算机学科的核心概 念与问题求解计算思维的技能 科学思维 逻辑思维 算法思维 效率思维 创新思维 伦理思维4计算思维（Computational thinki

2、ng,CT）由美国 Carnegie Mellon 大学计算机科学教授周以真女士 于2006年提出 她认为，计算思维是运用计算机科学的基础概念 进行问题求解、系统设计、以及人类行为理解 等涵盖计算机科学之广度的一系列思维活动 计算思维代表着一种普遍的态度和一类普适的技 能，每一个人都应热心于它的学习和运用5 是概念化的抽象思维而不只是程序设计 是基本的而不是死记硬背的技能 是人的而不是计算机的思维方式 是数学和工程思维的互补与融合 是思想而不是人造品 面向所有的人和所有地方 关注依旧亟待理解和解决的智力上极有挑战性 并且引人入胜的科学问题6Computation 是可用数学表示的任何形式的信息

3、处理 的概念，它包括简单的计算和人的思维（human thinking） 所以，计算思维无论是由人或机器执行，都是建立在计算 处理的能力和限制之上的 Computing 意味着任何面向目标的需要、受益于和创 造计算机的活动,包括 用于广泛目的的软件和硬件系统的设计、建造； 各种信息的处理、规范和管理； 用计算机开展的科研活动； 使计算机系统具有智能行为； 创建和使用通信和娱乐媒体； 寻找和收集与任何目的有关的信息等7本章涉及的“计算”包含了computation和computing 的内容 对于计算机基础学习而言，了解计算思维的宏观 特性，对于个人专业发展具有重要意义8通过网络可以求解的问题

4、信息查询 交流与沟通 资源的发布与共享9移动通信与地理信息 系统的结合，产生了 新的计算模式：与位 置有关的计算 利用GPS定位，可以找 到周边的服务设施 通过移动信号基站，发 现客户所需要的服务 ：天气、旅游、购物 等移动通讯设备的广泛应用， 催生了诸多新型的商业应用 模式10计算思维的信息化促进了 政务、商务、教育和社会 的信息化 小学校园的门禁系统与移动 通信结合，产生学生在校、 离校信息服务 信用卡消费信息与移动通信 和因特网结合，产生实时消 费报告和无纸化账单报告 校园一卡通11中国经济发展正在向服务 型经济转型 计算机科学与技术及信息 技术则是现代服务型经济 发展的根本保障 Sof

5、tware as a service (SaaS) 和服务计算（service computing）正在引起关注云计算模型示意12计算思维的智能化促进 了交通管理的智能化、 业务流程的智能化、电 子服务的智能化 电子服务和社会生活的 智能化的需求反过来促 进计算思维智能化的进 一步发展智能化能够缓解交通拥堵？13计算思维从计算理论、计算 技术、计算工程、计算工具 、计算服务和计算应用的转 化就是计算思维的工程化 计算思维的工程化促进了诸 如计算机、手机、平板电脑 等计算工具和系统的发展， 后者反过来促进了计算思维 的工程化14计算思维的人性化促进 了人机交互的人性 化、计算工具的人性 化和社会

6、的进步 计算和信息技术对人类 产生的负面影响同样 不可小视 信息社会中的“宅人” 数码相机 vs.胶片工业 数字印刷 vs. 铅字印刷人性化设计 笔记本电脑支架15层次化源于社会组织和分工 计算思维的层次包括计算理论思维、计算技术思 维、计算工程思维、计算工具思维、计算服务 思维和计算应用思维六个层次思维组成它们分别对应计算理论、计算技术、计算工程、 计算工具、计算服务和计算应用 每个层次上的思维都至少包含许多不同的思维过 程、思维模式和思维规律16结构化源于软件开发的结 构化系统分析、结构化设 计和结构化程序设计 重要的案例 计算机体系结构 多核CPU GPGPU（通用图形处理器） 网络体系

7、结构 ISO/OSI 参考模型 TCP/IP模型Intel Core 2 Duo Processor17计算思维源于并服务 于由计算理论、计 算技术、计算工程 、计算工具、计算 服务和计算应用构 成的计算思维生存 周期 这一生存周期以计算 理论为始点，以计 算应用为终点18“计算思维”是面向所有的人，所有学科的，应 当具有普适性，但这种普适的内部是有差异的 计算机科学是新兴学科，其内容日新月异，以 及人的智力水于有高低之分，人们已掌握的计 算机知识各有差异，不同人的计算思维具有很 大差别，因此计算思维具有层次性 只要具有思维品质中的独创性，就能创造性地 解决问题 不同层次上的计算机思维均可得到

8、同质性的发 展19科学界一般认为，科学 方法分为理论、实验 和计算三大类 与三大科学方法相对的 是三大科学思维，理 论思维以数学为基础 ，实验思维以物理等 学科为基础，计算思 维以计算机科学为基 础20理论源于数学，理论思 维支撑着所有的学科 领域。正如数学一样 ，定义是理论思维的 灵魂，定理和证明则 是它的精髓 公理化方法是最重要的 理论思维方法，科学 界一般认为，公理化 方法是世界科学技术 革命推动的源头。21实验思维方法可以分为以下三个步骤： 先提取出从现象中获得的直观认识的主 要部分，用最简单的数学形式表示出来 ，以建立量的概念； 再由此试用数学方法导出另一易于实验 证实的数量关系；

9、然后通过实验证实这种数量关系 对于实验思维来说，最为重要的事情就是 设计、制造实验仪器和追求理想的实验 环境22计算思维最根本的内容，即其本质是抽象（ Abstraction）与自动化（Automation） 计算思维中的抽象完全超越物理的时空观，并完 全用符号来表示，其中，数字抽象只是其中的 一类特例 计算思维中的抽象最终是要能够利用机器的一步 步自动执行。为了确保机器的自动化，就需要 在抽象的过程中进行精确和严格的符号标记和 建模 还要求计算机系统或软件系统生产厂家能够向公 众提供各种不同抽象层次之间的翻译工具23计算机科学在本质上源自数学思维，因为像所有 的科学一样，它的形式化基础建筑于

10、数学之上 计算机科学又从本质上源自工程思维，因为我们 建造的是能够与实际世界互动的系统，基本计 算设备的限制迫使计算机科学家必须计算性地 思考，而不能只是数学性地思考 构建虚拟世界的自由使我们能够超越物理世界的 各种系统 数学和工程思维的互补与融合很好的体现在抽象 、理论和设计三个学科形态（或过程）上24计算理论是研究使用计算机解决计算问题的数学 理论 有三个核心领域：自动机理论、可计算性理论和 计算的复杂性理论 自动机将离散数学系统的构造，作用和关系作为研究 对象的数学理论（描述通用计算机计算能力的图灵机 模型） 可计算性理论的中心问题是建立计算的数学模型，进 而研究哪些是可计算的，哪些是不

11、可计算的 计算的复杂性理论研究算法的时间复杂性和空间复杂 性 25计算机学科的方法论有三个过程：抽象、理论和 自动化设计及实现 最根本的问题在于：问题如何进行描述？哪些部分能 够被自动化？如何进行自动化描述？ 建立物理符号系统并对其实施等价变换是计算机 学科进行问题描述和求解的重要手段。 “可行性”所要求的“形式化”及其“离散特征”使得数 学成为重要的工具 而计算模型无论从方法还是工具等方面，都表现 出它在计算机上科学中的重要作用（参见1.3节 ）26科学：关于自然、社会和 思维的发展与变化规律 的知识体系，其核心是 发现 技术：根据实践经验和科 学原理而发展形成的各 种工艺操作方法、技能 和

12、技巧，其核心是发明 工程：将科学原理应用到 生产实践中，是某种形 式的科学应用，其核心 是建造我们所使用的工具影响着 我们的思维方式和思维习 惯，从而也将深刻地影响 着我们的思维能力Edsger Dijkstra27霍夫曼编码使用变长编码 表对源符号（如文件中 的字母）进行编码 变长编码表通过评估来源 符号出现概率的方法得 到的，概率高的字母用 较短的编码，出现概率 低的则用较长的编码 使编码之后的字符串的平 均长度、期望值降低， 从而达到无损压缩数据 的目的四个状态的霍夫曼编码过程28设信号源为X= 、a、e、I、m、t、c、h、r 。 对应的概率为 p= 0.22、0.22、0.14、0.

13、07、0.07 、0.07、0.07、0.07、0.07 ,试给出该信源的霍夫 曼编码方案。 解：若传送一个串字符串“I am a teacher”，共14个字 符。若用ASCII传送，每个字符8位，共需112位 。该字符串中有9个不同的符号，至少需要4位二 进制才能表示，这样传送该字符串也要56位。若 用计算的Huffman编码，只需要42位。 霍夫曼编码举例29霍夫曼编码过程 可以得到：a的编码00 e的编码 111 I的编码1101 m的编码1100 t的编码1011 c的编码 1010 h的编码1001 r的编码 1000原字符串（二进制）长度：= 112（148）位Huffman编码

14、长度： = 42位（01 00 111 1101 1100 1011 1010 1001 1000）30在数论中，反运算的问题往往是极难求解的，或 者说极难计算的 离散对数和整数因式分解问题就属于困难的计算数论 问题 如果给出两个素数p和q，要求两者的乘积，即使p和q 很大，那计算它们的乘积仍然是可行的 但反过来，给出N，要求p和q就极为困难了 利用反计算的难度，对数据进行加密，是现代密 码学的基础 计算机通讯中的公开密钥加密算法，就是利用了 数论的这个原理31密钥举例： 在马丁加德纳的数学游戏一书中，报告了1977年 由RSA（Rivest,shamir和Adleman）悬赏100美元求解对

15、一 个密钥的破解问题。给出一对整数（e,N）作为公开钥 ，e=9007，N是一个随机的129位数 114381625757888867669235779976146612010218296721242362562561 8429357069352457338978305971235639587058989075147599290026 878543541 经过它加密后得到的密文C是 968696137546220614771409222543558829057599911245743198746951 2093081629822514570835693147662288398962801339

16、905518299451 557815154 问C加密前的明文是什么？32问题结论这个问题在1994年4月2日，即相隔了17年之后由迪里克阿特金斯（ Derek Atkins），迈克尔克拉弗（Michael Graff）和阿尔金K廉斯特拉 （Arjen KLenstra），帕尔雷兰德（Panl Leyland）解出，他们对上述 的N成功地进行因式分解，它的两素因子是：3490529510847650949147849619903898133417764638493387843990820577 和3276913299326670954996198819083446143177642967991941539798288533在得到了p和q后，从密文计算明文的障碍就被克服了，这个明文是200805001