基础知识

已录入 😍Weidows-の成长路线#基础知识

分割线

思维导图

一些零散的不足以道,做成导图了

分割线

硬件

原反补码

  • 开局三张图,故事全靠编 🤣

    20210325114342 20210325114403 20210325114419
  • 因为带有符号位的二进制数在计算机内计算时,原码和反码的运算结果都不是 100%正确,而且会有+0-0两个零

  • 补码 100%正确,于是我们采用补码,而且补码只有一个零

    • 补码就是为了解决这两个问题的,没了.

单片机

  • 标志寄存器内部的八位是分开使用的,作用不同,但功能都是作为标志位

    20210331121042 20210331122847 20210331122957

单片机时钟周期、机器周期、指令周期与总线周期

分割线

复变函数

复数

  • 运算
    20210402161142

  • 一般表示
    20210325170144

  • 几何表示
    20210325170538

  • 幂与根
    20210325181554

分割线

计算机网络

摘自 湖科大教书匠-计算机网络

数据链路层

媒体接入控制分类

20210930170530

CSMA/CD

2016.6.20 计算机网络复习要点第三章之 CSMA/CD 协议(示例代码)

采用随机接入,当多个主机同时发送帧时会发生碰撞/冲突.无连接不可靠,尽力交付的服务.

  • CSMA/CD (载波监听多点接入/碰撞检测) 是以太网采用的解决冲突的方法

    • 多路接入 MA: 多个站点接入同一条总线上,竞争使用总线
    • 载波监听 CS: 站点发送数据前,先检查总线上是不是已经有数据在传输,如果有就暂缓发送,避免冲突。
    • 冲突检测: 边发送边对介质上电压信号进行检测,当电压摆动值超过一定门限时就认为发生了冲突。一旦发生冲突就停止发送数据,然后根据协议进行重传。

  • 在使用 CSMA/CD 协议时,一个站不可能同时进行发送和接收(但必须边发送边监听)。因此,使用 CSMA/CD 协议的以太网不可能进行全双工通信而只能进行半双工通信(双向交替通信);

    • 每一个站在自己发送数据之后的一小段时间内,存在着遭遇碰撞的可能性,这一小段时间是不确定的,它取决于另一个发送数据的站到本站的距离;

    • 最先发送数据帧的 A 站,在发送数据帧后至多经过时间 2r 就可知道所发送的数据帧是否遭受到碰撞;因此,以太网端到端往返时间 2r 称为争用期(碰撞窗口);

    • 经过争用期还没有检测到碰撞,才能肯定后续发送的数据一定不会发送碰撞;

    • 凡是长度小于 64 字节的帧都是由于冲突而异常中止的无效帧,只要收到了这种无效帧,就应当立即将其丢弃;


  • 采用截断二进制指数退避算法来确定碰撞后重传的时机

    • 让发生碰撞的站停止发送数据后,不是等待信道变为空闲后就立即发送数据,而是推迟(退避)一个随机的时间

    • 单位回退时间通常取冲突窗口(争用期)的值 2r,即传输最小帧长 512bit 数据用时,叫作时槽。

    • 取 r, 0 ≤ r < 2^k-1,重传的时延(退避时间)就是 r 倍的单位回退时间。

    • K 为碰撞次数时。K=Min[重传次数,10],当重传次数超过 10 时,K 就不在增大而是一直等于 10;当重传达 16 次仍不能成功时,则丢弃该帧,并向高层报告

    20210930181153
  • 信道利用率

    20210930191350
  • 帧发送/接收流程

    20210930191552 20210930191636

MAC 层协议

  1. 以太网 MAC 层基础知识学习
  2. 小林 Coding - 图解网络
  • MAC (media access control) / (message authentication code)

    • MAC 地址相同的设备只要不是同属一个数据链路就不会出现问题。同一网段下两设备都不能正常联网.

    I3E 注册管理结构 RA(Registration Authority)是局域网全球地址的法定管理机构[W-IEEERA],负责分配前三个字节;前三个字节又称组织唯一标识符 OUI(Organizationally Unique Identifier),又称公司标识符(Company ID)[RFC 7042]。后三个字节由厂家自行指派称为扩展标识符(Extended Identifier)。总的一起叫做 EUI-48 扩展的唯一标识符(Extended Unique Identifier)。


  • 以太网 V2 的 MAC 帧格式(MAC 格式标准有两个,一个是 DIX Ethernet V2 标准,一个是 IEEE 的 802.3 标准)

    • IEEE 802 标准中规定了一种 48 位的全球地址,此地址固化在适配器的 ROM 中(所以称为物理地址)。无线 LAN、蓝牙、以太网、FDDI、ATM 等设备都使用相同规格的 MAC 地址。
  • MAC 地址字段

    20210930194939 20210930202539
  • 网络包至此(数据链路层)的图解

    20210930204450

