基础知识

基础知识
思维导图
硬件
原反补码
单片机
复变函数
复数
计算机网络
数据链路层
媒体接入控制分类
CSMA/CD
MAC 层协议
网络层
路由选择协议
路由信息协议 RIP 的基本工作原理
开放最短路径优先 OSPF 的基本工作原理
边界网关协议 BGP
离散
图
算法分析与设计
题目
最大团-最大独立集
01-背包
矩阵连乘
八皇后解法速记
随机化算法
渐近阶高低
数论四大定理
棋盘覆盖问题
二分搜索
斐波那契
最长公共子序列
人工智能
零散的
河工大-UML
借物表

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

思维导图

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

基础知识
数据结构
二叉树的前,中,后序遍历详解
操作系统
我给总结了一下: 🤷‍♂️ 进程,线程,CPU 核心,并行,并发大杂碎!
一句话+一张图说清楚——银行家算法
操作系统：经典进程同步问题之生产者-消费者问题、读者-写者问题、哲学家进餐问题
调度算法的介绍及优缺点
编译原理
编译原理：总结
硬件
【一天掌握 51 单片机基础】单片机原理及应用东北大学（高宏亮主讲）
数据库
MySQL
【狂神说 Java】MySQL 最新教程通俗易懂
狂神说数据库笔记
MongoDB
有 MySQL 基础能很快上手
krislinzhao/StudyNotes
通用
MySQL 单列索引和组合索引的区别介绍
质量相当高的文章
我们为什么要分库分表？
这篇封神了,把我最近在数据库业务设计方面的疑问解决了.
读写分离
课程
数据库考试试题及答案
子查询
Neo4j
让所有程序员都能学懂的 Neo4j 数据库教程，B 站史上最实用的 Neo4j 数据库入门到实战学习教程
图数据库 Neo4j 的部署、数据导入和简单使用
算法-数学
傅里叶变换
👽 通信技术-开坑自埋
P/NP 问题
P 对 NP 问题
算法复杂度与 NP 问题
贪婪算法案例、np 完全问题及 java 代码实现
非常经典和值得探索的问题 (经验接收自@河北工业大学)
Hash-算法
用来校验文本/文件,主流有三类,不同算法产生的 hash code 不同
MD5
CRC-32, CRC-64
SHA-1, SHA-256, SHA-384, SHA-512
校验方法
文件完整性校验
排序算法
图解排序算法(四)之归并排序
论文
如何将 CNKI 论文信息转换成你想要的参考文献格式
关键时候挺好用的功能
word 操作技巧：有关脚注和尾注的使用方法

硬件

原反补码

开局三张图,故事全靠编 🤣
因为带有符号位的二进制数在计算机内计算时,原码和反码的运算结果都不是 100%正确,而且会有+0和-0两个零
补码 100%正确,于是我们采用补码,而且补码只有一个零
- 补码就是为了解决这两个问题的,没了.

单片机

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

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

复变函数

复数

运算
一般表示
几何表示
幂与根

计算机网络

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

数据链路层

媒体接入控制分类

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 次仍不能成功时，则丢弃该帧，并向高层报告
信道利用率
帧发送/接收流程

MAC 层协议

以太网 MAC 层基础知识学习
小林 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 地址字段
网络包至此(数据链路层)的图解

网络层

路由选择协议

动/静态路由选择
因特网采用动态路由选择,分层次自治
路由器基本结构

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

RIP 会选择距离向量短的路由,而不管带宽 (距离相同的话使用负载均衡)
RIP 交换要点
只和相邻路由器交换信息
交换自己的路由表
周期性交换 (比如 30s)
举例: RIP 路由条目更新规则
坏消息传得慢/路由环路/距离无穷计数问题
新更新的路由表被老版本覆盖,有几个措施可以减少出现概率或减小危害:
1. 限制最大路径为 15
2. 路由表发生变化时立即发送更新报文 (触发更新)
3. 记录特定接口的路由信息,而不反向传递 (水平分割)

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

基本工作原理
基于链路状态,使用最短路径优先,保证不会产生路由环路
不限制网络规模,更新效率高,收敛速度快
链路状态是指与哪些路由器相邻以及相应连路的代价 (费用/距离/时延/带宽等等)
链路状态更新 && 最短路径 SPF 计算
每个路由器会产生链路状态通告(LSA),包含: 直连网络/邻居路由器得到链路状态
LSA 封装在链路状态更新分组(LSU)中,采用洪泛法发送
每个路由器通过链路状态数据库(LSDB)来接收 LSU 维护链路状态,各路由器 LSDB 最终一致
OSPF 工作过程 && 五种数据分组
邻居关系建立 && 划分区域

边界网关协议 BGP

路由选择
不同自治系统内度量路由的代价可能是不同的,所以无法通过代价度量来寻找最佳路由
自治系统间路由选择还需要考虑政治,经济,安全等因素
BGP 力求找一条不兜圈子的较好的路由线路,而不是找最佳路由
举例: BGP 路径向量应用
BGP-4 的四种报文
直接封装 xx 报文的协议
RIP -> UDP
OSPF -> IP
BGP -> TCP

离散

图

有向图-邻接矩阵存储

算法分析与设计

题目

最大团-最大独立集

最大团: 顶点间都相连的最多顶点数 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 的时候不一定能确定没有主元素。
【是否正确】 $\frac{1}{2}<p<1$ ,如果得到正确解的概率不小于 p，则称该蒙特卡洛算法是 p 正确的， $p-\frac{1}{2}$ 是该算法的优势
【一致】如果对于同一个实例，算法不会给出两个正确的解答，那么称这个蒙特卡洛算法是一致的
【提高正确率】执行若干次，选择频次最高的
^[2]

渐近阶高低

$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]

数论四大定理

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

棋盘覆盖问题

根据黑的先画最中间绿色的
根据绿色的画黄色的
根据黄色画蓝色的
可以确定答案了
^[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] < 2^{11}$ -> k1=11 k2=11-1

$2^{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