算法引论：一种创造性方法.[美]Udi Manber(带详细书签).pdf

本书是国际算法大师乌迪·曼博（Udi Manber）博士撰写的一本享有盛誉的著作。全书共分12章：第1章到第4章为介绍性内容，涉及数学归纳法、算法分析、数据结构等内容；第5章提出了与归纳证明进行类比的算法设计思想；第6章到第9章分别给出了4个领域的算法，如序列和集合的算法、图算法、几何算法、代数和数值算法；第10章涉及归约，也是第11章的序幕，而后者涉及NP完全问题；第12章则介绍了并行算法；最后是部分习题的答案及参考文献。本书的特色有二，旨在提高读者的问题求解能力，使读者能够理解算法设计的过程和思想：一是强调算法设计的创造性过程，注重算法设计背后的创造性思想，而不拘泥于某个具体算法的详细讨论；二是将算法设计类比于定理归纳证明，揭示了算法设计的基本思想和本质。 本书的组织结构清晰且易于理解，强调了创造性，具有浓郁特色，时至今日仍有其巨大的价值，并且适合作为计算机及相关专业算法和高级算法课程的教材。 第1章 引论 第2章 数学归纳法 2.1 引言 2.2 三个简单的例子 2.3 平面内区域的计数 2.4 简单的着色问题 2.5 复杂一些的加法题 2.6 一个简单的不等式 2.7 欧拉公式 2.8 图论中的一个问题 2.9 格雷码 2.10 在图上寻找无重边的路 2.11 数学平均数和几何平均数定理 2.12 循环不变量：将十进制数转换为二进制数 2.13 常见的错误 2.14 小结 第3章 算法分析 3.1 引言 3.2 符号O 3.3 时间与空间复杂度 3.4 求和 3.5 递推关系 3.5.1 巧妙地猜测 3.5.2 分治关系 3.5.3 涉及全部历史的递推关系 3.6 一些有用的证明论据 3.7 小结 第4章 数据结构简介 4.1 引言 4.2 基本数据结构 4.2.1 元素 4.2.2 数组 4.2.3 记录 4.2.4 链表 4.3 树 4.3.1 树的表示 4.3.2 堆 4.3.3 二叉搜索树 4.3.4 AVL树 4.4 散列 4.5 合并?查找问题 4.6 图 4.7 小结 第5章 基于归纳的算法设计 5.1 引言 5.2 多项式求值 5.3 最大导出子图 5.4 寻找一对一映射 5.5 社会名流问题 5.6 分治算法：轮廓问题 5.7 在二叉树中计算平衡因子 5.8 寻找最大连续子序列 5.9 增强归纳假设 5.10 动态规划：背包问题 5.11 常见的错误 5.12 小结 第6章 序列和集合的算法 6.1 引言 6.2 二叉搜索的几种形式 6.2.1 纯二叉搜索 6.2.2 循环序列的二叉搜索 6.2.3 二叉搜索特殊下标 6.2.4 二叉搜索长度未知的序列 6.2.5 重叠子序列问题 6.2.6 解方程 6.3 内插搜索 6.4 排序 6.4.1 桶排序和基数排序 6.4.2 插入排序和选择排序 6.4.3 归并排序 6.4.4 快速排序 6.4.5 堆排序 6.4.6 排序问题的下界 6.5 顺序统计 6.5.1 最大数和最小数 6.5.2 查找第k小的数 6.6 数据压缩 6.7 串匹配 6.8 序列比较 6.9 概率算法 6.9.1 随机数 6.9.2 着色问题 6.9.3 将拉斯维加斯算法变换成确定性算法 6.10 查找众数 6.11 三个展现有趣证明方法的问题 6.11.1 最长递增序列 6.11.2 查找集合中两个最大的元素 6.11.3 计算多重集合的模 6.12 小结 第7章 图算法 7.1 引言 7.2 欧拉图 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索 7.4 拓扑排序 7.5 单源最短路径 7.6 最小代价生成树 7.7 全部最短路径 7.8 传递闭包 7.9 图的分解 7.9.1 双连通分支 7.9.2 强连通分支 7.9.3 利用图分解的例子 7.10 匹配 7.10.1 非常稠密图中的完美匹配 7.10.2 偶图匹配 7.11 网络流量 7.12 哈密尔顿旅行 7.12.1 反向归纳 7.12.2 在非常稠密图中找哈密尔顿回路 7.13 小结 第8章 几何算法 8.1 引言 8.2 判定点是否在多边形内部 8.3 构造简单多边形 8.4 凸包 8.4.1 直接方法 8.4.2 礼品包裹算法 8.4.3 Graham扫描算法 8.5 最近点对 8.6 水平线段和竖直线段的交点 8.7 小结 第9章 代数和数值算法 9.1 引言 9.2 求

Numerical Recipes 3rd Edition.pdf

英文第3版，压缩包内含PDF文档、源代码，其中PDF文档已加书签 本书选材内容丰富，包括了当代科学计算过程中涉及的大量内容：求特殊函数值、随机数、排序、最优化、快速傅里叶变换、谱分析、小波变换、统计描述和数据建模、偏微分议程数值解、若乾编码算法和任意精度计算等。本书科学性和实用性统一，不仅对每种算法进行了数学分析和比较，而且根据作者经验对算法给出了评论和建议，并在此基础上提供了用C++语言编写的实用程序。

并行计算导论（原书第2版）.[美]Ananth Grama(带详细书签).pdf

本书系统介绍涉及并行计算的体系结构、编程范例、算法与应用和标准等。覆盖了并行计算领域的传统问题，并且尽可能地采用与底层平台无关的体系结构和针对抽象模型来设计算法。书中选择MPI(Message Passing Interface)、POSIX线程和OpenMP这三个应用最广泛的编写可移植并行程序的标准作为编程模型，并在不同例子中反映了并行计算的不断变化的应用组合。本书结构合理，可读性强，加之每章精心设计的习题集，更加适合教学。 本书论述清晰，示例生动，并附有大量习题，适合作为高等院校计算机及相关专业本科生和研究生的教材或参考书。原版自1993年出版第1版到2003年出版第2版以来，已在世界范围内被广泛地采用为高等院校本科生和研究生的教材或参考书。 第1章 并行计算介绍 1.1 推动并行化 1.1.1 计算能力因素——从晶体管到浮点运算速度 1.1.2 内存及磁盘速度的因素 1.1.3 数据通信因素 1.2 并行计算适用范围 1.2.1 在工程及设计中的应用 1.2.2 科学计算中的应用 1.2.3 商业应用 1.2.4 计算机系统中的应用 1.3 本书的组织及内容 1.4 书目评注 习题 第2章 并行编程平台 2.1 隐式并行：微处理器体系结构的发展趋势 2.1.1 流水线与超标量执行 2.1.2 超长指令字处理器 2.2 内存系统性能的局限 2.2.1 使用高速缓存改善有效内存延迟 2.2.2 内存带宽的影响 2.2.3 躲避内存延迟的其他方法 2.2.4 多线程与预取间的权衡 2.3 并行计算平台剖析 2.3.1 并行平台的控制结构 2.3.2 并行平台的通信模型 2.4 并行平台的物理组织 2.4.1 理想并行计算机的体系结构 2.4.2 并行计算机互连网络 2.4.3 网络拓扑结构 2.4.4 静态互连网络评价 2.4.5 动态互连网络评价 2.4.6 多处理器系统中的高速缓存一致性 2.5 并行计算机的通信成本 2.5.1 并行计算机的消息传递成本 2.5.2 共享地址空间计算机的通信成本 2.6 互连网络的路由选择机制 2.7 进程-处理器映射的影响和映射技术 2.7.1 图的映射技术 2.7.2 成本-性能平衡 2.8 书目评注 习题 第3章 并行算法设计原则 3.1 预备知识 3.1.1 分解、任务与依赖图 3.1.2 粒度、并发性与任务交互 3.1.3 进程和映射 3.1.4 进程与处理器 3.2 分解技术 3.2.1 递归分解 3.2.2 数据分解 3.2.3 探测性分解 3.2.4 推测性分解 3.2.5 混合分解 3.3 任务和交互的特点 3.3.1 任务特性 3.3.2 任务间交互的特征 3.4 负载平衡的映射技术 3.4.1 静态映射方案 3.4.2 动态映射方案 3.5 包含交互开销的方法 3.5.1 最大化数据本地性 3.5.2 最小化争用与热点 3.5.3 使计算与交互重叠 3.5.4 复制数据或计算 3.5.5 使用最优聚合交互操作 3.5.6 一些交互与另一些交互的重叠 3.6 并行算法模型 3.6.1 数据并行模型 3.6.2 任务图模型 3.6.3 工作池模型 3.6.4 主-从模型 3.6.5 流水线模型或生产者-消费者模型 3.6.6 混合模型 3.7 书目评注 习题 第4章 基本通信操作 4.1 一对多广播以及多对一归约 4.1.1 环或线性阵列 4.1.2 格网 4.1.3 超立方体 4.1.4 平衡二叉树 4.1.5 算法细节 4.1.6 成本分析 4.2 多对多广播和归约 4.2.1 线性阵列和环 4.2.2 格网 4.2.3 超立方体 4.2.4 成本分析 4.3 全归约与前缀和操作 4.4 散发和收集 4.5 多对多私自通信 4.5.1 环 4.5.2 格网 4.5.3 超立方体 4.6 循环移位 4.6.1 格网 4.6.2 超立方体 4.7 提高某些通信操作的速度 4.7.1 消息分裂和路由选择 4.7.2 全端口通信 4.8 小结 4.9 书目评注 习题 第5章 并行程序的解析建模 5.1 并行程序中的开销来源 5.2 并行系统的性能度量 5.2.1 执行时间 5.2.2 总并行开销 5.2.3 加速比 5.2.4 效率 5.2.5 成本 5.3 粒度对性能的影响 5.4 并行系统的可扩展性 5.4.1

ACM国际大学生程序设计竞赛:知识与入门（带书签）