网络层

路由选择协议

  • 动/静态路由选择

    20211022084950
  • 因特网采用动态路由选择,分层次自治

    20211022085337 20211022085557
  • 路由器基本结构

    20211022090722

路由信息协议 RIP 的基本工作原理

20211022100415
  • RIP 会选择距离向量短的路由,而不管带宽 (距离相同的话使用负载均衡)

    20211022100624 20211022100656
  • RIP 交换要点

    只和相邻路由器交换信息

    交换自己的路由表

    周期性交换 (比如 30s)

  • 举例: RIP 路由条目更新规则

    20211022115640
  • 坏消息传得慢/路由环路/距离无穷计数问题

    新更新的路由表被老版本覆盖,有几个措施可以减少出现概率或减小危害:

    1. 限制最大路径为 15

    2. 路由表发生变化时立即发送更新报文 (触发更新)

    3. 记录特定接口的路由信息,而不反向传递 (水平分割)


开放最短路径优先 OSPF 的基本工作原理

  • 基本工作原理

    基于链路状态,使用最短路径优先,保证不会产生路由环路

    不限制网络规模,更新效率高,收敛速度快

    链路状态是指与哪些路由器相邻以及相应连路的代价 (费用/距离/时延/带宽等等)

    20211022165456
  • 链路状态更新 && 最短路径 SPF 计算

    每个路由器会产生链路状态通告(LSA),包含: 直连网络/邻居路由器得到链路状态

    LSA 封装在链路状态更新分组(LSU)中,采用洪泛法发送

    每个路由器通过链路状态数据库(LSDB)来接收 LSU 维护链路状态,各路由器 LSDB 最终一致

    20211022170324
  • OSPF 工作过程 && 五种数据分组

    20211022170725
  • 邻居关系建立 && 划分区域

    20211022174329 20211022174754

边界网关协议 BGP

  • 路由选择

    不同自治系统内度量路由的代价可能是不同的,所以无法通过代价度量来寻找最佳路由

    自治系统间路由选择还需要考虑政治,经济,安全等因素

    BGP 力求找一条不兜圈子的较好的路由线路,而不是找最佳路由

    20211022232434
  • 举例: BGP 路径向量应用

    20211022232856
  • BGP-4 的四种报文

    20211022233905
  • 直接封装 xx 报文的协议

    RIP -> UDP

    OSPF -> IP

    BGP -> TCP

分割线

离散

  • 有向图-邻接矩阵存储

    20211028200201

分割线

算法分析与设计

题目

最大团-最大独立集

最大团: 顶点间都相连的最多顶点数 24567 或 45679

最大独立集: 顶点间都不直接相连的最多顶点数 158 或 168


01-背包

5 个物品,1 个背包,背包容量为 10.

价值:8,10,4,5,5

重量:6,4,2,2,3

求将该 5 个物品装入背包的最大价值20,以及 x[6]的向量值(0,0,1,0,1,1)(后 5 个空选择哪个对应的向量值为 1)


矩阵连乘

  • A1 A2 A3 A4 A5 五个矩阵连乘,通过下图判断怎么加括号使运算最少

  • 不看 0 那一斜线和 0 上面的一位,如下

    第三列: 在 A2 断开

    第四列: 在 A2 断开

    第五列: 在 A2 和 A4 断开

  • A1 A2 | A3 A4 | A5

    每组括起来就是结果: (A1 A2)(A3 A4)A5


八皇后解法速记

17582463
24683175
31758246
42736851

通过镜像操作可以得到对面四种解法: 1->8, 2->7, 3->6, 4->5


随机化算法

  • 舍伍德算法

    去掉问题最坏解,使得求解的时候的复杂度趋向于平均

  • 拉斯维加斯算法:

    问题求解时随机决策

    随机找,找到了一定是正确的,但是不一定能在有限的时间内找到正确的解

  • 蒙特卡洛算法

    以高概率给出一个正确的解,但是不能判定是不是正确的

    【主元素】随机找出一个元素,看看它有没有出现了很多次,如果是,就返回 true,否则返回 false。
    返回 true 一定能确定有主元素,但是返回 false 的时候不一定能确定没有主元素。

    【是否正确】12<p<1\frac{1}{2}<p<1,如果得到正确解的概率不小于 p,则称该蒙特卡洛算法是 p 正确的,p12p-\frac{1}{2} 是该算法的优势
    【一致】如果对于同一个实例,算法不会给出两个正确的解答,那么称这个蒙特卡洛算法是一致的
    【提高正确率】执行若干次,选择频次最高的
    [2]


渐近阶高低

