Introduction to Computer Science

Presentation on theme: "Introduction to Computer Science"— Presentation transcript:

1 Introduction to Computer Science
计 算 机 科 学 导 论 Introduction to Computer Science 毕 野 计算机科学系 计算机楼407

2 上课地点： 周三3-5节 计算机楼205 前6次理论，后8次上机 教学平台：

3 教学目标： 梳理学科脉络，构建宏观体系 培养计算思维，奠定编程基础 强化操作技能，解决应用问题

4 学习本课程的方法 适当预习 课前简单预习一下，主要清楚老师要讲些什么内容。 上课专心听讲，适当作笔记 记暂时没有听懂的地方，记每章重点
作业独立完成（帮助记忆） 主动加强选择和填空题的练习 进行必要的知识拓展 通过阅读文献资料,认真完成实验内容等方式

5 要求 （1）平时成绩30%，期末70% （2）切记不迟到，不早退，不旷课，上课安静听讲 （3）认真完成作业 用统一的作业本，整版纸书写
基础课作业多，字迹工整 按时交作业

6 第一章 计算机专业（本科段） 知识体系概述 系统的角度——一种横向视角 应用的角度——一种纵向视角

7 计算机系统——从计算器说起 使用计算机的目的是为了帮助人们解决各种问题 为什么不使用计算器？
没有自动计算的能力。为什么没有这种能力？ 没有程序（程序是软件之一）控制其计算过程 计算机解决问题既需要硬件更离不开软件，是一个系统——计算机系统 人们使用的是计算机系统（而不仅仅是硬件）

8 机械计算的简要发展历程是怎样的？ 从表示-自动存储-自动执行的角度 计算与自动计算----机械计算的探索 --任意可变的计算规则 1945年
1834年 现代计算机：一般程序 --任意可变的计算规则 Babbage机械计算机: (特定)程序 --可有限变化的计算规则 1642年 Pascal机械计算机: 自动计算--固定的计算规则 唐代 计算辅助工具 8

9 计算机系统（Compute System）
单机系统：硬件（Hardware）、软件（Software） 多计算机系统：计算机网络（Computer Network）、云计算平台… 系统的观点：资源的调度、优化，分而治之的策略… 本讲座的重点还是放在单机系统上

10 单机系统中的硬件和软件 硬件：现有硬件仍采用冯.诺伊曼体系结构 软件：包括程序、数据和相关文档
构成：五大部件（控制器、运算器、存储器、输入和输出设备） 工作原理：程序存储和程序控制 软件：包括程序、数据和相关文档 程序：控制计算机对数据的加工过程 数据：被加工的对象 程序（Program） 计算机系统硬件 数据（Data） 信息（Information）

11 以存储器为中心的现代计算机构成图 同样是五个部件，以不同的结构来连接，便体现了不同的性能----这就是“系统”：强调“结构”，强调部件连接后的整体性、协同性

12 数据和信息、程序和数据 数据和信息的区别（一般不做明显区分） 程序和数据 数据：原始的事实或观察结果
信息：加工后得到的有意义（meaningful）的事实或规律 程序和数据 从作用/分工角度看，分别是控制者和被控对象 从存在形态来看，程序也以数据的形式存在于系统内部，因此一个程序完全有可能受其它程序的控制，被其它程序看成是数据（奥巴马控制政府，国会控制奥巴马，奥巴马和国会议员都是人民，都可能成为被控对象）

13 硬软件间的桥梁/纽带 数据/信息的二进制编码 系统内部，数据/信息用特定的二进制0-1串表示，也称为数据编码或二进制编码
0和1两种状态对应于电子器件的两种状态 改变器件的状态也就对应着0和1状态位的改变，进而对应着系统状态的变化

14 1 实现0和1的基本元器件: 电信号和继电器开关 0和1与电子技术实现 (1) 如何用电信号及电子元件表达0和1?
数字信号：高电平为1, 低电平为0 1 用继电器开关实现基本逻辑运算 “或”运算电路 “与”运算电路 “非”运算电路 14

15 实现0和1的基本元器件: 二极管 0和1与电子技术实现 (2) 处理0和1的基本元件? 二极管的基本特性 K I V R (b) K V R
F K V L R I (b) K L R V (b) 15