ACM国际大学生程序设计竞赛（ACM-ICPC）是国际上公认的水平最高、规模最大、影响最深的计算机专业竞赛，目前全球参与人数达20多万。本书作者将16年的教练经验与积累撰写成本系列丛书，全面、深入而系统地将ACM-ICPC展现给读者。本系列丛书包括《ACM国际大学生程序设计竞赛：知识与入门》、《ACM国际大学生程序设计竞赛：算法与实现》、《ACM国际大学生程序设计竞赛：题目与解读》、《ACM国际大学生程序设计竞赛：比赛与思考》等4册，其中《ACM国际大学生程序设计竞赛：知识与入门》介绍了ACM-ICPC的知识及其分类、进阶与角色、在线评测系统；《ACM国际大学生程序设计竞赛：算法与实现》介绍了ACM-ICPC算法分类、实现及索引； 目录 第一部分 入门与进阶 第1章 入门 3 1.1 ACM-ICPC竞赛介绍 3 1.2 新手入门 5 1.3 团队的分工与配合 7 1.4 训练 9 1.5 备战分区赛 12 1.6 备战总决赛 13 第2章 进阶 16 2.1 如何提高读题能力 16 2.2 如何提高代码能力 17 2.3 Bug与Debug 19 2.4 从做题者到命题者 20 第二部分 知识点与求解策略 第3章 数学基础 25 3.1 函数增长与 复杂性分类 25 3.1.1 渐进符号 25 3.1.2 阶的计算 26 3.1.3 复杂性分类 27 3.2 概率论 28 3.2.1 事件与概率 28 3.2.2 期望与方差 30 3.3 代数学 31 3.3.1 矩阵 31 3.3.2 行列式 33 3.3.3 解线性方程组 34 3.3.4 多项式 37 3.3.5 复数 38 3.3.6 群 39 3.4 组合学 42 3.4.1 排列与组合 42 3.4.2 鸽巢原理 43 3.4.3 容斥原理 44 3.4.4 特殊计数序列 45 3.4.5 Pólya计数定理 47 3.5 博弈论 50 3.5.1 博弈树 50 3.5.2 SG函数 51 3.5.3 Nim游戏与Nim和 53 3.6 数论 54 3.6.1 整除 54 3.6.2 不定方程 57 3.6.3 同余方程与欧拉定理 58 3.6.4 原根、离散对数和二项同余 ?方程 60 3.6.5 连分数 61 第4章 数据结构 64 4.1 线性表 64 4.1.1 链表 64 4.1.2 栈 65 4.1.3 队列 65 4.1.4 块状链表 66 4.2 集合 67 4.2.1 散列表 67 4.2.2 并查集 69 4.3 排序 71 4.3.1 朴素排序算法 71 4.3.1.1 插入排序 71 4.3.1.2 冒泡排序 72 4.3.2 高效排序算法 73 4.3.2.1 归并排序算法 73 4.3.2.2 快速排序算法 74 4.3.2.3 线性排序算法 76 4.4 树 78 4.4.1 堆 78 4.4.1.1 二叉堆 78 4.4.1.2 左偏树 80 4.4.2 二叉树 82 4.4.2.1 二叉搜索树 82 4.4.2.2 Treap 84 4.4.2.3 伸展树 85 4.4.3 线段树 89 第5章 图论 91 5.1 图 91 5.1.1 基本概念 91 5.1.1.1 图的定义与基本 ?术语 91 5.1.1.2 匹配与覆盖 92 5.1.1.3 独立集、团与支配集 94 5.1.1.4 图的染色 95 5.1.2 特殊图的分类 96 5.1.3 图的遍历 99 5.1.3.1 深度优先遍历 99 5.1.3.2 广度优先遍历 100 5.1.4 连通性 103 5.1.4.1 连通性的基本定义 103 5.1.4.2 割点与桥 104 5.1.4.3 强连通分量 105 5.1.4.4 应用：2-SAT 107 5.1.5 哈密顿路与欧拉路 108 5.1.5.1 哈密顿路 108 5.1.5.2 欧拉路 109 5.1.6 最短路 111 5.1.6.1 Bellman-ford算法 111 5.1.6.2 Dijkstra算法 113 5.1.6.3 Floyd算法 114 5.2 树 115 5.2.1 基本概念与遍历 115 5.2.1.1 树的基本定义与术语 115 5.2.1.2 树的遍历 117 5.2.2 生成树 117 5.2.2.1 生成树的基本概念 117 5.2.2.2 Prim算法 118 5.2.2.3 Kruskal算法 120 5.2.2.4 最小生成树的变种 121 5.2.2.5 生成树计数 123 5.3 二分图 124 5.3.1 最大匹配 124 5.3.2 最大权匹配 126 5.3.3 稳定婚姻 128 5.4 网络流 129 5.4.1 基本概念 129 5.4.1.1 流网络 129 5.4.1.2 残量网络 130 5.4.1.3 增广路径 130 5.4.1.4 最大流最小割定理 131 5.4.2 最大流算法 131 5.4.2.1 Ford-Fulkerson算法 131 5.4.2.2 Dinic算法 133 5.4.3 费用流 135 5.4.4 流与割模型 137 5.4.4.1 上下界网络流 137 5.4.4.2 混合图欧拉回路 139 5.4.4.3 最大权闭合子图 140 第6章 计算几何 142 6.1 向量 142 6.2 点的有序化 143 6.3 多边形与圆 144 6.3.1 简单多边形 144 6.3.2 凸包问题 146 6.3.3 圆的面积并 147 6.4 半平面交 148 6.5 经典问题 151 6.5.1 线段求交 151 6.5.2 最近点对 152 6.5.3 最远点对 154 第7章 论题选编 156 7.1 背包问题 156 7.2 LCA与RMQ 157 7.3 快速傅里叶变换 159 7.4 字符串 161 7.4.1 字符串匹配 161 7.4.2 Trie 164 7.4.3 AC自动机 165 7.4.4 后缀数组 167 7.4.5 扩展KMP 169 第8章 求解策略 171 8.1 搜索 171 8.2 分治 175 8.3 贪心 176 8.4 动态规划 179 8.5 随机化 183 第三部分 在 线 资 源 第9章 在线评测系统 187 9.1 基本使用方法 187 9.2 USACO介绍 190 9.3 CII介绍 191 9.4 PKU介绍 192 9.5 SGU介绍 193 9.6 SPOJ介绍 195 第10章 网上比赛 197 10.1 GCJ介绍 197 10.2 TopCoder介绍 199 10.3 Codeforces介绍 200 参考文献 203

图像处理基础（第2版）.[美]Maria Petrou(带详细书签).pdf

