20202423陈驭骐《网络空间安全专业导论》第三周学习总结

第六章 低级程序设计语言与伪代码

1. 机器语言与汇编语言的关系及其区别

机器语言（machine language）：由计算机直接使用的二进制编码指令构成的语言。
汇编语言（assembly language）：一种低级语言，用助记码表示特定计算机的机器语言指令。
汇编器（assembly）：把汇编语言程序翻译成机器代码的程序。

机器语言是人们在还没有发明其他程序设计语言时用来编写指令的最原始的语言，直接对应计算机的二进制编码，每条指令都是最基础的，只能执行最低级的任务，所有微小的操作都需要被明确编码。为了提高效率，人们开发出了汇编语言，为每条机器语言指令分配了一个助记指令码来代替二进制和十六进制数字，使之更形象，并减少了错误发生率。其以汇编器为中介，联系起了汇编语言程序和机器码程序。
因为每种类型的计算机都有自己的机器语言，所以有多少种计算机，就有多少种汇编语言和翻译程序。

2. 虚拟机Pep/9的重要特性

虚拟机（virtual computer（machine））：为了模拟真实机器的重要特征而设计的假象机器。

虚拟机Pep/9的内存单元由65536字节的储存空间构成。Pep/9的字长是2字节或16位。其可以表示的十六进制数的返回约为-7FFF到+7FFF.其拥有七个寄存器，其中包括：

程序记数器（PC），其中包含下一条即将被执行的指令的地址。
指令寄存器（IR），其中包含正在被执行的指令的下一个副本。
累加器（A），用来储存数据和运算的结果。

3. 立即寻址模式和直接寻址模式的区别

前者的操作数说明符包含将要处理的数据，而后者的操作数说明符包含将要处理的数据的地址。

4. 创建和运行汇编语言程序的步骤

选择汇编器，使用助记码编写程序，适当添加注释和标签增加可读性，选择“运行源代码”。

5. 区分给汇编器的指令和要翻译的指令

给汇编器的指令称为汇编器指令（assembler directive），这是指导汇编器完成功能所使用的指令，而要翻译的指令则是汇编器在指导下发挥功能翻译的指令。

6. 区分执行一个算法和开发一种算法

算法（algorithm）：解决方案的计划或概要，或解决问题的逻辑步骤程序。

执行一个算法是按照算法的逻辑顺序进行，而开发一种算法是开发一种解决问题逻辑顺序。

7. 描述表达算法时使用的伪代码结构。

伪代码（pseudocode）：一种表达算法的语言。

输入——判断——操作——输出（个人向理解） 

8. 两种测试方式

代码覆盖（明箱）测试法（code-coverage（clear-box）testing）：通过执行代码中的所有语句测试程序或子程序的测试方法。
数据覆盖（暗箱）测试法（data-coverage（black-box）testing）：把代码作为一个暗箱，基于所有可能的输入数据测试程序或子程序的测试方法。

第七章 问题求解与算法设计

1．结合Polya提出的如何解决问题的列表，描述计算机问题求解的过程

计算机问题求解过程包括四个阶段，即分析和说明阶段、算法开发阶段、实现阶段和维护阶段，详见附图。

2．简单类型与复合类型

简单类型：包括语言的基本类型和抽象数据类型。
复合类型：由简单类型构成。

3．递归

递归（recursion）：算法调用它本身的能力。

每个递归算法至少由两种情况：基本情况和一般情况。基本情况是答案已知的情况；一般情况则是调用自身来解决问题的更小版本的解决方案。因为一般情况下解决的是原始问题越来越小的版本，所以程序最终达到基本情况，即答案是已知的，所以递归停止。

4.无序数组和有序数组

前者是杂乱无序排列的数组，后者是以一定的顺序排列的数组。

5．选择排序和插入排序

选择排序：依次查找符合顺序的个体，每找到一个便将之以所需顺序排列，之后再重新经行查找，反复操作直至排序成功。需要两个完整列表的空间。
插入排序：每次迭代后，一个元素将被放在相对于其他元素来说适当的位置上。

6．快速排序算法

其为对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序数列。

7．二分检索

二分检索是快速排列的基础。

二分检索（binary search）：算法假设要检索的数组是有序的，其中每次比较操作可以找到要找的项目或把数组减少一半。二分检索不是从数组开头开始顺序前移，而是从数组中间开始。如果要搜索的项目小于数组的中间项，那么可以知道这个项目一定不会出现再数组的后半部分，因此只需要搜索数组的前半部分即可。

小结

从计算机的发展史可以窥见人类看待、解决问题的发展史。从某些方面来说，计算机是局限的，但是应用于其和其体现的解决问题的方法，却是广泛适用且能启迪众人的。