O(1)<O(logn))<O(n)<O(nlogn)<O(n2)<O(n3)<O(nk)<O(2n)<O(n!)<O(nn)O(1) < O(\log{n})) < O(n) < O(n\log{n}) < O(n^2) < O(n^3) < O(n^k) < O(2^n) < O(n!) < O(n^n) [1]


数论四大定理

威尔逊定理, 欧拉定理, 中国剩余定理, 费马小定理


棋盘覆盖问题

  1. 根据黑的先画最中间绿色的
  2. 根据绿色的画黄色的
  3. 根据黄色画蓝色的
  4. 可以确定答案了
    [3]

二分搜索

1)给定从小到达已排好序的2021个整数,存放在数组a[2021]中,执行以下BinarySearch()函数,需要查找的特定元素x
1:当x > a[2020]时,查找不到元素x时,比较了______ 次。
2:当x < a[0]时,查找不到元素x时,比较了______ 次。

2)给定从小到达已排好序的2048个整数,存放在数组a[2048]中,执行以下BinarySearch()函数,需要查找的特定元素x
3:当x > a[2047]时,查找不到元素x时,比较了______ 次。
4:当x < a[0]时,查找不到元素x时,比较了______ 次。

11 10 12 11

[0,2020]<211[0,2020] < 2^{11} -> k1=11 k2=11-1

211<=[0,4047]<2122^{11} <= [0,4047] < 2^{12} -> k3=12 k4=12-1


斐波那契

F()执行 15 次, f(1) 3 次


最长公共子序列

  • 填写 C 表和 B 表 (不知道还有什么学校教这种老套,反正是考点没的办法了…)

  • 思路

    C/B 表同时写不要分开先后写,只不过 B 表要根据 C 表写

    // c[行][列]  b[行][列]
    for (i = 1; i < m; i++) {
    for (j = 1; j < n; j++) {
    // 首先判断行列字符是否一样,相同的话
    if (x[i] == y[j]) {
    c[i][j] = c[i - 1][j - 1] + 1; // c[i][j]=C表左上角+1
    b[i][j] = 1;

    // 如果行列字符不一样,判断C表上面一格是否>=左边,如果true
    } else if (c[i - 1][j] >= c[i][j - 1]) {
    c[i][j] = c[i - 1][j]; // c[i][j]=C表上面一格
    b[i][j] = 2;

    // 如果行列字符不一样,判断C表上面一格是否>=左边,如果false
    } else {
    c[i][j] = c[i][j - 1]; // c[i][j]=C表左边一格
    b[i][j] = 3;
    }
    }
    }

分割线

人工智能

🐊 人工智能笔记

分割线

零散的

河工大-UML

这是河北工业大学-刘洪普老师的 UML 课程截图记录

讲的领域很广, 互联网领域架构, 计算机底层交互/操作系统设计, AI 领域, 并行计算…etc, i了i了

并发程序: 指的是具有并行处理能力的程序(多线程/协程), 当遇到单核 U 或者环境不适合时会变为顺序执行的程序

同一机子内多个进程可以通过操作系统来完成进程间通信, Socket 实现的是不同机子之间通过网络来进行进程间的通信

关于分布式并行计算, 这里引 Linus 说的:
放弃吧。“并行就是未来”的说法就是一片浮云。 [4]

  • 显卡: 3d 计算加速卡,图形处理需要做大量线性代数向量运算(3 维模型的坐标转换和投影), 取决于向量运算的数学性质, 其可以通过并行运算来加速处理,区别如下:

    CPU 的这种逻辑运算可以通过分支预测来加速,但是必须顺序执行 (这也就限制了一些程序吃不到多核性能, 两核 3G 打不过一核 5G 的)

    GPU 的运算独立, 简单看来核心越多算的越快,这种计算方式叫向量化计算

    # CPU
    C = A + B
    B = A + C
    A = B + C

    # GPU
    A1 = B1 + C1
    A2 = B2 + C2
    A3 = B3 + C3

CPU 核心少而且更适合做逻辑运算, 把向量运算能力加进 CPU (也就是如今的 TPU) 并不是很合适, 所以独立出来了显卡 (一般核心数量上千,高出 CPU 两个量级)

深度学习就是要做大量的线性计算和非线性计算(最终也是通过数学转化为线性计算), 所以炼丹也是吃显卡

分割线

借物表

[1]: https://www.nowcoder.com/questionTerminal/7401d66e14e84279ba278ce04e735deb?page=1&onlyReference=false

[2]: 随机化算法-舍伍德算法&拉斯维加斯算法&蒙特卡洛算法

[3]: 棋盘覆盖问题-分治法

[4]: Linux 之父 Linus 说:并行计算基本上就是浪费大家的时间