本书也是一本介绍图像技术的教材，但它有不同的视点和方式。至少有两点值得指出： 首先，作者完全采用了一种问答的形式来组织和介绍相关内容。全书从头到尾共设计了472个问题（很多是由学生提出来的），有问有答，循序渐进，逐步将各种图像技术依次介绍。这种形式除能帮助课堂教学外，也很适合自学，因为每一段都解决了一个疑问，对自学者会很有吸引力。书中还有383个详细的示例，不仅方便读者学习，对讲授相关课程的教师也是一个很好的资源。 其次，作者对基本内容和高级内容进行了划分。但与许多教材中这两部分内容不相重合、后者是前者的延伸不同，该书两部分内容密切相关、后者对应前者的更深层次。从其安排来看，基本内容是主干，而高级内容（放在63个框内，且有161个配合示例，编号前均加B）则分布在书中与相关基本内容对应的位置。如果把基本内容看作一个主程序，那么这些高级内容部分就像子程序，随时可在需要处调用。 本书是一本篇幅较大的书，从结构上看，有7章共27节。全书共有编了号的图307个（其中10个为彩图）、表格25个、公式1892个。另外有一个约80篇参考文献的目录，以及可进行索引的近400个术语。全书译成中文约合100万字（也包括图片、绘图、表格、公式等）。本书可作为已具有初步图像技术知识的相关专业高年级本科生和低年级研究生的专业基础课教材，也可供从事图像应用相关领域的科研技术人员参考。 译者基本忠实原书的结构和文字风格进行了翻译。为方便阅读，对书中问答中的问题按章节进行了编号。考虑到书中分散介绍了40多个具体算法，译文中归纳增加了一个算法列表。另外，对原书的索引，考虑中文的习惯进行了一些调整，并按中文次序进行了排列，希望能更好地服务于读者。 封面 -27 封底 -26 书名 -25 版权 -24 译者序 -19 前言 -18 目录 -16 第1章 导论 1 1.0.1 为什么要处理图像？ 1 1.0.2 什么是一幅图像？ 1 1.0.3 什么是一幅数字图像？ 1 1.0.4 什么是一个光谱带？ 1 1.0.5 为什么大多数图像处理算法都参照灰度图像进行，而实际中遇到的都是彩色图像？ 2 1.0.6 一幅数字图像是如何形成的？ 2 1.0.7 如果一个传感器对应物理世界中的一个小片，如何能让多个传感器对应场景中的同一个小片？ 2 1.0.8 什么是图像中一个像素位置亮度的物理含义？ 3 1.0.9 为什么图像常用512×512，256×256，128×128 等来表示？ 4 1.0.10 需要多少个比特以存储一幅图像？ 5 1.0.11 什么决定了一幅图像的质量？ 5 1.0.12 什么会使得图像模糊？ 5 1.0.13 图像分辨率是什么含义？ 5 1.0.14 “良好对比度”是什么含义？ 7 1.0.15 图像处理的目的是什么？ 8 1.0.16 如何进行图像处理？ 8 1.0.17 图像处理中使用非线性操作符吗？ 9 1.0.18 什么是线性操作符？ 9 1.0.19 如何来定义线性操作符？ 9 1.0.20 一个成像装置的点扩散函数和一个线性操作符之间有什么联系？ 9 1.0.21 一个线性操作符如何变换一幅图像？ 9 1.0.22 点扩散函数的含义是什么？ 10 B1.1 在连续空间中一个点源的正式定义 10 1.0.23 实际中如何描述一个线性操作符作用在一幅图像上的效果？ 15 1.0.24 对一幅图像可使用多于一个线性操作符吗？ 18 1.0.25 线性操作符使用的次序会导致结果的不同吗？ 18 B1.2 因为矩阵运算次序是不能互换的，如果改变使用移不变线性操作符的次序会发生什么情况？ 18 B1.3 什么是堆叠操作符？ 24 1.0.26 对矩阵H结构上可分离性的假设意味着什么？ 30 1.0.27 如何能将一个可分离变换写成矩阵的形式？ 31 1.0.28 可分离性假设的含义是什么？ 32 B1.4 可分离矩阵方程的正式推导 32 1.0.29 本章要点 34 1.0.30 式（1.108）在线性图像处理中的意义是什么？ 34 1.0.31 这本书有些什么内容呢？ 36 第2章 图像变换 37 2.0.1 本章概况 37 2.0.2 如何能定义一幅基本图像？ 37 2.0.3 什么是两个矢量的外积？ 37 2.0.4 如何可将一幅图像展开成矢量的外积？ 37 2.0.5 如何选择矩阵hc和hr？ 39 2.0.6 什么是酉矩阵？ 39 2.0.7 酉矩阵的逆是什么样的？ 39 2.0.8 如何能构建一个酉矩阵？ 40 2.0.9 如何选择矩阵U和V以使表达g的比特数比f少？ 40 2.0.10 什么是矩阵对角化？ 40 2.0.11 可以对角化任何矩阵吗？ 40 2.1 奇异值分解 40 2.1.1 如何能对角化一幅图像？ 40 B2.1 可将任何图像都展开成矢量的外积吗？ 43 2.1.2 如何计算图像对角化所需的矩阵U，V和Λ.？ 44 B2.2 如果矩阵ggT 的本征值为负会如何？ 44 2.1.3 什么是对一幅图像的奇异值分解？ 47 2.1.4 能将一幅本征图像分解成多幅本征图像吗？ 48 2.1.5 如何可用SVD 来近似一幅图像？ 49 B2.3 SVD 的直观解释是什么？ 49 2.1.6 什么是用SVD 近似一幅图像的误差？ 50 2.1.7 如何能最小化重建误差？ 51 2.1.8 任何图像都可以从某一组基本图像扩展出来吗？ 56 2.1.9 什么是完备和正交的离散函数集合？ 56 2.1.10 存在正交归一化离散值函数的完备集合吗？ 57 2.2 哈尔、沃尔什和哈达玛变换 57 2.2.1 哈尔函数是如何定义的？ 57 2.2.2 沃尔什函数是如何定义的？ 57 B2.4 用拉德马赫函数定义的沃尔什函数 58 2.2.3 如何能用哈尔或沃尔什函数来生成图像基？ 58 2.2.4 实际中如何用哈尔或沃尔什函数构建图像变换矩阵？ 58 2.2.5 哈尔变换的基元图像看起来是什么样的？ 61 2.2.6 可以定义元素仅为+1 或.1 的正交矩阵吗？ 65 B2.5 对沃尔什函数的排列方式 65 2.2.7 哈达玛/沃尔什变换的基图像看起来是什么样的？ 67 2.2.8 沃尔什和哈尔变换的优点和缺点各是什么？ 69 2.2.9 什么是哈尔小波？ 70 2.3 离散傅里叶变换 71 2.3.1 傅里叶变换的离散形式（DFT ）是怎样的？ 71 B2.6 离散傅里叶反变换是什么样的？ 72 2.3.2 如何能将傅里叶变换写成矩阵形式？ 72 2.3.3 用于DFT 的矩阵U是酉矩阵吗？ 74 2.3.4 DFT 用来扩展图像的基元图像是什么样的？ 76 2.3.5 为什么离散傅里叶变换比其他变换得到了更广泛的应用？ 78 2.3.6 什么是卷积定理？ 79 B2.7 如果一个函数是两个其他函数的卷积，它的DFT 与另两个函数的DFT 是什么关系？ 79 2.3.7 如何显示一幅图像的离散傅里叶变换？ 83 2.3.8 当图像旋转后其离散傅里叶变换将会怎么样？ 84 2.3.9 当图像平移后其离散傅里叶变换将会怎么样？ 85 2.3.10 图像的平均值与其DFT 有什么联系？ 88 2.3.11 一幅图像放缩后其DFT 会如何变化？ 89 B2.8 什么是快速傅里叶变换？ 92 2.3.12 DFT 有哪些优点和缺点？ 93 2.3.13 可以有实值的DFT 吗？ 94 2.3.14 可以有纯虚部的DFT 吗？ 96 2.3.15 一幅图像可以有纯实部或纯虚部值的DFT 吗？ 101 2.4 偶对称离散余弦变换（EDCT） 101 2.4.1 什么是偶对称离散余弦变换？ 101 B2.9 逆1-D 偶离散余弦变换的推导 106 2.4.2 2-D 时的逆偶余弦变换是怎样的？ 107 2.4.3 用偶余弦变换扩展一幅图像时的基图像是怎样的？ 107 2.5 奇对称离散余弦变换（ODCT） 109 2.5.1 什么是奇对称离散余弦变换？ 109 B2.10 推导1-D 逆奇离散余弦变换 112 2.5.2 2-D 时的逆奇余弦变换是怎样的？ 113 2.5.3 用奇余弦变换扩展一幅图像时的基图像是怎样的？ 113 2.6 偶反对称离散正弦变换（EDST） 115 2.6.1 什么是偶反对称离散正弦变换？ 115 B2.11 逆1-D 偶离散正弦变换的推导 118 2.6.2 2-D 时的逆偶正弦变换是怎样的？ 119 2.6.3 用偶正弦变换扩展一幅图像时的基图像是怎样的？ 119 2.6.4 如果在计算图像的EDST 前没有消除其均值会发生什么情况？ 121 2.7 奇反对称离散正弦变换（ODST） 122 2.7.1 什么是奇反对称离散正弦变换？ 122 B2.12 推导1-D 逆奇离散正弦变换 125 2.7.2 2-D 时的逆奇正弦变换是怎样的？ 126 2.7.3 用奇正弦变换扩展一幅图像时的基图像是怎样的？ 126 2.7.4 本章要点 128 第3章 图像的统计描述 130 3.0.1 本章概况 130 3.0.2 为什么需要对图像的统计描述？ 130 3.1 随机场 130 3.1.1 什么是一个随机场？ 130 3.1.2 什么是一个随机变量？ 130 3.1.3 什么是一个随机试验？ 131 3.1.4 如何用计算机做一个随机试验？ 131 3.1.5 如何描述随机变量？ 131 3.1.6 一个事件的概率是多少？ 131 3.1.7 什么是一个随机变量的分布函数？ 132 3.1.8 什么是一个随机变量取一个特殊值的概率？ 133 3.1.9 什么是一个随机变量的概率密度函数？ 133 3.1.10 如何描述许多随机变量？ 134 3.1.11 n个随机变量互相之间有什么联系？ 135 3.1.12 如何定义一个随机场？ 138 3.1.13 如何能将在同一个随机场中的两个随机变量联系在一起？ 139 3.1.14 如何能将在两个不同随机场中的两个随机变量联系在一起？ 140 3.1.15 如果仅有系综图像中的一幅图像，可以计算期望值吗？ 142 3.1.16 何时一个随机场相对于均值均匀？ 142 3.1.17 何时一个随机场相对于自相关函数均匀？ 142 3.1.18 如何计算一个随机场的空间统计？ 143 3.1.19 实际中如何计算一幅图像随机场的空间自相关函数？ 143 3.1.20 什么时候一个随机场相对于均值遍历？ 144 3.1.21 什么时候一个随机场相对于自相关函数遍历？ 144 3.1.22 什么是遍历性的含义？ 145 B3.1 遍历性，模糊逻辑和概率理论 146 3.1.23 如何可以构建一个基元图像的基，从而用最优的方式描述完整的图像集合？ 146 3.2 卡洛变换 147 3.2.1 什么是卡洛变换？ 147 3.2.2 为什么一个图像集合的自协方差矩阵对角化定义了描述集合中图像所需的基？ 147 3.2.3 如何变换一幅图像以使其自协方差矩阵成为对角的？ 149 3.2.4 如果系综相对于自相关是平稳的，一组图像的系综自相关矩阵的形式是怎么样的？ 154 3.2.5 如何根据一幅图像的矢量表达，从1-D 自相关函数得到其2-D 自相关矩阵？ 155 3.2.6 如何能变换图像使其自相关矩阵成为对角的？ 157 3.2.7 实际中如何计算一幅图像的卡洛变换？ 158 3.2.8 如何计算系综图像的卡洛（K-L）变换? 158 3.2.9 遍历性假设切合实际吗？ 158 B3.2 当一幅图像被表示成一个矢量时，如何计算该图像的空间自相关矩阵？ 159 3.2.10 期望变换后图像的均值真正为0 吗？ 162 3.2.11 如何能用一幅图像的卡洛变换来近似该图像？ 162 3.2.12 将一幅图像的卡洛展开截断而近似该图像的误差是什么？ 163 3.2.13 用卡洛变换展开一幅图像的基图像是什么样的？ 163 B3.3 使用卡洛变换近似一幅图像的误差是多少？ 167 3.3 独立分量分析 173 3.3.1 什么是独立分量分析（ICA）? 173 3.3.2 什么是鸡尾酒会问题？ 174 3.3.3 如何解鸡尾酒会问题？ 174 3.3.4 中心极限定理说些什么？ 174 3.3.5 当讨论鸡尾酒会问题时说“x1(t)的采样比s1(t)或s2(t)的采样更趋向于高斯分布”是什么含义？是谈论x1(t)的时间采样还是谈论在给定时间x1(t)的所有可能版本？ 174 3.3.6 如何测量非高斯性？ 177 3.3.7 如何计算一个随机变量的矩？ 178 3.3.8 峰度是如何定义的？ 178 3.3.9 负熵是如何定义的？ 180 3.3.10 熵是如何定义的？ 180 B3.4 在所有方差相同的概率密度函数中，高斯函数具有最大的熵 182 3.3.11 如何计算负熵？ 182 B3.5 用矩对负熵的近似推导 186 B3.6 用非二次函数近似负熵 187 B3.7 选择非二次函数以近似负熵 190 3.3.12 如何使用中心极限定理来解鸡尾酒会问题？ 194 3.3.13 ICA 如何用于图像处理？ 194 3.3.14 如何搜索独立分量？ 195 3.3.15 如何白化数据？ 196 3.3.16 如何从白化数据中选取独立分量？ 196 B3.8 拉格朗日乘数法如何工作？ 197 B3.9 如何选择一个能最大化负熵的方向？ 198 3.3.17 实际中如何在图像处理中进行ICA? 202 3.3.18 如何将ICA 用于信号处理？ 208 3.3.19 什么是独立分量分析的主要特点？ 213 3.3.20 将ICA 应用于图像处理和信号处理有什么不同？ 213 3.3.21 本章要点 213 第4章 图像增强 216 4.0.1 什么是图像增强？ 216 4.0.2 如何能增强一幅图像？ 216 4.0.3 什么是线性滤波器？ 216 4.1 线性滤波器理论基础 216 4.1.1 如何定义一个2-D 滤波器？ 216 4.1.2 频率响应函数和滤波器的单位采样响应是如何联系的？ 217 4.1.3 为什么关心在实域中的滤波器函数？ 217 4.1.4 h(k, l)需要满足什么条件才能用作卷积滤波器？ 217 B4.1 2-D 理想低通滤波器的单位采样响应是什么样的？ 218 4.1.5 1-D 和2-D 理想低通滤波器之间有什么联系？ 221 4.1.6 如何可在实域中实现无穷延伸的滤波器？ 222 B4.2 z-变换 222 4.1.7 可以为了方便而在实域中直接定义一个滤波器吗？ 227 4.1.8 可以在实域中定义一个滤波器，但在频域中没有旁瓣吗？ 228 4.2 消减高频噪声 228 4.2.1 一幅图像中会有什么种类的噪声？ 228 4.2.2 什么是脉冲噪声？ 228 4.2.3 什么是高斯噪声？ 229 4.2.4 什么是加性噪声？ 229 4.2.5 什么是乘性噪声？ 229 4.2.6 什么是齐次噪声？ 229 4.2.7 什么是零均值噪声？ 229 4.2.8 什么是有偏噪声？ 229 4.2.9 什么是独立噪声？ 229 4.2.10 什么是不相关噪声？ 230 4.2.11 什么是白噪声？ 230 4.2.12 零均值不相关噪声与白噪声间有什么联系？ 230 4.2.13 什么是iid 噪声？ 231 4.2.14 可能有不是独立同分布的白噪声吗？ 232 B4.3 一个随机变量的函数的概率密度函数 235 4.2.15 为什么噪声常与高频有关？ 238 4.2.16 如何对待乘性噪声？ 239 B4.4 德尔塔函数的傅里叶变换 239 B4.5 维纳-辛钦定理 239 4.2.17 对高斯噪声的假设在图像中合理吗？ 240 4.2.18 如何消除散粒噪声？ 240 4.2.19 什么是排序滤波器？ 240 4.2.20 什么是中值滤波器？ 240 4.2.21 什么是最频值滤波？ 241 4.2.22 如何减小高斯噪声？ 241 4.2.23 可以像加权平均滤波器那样对中值滤波器和最频值滤波器加权吗？ 246 4.2.24 可以使用第2 章中的线性方法来对图像滤波吗？ 247 4.2.25 如何处理图像中的混合噪声？ 248 4.2.26 能在平滑图像时避免模糊它吗？ 248 4.2.27 什么是边缘自适应平滑？ 249 B4.6 有效计算局部方差 250 4.2.28 均移算法是如何工作的？ 250 4.2.29 什么是非各向同性扩散？ 252 B4.7 尺度空间和热力方程 252 B4.8 梯度，散度和拉普拉斯 253 B4.9 对一个积分相对于一个参数求导 255 B4.10 从热力学方程到非各向同性扩散算法 255 4.2.30 实际中如何实现非各向同性扩散？ 256 4.3 消减低频干扰 257 4.3.1 什么时候会产生低频干扰？ 257 4.3.2 变化的照明在高频也有体现吗？ 257 4.3.3 还有哪些其他情况需要减少低频？ 258 4.3.4 理想高通滤波器是什么样的？ 258 4.3.5 如何用非线性滤波器来增强图像中的小细节？ 262 4.3.6 什么是非锐化掩膜？ 262 4.3.7 如何局部地使用非锐化掩膜算法？ 263 4.3.8 局部自适应非锐化掩膜是如何工作的？ 264 4.3.9 视网膜皮层理论算法是如何工作的？ 265 B4.11 用视网膜皮层理论算法对哪些灰度值拉伸的最多？ 266 4.3.10 如何增强受到变化照明影响的图像？ 267 4.3.11 什么是同态滤波？ 267 4.3.12 什么是光度立体视觉？ 268 4.3.13 平场校正是什么意思？ 268 4.3.14 平场校正是如何进行的？ 268 4.4 直方图操作 269 4.4.1 什么是一幅图像的直方图？ 269 4.4.2 什么时候需要改变图像的直方图？ 269 4.4.3 如何改变一幅图像的直方图？ 269 4.4.4 什么是直方图操作？ 270 4.4.5 什么会影响一幅图像的语义信息内容？ 270 4.4.6 如何能执行直方图操作并同时保留图像的信息内容？ 270 4.4.7 什么是直方图均衡化？ 271 4.4.8 为什么直方图均衡化程序一般并不产生具有平坦直方图的图像？ 271 4.4.9 实际中如何进行直方图均衡化？ 271 4.4.10 可能得到具有完全平坦直方图的图像吗？ 273 4.4.11 如果不希望图像具有平坦的直方图应如何做？ 273 4.4.12 实际中如何进行直方图双曲化？ 273 4.4.13 如何结合随机加法进行直方图双曲化？ 274 4.4.14 为什么在直方图均衡化外还需要其他处理？ 275 4.4.15 如果图像具有不均匀的对比度怎么办？ 275 4.4.16 可以在增加纯粹亮度过渡区的对比度时避免损坏平坦结构吗？ 276 4.4.17 如何能通过仅拉伸纯粹亮度过渡区的灰度值来增强一幅图像？ 277 4.4.18 实际中如何执行成对的图像增强？ 278 4.5 通用去模糊算法 280 4.5.1 最频值滤波如何帮助去图像模糊？ 281 4.5.2 可以在最频值滤波器中使用边缘自适应窗吗？ 282 4.5.3 如何可使用均移作为通用的去模糊算法？ 283 4.5.4 什么是滑降对比度增强？ 283 4.5.5 实际中如何进行滑降对比度增强？ 284 4.5.6 本章要点 287 第5章 图像恢复 290 5.0.1 什么是图像恢复？ 290 5.0.2 为什么图像需要恢复？ 290 5.0.3 什么是图像配准？ 290 5.0.4 图像恢复是如何进行的？ 290 5.0.5 图像增强和图像恢复的区别是什么？ 290 5.1 齐次线性图像恢复：逆滤波 290 5.1.1 如何对齐次线性图像退化建模？ 290 5.1.2 图像恢复问题可如何解决？ 291 5.1.3 如何可以获得退化过程的频率响应函数H.(u, v)的信息？ 291 5.1.4 如果已知退化过程的频率响应函数，解决图像恢复的问题是否很容易？ 298 5.1.5 在频率响应函数为零处，频率会发生什么情况？ 299 5.1.6 频率响应函数和图像的零点总相同吗？ 299 5.1.7 如何避免噪声的放大？ 299 5.1.8 实际中如何使用逆滤波？ 301 5.1.9 可以定义一个自动考虑模糊图像中噪声的滤波器吗？ 306 5.2 齐次线性图像恢复：维纳滤波 307 5.2.1 如何能将图像恢复问题描述成一个最小均方误差估计问题？ 307 5.2.2 图像恢复问题有线性最小均方解吗？ 307 5.2.3 什么是图像恢复问题的线性最小均方误差解？ 308 B5.1 最小均方误差解 308 B5.2 从图像相关函数的傅里叶变换到它们的频谱密度 313 B5.3 维纳滤波器的推导 313 5.2.4 维纳滤波和逆滤波之间有什么联系？ 314 5.2.5 如何确定噪声场的频谱密度？ 315 5.2.6 如果不知道未知图像的统计特性，还有可能使用维纳滤波器吗？ 315 5.2.7 实际中如何使用维纳滤波？ 316 5.3 齐次线性图像恢复：约束矩阵求逆 319 5.3.1 如果假设退化过程是线性的，为什么要使用卷积定理而不通过解线性方程组来反演其效果？ 319 5.3.2 式（5.146 ）看起来非常直观，为什么还需要考虑其他方法？ 320 5.3.3 有可以对矩阵H求逆的方法吗？ 320 5.3.4 什么时候矩阵块轮换？ 321 5.3.5 什么时候矩阵轮换？ 321 5.3.6 为什么块轮换矩阵可以方便地求逆？ 321 5.3.7 什么是一个轮换矩阵的本征值和本征矢量？ 321 5.3.8 有关一个矩阵本征值和本征矢量的知识如何帮助对矩阵的求逆？ 322 5.3.9 如何确定描述线性退化过程的矩阵H是块轮换的？ 326 5.3.10 如何对角化一个块轮换矩阵？ 327 B5.4 式（5.189）的证明 327 B5.5 矩阵H的转置是怎么样的？ 328 5.3.11 如何克服矩阵求逆对噪声的极度敏感性？ 334 5.3.12 如何将约束结合进矩阵的求逆？ 335 B5.6 约束矩阵求逆滤波器的推导 338 5.3.13 维纳滤波器和约束矩阵求逆滤波器有什么联系？ 339 5.3.14 实际中如何使用约束矩阵求逆？ 341 5.4 非齐次线性图像恢复：旋转变换 344 5.4.1 如何对线性但非齐次的图像退化建模？ 344 5.4.2 当退化矩阵不是轮换矩阵时如何使用约束矩阵求逆？ 351 5.4.3 如果矩阵H非常大不能求逆怎么办？ 353 B5.7 用于对大线性方程组求逆的雅克比法 354 B5.8 用于对大线性方程组求逆的高斯-赛德尔法 356 5.4.4 在例5.41、例5.43、例5.44 和例5.45 中构建的矩阵H满足使用高斯-赛德尔法或雅克比法的条件吗？ 356 5.4.5 如果矩阵H不满足高斯-赛德尔法所需的条件会怎么样？ 357 5.4.6 实际中如何使用梯度下降算法？ 358 5.4.7 如果不知道矩阵H怎么办？ 359 5.5 非线性图像恢复：MAP 估计 359 5.5.1 MAP 估计是什么意思？ 359 5.5.2 如何将图像恢复问题公式化为一个MAP 估计问题？ 360 5.5.3 给定退化模型和退化图像如何选择最可能的恢复像素值的组合？ 360 B5.9 概率：先验，后验，条件 360 5.5.4 代价函数的最小值是唯一的吗？ 361 5.5.5 如何从能最小化代价函数的所有可能解中选出一个来？ 361 5.5.6 可以对一个组态x结合后验和先验概率吗？ 362 B5.10 巴斯维尔定理 364 5.5.7 一般如何模型化需要最小化以恢复图像的代价函数？ 366 5.5.8 当模型化联合概率密度函数时，温度参数并不改变概率取最大值的组态，那为什么要使用它？ 367 5.5.9 温度参数是如何在解空间中允许聚焦或离焦的？ 367 5.5.10 如何模型化组态的先验概率？ 368 5.5.11 如果图像具有真正的不连续性会发生什么情况？ 368 5.5.12 如何最小化代价函数？ 369 5.5.13 如何从前一个解构建一个可能的新解？ 369 5.5.14 如何知道何时停止迭代？ 371 5.5.15 在模拟退火中如何减小温度？ 371 5.5.16 实际中如何利用重要中心采样器进行模拟退火？ 371 5.5.17 实际中如何利用吉伯斯采样器进行模拟退火？ 372 B5.11 如何根据给定的概率密度函数取出一个随机数？ 373 5.5.18 为什么模拟退火很慢？ 375 5.5.19 如何能加快模拟退火？ 375 5.5.20 如何能粗化组态空间？ 376 5.6 几何图像恢复 376 5.6.1 如何会产生几何失真？ 376 5.6.2 为什么镜头会导致失真？ 377 5.6.3 如何恢复一幅几何失真的图像？ 377 5.6.4 如何执行空间变换？ 377 5.6.5 如何模型化镜头失真？ 377 5.6.6 如何模型化非均匀失真？ 379 5.6.7 如何确定空间变换模型的参数？ 379 5.6.8 为什么需要灰度插值？ 379 B5.12 检测线的哈夫变换 382 5.6.9 本章要点 386 第6章 图像分割和边缘检测 388 6.0.1 本章概况 388 6.0.2 图像分割和边缘检测的准确目的是什么？ 388 6.1 图像分割 388 6.1.1 如何将一幅图像分成均匀的区域？ 388 6.1.2 “标记”一幅图像是什么含义？ 388 6.1.3 如果直方图中的谷没有被很明确地定义应怎么办？ 389 6.1.4 如何最小化误分像素的数量？ 389 6.1.5 如何选择最小误差阈值？ 390 6.1.6 什么是目标和背景像素正态分布时的最小误差阈值？ 393 6.1.7 什么是最小误差阈值方程两个解的含义？ 394 6.1.8 如何估计代表目标和背景的高斯概率密度函数的参数？ 395 6.1.9 最小误差阈值化方法的缺点是什么？ 398 6.1.10 有能不依赖于目标和背景像素分布模型的方法吗？ 398 B6.1 大津方法的推导 399 6.1.11 大津方法有什么缺点吗？ 401 6.1.12 如何能对在照明变化的场合下获得的图像取阈值？ 402 6.1.13 如果根据lnf(x, y)的直方图来对图像取阈值，是根据成像表面的反射性质来阈值化吗？ 402 B6.2 两个随机变量和的概率密度函数 402 6.1.14 如何解决照明变化情况下直接阈值化算法会失败的问题？ 403 6.1.15 如果直方图只有一个峰应怎么办？ 404 6.1.16 灰度阈值化方法有什么缺点吗？ 405 6.1.17 如何分割包含不均匀但感觉均匀区域的图像？ 406 6.1.18 可以通过考虑像素的空间接近度来改进直方图化方法吗？ 408 6.1.19 有考虑像素空间接近度的分割方法吗？ 408 6.1.20 如何选择种子像素？ 408 6.1.21 分裂和合并法如何工作？ 409 6.1.22 什么是形态学图像重建？ 409 6.1.23 如何用形态学图像重建确定水线算法所需的种子？ 411 6.1.24 如何计算梯度幅度图？ 411 6.1.25 在用g对f的形态学重建中，为生成模板g而从f中减去的数起什么作用？ 412 6.1.26 结构元素的形状和尺寸在用g对f的形态学重建中起什么作用？ 413 6.1.27 如何使用梯度幅度图像以帮助用水线算法分割图像？ 419 6.1.28 在水线算法中使用梯度幅度图像有什么缺点吗？ 419 6.1.29 可以用滤波来分割图像吗？ 424 6.1.30 如何使用均移算法去分割图像？ 424 6.1.31 什么是一个图？ 425 6.1.32 能用一个图表示一幅图像吗？ 425 6.1.33 如何借助一幅图像的图表达来分割它？ 425 6.1.34 什么是归一化割算法？ 426 B6.3 归一化割算法作为一个本征值问题 426 B6.4 如何最小化瑞利商？ 433 6.1.35 实际中如何使用归一化图割算法？ 435 6.1.36 与考虑像素间的相似性相对，可以通过考虑区域间的不相似性来分割图像吗？ 436 6.2 边缘检测 436 6.2.1 如何测量相邻像素间的不相似性？ 436 6.2.2 什么是最小可选的窗？ 437 6.2.3 当图像中有噪声时会怎么样？ 438 B6.5 如何选择用于边缘检测的3×3 模板的权重？ 439 6.2.4 参数K的最优值是什么？ 440 B6.6 索贝尔滤波器的推导 440 6.2.5 在通常情况下，如何确定一个像素是否为边缘像素呢？ 444 6.2.6 实际中如何执行线性边缘检测？ 445 6.2.7 索贝尔模板对所有图像都合用吗？ 448 6.2.8 如果由于图像中有很显著的噪声而需要一个较大的模板， 如何选择模板的权重？ 448 6.2.9 可以使用对边缘的最优滤波器以一种最优方式检测图像中的直线吗？ 450 6.2.10 什么是阶跃边缘和直线间的基本差别？ 450 B6.7 将一个随机噪声与一个滤波器卷积 454 B6.8 将一个有噪边缘信号与一个滤波器卷积后的信噪比计算 455 B6.9 良好局部性测度的推导 455 B6.10 虚假极值计数的推导 457 6.2.11 边缘检测能导致图像分割吗？ 458 6.2.12 什么是滞后边缘连接？ 458 6.2.13 滞后边缘连接能导致封闭的边缘轮廓吗？ 459 6.2.14 什么是拉普拉斯-高斯边缘检测法？ 460 6.2.15 有可能同时检测边缘和直线吗？ 461 6.3 相位一致性和单基因信号 461 6.3.1 什么是相位一致性？ 461 6.3.2 什么是1-D 数字信号的相位一致性？ 462 6.3.3 如何能借助相位一致性检测直线和边缘？ 462 6.3.4 为什么相位一致性与信号的局部能量最大值重合？ 462 6.3.5 如何测量相位一致性？ 463 6.3.6 能否简单地平均谐波分量的相位来测量相位一致性？ 463 6.3.7 实际中如何测量相位一致性？ 465 6.3.8 如何测量信号的局部能量？ 466 6.3.9 为什么需要与两个基信号卷积以得到局部信号在基信号上的投影？ 467 B6.11 连续傅里叶变换的一些性质 470 6.3.10 如果只需计算信号的局部能量，为什么不在实域的局部窗口中用帕赛瓦尔定理来计算？ 477 6.3.11 如何决定使用哪个滤波器计算局部能量？ 478 6.3.12 实际中如何计算一个1-D 信号的局部能量？ 481 6.3.13 如何能判断局部能量的最大值对应一个对称或反对称的特征？ 481 6.3.14 如何计算2-D 时的相位一致性和局部能量？ 487 6.3.15 什么是解析信号？ 487 6.3.16 如何推广希尔伯特变换到2-D？ 487 6.3.17 如何计算一幅图像的里斯变换？ 487 6.3.18 如何使用单基因信号？ 488 6.3.19 如何选择要使用的偶滤波器？ 488 6.3.20 本章要点 493 第7章 多光谱图像处理 495 7.0.1 什么是多光谱图像？ 495 7.0.2 多光谱图像有哪些特殊的问题？ 495 7.0.3 本章概述 496 7.1 多光谱图像处理 496 7.1.1 为什么会希望用其他带来替换多光谱图像的带？ 496 7.1.2 一般如何从多光谱图像构建一幅灰度图像？ 496 7.1.3 如何从一幅包含最大量图像信息的多光谱图像构建单个带？ 496 7.1.4 什么是主分量分析？ 497 B7.1 如何测量信息？ 497 7.1.5 实际中如何进行主分量分析？ 498 7.1.6 使用一幅图像的主分量而不是原始带的优点是什么？ 499 7.1.7 使用一幅图像的主分量而不是原始带的缺点是什么？ 499 7.1.8 如果对其他分量不感兴趣，有可能仅计算出一幅多光谱图像的第1 个主分量吗？ 504 B7.2 用于估计一个矩阵的最大本征值的功率法 504 7.1.9 什么是光谱恒常性问题？ 506 7.1.10 什么影响一个像素的光谱标记？ 506 7.1.11 什么是反射函数？ 506 7.1.12 成像几何影响一个像素的光谱标记吗？ 506 7.1.13 成像几何如何影响一个像素所接收的光能量？ 506 7.1.14 如何对朗伯表面的成像过程建模？ 507 7.1.15 如何能消除一个像素的光谱对成像几何的依赖性？ 507 7.1.16 如何能消除一个像素的光谱对照明源光谱的依赖性？ 507 7.1.17 如果有不止一个照明源会发生什么情况？ 508 7.1.18 如何能消除一个像素的光谱标记对成像几何和照明光谱的依赖性？ 508 7.1.19 如果成像表面不是由相同材料构成时怎么办？ 509 7.1.20 什么是光谱分解问题？ 509 7.1.21 如何解决线性光谱分解问题？ 510 7.1.22 可以对纯材料使用光谱库吗？ 510 7.1.23 当已知纯分量的光谱时如何解线性光谱分解问题？ 510 7.1.24 有可能不计算矩阵Q的逆吗？ 513 7.1.25 如果库光谱是在与混合光谱不同的波长进行的采样会发生什么问题？ 513 7.1.26 如果不知道在混合物质中有哪些纯物质可能存在会发生什么问题？ 514 7.1.27 如果不知道纯材料的光谱如何解线性光谱分解问题？ 515 7.2 彩色视觉的物理学和心理物理学 518 7.2.1 什么是彩色？ 518 7.2.2 从工程的观点看彩色有什么感兴趣的地方？ 518 7.2.3 哪些因素影响从一个暗物体感知到的彩色？ 519 7.2.4 什么导致日光的变化？ 520 7.2.5 如何能模型化日光的变化？ 520 B7.3 标准光源 522 7.2.6 什么是天然材料的观测变化？ 523 7.2.7 一旦光线到达传感器会发生什么情况？ 529 7.2.8 一个传感器有可能对不同的材料产生相同的记录吗？ 530 7.2.9 人类视觉系统是如何实现彩色恒常性的？ 531 7.2.10 彩色视觉的三基色理论讲了什么？ 531 7.2.11 用什么来定义一个彩色系统？ 531 7.2.12 三刺激值是如何确定的？ 531 7.2.13 所有的单色参考刺激都可以通过简单调节基色光的强度来匹配吗？ 532 7.2.14 所有人都需要相同强度的基色光以匹配同样的单色参考刺激吗？ 533 7.2.15 谁是具有正常彩色视觉的人？ 533 7.2.16 什么是最常使用的彩色系统？ 533 7.2.17 什么是CIE-RGB 彩色系统？ 533 7.2.18 什么是XYZ 彩色系统？ 534 7.2.19 如何在3-D 空间中表达彩色？ 534 7.2.20 如何在2-D 空间中表达彩色？ 534 7.2.21 什么是色度图？ 535 B7.4 一些3-D 几何中有用的定理 536 7.2.22 CIE-RGB 彩色系统中的色度图是什么样的？ 538 7.2.23 人的大脑是如何感知彩色强度的？ 539 7.2.24 在CIE-RGB 彩色系统中是如何定义零发光线的呢？ 539 7.2.25 XYZ 彩色系统是如何定义的？ 540 7.2.26 XYZ 彩色系统中的色度图是什么样的？ 542 7.2.27 实际中可能用虚的基色生成一个彩色系统吗？ 542 7.2.28 如何模型化一个特定人观察彩色的方式？ 542 7.2.29 如果不同的观察者需要不同强度的基色光以看到白色，如何在不同观察者间校正彩色？ 543 7.2.30 如何使用参考白色？ 543 7.2.31 sRGB 彩色系统是如何定义的？ 544 7.2.32 如果将一个彩色的所有三刺激值都翻倍它会变化吗？ 545 7.2.33 用彩色系统的语言对一个彩色的描述与用日常语言的描述有什么联系？ 545 7.2.34 如何比较彩色？ 545 7.2.35 什么是一个测度？ 545 7.2.36 能用欧氏测度来测量两个彩色的差别吗？ 546 7.2.37 哪些是感知均匀的彩色空间？ 546 7.2.38 Luv彩色空间是如何定义的？ 546 7.2.39 Lab彩色空间是如何定义的？ 547 7.2.40 如何选择(Xn, Yn, Zn)的值？ 547 7.2.41 如何从Luv的值计算RGB 的值？ 548 7.2.42 如何从Lab的值计算RGB 的值？ 548 7.2.43 如何测量感知的饱和度？ 549 7.2.44 如何测量饱和度感知的差别？ 549 7.2.45 如何测量感知的色调？ 549 7.2.46 色调角是如何定义的？ 549 7.2.47 如何测量色调感知的差别？ 550 7.2.48 什么影响人感知彩色的方式？ 551 7.2.49 彩色的时间上下文是什么意思？ 551 7.2.50 彩色的空间上下文是什么意思？ 551 7.2.51 为什么当谈论空间频率时与距离有关系？ 552 7.2.52 如何解释对彩色感知的空间依赖性？ 552 7.3 实用彩色图像处理 553 7.3.1 对人类彩色视觉的研究如何影响进行图像处理的方式？ 553 7.3.2 感知均匀彩色空间实际中有多感知均匀？ 553 7.3.3 应如何将图像的RGB 值转换到Luv或Lab彩色空间中？ 553 7.3.4 在图像处理应用中如何测量色调和饱和度？ 557 7.3.5 如何能在图像处理中模仿彩色感知的空间依赖性？ 561 7.3.6 同色异谱现象与图像处理有什么联系？ 563 7.3.7 如何解决一个工业监视应用中的同色异谱问题？ 564 7.3.8 什么是蒙特卡洛方法？ 565 7.3.9 如何从多光谱图像中消除噪声？ 566 7.3.10 如何对矢量排序？ 566 7.3.11 如何处理多光谱图像中的混合噪声？ 567 7.3.12 如何增强一幅彩色图像？ 568 7.3.13 如何恢复多光谱图像？ 572 7.3.14 如何压缩彩色图像？ 572 7.3.15 如何分割多光谱图像？ 572 7.3.16 实际中如何使用k-均值聚类方法？ 573 7.3.17 如何提取多光谱图像的边缘？ 574 7.3.18 本章要点 574 附录A 算法列表 576 附录B 参考文献注解 578 附录C 参考文献 580 附录D 索引 584

