Computer
笔记列表 66
操作系统是什么 一句话：操作系统是一个运行在硬件之上、为应用程序提供抽象和保护的软件层。 更具体地说，它做四件事： 抽象（Abstraction）：把丑陋的硬件接口包装成好用的 API（write(fd, buf, n) 而不是"…
自动关联目录：2 并发 概念 并发： 同一时间段，多个任务请求执行，任一时刻只能处理其中一个任务。 发生在 同一实体，单处理器 目的是 提高系统响应速度 并行： 同一时间段，多个任务同时执行，任一时刻同时处理多个任务。 发生在 不同实体，多…
虚拟化的目标是让每个进程以为自己独占资源。分两条线： CPU 虚拟化 → 进程（见总览章节） 内存虚拟化 → 虚拟地址空间（本章主体） 地址空间 什么是地址空间 **地址空间（Address Space）**是进程看到的内存视图： 0x…
内核在做什么 内核是唯一运行在内核态的代码。它的职责： 管理资源：进程、内存、设备、文件系统 提供抽象：把硬件包装成系统调用接口 维持秩序：调度、隔离、保护、错误处理 内核与应用程序的根本区别：内核可以直接碰硬件、可以执行特权指令、可以…
持久化解决的是：数据在程序结束、机器断电之后仍然存在。 与虚拟化和并发不同，持久化面对的核心难题是崩溃（crash）——写数据的过程中断电，磁盘上会留下一个"半写"的状态。 I/O 设备：标准模型 ┌──────────…
自动关联目录：Operating System 操作系统回答的问题是：如何在有限、杂乱、不可信的硬件之上，给应用程序提供一个简洁、安全、可复用的抽象。 它做的全部事情可以归纳为三个词：虚拟化（Virtualization）、并发（Concu…
四种遍历 A / \ B C / \ \ D E F 遍历 顺序 结果 先序（Preorder） 根 → 左 → 右 A B D E C F 中序（Inorder） …
自动关联目录：Tree 树是图的一个特例：连通且无环，nnn 个点恰好 n−1n-1n−1 条边。 但它值得单独成章，因为： 递归结构天然适配分治和 DP 大量问题（文件系统、语法树、组织架构、决策树）本身就是树 图上的很多问题在树上简单…
自动关联目录：Data Structures & Algorithm 这里记录的是解题方法，不是"把 STL 用熟"。核心是三类能力： 看出问题的结构（能归约到哪个模型） 选对工具（哪种数据结构/算法能支撑所需…
自动关联目录：LeetCode C++ 标准库速查 这不是 C++ 标准库百科，而是一份刷 LeetCode 时够用、能直接查代码的标准库清单。范围包括容器、算法、数值工具、字符串处理、函数对象和常用辅助类型。目标只有三个： 看到题目特征…
自动关联目录：Basic Algorithm 这一组是不依赖特定数据结构的通用算法思想。它们不是"某一类题的解法"，而是思考问题的方式——后面所有高级算法都是它们的组合。 一张表 思想 一句话 适用信号 枚…
二分在做什么 二分的本质不是"在有序数组里找数"，而是： 在一个单调的判定函数上，用 O(logn)O(\log n)O(logn) 次询问定位分界点。 把问题看成：有一个序列 [false, false, ...…
枚举在做什么 **枚举（Enumeration / Brute Force）**是最诚实的算法：把所有候选答案试一遍，取最优或计数。 复杂度通常是指数级，所以枚举不是"随便写个 for"，而是：如何高效、不重不漏地遍历答…
递归 递归是用函数自己定义自己。一个正确的递归需要两样东西： 1. 基础情形（Base Case）：最小规模直接给出答案，不再递归 2. 递归情形（Recursive Case）：把问题化归为更小的同类问题 缺了 base case → 无…
排序是所有算法的前置步骤 排序本身很少是目的，更多是手段——排完序之后： 二分查找成为可能 双指针成为可能 贪心策略有了明确的顺序 相同元素聚在一起（去重、计数） **"先排序再说"**是解题时最常用的一步。 比较排…
一对对偶操作 前缀和（Prefix Sum）和差分（Difference）是互逆的： 差分→前缀和原数组,原数组→差分差分数组\text{差分} \xrightarrow{\text{前缀和}} \text{原数组}, \qquad \te…
自动关联目录：Dynamic Programming 动态规划（DP）的本质：把穷举中的重复计算缓存下来。 穷举: 枚举所有方案，每个方案 O(n) 计算 → O(2^n · n) DP: 发现不同方案共享"子方案&quo…
动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。 原理 最优子结构 具有最优子结构也可能是适合用贪心的方法求解。 注意要确保我们考察了最…
自动关联目录：Graph 图是表达"关系"的通用模型。很多看起来不像图的题，建出图来就迎刃而解。 术语 术语 含义 顶点 / 边 vertex / edge 有向图 / 无向图 边有没有方向 度 /…
两种遍历 DFS（深度优先） BFS（广度优先） 数据结构 栈（递归 / 显式栈） 队列 顺序 一条路走到底再回溯 一层一层扩散 找什么 路径、连通性、拓扑序 最短（少）步数 空间 O(深度)O(\text{深度…
自动关联目录：Hash 哈希（Hash）回答的是：如何用 O(1)O(1)O(1) 的代价，判断"我见过这个东西吗"。 它的代价是放弃有序性——哈希表里取不出"最小的元素"，也做不了范围查询。 需要范…
自动关联目录：Linear 线性结构是元素排成一列的结构。区别在于允许在哪些位置插入/删除。 总览 结构 插入/删除位置 访问 典型用途 数组 任意（但要搬移） O(1)O(1)O(1) 随机 默认选择 链表 已知位置 O…
自动关联目录：Misc 不属于单一主题，但到处都在用的东西。 复杂度分析 三种记号 记号 含义 类比 OOO（大 O） 上界，不超过 ≤\le≤ Ω\OmegaΩ（大 Ω） 下界，至少 ≥\ge≥ Θ\ThetaΘ（大…
倍增在做什么 **倍增（Binary Lifting）**的核心思想： 预处理出"跳 2k2^k2k 步"的信息，之后任意 nnn 步都拆成二进制，用 O(logn)O(\log n)O(logn) 次跳跃拼出来。 …
自动关联目录：String 字符串问题的三个层次： 单串：在一个串里找结构（回文、周期、子串） 双串：两个串的关系（匹配、最长公共子串/子序列） 多串：一堆串的查询（Trie、AC 自动机、后缀数组） 字符串匹配 在文本 TTT（长 …
贪心在做什么 贪心（Greedy）：每一步都做当前看起来最优的选择，不回头。 贪心: 局部最优 → 局部最优 → ... → 全局最优（？） DP: 枚举所有选择，取全局最优 核心难点：贪心不一定对。它的正确性必须证明，不能靠&…
自动关联目录：Computer 计算机科学的系统主线：从硬件执行模型出发，经由操作系统和网络形成运行环境，再向上连接算法、编译器与图形学。 学习顺序 顺序 分支 回答什么问题 1 Computer Architecture 指…
网络的基本构件 任何网络都由三部分组成： 端系统（End System / Host）：运行应用程序的机器。PC、手机、服务器、物联网设备 通信链路（Link）：光纤、铜线、无线电、卫星。衡量指标是带宽（bit/s） 交换设备（Switc…
应用层在做什么 应用层是唯一"用户看得见"的层。它的全部工作就是：定义通信双方交换的消息格式和交互顺序。 与下层不同，应用层协议没有通用框架——每个协议自己定义自己的语义。但有几样东西是共通的： 进程如何标识（IP +…
传输层的定位 网络层提供主机到主机的交付，传输层把它提升到进程到进程。 网络层: 把数据送到 93.184.216.34 这台机器 传输层: 把数据送到这台机器上的 443 端口（某个 socket） 这个提升靠的是端口号 + 传输层头…
网络层的职责 网络层做两件事： 转发（Forwarding）：分组到达路由器时，查表决定从哪个口出去。是单台设备的本地动作 路由（Routing）：全网所有路由器协同计算转发表。是全局的、分布式的规划过程 转发 = 按地图走；路由 =…
链路层的职责 网络层负责"主机到主机"，链路层负责"一跳之内，相邻两点之间"。 具体提供： 成帧（Framing）：把网络层数据报封装成帧，加上头尾 介质访问控制（MAC）：多人共享一条链路时，谁先…
自动关联目录：Computer Network 计算机网络回答的核心问题是：两个进程如何在一堆不可靠、有延迟、会丢包、会乱序的物理链路上，可靠地交换数据。 这个问题被拆成了分层结构。分层的价值不在于"整洁"，而在于每层只…
刚体的自由度 刚体（Rigid Body）：形状不变，只有位置和朝向会变。 维度 2D 3D 平移 2 3 旋转 1（角度 θ\thetaθ） 3（四元数 / 旋转矩阵） 合计 3 6 关键区别（对比柔体）：柔体…
柔体 vs 刚体 vs 质点弹簧 模型 自由度 适用 物理正确性 刚体 6 不变形物体 ✓ 质点-弹簧 3n3n3n 布料、粗略软体 ✗ 有限元（FEM） 3n3n3n 真实弹性体 ✓ 柔体的核心：用连续介质力学…
两种视角 视角 含义 方法 典型 拉格朗日（Lagrangian） 跟踪流体质点 SPH、PBF 溅水、泡沫 欧拉（Eulerian） 固定网格，看每个格子有什么 网格法、Stable Fluids 烟、雾、火 拉格…
两个阶段 碰撞检测的经典结构： 宽相（Broad Phase）: 快速找出"可能碰撞"的物体对 用包围盒，O(n log n) 或 O(n) …
模型 **质点-弹簧系统（Mass-Spring System）**是最简单的弹性模型： 质点：有质量的点，位置 xi\mathbf{x}_ixi、速度 vi\mathbf{v}_ivi 弹簧：连接两个质点，产生弹力 用途：布料、头…
存储层次 为什么需要层次 CPU 寄存器: ~0.3 ns 几百字节 L1 Cache: ~1 ns 32~64 KB L2 Cache: ~4 ns 256 KB ~ 1 MB L3 Cache: …
指令级并行（ILP） 超标量 一个周期发射多条指令（现代 CPU 4~6 发射）。 乱序执行（Out-of-Order） 指令的实际执行顺序可以不同于程序顺序，只要数据依赖允许。 1. 发射（In-order）: 指令进入 reorde…
多核与缓存一致性 MESI 协议 每个 cache line 有 4 个状态： 状态 含义 M（Modified） 已修改，与内存不一致，本核独占 E（Exclusive） 未修改，与内存一致，本核独占 S（Share…
数字表示 整数 补码（Two's complement）： -1 的 8 位表示: 1111 1111 取反加一: ~1 + 1 = 1111 1110 + 1 = 1111 1111 ✓ 为什么用补码：加…
性能分析 perf stat ./program # 总览：cycles, instructions, cache-misses, branch-misses perf record ./program # 采样 p…
自动关联目录：Computer Architecture 计算机体系结构研究软件如何落到硬件上执行，以及硬件结构为什么会直接影响程序的正确性和性能。原来的单篇长文已按依赖关系拆为六个主题；旧链接仍指向本页。 学习路径 顺序 主题 核心…
自动关联目录：Computer Graphics 图形学回答两个问题： 几何：如何表示和操作形状 渲染：如何把三维场景变成二维图像 再加一个越来越重要的分支： 仿真：如何让物体动起来且符合物理 渲染的两条路线 光栅化（Ras…
作业代码仓库：https://github.com/HUSTJJD/Games-Homeworks 课程笔记：Games102 本页由 tools/sync_games_homeworks.py 自动生成，手写内容请写在标记块之外，不会…
作业代码仓库：https://github.com/HUSTJJD/Games-Homeworks 课程笔记：Games101 本页由 tools/sync_games_homeworks.py 自动生成，手写内容请写在标记块之外，不会…
GAMES101：现代计算机图形学入门（闫令琪）的笔记。 覆盖四大块：光栅化、几何、光线追踪、材质与外观。 一、变换（Transformation） 二维变换的矩阵形式 缩放: [s 0] 旋转: [cosθ -sinθ] …
GAMES102：几何建模与处理（刘利刚）的笔记。 主题：如何表示形状，以及如何处理形状。 一、几何表示的三类 类型 形式 优点 缺点 离散 点云、网格 通用、易获取 无连续性信息 连续 参数曲线曲面 光滑、可精确求值 难…
自动关联目录：Rendering 渲染方程 一切渲染方法的出发点都是 Kajiya 渲染方程（1986）： Lo(x,ωo)=Le(x,ωo)+∫Ωfr(x,ωi,ωo) Li(x,ωi) (ωi⋅n) dωiL_o(x, \omega_o…
问题定义 全局光照（Global Illumination, GI） = 直接光照 + 间接光照。 一次弹射（一次反射后到眼睛） → 直接光照（相对便宜） 多次弹射 → 间接光照（昂贵） 间接…
TAA 问题的两类走样 抗锯齿（AA）解决的走样有两类，需要分清： 类型 成因 解法 几何走样 三角形边缘被离散采样 超采样（MSAA/SSAA）、后处理边缘检测 着色走样 着色结果本身频率过高（高光、高频纹理、细几何） …
cascaded shading Cascaded Shadow Maps（CSM）——按距离分层 shadow map。 为什么 一张 4096² 的 shadow map 覆盖 500m 的场景 → 每米约 8 个纹素 → 近处…
要解决什么 环境光照（Environment Lighting / IBL, Image-Based Lighting）：用一张环境贴图（cubemap / 全景图）表示"来自四面八方的光"，代替若干离散光源。 渲染方程…
shadow mapping 基本思路 阴影 = 从光源看不到，但从相机看得到的地方。 Pass 1: 从光源渲染深度图（shadow map），只存深度 Pass 2: 从相机渲染，对每个片元： - 把它变换到光源空间，得…
表面模型 Microfacet BRDF（ microfacet 微表面模型） 现代 PBR 的统一框架：表面由无数微小的镜面组成，宏观的反射是它们的统计结果。 fr(i,o)=F(i,h)⋅G(i,o,h)⋅D(h)4(n⋅i)(n⋅o)…
自动关联目录：Simulation 物理仿真回答的是：给定当前状态，下一时刻的状态是什么。 统一的数学框架 几乎所有物理仿真都在解同一类方程——常微分方程（ODE）： ddt(xv)=(vM−1f(x,v,t))\frac{d}{dt}\b…
自动关联目录：Geometry 几何回答的是"形状如何表示，以及如何处理"。 表示的三大类 类别 形式 判断内外 采样表面 典型 隐式 f(x,y,z)=0f(x,y,z) = 0f(x,y,z)=0 易 …
核心矛盾 硬件光线追踪（RTX / DXR）能追踪光线，但一帧只能负担 1~2 spp（每像素 1~2 条光线）。 离线渲染: 几千 spp，无噪声 实时渲染: 1~2 spp，噪声极大（几乎不可用） 所以实时光追的全部技术 = 如何用…
职责 词法分析器（Scanner / Lexer）是编译器的第一个阶段，做三件事： 切分：把连续的字符流切成有意义的单元 归类：给每个单元打上类别 过滤：丢掉空白、换行、注释 输出是一串 Token，每个 Token 形如 <类别…
职责 输入 Token 流，输出语法树。做两件事： 判定：这串 Token 是否合法 构造：如果合法，把它的层级结构还原出来 第二点才是目的。编译器要的不是"通过/不通过"，而是一棵能往下走的树。 x = …
要解决的问题 语法分析只回答"结构对不对"。但编译器真正要的是在识别结构的同时做点事：算类型、建符号表、生成代码。 语法制导翻译（Syntax-Directed Translation, SDT）就是这套机制：把语义动作…
为什么需要 IR 没有 IR：M 种语言 × N 种目标机 = M×N 个编译器。 有 IR：M 个前端 + N 个后端 = M+N 个模块。 除此之外 IR 还有两个不可替代的作用： 优化需要一个稳定的平台。在 AST 上做数据流分析很…
自动关联目录：Compilation Principle 编译原理回答的是一个很具体的工程问题：如何把人写的字符流，机械地、可验证地、可优化地翻译成机器能执行的指令流。 它不是"背文法"的学科。真正有价值的部分是三件事：…
冯·诺依曼结构 ┌──────────┐ │ CPU │ ← 控制器 + 运算器 + 寄存器 └────┬─────┘ │ 总线 ┌────┴─────────────────────┐ │ 存储器（内存） …
编译器在做什么 编译器的输入是字符序列，输出是指令序列。它做的全部事情可以概括为一句话： 逐步把"无结构的文本"转换成"有结构的中间表示"，每转换一次就丢弃一点源语言的表层信息、补充一点机器需要的信…