16 c b 实现0和1的基本元器件: 三极管 用b点的0和1来控制c点产生1和0 水 0和1与电子技术实现 (2) 处理0和1的基本元件?
三极管的基本特性： 开关和放大 以较小的b极电流信号可控制较大的e极流过的电流--放大。 第一个三极管试验装置 用b点的0和1来控制c点产生1和0 b c 三极：b点为基极, c点为集电极, e点为发射极。 闸门控制 大坝 水 大水库 典型的三极管电路 16

17 用二极管、三极管可实现基本的集成电路: 与门、或门和非门（对应于三种基本的逻辑运算：与、或、非）
0和1与电子技术实现 (3) 如何用基本电子元件实现基本逻辑运算? 用二极管、三极管可实现基本的集成电路: 与门、或门和非门（对应于三种基本的逻辑运算：与、或、非） 这些电路被封装成集成电路(芯片)，即所谓的门电路。 “与”门电路 “或”门电路 “非”门电路 17

18 基于门电路的复杂组合逻辑电路 1 1 Ai Bi + Ci 1 Ci+1 Si 1 1 0和1与电子技术实现
(5) 如何用已实现的基本逻辑运算(门电路)来实现更复杂的运算? 基于门电路的复杂组合逻辑电路 可验证一位加法器实现的正确性。 1 1 Ai Bi Ci Ci Si 1 1 1 &0 &

19 站在系统的角度——一种横向视角 计算机网络/云计算平台 计算平台构成了为用户提供计算服务的物质基础
可以看成是一种理解计算机系统的横向视角，其计算服务的提供能力不断向外拓展 计算机网络/云计算平台 计算机系统 计算机系统 计算机系统 软件（程序、数据） 硬件 软件（程序、数据） 硬件 软件（程序、数据） 硬件

20 站在应用的角度——一种纵向视角（又称为“0—1思维”）
问题符号化---问题抽象、数学建模 符号计算化---数据表示（或特征表达）、数据结构；算法和程序 计算0-1化---语言处理程序（编译、解释、汇编） 0-1自动化---数据编码、程序存储控制（机器指令执行）

21 问题符号化（1）——抽象 抽象 超越物理的时空观，并完全用符号来表示。数学抽象是一种特例。
示例1.3 哥尼斯堡七桥问题 18世纪经典数学问题 在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛以及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好不重复地通过每座桥一次，再回到起点？ 抽象成一张图

22 问题符号化（2）——数学建模 数学建模 用数学的语言和方法，通过抽象、简化，建立对问题进行精确描述和定义的数学模型
将现实世界的问题抽象成数学模型，就可能发现问题的本质及其能否求解，甚至找到求解该问题的方法和算法

23 算法与算法类问题求解 (5)你知道TSP问题吗? 问题符号化（3）——数学建模示例 TSP问题(Traveling Salesman Problem，旅行商问题)，由威廉哈密尔顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出 TSP问题：有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少。 TSP是最有代表性的组合优化问题之一， 在半导体制造(线路规划)、物流运输(路径规 划)等行业有着广泛的应用。 城市之间的距离 23

24 TSP问题的数学模型 24

25 符号计算化（1）——引入数据结构 寻求数学模型的实质是分析问题，从中提取操作的对象（输入量、输出量、状态变量等），并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 分析待处理的对象的特征及各对象之间存在的关系，这就是《数据结构》这门课所要研究的问题。即：数据结构其实是数学建模后的产物。

26 符号计算化——TSP问题的 数据结构设计 城市映射为编号: A---1, B---2, C---3, D---4
城市间距离关系: 表或二维数组D，用D[i][j]或D[i,j]来确定欲处理的每一个元素 访问路径/解: 一维数组S，用S[j]来确定每一个元素 D[2][3] S 1 4 3 2 {A->D->C->B->A} S[1] S[2] S[3] S[4]

27 符号计算化（2）——算法设计 算法是计算机系统和软件的灵魂。
算法是一个有穷规则的集合，它用规则规定了解决某一特定类型问题的运算序列，或者规定了任务执行或问题求解的一系列步骤。 算法是对数学建模过程中所建模型的求解过程。 算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。 如音乐乐谱、太极拳谱等都可看作广义的算法

28 符号计算化（2）——TSP问题的 算法设计 算法策略设计---算法思想
当数学建模和数据结构设计完成后，就要考虑算法的策略或者说问题求解的策略。 求解TSP的遍历算法：列出每一条可供选择的路线，计算出每条路线的总里程，最后从中选出一条最短的路线。 出现的问题是：组合爆炸 路径组合数目：(n-1)! 20个城市，遍历总数1.216×1017 计算机以每秒检索1000万条路线的计算 速度，需386年。 所有路径组合及其长度 城市之间的距离 28