电能变换与控制_巫付专，沈虹主编_电子工业出版社

电能变换与控制_巫付专,沈虹主编，电子工业出版社2014年出版的书，有书签目录的。 第1章 电能信号的检测与处理 1.1 信号分析与处理基础 1.1.1 周期信号的傅里叶级数表示 1.1.2 离散信号 1.1.3 快速傅里叶变换 1.2 信号检测方法 1.2.1 均方根法 1.2.2 傅里叶法 1.2.3 瞬时无功功率理论 1.2.4 其他检测方法 1.3 信号滤波器 1.3.1 滤波器概述 1.3.2 模拟滤波器 1.3.3 数字滤波器 1.4 信号检测调理电路设计 1.4.1 检测元件及电路 1.4.2 调理电路设计 1.5 锁相环技术 1.5.1 锁相环基本原理 1.5.2 锁相环的捕捉、跟踪过程与倍频 思考与练习 第2章 PWM控制原理与方法 2.1 正弦脉宽调制SPWM 2.1.1 SPWM原理 2.1.2 产生SPWM的算法 2.1.3 SPWM的仿真及DSP程序实现 2.2 空间矢量SVPWM 2.2.1 三相空间矢量电压的分布 2.2.2 空间电压矢量的合成 2.2.3 SVPWM的仿真及DSP程序实现 2.3 滞环控制产生PWM的控制方法 2.3.1 滞环比较控制方式的原理 2.3.2 滞环比较控制分析 2.3.3 滞环控制仿真与DSP程序的实现 2.4 三角波比较法 2.4.1 PI调节 2.4.2 三角波比较法的原理 2.4.3 三角波比较控制仿真及DSP程序的实现 2.5 PWM波其他控制方法简介 2.5.1 定频电流滞环最优矢量控制 2.5.2 不定频电流滞环最优矢量控制 思考与练习 第3章 DCDC变换原理与控制 3.1 降压斩波变换电路 3.1.1 降压斩波变换电路组成及工作原理 3.1.2 降压斩波变换电路稳态分析 3.1.3 降压斩波变换电路状态空间平均模型 3.1.3 降压斩波变换电路仿真 3.2 升压斩波变换电路 3.2.1 升压斩波变换电路组成及工作原理 3.2.2 升压斩波变换电路稳态分析 3.2.3 升压斩波变换电路状态空间平均模型 3.2.4 升压斩波变换电路系统仿真 3.3 带变压器隔离的DCDC变换电路 3.3.1 单端DCDC变换电路原理及设计 3.3.2 双端推挽式（PUSHPULL）DCDC变换电路 3.3.3 半桥式DCDC变换电路原理及设计 3.3.4 全桥DCDC变换电路原理 3.4 其他形式的DCDC变换电路 3.4.1 直接半桥DCDC变换电路 3.4.2 直接全桥DCDC变换电路 3.4.3 多相、多重DCDC变换电路简介 思考与练习 第4章 AC/DC、DC/AC变换原理与控制 4.1 PWM变流器的工作原理 4.1.1 PWM变流器的分类 4.1.2 电压型PWM变流器数学模型 4.2 AC/DC变换 4.2.1 AC/DC变换的控制策略 4.2.2 基于SVPWM的控制方法分析 4.2.3 AC/DC变换仿真与DSP程序的实现 4.3 DC/AC变换 4.3.1 DC/AC变换的原理 4.3.2 DC/AC变换的控制策略 4.3.3 DC/AC变换仿真与DSP程序的实现 思考与练习（四） 第5章 电能变换的其他应用 5.1 静止无功发生器 5.1.1 静止无功发生器的工作原理及主电路设计 5.1.2 静止无功发生器的检测算法 5.1.3 静止无功发生器的控制策略 5.1.4 静止无功发生器仿真与DSP程序的实现 5.2 有源电力滤波器 5.2.1 有源电力滤波器的工作原理及主电路设计 5.2.2 有源电力滤波器的检测算法 5.2.3 有源电力滤波器的控制策略 5.2.4 有源电力滤波器仿真及DSP程序实现的流程 5.3 动态电压恢复器 5.3.1 动态电压恢复器工作原理及分类 5.3.2 动态电压恢复器检测算法 5.3.3 动态电压恢复器的补偿策略 5.3.4 动态电压恢复器主要参数的确定 5.3.5 动态电压恢复器仿真与DSP程序实现的流程 5.4 有源功率因数校正器 5.4.1 有源功率因数校正的基本原理 5.4.2 有源功率因数校正器的控制策略 5.4.3 有源功率因数校正器的实例分析与仿真 5.4.4 UC3854简介 5.5 统一电能质量调节器(UPQC) 5.5.1 统一电能质量调节器的工作原理 5.5.2 统一电能质量调节器检测算法及检测硬件电路设计 5.5.3 统一电能质量调节器的控制策略 5.5.4 统一电能质量调节器的主电路设计 5.5.5 统一电能质量调节器的软件设计 思考与练习 第6章 磁性元件的设计 6.1 磁性元件概述 6.1.1 磁性元件 6.1.2 磁性元件的发展趋势 6.2 磁性材料及磁芯结构 6.2.1 磁性材料的基本特性 6.2.2 磁性材料的分类 6.2.3 磁芯材料的选择 6.2.4 磁芯结构 6.

