我的笔记

计算机学习笔记-归档

计算机科学导论-笔记

计算机科学导论

课程介绍

视频链接：https://www.bilibili.com/video/BV13V41117xc/?vd_source=2d5bdee7ea59486ed4aa4a9b10020224

计算机科学导论

播放量 96.2万

2020-11-04 20:33:38

课程比较基础（大一课程）

​

计算机基础很重要

书籍介绍：计算机科学导论（第三版）-国外经典书籍

本书理论比较多，不涉及具体的代码。本书比较系统，一共18章。

一步一个脚印，基础扎实，都能看懂。

未来有机会自己买书看。

第一章 绪论

图灵模型

图灵机：​一个可以执行计算的概念机。输入数据——处理数据——输出数据。没有确定什么类型的数据。

程序：计算机对数据处理的指令集合。

输入数据不同，或程序不同，那么输出结果不同。

冯诺依曼模型

冯诺依曼计算机：程序和数据都存储在计算机的寄存器上，分成四个系统

  • 输入设备+输出设备

  • 存储器：主存

  • 算术逻辑单元（ALU）

  • 控制器：对其他三部分进行控制操作

程序存放在存储器中，程序和数据使用相同的格式存储（电位模式）

程序是数量有限的指令组成，控制单元一条一条执行指令（取指令，解释指令，执行指令）

计算机基本组成（软件，硬件，数据）

计算机组成：

  • 硬件

  • 数据

  • 软件

    • 算法

    • 程序语言

    • 软件工程（高效的程序开发和维护）

    • 操作系统+应用软件

计算机的历史和社会问题

了解物理层面计算器——电子计算机

社会问题：依赖性，信息差异化

道德问题：隐私，版权，安全

第二章 数字系统-各种进制及转换

数学系统

这部分是基础数学，难度不大，部分略过

数字系统：用特定符号表示数字（例如阿拉伯符号，罗马符号，汉字符号）都是独立的数字系统。分成位置化系统和非位置化系统。

位置化系统：阿拉伯数字，每一位直接表示一个数字（重点学习）

非位置化系统：罗马数字，每一位和前后加减得到一个数字（非重点）

进制

十进制：十进制不能直接存储在计算机中，正负号需要单独存放（来源于十个手指）

二进制：用于计算机底层数字存储，二进制计算和转换

十六进制：为什么需要？二进制便于存储，但是不便于人类阅读，二进制符号太长。十进制便于阅读，但是不能直接存储，和二进制转换比较麻烦。所以计算机很多使用十六进制和八进制（便于人类阅读，也便于转换成底层存储）。

八进制和十六进制类似。

考点：使用不同进制表示 0-15 的数字

进制转换

十进制转换成其他进制：使用整数除以进制数，每次的余数就是转换后的数字。

十进制转其它进制

小数部分计算不一样，例如把 12.625 转换成2进制

1、先分成整数部分和小数部分，12 和 0.625

2、整数部分 （110）2

3、计算小数部分，每次小数部分都乘以进制，然后整数部分就是结果，每次计算后把整数部分归零

0.625 * 2 = 1.25 ——1

(1.25 - 1) * 2 = 0.5 ——0

0.5 * 2 = 1 ——1

结果就是 （0.101）2

注意，十进制整数可以完全转换成二进制整数，但是十进制有限小数，可能转换成二进制循环小数（例如十进制0.1转换）

讲师这部分案例比较多，都是手算，实际上没有意义（理解原理即可，有高效的程序进行转换，不需要手写转换很多进制）

二进制&十六进制互转

二进制和十六进制转换，比较简单（比十进制简单）

0000 对应一个十六进制，那么直接把二进制每4个分成一组，然后进行转换即可

例如 （0001 0101 1111 0001）2

转换成 (15E1)16 即可

同理，十六进制转换成二进制，就是反向转换即可。每一个位置转换成4个位置即可。

二进制&八进制互转

二进制和八进制转换，类似16进制

000 对应一个八进制，那么直接把二进制每3个分成一组，然后进行转换即可。

八进制和十六进制转换，可以先转换成二进制，然后不同分组再进行转换即可。

​

83.算法

算法：通俗的，逐步解决复杂问题的方法

84.算法-三种结构

程序的三种结构：顺序、循环、判断（条件判断）

85.算法的表示

UML 图描述算法

伪代码描述算法

86.基本算法

算法：是一组明确步骤的有序组合，在有限的时间内，产生结果并终止

​

87.基本算法-选择排序

选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

简单算法实现，跳过

88.基本算法-冒泡排序

简单算法实现，跳过

89.基本算法-插入排序

简单算法实现，跳过

90.基本算法-其他排序

简单算法实现，跳过

91.基本算法-顺序查找

简单算法实现，跳过

92.基本算法-折半查找

简单算法实现，跳过

93.基本算法-子算法

子算法，就是算法的模块化和拆分，便于阅读功能，实现代码复用

94.基本算法-迭代和递归

递归：函数自己调用自己（函数内部调用这个函数）

斐波那契数列递归实现

1
2
3
4
5

function fibonacci(n) {
    if (n <= 0) return 0; // 基础情况
    if (n === 1) return 1; // 基础情况
    return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用
}

迭代：出现循环计算，但是不涉及函数调用自己的情况

斐波那契数列迭代实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function fibonacci(n) {
    if (n <= 0) return 0;
    if (n === 1) return 1;

    let a = 0, b = 1, temp;
    for (let i = 2; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

​

95.基本算法-迭代和递归示例

同上