29 TSP问题的难解性：随着城市数量的上升，TSP问题的“遍历”方法计算量剧增，计算资源将难以承受。
数学建模与算法策略设计---算法思想 (3)算法思想或者算法策略对问题求解有什么影响? TSP问题的难解性：随着城市数量的上升，TSP问题的“遍历”方法计算量剧增，计算资源将难以承受。 2001年解决了德国15112个城市的TSP问题，使用了美国Rice大学和普林斯顿大学之间互连的、速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。 TSP是可计算性问题，但属于可计算问题中的难解性问题！ An optimal TSP tour through Germany’s 15 largest cities. It is the shortest among possible tours visiting each city exactly once. 29

30 TSP问题，有没有其他求解算法呢？ 最优解 vs. 可行解 不同的算法设计策略： 遍历、搜索算法 分治算法 贪心算法 动态规划算法 ……
数学建模与算法策略设计---算法思想 (4)有哪些算法策略? TSP问题，有没有其他求解算法呢？ 最优解 vs. 可行解 不同的算法设计策略： 遍历、搜索算法 分治算法 贪心算法 动态规划算法 …… 可行解 最优解 TSP问题的可行解与最优解示意 30

31 贪心算法是一种算法策略，或者说问题求解的策略。基本思想“今朝有酒今朝醉”。
数学建模与算法策略设计---算法思想 (5)为什么称为“贪心算法”? 贪心算法是一种算法策略，或者说问题求解的策略。基本思想“今朝有酒今朝醉”。 一定要做当前情况下的最好选择，否则将来可能会后悔，故名“贪心”。 TSP问题的贪心算法求解思想 从某一个城市开始，每次选择一个城市，直到所有城市都被走完。 每次在选择下一个城市的时候，只考虑当前情况，保证迄今为止经过的路径总距离最短。 城市之间的距离 31

32 判断某条路径的距离是不是比当前最短路径距离短；
算法思想的精确表达--算法的控制结构设计(II) (1)具体算法-TSP的遍历算法的控制结构如何设计? 开始 求解TSP问题的遍历算法 遍历所有的组合路径； 累加一条路径的距离之和； 判断某条路径的距离是不是比当前最短路径距离短； 如果是，则用新路径取代当前最短路径，并记录其距离； 直到所有路径比较完毕； …… 当前最短路径设为空，当前最短距离设为最大值 组合一条新路径并计算该路径的距离 将思想/策略 转变为“步骤” 比当前最 短距离小吗？ 否 是 将该路径记录为当前最短路径，并用其距离值更新当前最短距离 是 所有路径组 合完毕否？ 否 输出当前最短路径及当前最短距离 结束 32

33 Start of the Algorithm End of the Algorithm 步骤描述法表示的求解TSP问题的贪心算法：
任何两个城市的距离记录在数组D[i,j]中 依次访问过的城市编号被记录在S[1], S[2], …, S[N}中,即第i 次访问的城市记录在S[i]中。 Step(1)：从第1个城市开始访问起，将城市编号1赋值给S[1]。 Step(6)：第I次访问的城市为城市j，其距第I-1次访问城市的距离最短。 Start of the Algorithm (1) S[1]=1; (2) Sum=0; (3) 初始化距离数组D[N, N]; (4) I=2; (5) 从所有未访问过的城市中查找距离S[I-1]最近的城市j; (6) S[I]=j; (7) I=I+1; (8) Sum=Sum+Dtemp; (9) 如果I<=N，转步骤(5)，否则，转步骤(10); (11)Sum=Sum+D[1, j]； (12)逐个输出S[N]中的全部元素; (13)输出Sum。 End of the Algorithm 33

34 步骤描述法表示的求解TSP问题的贪心算法(Cont.)
算法思想的精确表达--算法的控制结构设计(II) (2)具体算法-TSP问题的贪心算法的控制结构如何设计? 步骤描述法表示的求解TSP问题的贪心算法(Cont.) 前述第5步“从所有未访问过的城市中查找距离S[I-1]最近的城市j”还是不够明确，需要进一步细化 (5.1)K=2; (5.2)将Dtemp设为一个大数(比所有两个城市之间的距离都大) (5.3)L=1； (5.4)如果S[L]==K，转步骤5.8；//该城市已出现过，跳过 (5.5)L=L+1； (5.6)如果L<I，转5.4； (5.7)如果D[K,S[I-1]]<Dtemp,则j=K; Dtemp＝D[K,S[I-1]]； (5.8)K=K+1; (5.9)如果K<=N，转步骤5.3。 34