科学计算导论（第2版）.[英]Michael T.Heath(带详细书签).pdf

本书全面地介绍了科学计算中解各种主要问题的数值方法，包括线性和非线性方程、最小二乘法、特征值、最优化、插值、积分、常微分方程和偏微分方程、快速傅里叶变换和随机数生成。本书的特点是： 以使用算法的读者为对象，重点讲授算法背后的思想和原理，而不是算法的详细分析。 强调敏感性和病态性等概念，对同一问题的不同算法进行比较和评价，提高读者对算法的鉴赏能力。 对每类问题都专门介绍和讨论有关的数学软件，包括在Internet上可以获得的免费软件和有版权保护的商业软件平台，供读者选用。 丰富的例题和习题，书中包括160多道例题，500多道思考题，240多道练习题和200多道数值计算题。 本书可作为研究生“数值分析”课程的教材或参考书，对于需要解决计算问题的科技人员，本书具有很高的参考价值。 第1章 科学计算 1 1.1 引言 1 1.2 科学计算中的近似 3 1.3 计算机运算 13 1.4 数学软件 26 1.5 有关历史的注记及参考文献 31 第2章 线性方程组 41 2.1 线性方程组 41 2.2 解的存在性和惟一性 42 2.3 问题的敏感性和病态性 43 2.4 线性方程组的求解 53 2.5 特殊类型的线性方程组 72 2.6 线性方程组的迭代法 76 2.7 有关线性方程组的软件 76 2.8 有关历史的注记及参考文献 78 第3章 线性最小二乘 90 3.1 线性最小二乘问题 90 3.2 解的存在性和惟一性 93 3.3 问题的敏感性和病态性 97 3.4 问题的变形 100 3.5 正交化方法 104 3.6 奇异值分解 119 3.7 方法间的比较 124 3.8 有关线性最小二乘的软件 125 3.9 有关历史的注记及参考文献 126 第4章 特征值问题 136 4.1 特征值和特征向量 136 4.2 解的存在性和惟一性 138 4.3 问题的敏感性和条件数 144 4.4 问题的变形 146 4.5 特征值和特征向量的计算 150 4.6 广义特征值问题 174 4.7 奇异值分解的计算 175 4.8 有关特征值问题的软件 175 4.9 有关历史的注记及参考文献 177 第5章 非线性方程 187 5.1 非线性方程 187 5.2 解的存在性和惟一性 188 5.3 问题的敏感性和病态性 191 5.4 收敛速度和判停准则 192 5.5 一维非线性方程 193 5.6 非线性方程组 205 5.7 有关非线性方程组的软件 210 5.8 有关历史的注记及参考文献 212 第6章 优化问题 221 6.1 优化问题 221 6.2 最优解的存在性和惟一性 223 6.3 问题的敏感性和病态性 232 6.4 一维优化 233 6.5 无约束优化 239 6.6 非线性最小二乘 247 6.7 约束优化 250 6.8 有关优化的软件 256 6.9 有关历史的注记及参考文献 258 第7章 插值 269 7.1 插值 269 7.2 插值的存在性、惟一性和病态性 271 7.3 多项式插值 272 7.4 分段多项式插值 283 7.5 有关插值的软件 287 7.6 有关历史的注记及参考文献 289 第8章 数值积分和数值微分 294 8.1 积分 294 8.2 积分解的存在性、惟一性和问题的病态性 295 8.3 数值求积 296 8.4 其他积分问题 310 8.5 积分方程 313 8.6 数值微分 315 8.7 理查森外推法 318 8.8 有关积分和微分的软件 321 8.9 有关历史的注记及参考文献 322 第9章 常微分方程的初值问题 330 9.1 常微分方程 330 9.2 解的存在性、惟一性和问题的病态性 334 9.3 常微分方程数值解 336 9.4 有关常微分方程初值问题的软件 354 9.5 有关历史的注记及参考文献 355 第10章 常微分方程边值问题 363 10.1 边值问题 363 10.2 解的存在性、惟一性和问题的病态性 364 10.3 打靶法 367 10.4 有限差分法 370 10.5 配置法 371 10.6 伽辽金方法 374 10.7 特征值问题 378 10.8 有关常微分方程边值问题的软件 378 10.9 有关历史的注记及参考文献 379 第11章 偏微分方程 384 11.1 偏微分方程 384 11.2 时间相关问题 389 11.3 时间无关问题 395 11.4 稀疏线性方程组的直接法 398 11.5 线性方程组的迭代法 401 11.6 方法间的比较 412 11

