计算机科学导论第十五周学习总结

一、程序设计语言

1.程序设计语言的历史和简介

(1)简介

程序设计语言是为了书写计算机程序而人为设计的符号语言，用于对计算过程进行描述、组织和推导。

(2)历史和发展

程序设计语言的发展过程

程序设计语言的广泛使用始于1957年出现的FORTRAN，程序设计语言的发展是一个不断演化的过程，其根本推动力是更高的抽象机制以及对程序设计思想的更好支持。

低级语言与高级语言

计算机硬件只能识别由0、1组成的机器指令序列，即机器指令程序，因此机器指令是最基本的计算机语言。

由于机器指令是特定的计算机系统所固有的、面向机器的语言，所以用机器语言进行程序设计时效率很低，程序的可读性很差，也难以修改和维护。

因此，人们就用易记忆的符号代替0、1序列来表示机器指令，例如，用ADD表示加法，用SUB表示减法等。用符号表示的指令称为汇编指令，汇编指令的集合被称为汇编语言。

汇编语言的源程序由若干条语句组成，其中可以有三类语句：指令语句、伪指令语句和宏指令语句。

汇编语言程序设计流程

指令语句又称为机器指令语句，将其汇编后能产生相应的机器代码，这些代码能被CPU直接识别并执行相应的操作。基本的指令有ADD、SUB和AND等，书写指令语句时必须遵守指令的格式要求。

伪指令语句指示汇编程序在汇编源程序时完成某些工作，例如为变量分配存储单元地址，给某个符号赋一个值等。伪指令语句经编译后不产生机器代码。

在汇编语言中，还允许将多次重复使用的程序段定义为宏。宏指令语句就是宏的引用。

汇编语言的书写格式在很大程度上取决于特定计算机的机器指令，因此它仍然是一种面向机器的语言，人们称机器语言和汇编语言为低级语言。

在此基础上，人们开发了功能更强、抽象级别更高的语言以支持程序设计，于是就产生了面向各类应用的程序设计语言，称为高级语言。常见的有Java、C、C++、PHP、Python等。

2.程序设计语言的定义

一般地，程序设计语言的定义都涉及语法、语义和语用等方面。

(1)语法是指由程序设计语言的基本符号组成程序中的各个语法成分（包括程序）的一组规则。其中由基本字符构成的符号（单词）书写规则称为词法规则，由符号构成语法成分的规则称为语法规则。

(2)语义是程序设计语言中按语法规则构成的各个语法成分的含义，分为静态语义和动态语义。静态语义是指编译时可以确定的语法成分的含义，而运行时刻才能确定的含义是动态语义。

一个程序的执行效果说明了该程序的语义，它取决于构成程序的各个组成部分的语义。

(3)语用表示了构成语言的各个记号和使用者的关系，设计符合的来源、使用和影响。

3.程序设计语言的分类

程序设计语言的分类

(1)命令式和结构化程序设计语言

命令式语言是基于动作的语言，在这种语言中，计算被看成是动作的序列。命令式语言族开始于Fortran，Pascal和C语言都可以体现命令式程序设计的关键思想。

在这种语言中，计算机被看作是动作的序列，程序就是用语言提供的操作命令书写的一个操作序列。用命令式程序设计语言编写程序，就是描述解题过程中每一步的过程，程序的运行过程就是问题的求解过程，因此也称为过程式语言。

机器语言及汇编语言是最早的命令式语言。

通常所称的结构化程序设计语言属于命令式语言类，其结构特性主要体现在以下几个方面：

①用自顶向下的逐步精化的方法编程

②按模块组织的方法编程

③程序只包含顺序、判定及循环构造，而且每种构造只允许单入口和单出口。

结构化程序的结构简单清晰、模块化强，描述方式接近人们习惯的推理式思维方式，因此可读性强。C、PASCAL等都是典型的结构化程序设计语言。

(2)面向对象的程序设计语言

程序设计语言的演化从机器语言开始到汇编语言到各种结构化高级语言，最后到支持面向对象技术的面向对象语言，反映的就是一条抽象机制不断提高的演化道路。

C++、Java和Smalltalk是面向对象程序设计语言的代表，它们都支持封装、继承、多态等面向对象技术。

计算机科学导论第十五周学习总结 计算机科学导论第十五周学习总结 计算机科学导论第十五周学习总结

(3)函数式程序设计语言

函数式设计语言是一类以λ演算为基础的语言，其基本概念来自于LISP，这是一个在1958年为了人工智能应用而设计的语言。函数是一种对应规则（映射），使定义域的每个元素和值域中的唯一的元素相对应。

常见的函数式程序设计语言有Haskell、Scala、Scheme、APL等。

(4)逻辑型程序设计语言

