Stellary's Notes

Abstract. 本章从牛顿定律出发推导欧拉-拉格朗日方程，以窥如何从能量出发解决动力学问题。

• 引入
• 约束与广义坐标
• 虚功原理与达朗贝尔原理
• 弱耗散系统的运动方程

Abstract. 本合集包含一些今后可能用到的数理基础。现在包含：

1. 力学

• 中性 Rydberg 原子量子计算机的建模
• 保真度建模
• 线路规划（Scheduling）
• 量子比特放置（Placement）
• 量子比特路由（routing）

Abstract.

• 问题
• 完美哈希
  • 一级完美哈希
• Succint Dictionaries

Abstract. 更好的 union bound，和相应的搜索可行解算法。

• 引入
• 原始定理陈述和证明
• Moser-Tardos 算法
• Moser 算法及其信息论证明

Abstract. 官方页面。简单整理一下收听该课程的笔记。

Abstract. 主干参考教学课件，预计将覆盖 Michael Sipser Book 的重要内容，以及 Arora Book 第一部分前八个章节的内容。

最后一节 交互式证明 写的非常糟糕。

• 形式语言和自动机
  • 有限状态自动机和正则语言
  • （非确定性）下推自动机和上下文无关语言
• 可计算性理论
  • 图灵机的基本定义
  • 关于可计算性的一些论题
• 复杂度理论
  • 时间复杂度
  • 空间复杂度
  • 多项式层
  • 布尔电路
  • 随机算法
  • 交互式证明
• 附录
  • 开放性问题
  • 练习和补充结论

Abstract. 前半部分是集中不等式、大数定律和中心极限定理。后半部分是无聊的统计。

• 准备工具
  • 集中不等式
  • 随机变量的收敛
  • 特征函数
• 大数定律，中心极限定理
• 统计基础
• 参数估计
  • 点估计的评价
  • 点估计的方法
  • 区间估计
• 假设检验
• 方差分析
• 回归分析
• 附录：统计常用速查表格

Abstract. 仅 Focus 在当年学 OI 的时候没有重视的网络流复杂度分析、下界计算、近似比计算等。

• 最大流
  • 最小割最大流定理
  • 基于增广路的算法
  • 基于预流推进的算法
• 费用流

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

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