35 流程图表示的求解TSP问题的贪心算法 35

36 符号计算化（3）——程序设计 设计的算法还不能被计算机所理解和执行，需要借助某种程序设计语言把算法中的步骤或规则以计算机能理解的方式表达出来，这就是算法实现，即需要编写出相应的程序。 经典说法：程序=算法+数据结构（N.沃斯） 程序=算法+数据结构+程序设计语言

37 算法、计算机语言与程序的关系 计算机语言 算法 程序 步骤书写的规范、语法规则、标准的集合 是人和计算机都能理解的语言 解决问题 的步骤
由机器语言到高级语言 (1)为什么需要计算机语言? 算法、计算机语言与程序的关系 步骤书写的规范、语法规则、标准的集合 是人和计算机都能理解的语言 计算机语言 算法 解决问题 的步骤 程序 计算机能够理解与 执行的解决问题的步骤

38 算法的实现--TSP问题贪心算法的C程序实例
38

39 计算0-1化——语言处理程序 计算机程序设计语言的发展： 机器语言——汇编语言——高级语言 语言处理程序：
负责将高级语言/汇编语言编写的源程序翻译成机器语言目标程序的程序，包括： 编译程序（编译器） 解释程序（解释器） 汇编程序

40 指令系统：CPU用二进制和编码提供的可以解释并执行的命令的集合。
由机器语言到高级语言 (2)计算机能够理解与执行什么? 计算机语言---机器语言 指令系统 指令系统：CPU用二进制和编码提供的可以解释并执行的命令的集合。 操作码 地址码 计算7+10并存储的程序 机器语言 机器语言：用二进制和编码方式提供的指令系统所编写程序的语言被称为机器语言 所有程序都需转换成机器语言程序，计算机才能执行 问：用机器语言编写程序存在什么问题呢？

41 计算机语言---汇编语言 汇编语言 MOV A, 7 ADD A, 10 MOV (6), A HLT 由机器语言到高级语言
(3)怎样解决机器语言编写程序所存在的困难? 计算机语言---汇编语言 用符号编写程序 == 翻译 == 机器语言程序 人们提供了用助记符编写程序的规范/标准。同时开发了一个翻译程序，实现了将符号程序自动转换成机器语言程序的功能。 汇编语言 计算7+10并存储的程序 操作码 地址码 MOV A, 7 MOV A, 7 ADD A, 10 MOV (6), A HLT 汇编语言：是用助记符号编写程序的语言，是机器语言的符号化。 汇编语言源程序：是用汇编语言编出的程序。 汇编程序: 是将汇编语言源程序翻译成机器语言程序的程序。

42 计算机语言---汇编语言---汇编程序(编译器)
由机器语言到高级语言 (4)符号化程序机器不能直接执行怎么办? 计算机语言---汇编语言---汇编程序(编译器) 汇编语言程序处理过程 汇编 语言 汇编语言源程序 机器语 言程序 机器 语言 转换 用助记符号书写程序的规范、语法规则、标准的集合 是人和计算机都能理解的语言 助记符号 执行 二进制和编码 机器指令的集合 是计算机能够理解并执行，但人理解困难的语言 汇编 程序 转换规则 { 助记符号，机器指令} MOV A, 7 ADD A, 10 MOV (6), A HLT 编制 执行 由汇编程序 自动转换 完成7+10并存储的汇编语言程序 完成7+10并存储的机器语言程序

43 计算机语言---高级语言 高级语言 Result = 7+10; Return 由机器语言到高级语言 (5)为什么还要提出高级语言?
人们提供了类似于自然语言方式、以语句为单位书写程序的规范/标准。并开发了一个翻译程序，实现了将语句程序自动翻译成机器语言程序的功能。 计算7+10并存储的程序 Result = 7+10; Return 高级语言：是用类似自然语言的语句编写程序的语言。 高级语言源程序：是用高级语言编出的程序。 编译程序：是将高级语言源程序翻译成机器语言程序的程序。