计算复杂性：现代方法.[美]桑杰夫·阿罗拉（Sanjeev Arora）(带详细书签).pdf

复杂性理论是计算机科学的理论基础的核心。本书是普林斯顿大学Sanjeev Arora和Boaz Barak的力作，目前在princeton，yale等很多学校采用，我国复旦大学等重点教材也有采用。书中全面分析了复杂性理论的经典原理和现代主题，适合作为“非密码专业方向”的计算机、信息安全等相关专业的研究生教材。 第0章 记号约定 1 0.1 对象的字符串表示 1 0.2 判定问题/语言 2 0.3 大O记号 2 习题 3 第一部分 基本复杂性类 5 第1章 计算模型——为什么模型选择无关紧要 6 1.1 计算的建模：你真正需要了解的内容 6 1.2 图灵机 7 1.2.1 图灵机的表达能力 10 1.3 效率和运行时间 11 1.3.1 定义的健壮性 11 1.4 机器的位串表示和通用图灵机 14 1.4.1 通用图灵机 14 1.5 不可计算性简介 15 1.5.1 停机问题 16 1.5.2 哥德尔定理 17 1.6 类P 18 1.6.1 为什么模型选择无关紧要 19 1.6.2 P的哲学意义 19 1.6.3 P的争议和解决争议的一些努力 20 1.6.4 埃德蒙兹的引言 21 1.7 定理1.9的证明：O(TlogT)时间的通用模拟 21 本章学习内容 24 本章注记和历史 24 习题 26 第2章 NP和NP完全性 29 2.1 类NP 29 2.1.1 P和NP的关系 31 2.1.2 非确定型图灵机 31 2.2 归约和NP完全性 32 2.3 库克勒维定理：计算的局部性 34 2.3.1 布尔公式、合取范式和SAT问题 34 2.3.2 库克勒维定理 34 2.3.3 准备工作：布尔公式的表达能力 35 2.3.4 引理2.11的证明 35 2.3.5 将SAT归约到3SAT 38 2.3.6 深入理解库克勒维定理 38 2.4 归约网络 39 2.5 判定与搜索 42 2.6 coNP、EXP和NEXP 43 2.6.1 coNP 43 2.6.2 EXP和NEXP 44 2.7 深入理解P、NP及其他复杂性类 45 2.7.1 NP的哲学意义 45 2.7.2 NP与数学证明 45 2.7.3 如果P=NP会怎样 45 2.7.4 如果NP=coNP会怎样 46 2.7.5 NP和NP完全之间存在其他复杂性类吗 47 2.7.6 NP难的处理 47 2.7.7 更精细的时间复杂性 48 本章学习内容 48 本章注记和历史 48 习题 49 第3章 对角线方法 53 3.1 时间分层定理 53 3.2 非确定型时间分层定理 54 3.3 拉德纳尔定理:NP非完全问题的存在性 55 3.4 神喻机器和对角线方法的局限性 57 3.4.1 逻辑独立与相对 59 本章学习内容 59 本章注记和历史 59 习题 60 第4章 空间复杂性 61 4.1 空间受限计算的定义 61 4.1.1 格局图 62 4.1.2 一些空间复杂性类 63 4.1.3 空间分层定理 64 4.2 PSPACE完全性 64 4.2.1 塞维奇定理 67 4.2.2 PSPACE的本质：最佳博弈策略 67 4.3 NL完全性 68 4.3.1 基于证明的NL定义:仅能读一次的证明 70 4.3.2 NL=coNL 71 本章学习内容 72 本章注记和历史 73 习题 73 第5章 多项式分层和交错 75 5.1 类Σp2 75 5.2 多项式分层 76 5.2.1 多项式分层的性质 76 5.2.2 PH各层的完全问题 77 5.3 交错图灵机 78 5.3.1 无限次交错 79 5.4 时间与交错：SAT的时空平衡 79 5.5 用神喻图灵机定义多项式分层 80 本章学习内容 81 本章注记和历史 81 习题 82 第6章 布尔线路 83 6.1 布尔线路和P/poly 83 6.1.1 P/poly和P之间的关系 85 6.1.2 线路的可满足性和库克勒维定理的另一种证明 86 6.2 一致线路 87 6.2.1 对数空间一致线路族 87 6.3 纳言图灵机 88 6.4 P/poly和NP 88 6.5 线路下界 89 6.6 非一致分层定理 90 6.7 线路复杂性类的精细分层 91 6.7.1 类NC和类AC 92 6.7.2 P完全性 92 6.8 指数规模的线路 93 本章学习内容 93 本章注记和历史 94 习题 94 第7章 随机计算 96 7.1 概率型图灵机 97 7.2 概率型图灵机示例 98 7.2.1 寻找中位数 99 7.2.2 概率型素性测试 100 7.2.3 多项式恒等测试 101 7.2.4 二分图的完美匹配测试 102 7.3 单面错误和“零面”错误：RP、coRP、ZPP 103 7.4 定义的健壮性 103 7.4.1 准确度常数的作用：错率归约 104 7.4.2 期望运行时间与最坏运行时间 105 7.4.3 使用比均匀硬币投掷更具一般性的随机选择 106 7.5 BPP同其他复杂性类之间的关系 106 7.5.1 BPP⊆P/poly 107 7.5.2 BPP⊆PH 107 7.5.3 分层定理与完全问题 108 7.6 随机归约 109 7.7 空间受限的随机计算 109 本章学习内容 110 本章注记和历史 110 习题 111 第8章 交互式证明 113 8.1 交互式证明及其变形 113 8.1.1 准备工作：验证者和证明者均为确定型的交互式证明 113 8.1.2 类IP：概率型验证者 115 8.1.3 图不同构的交互式证明 116 8.2 公用随机源和类AM 118 8.2.1 私有随机源的模拟 119 8.2.2 集合下界协议 120 8.2.3 定理8.12的证明概要 123 8.2.4 GI能是NP完全的吗 123 8.3 IP=PSPACE 124 8.3.1 算术化 125 8.3.2 #SATD的交互式协议 125 8.3.3 TQBF的协议：定理8.19的证明 127 8.4 证明者的能力 128 8.5 多证明者交互式证明 129 8.6 程序检验 130 8.6.1 具有验证程序的语言 131 8.6.2 随机自归约与积和式 131 8.7 积和式的交互式证明 132 8.7.1 协议 133 本章学习内容 134 本章注记和历史 134 习题 135 第9章 密码学 137 9.1 完全保密及其局限性 138 9.2 计算安全、单向函数和伪随机数产生器 139 9.2.1 单向函数：定义和实例 141 9.2.2 用单向函数实现加密 142 9.2.3 伪随机数产生器 143 9.3 用单向置换构造伪随机数产生器 144 9.3.1 不可预测性蕴含伪随机性 144 9.3.2 引理9.10的证明：戈德赖希勒维定理 145 9.4 零知识 149 9.5 应用 151 9.5.1 伪随机函数及其应用 151 9.5.2 去随机化 153 9.5.3 电话投币和比特承诺 154 9.5.4 安全的多方计算 154 9.5.5 机器学习的下界 155 本章学习内容 155 本章注记和历史 155 习题 158 第10章 量子计算 161 10.1 量子怪相：双缝实验 162 10.2 量子叠加和量子位 163 10.2.1 EPR悖论 165 10.3 量子计算的定义和BQP 168 10.3.1 线性代数预备知识 168 10.3.2 量子寄存器及其状态向量 168 10.3.3 量子操作 169 10.3.4 量子操作实例 169 10.3.5 量子计算与BQP 171 10.3.6 量子线路 172 10.3.7 传统计算是量子计算的特例 173 10.3.8 通用操作 173 10.4 格罗弗搜索算法 174 10.5 西蒙算法 177 10.5.1 定理10.14的证明 177 10.6 肖尔算法:用量子计算机实现整数分解 178 10.6.1 ZM上的傅里叶变换 179 10.6.2 ZM上的量子傅里叶变换 180 10.6.3 肖尔的阶发现算法 181 10.6.4 因数分解归约为阶发现 184 10.6.5 实数的有理数近似 185 10.7 BQP和经典复杂性类 186 10.7.1 量子计算中类似于NP和AM的复杂性类 187 本章学习内容 187 本章注记和历史 188 习题 190 第11章 PCP定理和近似难度简介 192 11.1 动机：近似求解NP难的优化问题 193 11.2 用两种观点理解PCP定理 194 11.2.1 PCP定理与局部可验证明 194 11.2.2 PCP定理与近似难度 197 11.3 两种观点的等价性 197 11.3.1 定理11.5与定理11.9的等价性 198 11.3.2 重新审视PCP的两种理解 199 11.4 顶点覆盖问题和独立集问题的近似难度 200 11.5 NP⊆PCP(poly(n),1):由沃尔什哈达玛编码得到的PCP 202 11.5.1 线性测试与沃尔什哈达玛编码 202 11.5.2 定理11.19的证明 203 本章学习内容 206 本章注记和历史 206 习题 207 第二部分 具体计算模型的下界 209 第12章 判定树 210 12.1 判定树和判定树复杂性 210 12.2 证明复杂性 212 12.3 随机判定树 213 12.4 证明判定树下界的一些技术 214 12.4.1 随机复杂性的下界 214 12.4.2 敏感性 215 12.4.3 次数方法 216 本章学习内容 217 本章注记和历史 217 习题 218 第13章 通信复杂性 219 13.1 双方通信复杂性的定义 219 13.2 下界方法 220 13.2.1 诈集方法 220 13.2.2 铺砌方法 221 13.2.3 秩方法 222 13.2.4 差异方法 223 13.2.5 证明差异上界的一种技术 223 13.2.6 各种下界方法的比较 224 13.3 多方通信复杂性 225 13.4 其他通信复杂性模型概述 227 本章学习内容 228 本章注记和历史 228 习题 229 第14章 线路下界：复杂性理论的滑铁卢 232 14.1 AC0和哈斯塔德开关引理 232 14.1.1 哈斯塔德开关引理 233 14.1.2 开关引理的证明 234 14.2 带“计数器”的线路:ACC 236 14.3 单调线路的下界 239 14.3.1 定理14.7的证明 239 14.4 线路复杂性的前沿 242 14.4.1 用对角线方法证明线路下界 242 14.4.2 ACC Vs P的研究现状 243 14.4.3 具有对数深度的线性线路 244 14.4.4 线路图 244 14.5 通信复杂性方法 245 14.5.1 与ACC0线路之间的联系 245 14.5.2 与线性规模对数深度的线路之间的联系 246 14.5.3 与线路图之间的联系 246 14.5.4 卡奇梅尔维格德尔森通信游戏与深度下界 246 本章学习内容 248 本章注记和历史 249 习题 249 第15章 证明复杂性 251 15.1 几个例子 251 15.2 命题演算与归结 252 15.2.1 用瓶颈法证明下界 253 15.2.2 插值定理和归结的指数下界 254 15.3 其他证明系统概述 256 15.4 元数学的思考 258 本章学习内容 258 本章注记和历史 258 习题 259 第16章 代数计算模型 260 16.1 代数直线程序和代数线路 261 16.1.1 代数直线程序 261 16.1.2 例子 262 16.1.3 代数线路 263 16.1.4 代数线路中类似于P、NP的复杂性类 264 16.2 代数计算树 266 16.2.1 下界的拓扑方法 268 16.3 布卢姆舒布斯梅尔模型 270 16.3.1 复数上的复杂性类 271 16.3.2 完全问题和希尔伯特零点定理 271 16.3.3 判定性问题——曼德勃罗集 272 本章学习内容 272 本章注记和历史 273 习题 274 第三部分 高级专题 277 第17章 计数复杂性 278 17.1 计数问题举例 278 17.1.1 计数问题与概率估计 279 17.1.2 计数可能难于判定 279 17.2 复杂性类#P 280 17.2.1 复杂性类PP：类似于#P的判定问题 281 17.3 #P完全性 281 17.3.1 积和式和瓦利安特定理 282 17.3.2 #P问题的近似解 286 17.4 户田定理：PH⊆P#SAT 287 17.4.1 过渡：具有唯一解的布尔满足性问题 288 17.4.2 ⊕的性质和对NP、coNP证明引理17.17 289 17.4.3 引理17.17的证明：一般情形 290 17.4.4 第二步：转换为确定型归约 291 17.5 待决问题 292 本章学习内容 293 本章注记和历史 293 习题 293 第18章 平均复杂性:勒维定理 295 18.1 分布问题与distP 296 18.2 “实际分布”的形式化定义 298 18.3 distNP及其完全问题 298 18.3.1 distNP的一个完全问题 300 18.3.2 P可抽样的分布 301 18.4 哲学意义和实践意义 301 本章学习内容 303 本章注记和历史 303 习题 303 第19章 难度放大和纠错码 305 19.1 从温和难度到强难度：姚期智XOR引理 306 19.1.1 用因帕利亚佐难度核引理证明姚期智XOR引理 307 19.1.2 因帕利亚佐难度核引理的证明 309 19.2 工具：纠错码 310 19.2.1 显式纠错码 312 19.2.2 沃尔什哈达玛纠错码 312 19.2.3 里德所罗门纠错码 313 19.2.4 里德穆勒纠错码 313 19.2.5 拼接纠错码 314 19.3 高效解码 315 19.3.1 里德所罗门解码 315 19.3.2 拼接解码 316 19.4 局部解码与难度放大 316 19.4.1 沃尔什哈达玛纠错码的局部解码算法 318 19.4.2 里德穆勒纠错码的局部解码算法 318 19.4.3 拼接纠错码的局部解码算法 319 19.4.4 局部解码算法综合运用于难度放大 320 19.5 列表解码 321 19.5.1 里德所罗门纠错码的列表解码 322 19.6 局部列表解码：接近BPP=P 323 19.6.1 沃尔什哈达玛纠错码的局部列表解码 323 19.6.2 里德穆勒纠错码的局部列表解码 323 19.6.3 拼接纠错码的局部列表解码 325 19.6.4 局部列表解码算法综合运用于难度放大 325 本章学习内容 326 本章注记和历史 327 习题 328 第20章 去随机化 330 20.1 伪随机数产生器和去随机化 331 20.1.1 用伪随机数产生器实现去随机化 331 20.1.2 难度与去随机化 333 20.2 定理20.6的证明：尼散维格德尔森构造 334 20.2.1 两个示意性例子 334 20.2.2 尼散维格德尔森构造 336 20.3 一致假设下的去随机化 339 20.4 去随机化需要线路下界 340 本章学习内容 343 本章注记和历史 343 习题 344 第21章 伪随机构造:扩张图和提取器 345 21.1 随机游走和特征值 346 21.1.1 分布向量和参数λ(G) 346 21.1.2 无向连通性问题的随机算法的分析 349 21.2 扩张图 349 21.2.1 代数定义 350 21.2.2 组合扩张和扩张图的存在性 350 21.2.3 代数扩张图蕴含组合扩张图 351 21.2.4 组合扩张图蕴含代数扩张图 352 21.2.5 用扩张图设计纠错码 353 21.3 扩张图的显式构造 355 21.3.1 旋转映射 356 21.3.2 矩阵乘积和路径乘积 356 21.3.3 张量积 356 21.3.4 替换乘积 357 21.3.5 显式构造 359 21.4 无向连通性问题的确定型对数空间算法 361 21.4.1 连通性问题的对数空间算法（定理21.21的证明） 361 21.5 弱随机源和提取器 362 21.5.1 最小熵 363 21.5.2 统计距离 364 21.5.3 随机性提取器的定义 364 21.5.4 提取器的存在性证明 364 21.5.5 基于哈希函数构造提取器 365 21.5.6 基于扩张图的随机游走构造提取器 366 21.5.7 由伪随机数产生器构造提取器 366 21.6 空间受限计算的伪随机数产生器 368 本章学习内容 372 本章注记和历史 372 习题 374 第22章 PCP定理的证明和傅里叶变换技术 378 22.1 非二进制字母表上的约束满足问题 378 22.2 PCP定理的证明 379 22.2.1 PCP定理的证明思路 379 22.2.2 迪纳尔鸿沟放大：引理22.5的证明 380 22.2.3 扩张图、随机游走和INDSET的近似难度 381 22.2.4 迪纳尔鸿沟放大 382 22.2.5 字母表削减：引理22.6的证明 387 22.3 2CSPW的难度：鸿沟和字母表大小之间的平衡 389 22.3.1 莱斯的证明思想：并行重复 389 22.4 哈斯塔德3位PCP定理和MAX3SAT的难度 390 22.4.1 MAX3SAT的近似难度 390 22.5 工具：傅里叶变换 391 22.5.1 GF(2)n上的傅里叶变换 391 22.5.2 从较高层面看傅里叶变换和PCP之间的联系 393 22.5.3 GF(2)上线性测试的分析 393 22.6 坐标函数、长编码及其测试 395 22.7 定理22.16的证明 396 22.8 SETCOVER的近似难度 400 22.9 其他PCP定理概述 402 22.9.1 具有亚常数可靠性参数的PCP定理 402 22.9.2 平摊的查验复杂度 402 22.9.3 2位测试和高效傅里叶分析 403 22.9.4 唯一性游戏和阈值结果 404 22.9.5 与等周问题和度量空间嵌入之间的联系 404 22.A 将qCSP实例转换成“精细”实例 405 本章学习内容 406 本章注记和历史 407 习题 408 第23章 为什么线路下界如此困难 411 23.1 自然证明的定义 411 23.2 为什么自然证明是自然的 412 23.2.1 为什么要求可构造性 413 23.2.2 为什么要求广泛性 413 23.2.3 用复杂性测度看自然证明 414 23.3 定理23.1的证明 415 23.4 一个“不自然的”下界 416 23.5 哲学观点 417 本章注记和历史 417 习题 418 附录A 数学基础 419 部分习题的提示 438 参考文献 447 术语索引 472