逻辑型程序设计语言是一类以形式逻辑为基础的语言，其代表是建立在关系理论和一阶谓词理论基础上的PROLOG。PROLOG有很强的推理功能，适用于编写自动定理证明、专家系统和自然语言理解等问题的程序。

计算机科学导论第十五周学习总结

4.高级编程语言简介

计算机科学导论第十五周学习总结

二、计算机中的数据

1.数据

(1)数据的定义

数据（data）是事实或观察的结果，是对客观事物的逻辑归纳，是用于表示客观事物的未经加工的的原始素材。 数据可以是连续的值，比如声音、图像，称为模拟数据，也可以是离散的，如符号、文字，称为数字数据。在计算机系统中，数据以二进制信息单元0、1的形式表示。

(2)数据与信息的区别

①数据是物理的，而数据是释义的；

    信息是对数据的解释，是数据含义的体现。

②数据反映的是事物的表象，信息反映的是事物的本质。

③数据时信息的重要来源，可以用人工或自动化装置进行通讯，翻译和处理；信息是根据一定的规则对数据承载的事实进行组织后形成的结果。

④数据的形式变化多端，很容易受载体的影响，信息则比较稳定，不随载体的性质而随意改变。   

(3)计算机常用的编码方式

①ASCII码

用一个字节大小表示常用的字符，最开始ASCII码只表示128个字符，只需要7位表示，最高位统一用0表示。

计算机科学导论第十五周学习总结

可打印字符有95个；

第一个可打印字符的ASCII是32，为空格；

最后一个可打印字符的ASCII是126，为~;

控制字符有33个；

第一个大写字母的ASCII 为65；

第一个小写字母的ASCII为97；

第一个数组的ASCII为48.

②GB 2312：信息交换用汉字编码字符集

GB2312编码适用于汉字处理、汉字通信等系统之间的信息交换，通行于中国大陆;新加坡等地也采用此编码。中国大陆几乎所有的中文系统和国际化的软件都支持GB 2312。

基本集共收入汉字6763个和非汉字图形字符682个。整个字符集分成94个区，每区有94个位。每个区位上只有一个字符，因此可用所在的区和位来对汉字进行编码，称为区位码。

③Unicode

统一编码，对于不同国家字符都能解析。（汉字用两个字节表示）

④UTF-8

UTF-8是UCS字符集的另一种编码方式，UTF-16的每个单元是两个字节（16位），而UTF-8的每个单元是一个字节（8位）。UTF-16中用一个或两个双字节表示一个字符，UTF-8中用一个或几个单字节表示一个字符。

可以认为UTF-8编码是根据一定规律从UCS-2转换得到的，从UCS-2到UTF-8之间有以下转换关系：

UCS-2 UTF-8

U+0000 - U+007F 0xxxxxxx

U+0080 - U+07FF 110xxxxx 10xxxxxx

U+0800 - U+FFFF 1110xxxx 10xxxxxx 10xxxxxx

2.数据结构

(1)定义

数据结构包括逻辑结构和存储结构，逻辑结构是对数据之间关系的描述，有时候也把逻辑结构简称为数据结构。

(2)逻辑结构

有四种基本类型：集合结构、线性结构、树状结构和网络结构。

(3)物理结构

①顺序存储：逻辑相邻，物理相邻

链式存储：不要求逻辑相邻的结点物理位置也相邻，结点间的逻辑关系由附加的引用字段表示（指针域）。一个结点的引用字段往往指导下一个结点的存放位置。

②索引存储：采用附加索引表的方式来存储结点信息的一种存储方式

③散列存储：根据结点的关键字直接计算出该结点的存储地址的一种存储的方式（字典），如哈希表。

④哈希表：哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。

(4)常见的数据结构

①线性表

线性表是最常用且最简单的一种数据结构，它是n个数据元素的有限序列。

实现线性表的方式一般有两种，一种是使用数组存储线性表的元素，即用一组连续的存储单元依次存储线性表的数据元素。另一种是使用链表存储线性表的元素，即用一组任意的存储单元存储线性表的数据元素（存储单元可以是连续的，也可以是不连续的）。

②栈（后进先出）

是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

访问、插入和删除元素只能在栈顶进行。

计算机科学导论第十五周学习总结

③队列（先进先出）

一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列是按照“先进先出”或“后进后出”的原则组织数据的。队列中没有元素时，称为空队列。

元素只能从队列尾插入，从队列头访问和删除。

计算机科学导论第十五周学习总结

④树

树型结构是一类非常重要的非线性数据结构，其中以树和二叉树最为常用。

树 是由n（n>=1）个有限节点组成一个具有层次关系的集合。它具有以下特点：每个节点有零个或多个子节点；没有父节点的节点称为 根 节点；每一个非根节点有且只有一个 父节点 **；除了根节点外，每个子节点可以分为多个不相交的子树。

计算机科学导论第十五周学习总结

