Stellary's Notes

Abstract. 这是本学期信息论的复习笔记。主干内容是证明有噪信道编码定理，佐以一些神秘小结论。

• 基本定义
  • 信息熵
  • 互信息，相对熵
  • 凸性
  • 数据处理不等式
• 信源编码
  • Kraft 不等式
  • Haffman 编码
• 纠错码
  • Non-uniform 纠错码效率的上下界
  • 可高效计算的纠错码
• 信道编码定理
  • 渐进等分性质和有噪信道编码存在性
  • Fano 不等式和有噪信道编码错误率下界
• 杂项
  • 无偏估计和 Cramer-Rao 不等式
  • 通信复杂度
  • 最大熵估计
  • Kolmogrov 复杂度

Abstract. 因为最近在一个 EDA 组里轮转，所以需要学一些经典 EDA 算法。现在主要包括如下线索：

• Trees in Routing

• 球和桶模型（Balls and Bins）
  • The Power of Two Choices
• 随机图
  • 大连通块（Giant Component）
• 鞅

• 基本概念
• 随机变量
  • 离散随机变量
  • 连续随机变量

Abstract. Under Construction

• 关于计算模型的说明
• Hybrid Method
• Adversary Method
• 实例
  • 二分查找 bound