基础知识

• 基础知识
  • 思维导图
  • 硬件
    • 原反补码
    • 单片机
  • 复变函数
    • 复数
  • 计算机网络
    • 数据链路层
      • 媒体接入控制分类
      • 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 层协议

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 地址字段

  

  ---

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

  

网络层

路由选择协议

• 动/静态路由选择

  

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

  

• 路由器基本结构

  

路由信息协议 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]

数论四大定理

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

棋盘覆盖问题

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

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

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

借物表

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

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

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

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