SystemTap 工具

SystemTap 允许用户在不重新编译代码的情况下利用静态追踪、动态追踪工具，比如在任何地方动态插入printk，或者改变内核的关键数据结构（guru模式）。所有的操作都要以root用户模式下进行。

数列求和公式

决策论概述

决策的内涵

决策是在人们的政治、经济、技术和日常生活中，为了达到预期目的，从所有可供选择的多个方案中，找出最满意方案的一种活动。

• 狭义决策认为决策就是做决定，单纯强调最终结果。

• 广义决策认为将管理过程的行为都纳入决策范畴，决策贯穿于整个管理过程中。

1. 函数渐近界的定理

   • 定理1

     设$f$和 $g$是定义域为自然数集合的函数：

     （1）如果$\lim\limits_{n\rightarrow\infty}f(n)/g(n)$存在，并且等于某个常数$c>0$，那么$f(n)=\Theta(g(n))$。

     （2）如果$\lim\limits_{n\rightarrow\infty}f(n)/g(n)=0$，那么$f(n)=o(g(n))$。

     （3）如果$\lim\limits_{n\rightarrow\infty}f(n)/g(n)=+\infty$，那么$f(n)=\omega(g(n))$。

     推理1 → 多项式函数的阶低于指数函数的阶，$n^d=o(r^n),r>1,d>0$。

     推理2 →对数函数的阶低于幂函数的阶，$\ln n=o(n^d),d>0$。

算法研究的主要内容

1. 计算复杂性理论（Computational complexity theory）

   • 常见问题：

     • 货郎问题 （NP-hard 问题）

     • 0-1背包问题

       问题的解为0-1向量 $<X_1,X_2,...,Xn_>$

     • 双机调度问题

   • NP-hard问题

     • 问题有数千个，大量存在于各个领域；

     • 至今未找到有效算法：现有算法的运行时间是输入规模的指数或更高阶函数；、

     • 至今没有人能够证明对于这类问题存在多项式时间算法；

     • 是否存在多项式时间算法等价于存在有效计算的边界

   • 程序 = 算法 + 数据结构

     • 好的算法： 提高求解问题的效率；节省存储空间

     • 算法的研究目标：

       问题 → 建模并寻找算法 （算法技术设计）

       算法 → 算法的评价 （算法分析方法）

       算法类 → 问题复杂度的估计 （问题复杂度分析）

       问题类 → 能够求解的边界 （计算复杂性理论）

   • NP完全理论

网络流量的博弈

1. 网络结构上的博弈

   • 公路交通网

博弈论的基本概念

1. 博弈（game）

   博弈三要素：

   • 参与人（player，玩家）

   • 策略集（strategy，战略）

   • 回报（payoff，收益、支付）

   • 次序（order）

   • 均衡（equilibrium）

   每个参与人都有一个策略集；

   策略组：每个参与人出一个策略构成策略组合

   对应每个策略组，每个参与人都有一个回报

一、有向图

小世界问题 The Small-World Program

同质性

1. 同质性是古老议题：

   • 柏拉图

     相似性带来友谊

   • 亚里士多德

     人们喜欢与自己相似的人

   • 俗语

     夫妻相