← Notedeck
All engines
·
计算机
en
zh-CN
zh-TW
ja
ko
fr
de
es
pt-BR
tr
it
ar
计算机
66
engines
时间复杂度 · 大 O 增长
Time complexity · Big-O growth
运算量如何随输入规模增长 —— 差距决定能不能扩展
How the work grows with input size — the gap decides what scales
逻辑门 · 真值表
Logic gates · truth tables
AND / OR / NOT / XOR / NAND / NOR —— 数字电路的基本单元
AND / OR / NOT / XOR / NAND / NOR — the building blocks of digital circuits
哈希表 · 散列与冲突
Hash table · hashing & collisions
h(k)=k mod m 把键散布到桶中;冲突用链表挂接
h(k)=k mod m spreads keys into buckets; clashes are chained
排序算法 · 可视化
Sorting algorithms · visualized
看冒泡排序与选择排序如何通过比较和交换把数组排好序
See how bubble and selection sort compare and swap their way to order
二叉搜索树(BST)
Binary search tree (BST)
左 < 节点 < 右,查找只需一路向下 —— O(log n)
Left < node < right, so search walks straight down — O(log n)
卡诺图化简
Karnaugh map minimization
2–4 变量 · 质蕴涵分组(循环相邻) · 最简 SOP
Prime implicants, minimal cover and the simplest sum-of-products
Dijkstra · 单源最短路径
Dijkstra · single-source shortest path
单源最短路 · 优先队列 + 松弛 · 最短路径树
Pick the nearest unvisited node, finalize it, relax its neighbours — step by step
BFS 与 DFS · 图遍历
BFS & DFS · graph traversal
队列 BFS / 栈 DFS · 访问顺序 · 遍历树/回边
Queue fans out level by level; stack dives deep — same graph, different order
拓扑排序 · Kahn 算法
Topological sort · Kahn's algorithm
DAG 入度 · Kahn 算法 · 线性拓扑序
Repeatedly output a node with no remaining prerequisites (in-degree 0)
AVL 自平衡树 · 旋转
AVL self-balancing tree · rotations
平衡因子 · LL/RR/LR/RL 旋转 · O(log n)
Insert keys one at a time; balance factors trigger LL/RR/LR/RL rotations
二叉堆 · 上浮 / 下沉 / 堆化
Binary heap · sift-up / sift-down / heapify
上浮/下沉 · 堆化 · 数组↔树 i→2i+1
A complete tree in an array — watch insert, extract-root and build-heap step by step
最小生成树 · Prim 与 Kruskal
Minimum spanning tree · Prim & Kruskal
Prim/Kruskal · 并查集 · 最小总权重
Two algorithms, one graph — union-find, cycle rejection and running weight
编辑距离(Levenshtein)· 动态规划
Edit distance (Levenshtein) · DP
Levenshtein DP 表 · 增删改 · 回溯对齐
Fill the DP table cell by cell, then backtrace the optimal alignment
霍夫曼编码 · 贪心前缀码
Huffman coding · greedy prefix code
贪心合并 · 前缀码树 · 平均码长/压缩
Merge the two lowest-frequency nodes step by step to build the optimal prefix code
递归 / 调用树
Recursion / call tree
斐波那契/归并/汉诺塔 · 重叠子问题 · 复杂度
Fibonacci · merge sort · Towers of Hanoi — the exact call tree and its cost
图灵机模拟器
Turing machine simulator
纸带 + 读写头 · δ 转移表 · 停机接受/拒绝
Step a machine over its tape, driven only by a numeric δ table
正则表达式 → NFA(汤普森构造)
Regex → NFA (Thompson construction)
汤普森构造 · ε 转移 · 串匹配 active-states
Compile a regex to an NFA with ε-transitions, then match a string by ε-closure
二进制数值表示
Binary number representation
无符号/补码/IEEE-754 · 位域 · 溢出/NaN
Unsigned · two's complement · IEEE-754 float — flip bits, read the value straight back
凯撒 / 维吉尼亚密码 · 频率分析
Caesar & Vigenère ciphers · frequency analysis
移位替换 c=(p+k) mod 26 · 维吉尼亚多表加密 · 字母频率分析破译
Shift and polyalphabetic substitution — see the frequency profile shift vs. flatten
一次一密(XOR)· 完美保密与密钥重用
One-time pad (XOR) · perfect secrecy & key reuse
逐比特异或 · 完美保密 · 密钥复用攻击 c1⊕c2=p1⊕p2
c = p XOR k byte by byte — reversible, and why the key must never repeat
进制转换 · 位值展开与除基取余
Base conversion · positional expansion & division
2/8/10/16 及任意 2–36 进制 · 按位展开 Σdᵢ·bⁱ · 除基取余
Convert integers between bases 2–36, showing both algorithms step by step
RSA encryption · key generation + encrypt/decrypt
RSA encryption · key generation + encrypt/decrypt
n=pq、φ、e/d 逆元 · c=m^e、m=c^d mod n · BigInt 往返验证
Generate a key pair from two primes, encrypt then decrypt, proving the message round-trips exactly
Diffie–Hellman key exchange
Diffie–Hellman key exchange
A=g^a、B=g^b · 共享密钥 g^ab mod p · 离散对数难题
Over a prime field both parties derive the SAME shared secret after a public exchange; an eavesdropper faces the discrete-log problem
Modular exponentiation · square-and-multiply
Modular exponentiation · square-and-multiply
平方-乘法 · 指数二进制展开 · O(log n) 步表
Compute base^exp mod m from the binary expansion of exp — only O(log exp) multiplications
模运算 · 时钟同余环
Modular arithmetic · clock wheel
同余时钟环 · 模加/模乘 · 加法与乘法逆元(扩展欧几里得)
Arithmetic on Z/nZ drawn as a wheel; inverses via the extended Euclidean algorithm
离散分布的香农熵
Shannon entropy of a distribution
H=−Σp·log₂p 比特 · 最大熵 log₂N · 冗余度
Uncertainty in bits: 0 when one outcome is certain, log₂N when uniform
二分查找 · O(log n)
Binary search · O(log n)
lo/mid/hi 窗口 · O(log n) 比较次数 · 步进追踪
Halve the search window each step; comparisons stay near ⌈log₂ size⌉
汉明码 Hamming(7,4) · 单比特纠错
Hamming(7,4) · single-error correction
Hamming(7,4) · 奇偶校验位 · syndrome 定位单比特纠错
Three parity checks pinpoint and repair any single flipped bit
奇偶校验 与 CRC · 差错检测
Parity & CRC · error detection
奇偶校验 · 生成多项式 · 模 2 长除法 · 检错
A parity bit and a polynomial-division checksum that catch flipped bits
哈希雪崩效应 · 扩散
Hash avalanche · diffusion
翻转 1 输入比特→约 50% 输出翻转 · FNV-1a 扩散 · 汉明距离
Flip one input bit and watch ~half the output bits flip
Bellman–Ford shortest paths
Bellman–Ford shortest paths
所有边松弛V−1次 · 处理负权 · 检测负环
Relax every edge V−1 times — handles negative weights and detects negative cycles
Floyd–Warshall all-pairs shortest paths
Floyd–Warshall all-pairs shortest paths
全源最短路DP · dist=min(dist,dist[i][k]+dist[k][j])
DP over intermediate vertices: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
A* pathfinding on a grid
A* pathfinding on a grid
f=g+h · 可采纳启发式(曼哈顿) · 比Dijkstra扩展更少
Expand by f = g + h — optimal path, fewer nodes than Dijkstra
Disjoint-set (union–find) · union by rank + path compression
Disjoint-set (union–find) · union by rank + path compression
按秩合并+路径压缩 · 近O(1) find/union · 连通性
Merge elements into sets and flatten the trees — near-O(1) connectivity
Strongly connected components · Tarjan's algorithm
Strongly connected components · Tarjan's algorithm
Tarjan lowlink/Kosaraju两遍DFS · SCC着色 · 缩点
One DFS, index + lowlink — colour every maximal mutually-reachable group
Maximum bipartite matching · augmenting paths
Maximum bipartite matching · augmenting paths
增广路 匈牙利/Hopcroft · König:最大匹配=最小点覆盖
Pair left and right vertices with no shared endpoints — grow the matching one path at a time
Longest Common Subsequence · dynamic programming
Longest Common Subsequence · dynamic programming
DP dp[i][j] · 匹配对角线 · 回溯重构LCS
Fill the DP table, follow the matched diagonals, backtrack to recover the LCS
Coin change · dynamic programming
Coin change · dynamic programming
最少硬币 dp[a]=min dp[a−c]+1 · 方案数 · 回溯选币
Fewest coins for each amount, plus how many distinct ways — built bottom-up
Matrix-chain multiplication · optimal parenthesization
Matrix-chain multiplication · optimal parenthesization
DP最小标量乘法数 · 最优加括号 · vs朴素
Reorder the products to minimise scalar multiplications — same result, far fewer operations
KMP string matching · prefix function & mismatch jumps
KMP string matching · prefix function & mismatch jumps
前缀函数失配表 · O(n+m) · 文本不回溯
Precompute the failure table, then search in O(n+m) — the text pointer never moves backward
Rabin–Karp · rolling-hash substring search
Rabin–Karp · rolling-hash substring search
窗口滚动哈希 · 哈希命中再逐字符验证 · 误命中
Hash each window in O(1), compare to the pattern hash, verify on a hit to reject collisions
PageRank · power iteration on a web graph
PageRank · power iteration on a web graph
PR=(1−d)/N+d·Σ PR(in)/outdeg · d≈0.85 · 稳态排名
PR(p) = (1−d)/N + d·Σ PR(q)/outdeg(q) — iterate until the scores stop changing
先来先服务(FCFS)· CPU 调度
FCFS · CPU scheduling
先来先服务 · 甘特图 · 周转/等待时间
Processes run to completion in arrival order · Gantt chart + turnaround/waiting
最短作业优先 · CPU 调度
SJF / SRTF · CPU scheduling
最短作业优先 · 非抢占/SRTF · 平均等待最小
Shortest job (or shortest remaining time) runs next · Gantt + turnaround/waiting
时间片轮转 · CPU 调度
Round-Robin · CPU scheduling
时间片轮转 · 可调quantum · 就绪队列+上下文切换
Each process runs one quantum in turn · Gantt + context switches
FIFO 页面置换
FIFO page replacement
FIFO淘汰最早帧 · 帧表演化 · 缺页数(Belady异常)
First-in-first-out frame eviction · frame-table evolution + fault count
最优页面置换(OPT)
Optimal page replacement (OPT)
OPT淘汰最远将来使用 · 缺页理论下界 · vs FIFO
Evict the page used farthest in the future · theoretical minimum faults
时钟(二次机会)页面置换
Clock (second-chance) page replacement
二次机会 · 引用位+时钟指针环 · 缺页数
Circular list + reference bits approximate LRU · ring + frame-table
Disk-head scheduling
Disk-head scheduling
FCFS/SSTF/SCAN/C-SCAN · 寻道距离对比 · 磁头路径
Compare seek distance for FCFS · SSTF · SCAN · C-SCAN over a cylinder axis
Banker's algorithm
Banker's algorithm
Need=Max−Alloc · 安全序列搜索 · 死锁避免
Deadlock avoidance · derive Need, run the safety algorithm, read off a safe sequence
Resource-Allocation Graph
Resource-Allocation Graph
资源分配图 · 请求/分配边 · 单实例环=死锁
Single-instance resources · a cycle means deadlock
Producer / Consumer · bounded buffer
Producer / Consumer · bounded buffer
empty/full/mutex信号量 · 有界缓冲 · 不溢出不下溢
Three semaphores (empty, full, mutex) coordinate a ring buffer — no overflow, no underflow
Dining Philosophers · ordered-fork solution
Dining Philosophers · ordered-fork solution
5哲学家5叉 · 资源分层取叉 · 确定调度无死锁
Pick up the lower-numbered fork first — the wait-for cycle is broken, so no deadlock
Paging · address translation
Paging · address translation
逻辑地址→页号+偏移 · 查页表 · 组合物理地址
Split a logical address into page number + offset, look up the frame, form the physical address
FIRST & FOLLOW sets
FIRST & FOLLOW sets
可空传播 · FIRST/FOLLOW集 · CFG分析
Nullable, FIRST and FOLLOW by least-fixpoint over a grammar
LL(1) parse table & predictive parsing
LL(1) parse table & predictive parsing
FIRST/FOLLOW建表 · 冲突检测 · 栈式预测分析
Build M[A,a] from FIRST/FOLLOW, flag conflicts, then drive a stack parse
递归下降分析器 · 预测分析
Recursive-descent parser · predictive parse
预测自顶向下 · 递归下降 · 分析树
Top-down parse of an arithmetic grammar: trace the recursive calls and build the parse tree
移进-归约分析器 · 自底向上 LR
Shift-reduce parser · bottom-up LR
自底向上 · 显式栈移进/归约 · 动作序列
An explicit stack shifts tokens and reduces handles until the whole input collapses to the start symbol
Earley 分析器 · 任意 CFG 图分析
Earley parser · chart parsing any CFG
predict/scan/complete · 逐位置状态集 · 任意CFG
Predict / scan / complete build state sets S(0)…S(n) · handles left recursion
NFA → DFA(子集构造)
NFA → DFA (subset construction)
ε闭包+move · 子集构造 · NFA→等价DFA状态表
Determinize an NFA: every DFA state is a set of NFA states via ε-closure and move
DFA 最小化
DFA minimization
划分细化/表填充 · 合并等价状态 · 最小DFA
Merge indistinguishable states by refining a partition until it is stable
泵引理
Pumping lemma
正则xyz分解 |xy|≤p · 泵入泵出 · 非正则反例
Pump the middle segment y and watch whether x yⁱ z stays in the language
LR(0) 项集
LR(0) items
closure/goto · 规范项集族 · LR(0)项集DFA
CLOSURE and GOTO build the item-set DFA of an LR parser
CYK 分析
CYK parser
CNF文法 · 三角DP表 · O(n³)成员判定
Dynamic-programming membership test for a Chomsky-Normal-Form grammar
λ 演算 · β 归约
Lambda calculus · β-reduction
避免捕获替换 · 正规序β归约 · 到范式
Normal-order (leftmost-outermost) reduction with capture-avoiding substitution
抽象语法树求值
AST evaluation
表达式→AST · 优先级 · 语法树自底向上求值
Parse an arithmetic expression into a tree, then evaluate bottom-up with correct precedence