44 高级语言：机器无关性；一条高级语言语句往往可由若干条机器语言语句实现且不具有对应性 汇编语言：机器相关性；汇编语言语句和机器语言语句有对应性
由机器语言到高级语言 (6)高级语言和汇编语言的差别在哪里? 高级语言：机器无关性；一条高级语言语句往往可由若干条机器语言语句实现且不具有对应性 汇编语言：机器相关性；汇编语言语句和机器语言语句有对应性 高级语言程序处理过程示意 机器语 言程序 二进制和编码 源程序 语句 编译 程序 MOV A, 7 ADD A, 10 MOV (6), A HLT Result = 7+10 Return

45 高级语言编译器 转换 编译器 汇编器 编译规则 转换 高级语言源程序 汇编语言源程序 机器语 言程序 转换 转换 编译 程序 汇编 程序
助记符号 高级语言源程序 汇编语言源程序 机器语 言程序 转换 转换 执行 执行 变量/表达式/语句 二进制和编码 编译器 汇编器 编译 程序 汇编 程序 编译规则 转换规则 { 助记符号，机器指令} 转换 MOV A, 7 ADD A, 10 MOV (6), A HLT Result = 7+10 Return 编制 执行 自动转换 自动转换 高级语言 机器语言

46 符号化、计算化目前还都依靠人类，不过计算化中的程序化已经可以部分自动实现了！
用计算机进行问题求解 的0-1思维 自然/社会问题 符号化,计算化 自然/社会问题的求解结果 再语义化 执行化 算法 算法的结果 程序化 产生 高级语言程序 程序执行 编译 汇编语言程序 程序执行 汇编 执行化 机器级程序 --机器指令 运算器和控制器(CPU)-执行 自动化 0/1化 信号化 存储 用0/1编码：指令和数据 存储器：0/1存与取

47 相关课程（1） 计算机网络/云计算平台 计算机组成原理：硬件原理 操作系统原理：硬软件资源调度与管理
计算机网络：联网的计算机如何进行有效通信 计算机网络/云计算平台 计算机系统 计算机系统 计算机系统 软件（程序、数据） 硬件 软件（程序、数据） 硬件 软件（程序、数据） 硬件

48 相关课程（2） 编译原理 计算机组成原理、硬件技术基础 数学建模、软件工程 问题符号化---问题抽象、数学建模
符号计算化---数据表示（或特征表达）、数据结构；算法和程序 计算0-1化---语言处理程序（编译、解释、汇编） 0-1自动化---数据编码、程序存储控制（机器指令执行） 数据结构 算法分析和设计 程序设计语言（C、Java等） 数据库 编译原理 计算机组成原理、硬件技术基础

49 Any Question? 软件开发学习路线图 C语言程序设计（面向过程的开发语言） 数据结构 算法分析和设计
Java语言程序设计（面向对象的开发语言） 数学建模（选修） 数据库原理 软件工程 Web开发技术 嵌入式应用开发 Any Question?

50 数据结构与算法的联系与区别 1）数据结构与算法的联系：   程序=算法+数据结构。数据结构是算法实现的基础，算法总是要依赖于某种数据结构来实现的。往往是在发展一种算法的时候，构建了适合于这种算法的数据结构。    算法的操作对象是数据结构。算法的设计和选择要同时结合数据结构，简单地说数据结构的设计就是选择存储方式，如确定问题中的信息是用数组存储还是用普通的变量存储或其他更加复杂的数据结构。算法设计的实质就是对实际问题要处理的数据选择一种恰当的存储结构，并在选定的存储结构上设计一个好的算法。 不同的数据结构的设计将导致差异很大的算法。数据结构是算法设计的基础。用一个形象的比喻来解释：开采煤矿过程中，煤矿以各种形式深埋于地下。矿体的结构就像相当于计算机领域的数据结构，而煤就相当于一个个数据元素。开采煤矿然后运输、加工这些“操作”技术就相当于算法。显然，如何开采，如何运输必须考虑到煤矿的存储（物理）结构，只拥有开采技术而没有煤矿是没有任何意义的。算法设计必须考虑到数据结构，算法设计是不可能独立于数据结构的。 另外，数据结构的设计和选择需要为算法服务。如果某种数据结构不利于算法实现它将没有太大的实际意义。知道某种数据结构的典型操作才能设计出好的算法。   总之，算法的设计同时伴有数据结构的设计，两者都是为最终解决问题服务的。 2）数据结构与算法的区别：   数据结构关注的是数据的逻辑结构、 存储结构以及基本操作， 而算法更多的是关注如何在数 据结构的基础上解决实际问题。算法是编程思想，数据结构则是这些思想的逻辑基础。