二叉树

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree），二叉树的子树有左右之分，次序不能颠倒。二叉树常被用于实现二叉查找树和二叉堆。

计算机科学导论第十五周学习总结

树和二叉树的主要差别：

树中结点的最大度数没有限制，而二叉树结点的最大度数为2；

树的结点无左、右之分，而二叉树的结点有左、右之分。

⑤图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

图是一种较线性表和树更为复杂的数据结构，在线性表中，数据元素之间仅有线性关系，在树形结构中，数据元素之间有着明显的层次关系，而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

计算机科学导论第十五周学习总结

3.算法

(1)简介

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

(2)一个算法应该具有以下五个重要的特征：

①输入项 一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件

②输出项 一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的

③有穷性 算法的有穷性是指算法必须能在执行有限个步骤之后终止

④确切性 算法每个步骤都应被精确定义,同样的输入只能有一种输出

⑤可行性 算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）

(3)算法的设计原则：

①正确性：首先，算法应当满足以特定的“规则说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：

a.程序语法错误。

b.程序对于几组输入数据能够得出满足需要的结果。

c.程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果。

d.程序对于一切合法的输入数据都能得到满足要求的结果。

PS：通常以第c层意义的正确性作为衡量一个算法是否合格的标准。

②可读性：算法为了人的阅读与交流，其次才是计算机执行。因此算法应该易于人的理解；另一方面，晦涩难懂的程序易于隐藏较多的错误而难以调试。

③健壮性：当输入的数据非法时，算法应当恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序执行，而是应当返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

④高效率与低存储量需求：通常算法效率值得是算法执行时间；存储量是指算法执行过程中所需要的最大存储空间，两者都与问题的规模有关。

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

(4)算法的时间复杂度与空间复杂度

①时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做T(n)=Ο(f(n))。 因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

②空间复杂度

算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

(5)算法举例

递推法、递归法、穷举法、贪心算法、分治法、动态规划法、迭代法、分支界限法、回溯法。

4.数据库

(1)数据库简介

数据库：就是数据的仓库，它是长期存储在计算机内，有组织的、可共享的数据的集合。

数据库管理系统（DBMS: 用来对数据进行存储、管理等操作的软件)

(2)数据库分类

数据库通常分为层次式数据库、网络式数据库和关系式数据库三种。而不同的数据库是按不同的数据结构来联系和组织的。而在当今的互联网中，最常见的数据库模型主要是两种，即关系型数据库（SQL）和非关系型数据库（NoSQL，Not Only SQL）。

(3)常见数据库简介

关系型数据库与实例

关系型数据库是指采用了关系模型来组织数据的数据库，而关系模型是由二维表及其联系组成的数据组织。

优点：

①易于维护：都是使用表结构，格式一致；

②使用方便：SQL语言通用，可用于复杂查询；

③复杂操作：支持SQL，可用于一个表以及多个表之间非常复杂的查询。

缺点：

①读写性能比较差，尤其是海量数据的高效率读写；

②固定的表结构，灵活度稍欠；

③高并发读写需求，传统关系型数据库来说，硬盘I/O是一个很大的瓶颈。

目前主流的关系型数据库有——

MYSQL

目前使用最广泛的开源、多平台的关系型数据库，支持事务、符合ACID、支持多数SQL规范

SQL Server

支持事务、符合ACID、支持多数SQL规范，属于商业软件，需要注意版权和licence授权费用

Oracle

支持事务，符合关系型数据库原理，符合ACID，支持多数SQL规范，功能最强大、最复杂、市场占比最高的商业数据库

Postgresql

开源、多平台、关系型数据库，功能最强大的开源数据库，需要python环境，基于postgresql的TimeScaleDB，是目前比较火的时序数据库之一。

非关系型数据库与实例

非关系型数据库也称为NOSQL（Not Only SQL），作为关系型数据库的一个补充，能在特定场景和特点问题下发挥高效率和高性能。

常见的非关系型数据库类型有键值（Key-Value）存储数据库和面向文档数据库（Document-oriented）

键值存储数据库类似hash，通过key做添加、删除、查询，性能高，优势在于简单、易部署、高并发，主要产品有

Redis

开源、Linux平台、key-value键值型Nosql数据库，简单稳定，非常主流的、全数据in-momory、定位于“快”的键值型nosql数据库

Memcaced

一个开源的、高性能的、具有分布式内存对象的缓存系统，通过它可以减轻数据库负载，加速动态的web应用

面向文档数据库以文档的形式存储，每个文档是一系列数据项的集合，每个数据项有名称与对应的值，主要产品有

MongoDB

开源、多平台、文档型nosql数据库，“最像关系型数据库”，定位于“灵活”的nosql数据库。适用于网站后台数据库（更新快、实时复制）、小文件系统（json，二进制）、日志分析系统（数据量大的文件）