§2.2 P-问题与NP-问题 第三节 多项式时间变换, Cook定理 §3.1 §3.2 多项式时间归结，多项式时间变换 Cook定理 第四节 基本的NP-完备问题 §４.1 §４.2 §４.3 3-适定问题 顶点覆盖和团问题，3-维匹配问题 Hamilton圈问题，划分问题 基本框架、基本证明方法，并能够融会贯通地解决一些初步的复杂性证明问题。为学生理解后续的复杂性理论提供支持。 2 8 传统讲授 4 2 2 传统讲授 8 2 2 4 20 第五节 证明NP-完备性的技巧 §５.1 §５.2 限制与局部替换 分枝设计 本章的教学目标是使学生进一步了解如何利用NP-完备性理论来分析问题的复杂性，掌握Co-NP-完备、强NP-困难性问题的概念和证明技巧以及拟多项式时间算法的设计思路。 讨论报告 8 4 4 8 16 第二章 利用NP-完备性分析问题 第一节 强NP-完备性和拟多项式时间算法 §1.1 §1.2 Number问题与强NP-完备性 拟多项式时间算法 16 12 传统讲授 6 2 4 第二节 Co-NP-完备性，NP-困难性 §2.1 §2.2 Co-NP-完备性 Turing递归与NP-困难性 传统讲授 2 1 1 28 4 本章的教学目标第一节 近似算法的有关概念 是通过近似算法及其第二节 近似算法中的复杂性分析 复杂性分类使学生了解如何从算法的角度§2.1 顶点覆盖问题的近似算法 来处理NP-困难问题，§2.2 货郎问题的复杂性和近似度 更加深入地理解复杂§2.3 划分问题与背包问题的PTAS/ FPTAS 性理论的发展，学会近似算法的基本设计§2.4 装箱问题（渐进PTAS） 技巧和分析方法。为§2.5 排序问题的近似算法（PTAS） 学生学习后续的“近第三节 线性规划方法在近似算法中的应用 似算法”课程提供做好准备。 §3.1 线性规划方法简介 第三章 近似算法及其复杂性 §3.2 §3.3
线性规划舍入法 原始-对偶近似算法技巧 54 2 32 传统讲授 2 传统讲授 16 2 2 4 4 4 讨论报告 10 2 4 4 20 参考书目
[1] C.H. Papadimitriou, K. Steiglitz（美）著，刘振宏，蔡茂诚译.组合最优化：算法
和复杂性.清华大学出版社，1988年。
[2] Michael R. Garey and David S. Johnson（美）著，Computers and Intractability--- A Guide to
the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco, 1979. [3] Vijay V. Vazirani（美）著. Approximation Algorithm. Springer-Verlag Berlin Heidelberg
Inc. 2003.
[4] G. Ausiello, P. Crescenzi et al.（美）著.Complexity and Approximation (Combinatorial
Optimization Problems and Their Approximability Properties). Springer-Verlag New York Inc. 2000.
[5] Christos H. Papadimitriou（美）著. Computational Complexity. Addison-Wesley Publishing
Company，1994.
[6] 堵丁柱 葛可一 王洁 著. 计算复杂性导论. 高等教育出版社。
《统计学习理论及应用》课程教学大纲
撰 写 人：王莉萍
撰写时间：2006年5月06日 开课院系：数学系 课程编号：100K0050
课程英文名称：The Statistical Learning Theory and Application 课内总学时：64 学分：3 推荐使用教材：统计学习理论及应用 编者：陈永义
出版社：中国气象局培训中心 出版时间及版次：2004年2月 课程教学目标与基本要求：
SVM 是一种有坚实理论基础的新颖的小样本学习方法。它避开了从归纳到演绎的
传统过程，实现了高效的从训练样本到预报样本的“转导推理”(transductive inference)，大大简化了通常的分类和回归等问题。本课程详细介绍了应用SVM的模式识别方法、SVM回归分析的主要思路、机器学习的有关理论问题以及SVM的应用。通过本课程的学习，可使学生掌握SVM模式识别、回归分析及参数优化的知识，并能将该方法应用于某些实际领域，例如天气预报的预测。课程强调案例分析，并结合实际应用背景开展其在气象、经济、环境、生态等领域的应用。
考试形式：期末闭卷考试与平时考核相结合。
授课内容（细化到章、节、目） 第一章导言 1.1计算机应用的历史回顾 1.2计算机学习的基本问题 1.3支持向量机方法的基本思想 1.4SVM方法的应用展望 第二章线形支持向量机模式识别 掌握线性支持向量2.1模式识别的问题表述 2.2最优划分超平面与支持向量机的模式识别方法 讲授 8 教学目标 支持向量机方法介绍及其基本思想 授课模式 讲授 学时分配 4 的概念 2.3最优划分超平面的求解 2.4线性不可分问题的求解 2.5线性多类分类问题的求解 第三章非线性支持向量机模式识别 3.1数学预备知识 3.2非线性映射与特征空间 3.3特征空间中的线性学习机 3.4Mercer核和内积 3.5基于核方法的非线性支持向量机 3.6支持向量机方法的特点 第四章支持向量机回归分析 4.1回归分析的问题表述 4.2?-不灵敏函数 4.3最优回归超平面与SVM线性回归 4.4非线性SVM回归 4.5SVM回归方法的特点 第五章关于SVM方法的进一步思考 5.1从样本到样本的推理 5.2SVM方法的非线性本质 5.3关于核方法 5.4学习机性能的评价 5.5支持向量机参数优化 结合应用实践掌握支持向量机的参数优化方法 第六章统计学习理论 6.1经验分险最小化归纳原则 6.2统计学习的基本定理 6.3函数集的VC群 6.4 VC维与生长函数的关系 6.5关于学习机推广能力的界 掌握支持向量机方法中估计推广能力讲授与分组讨论、建模相结合 5 结合实例掌握函数集的VC维 讲授与分组讨论、建模相结合 8 讲授与分组讨论、建模相结合 8 掌握支持向量机的非线性本质， 讲授与分组讨论、建模相结合 8 掌握支持向量机的回归分析及其特点 讲授与分组讨论、建模相结合 8 掌握非线性支持向量机的模式识别方法 讲授 6 6.6结构分险最小化归纳原则 第七章SVM方法在天气预报中的应用试验 7.1SVM方法与天气预报 的依据 结合实例SVM方法掌握在天气预报中推理模型的建立方讲授与分组讨论、建模相结合 5 7.2SVM推理预报模型的建立方法 法 7.3SVM模型的试验效果分析 7.4预报对象与因子的相关性对建模影响分析 7.5建模样本变化与SVM模型 7.6SVM方法应用实例 学习参考书（注明编者，出版社，出版时间及版次）：
掌握建立SVM模型的一些影响因素 讲授与分组讨论、建模相结合 4 1 Vapnik V N. The Nature of Statistical Learning Theory. Springer-Verlag, New York, 2000.（有中译本：张学工译. 统计学习理论的本质. 北京：清华大学出版社，2000.）
2 Cristianini N and Shawa-Taylor J. An Introduction of Support VectorMachines and other kernel_based learning methods. CambridgeUniversity Press, 2000.
3 黄嘉佑，气象统计分析与预报方法（第二版），北京：气象出版社，2000