数学-是不动点的味道

数列的极限

1. 概念
2. 数列极限的定义
3. 数列收敛的性质
   • 唯一性
   • 有界性
   • 保号性
4. 海涅定理（归结原则）
5. 夹逼准则
6. 单调有界准则
7. ${x_n}$收敛于$a$的速度问题

数据结构-前序中序后序blablabla

树的性质

let $T_m$ denote a tree with degree $m$.

let $D(n)$ denote the out degree of the node $x$ in the tree $T_m$.

let $n_i$ denote the number of notes with degree $i$.

let $H$ denote the depth/height of the tree $T_m$.

let $N$ denote the total number of nodes in tree.$N=\sum\limits_{i=0}^mn_i$.

let $N_i$ denote the number of nodes at layer $i\in \mathcal{N^*}$

1. $N=1 + \sum\limits_{i=1}^mi\cdot n_i$.
2. $n_0 =1 + \sum\limits_{i=2}^m(i-1)\cdot n_i$
3. $N_i\leq m^{i-1}$ if not an empty tree with degree m.
4. $N\leq \frac{m^H-1}{m-1}$
5. $H\geq \lceil\log_{m}\left((N(m-1))+1\right)\rceil$

二叉树

1. 二叉树的性质
   1. $N_i\leq 2^{i-1}$ if not an empty tree.
   2. $N\leq 2^H-1$
   3. $n_0 =1 + n_2$
   4. $H\geq \lceil\log_{2}(N+1)\rceil$
2. 完全二叉树
3. 满二叉树
4. 二叉树的构造
   1. 前序加中序
   2. 后序加中序
   3. 层次加中序
   4. 前序加树形结构
   5. 中序加树形结构
   6. 后序加树形结构
   7. 层次加树形结构
5. 二叉树的遍历
   1. 前序
   2. 中序
   3. 后序
   4. 层次

操作系统-nice of linux

1. Multi-Level Feedback Queue (cpu-sched-mlfq)
   1. Basic Rules
      • Rule 1:If Priority(A) $>$ Priority(B), A runs (B doesn’t).
      • Rule 2:If Priority(A) $=$ Priority(B), A & B run in RR(Round Robin).
      • However: Those with low Priority will get starved!
      • Therefore: We need to change the Priority over time.
   2. To change Priority
      • Rule 3: When a job enters the system, it is placed at the highest priority (the topmost queue).
      • Rule 4a: If a job uses up its allotment while running, its priority is reduced (i.e., it moves down one queue).
      • Rule 4b: If a job gives up the CPU (for example, by performing an I/O operation) before the allotment is up, it stays at the same priority level (i.e., its allotment is reset).
      • However:
        1. Those with long cpu-time will get starved as them move down to the lowest!
        2. Those with smart heart will game the scheduler as they I/O at the last ms of the allotment.
      • Therefore: We need to change rule4a,b and boost periodically.
   3. The Priority Boost
      • Rule 5: After some time period S, move all the jobs in the system to the topmost queue.
   4. Better Accounting
      • Rule 4: Once a job uses up its time allotment at a given level (re gardless of how many times it has given up the CPU), its priority is reduced (i.e., it moves down one queue).
2. Proportional share(cpu-sched-lottery)
   1. Basic Concept: Tickets Represent Your Share
   2. Stride Scheduling
   3. The Linux Completely Fair Scheduler (CFS)