晓强Deep Learning的读书分享会，先从这里开始，从大学开始。大家好，我是晓强，计算机科学与技术专业研究生在读。我会不定时的更新我的文章，内容可能包括深度学习入门知识，具体包括CV，NLP方向的基础知识和学习的论文；网络表征学习的相关论文解读。当然我每天的读书心得也会分享给大家，可能涉及我们生活各个方面的书籍。我也会不定时回答大家的问题与大家一同进步，共同交流，互相监督，结交更多的朋友。希望大家多留言，多交流，多多关照。我在这里等你一同学习，如果需要相关资料也可以私信我，进入我们的群大家庭。
【晓白】今天事情可能很多，所以下午有时间的话，我就把今天的文章完成吧，继续更新算法设计与分析的内容，预祝顺利，加油！
近似算法
Although this may seem a paradox, all exact science is dominated by the idea of approximation.
Bertrand Russell(1872-1970)
Bertrand Arthur William Russell was a British philosopher, logician, mathematician, historian, and social critic.
Computation Complexity
Combinatorial Methods
Linear programming based Methods
Semi-definite program based Methods
Counting Methods
Hardness of Approximation
Lagrangean Methods
前驱课程
计算理论
算法设计与分析
晓强DL：计算理论与计算模型zhuanlan.zhihu.com
问题分类
判定问题(decision problem)
优化问题(optimization problem)
搜索问题(search problem)
计数问题(counting problem)
枚举问题(enumeration problem)
计算问题(calculation problem)
判定问题
可满足性问题
是否存在对变量的赋值，使得布尔表达式为真?
优化问题
最小顶点覆盖问题
优化问题有对应的判定版本
最小顶点覆盖问题的判定版本
输入: 无向图G=(V, E)，整数K
输出: 是否存在一个顶点覆盖小于等于K?
搜索问题
找到满足条件的一个对象
输入：一个图数据库，一个支持度(例如：60%)
输出：大于等于该支持度的一个子图
枚举问题
找到满足条件的所有对象
频繁模式挖掘问题：
输入：一个图数据库，一个支持度(例如：60%)
输出：大于等于该支持度的所有子图
计数问题
求满足条件的所有对象的数量
输入：一个图数据库，一个支持度(例如：60%)
输出：大于等于该支持度的所有子图的数量
枚举问题有对应的计数版本
频繁模式挖掘问题：
输入：一个图数据库，一个支持度(例如：60%)
输出：大于等于该支持度的所有子图
输入：一个图数据库，一个支持度(例如：60%)
输出：大于等于该支持度的所有子图的数量
计算问题
例子：
1、求矩阵的特征值
2、求矩阵的行列式
……
问题类
根据是否可解进行分类
可解问题
不可解问题
不可解问题
停机问题不可解
没有一个计算机程序能够肯定地确定另外一个计算机程序是否能所有的输入停机
While (n > 1)
if (ODD(n))
n = 3n + 1;
else
n = n/2;
调用contrary(contrary)???
Bool halt(char *prog, char * input)
{ //code to solve halting problem
if(prog does halt on input) then
return(true);
else
return(false);
}
Bool selfhalt(char *prog)
{ //return false if program halts when given itself as input
if( halt(prog, prog) )
return(true);
else
return(false);
}
Bool contrary(char *prog)
{
if( selfhalt(prog) )
while(true); //go into an infinite loop
}
对可解问题进行分类
多项式时间内可解的问题(P类问题, tractable)
非多项式时间内可解的问题（难解问题, intractable)
NP类问题
……
P类问题
在确定性的机器上(常规的计算机上)使用多项式时间可以解决的问题(P类问题)
排序问题
最小扩展树问题
单源最短路径问题
……
NP类问题
存在多个等价的定义：
(1) 在非确定性的机器上在多项式时间内可以解决的问题。
(2) 非确定的多项式时间算法可以解决的判定问题
(3) 在多项式时间内可以验证的判定问题
非确定的算法有两个阶段：
(1) 猜测(guess)
(2) 验证
输入: 给定一个整数
输出: 是否是合数
可满足性问题
汉诺塔的判定问题
多项式时间规约
判定问题的多项式时间归约
定义.判定问题A在多项式时间内可归约为判定问题B, 如果存在具有多项式时间复杂性的变换f使得:
(1). 对A的任意实例x，f(x)是B的实例;
(2). 对x回答’yes’iff对f(x)回答’yes’
顶点覆盖的判定问题可归约到集合覆盖的判定问题
集合覆盖问题
问题的实例
X=12个黑点, F={S1, S2, S3, S4, S5, S6}
优化解C={S3, S4, S5}
集合覆盖的判定问题问题
问题的实例
X=12个黑点, F={S1, S2, S3, S4, S5, S6}，整数K =3
回答：是
多项式时间规约
顶点覆盖的判定问题可归约到集合覆盖的判定问题
多项式时间归约
定义1. 问题A在多项式时间内可归约为问题B, 如果存在具有多项式时间复杂性的变换f和g使得:
(1). 对A的任何实例x, if(x)是B的实例;
(2) s是B实例f(x)的解 iff g(s)是A实例x的解.
顶点覆盖的优化问题可归约到集合覆盖的优化问题
自规约(self–reduction)
给定求判定问题的一个算法
就可以在多项式时间内求出对应的解
例如：给定求可满足行问题的判定算法
就可以求出布尔表达式的真值分配
给定求判定问题的一个算法
就可以在多项式时间内求出对应优化版本的解
例如：给定顶点覆盖问题的判定算法
就可以计算出最小的顶点覆盖
NP-Hard Problems
NP-Hard Problem的定义
定义. 问题A称为NP-Hard, 如果BNP, B可以在多项式时间内归约为A.
NP-Complete Problems
NP-Complete Problem的定义
定义2. 问题A称为NP-Complete, 如果:
(1). A属于NP.
(2). 任意B属于NP, B可以多项式地归约为A.
Cook’s Theorem
Cook定理. 布尔表达式的可满足性(SAT)问题是
NP-complete.
P, NP, NPC关系
(1) P ⊂ NP 还是P = NP? 是计算机科学中 最难的问题!!!
(2) 任意一个NP-complete问题都属于NP-P?
- 图同构问题？
- 素数判定问题？
NP-Complete的证明
Karp的伟大贡献: 利用一个已知的NP-Complete
问题，通过规约，证明另一个问题也是NP-hard.
NP-hard分类
In computational complexity, an NP-complete (or NP-hard) problem is weakly NP-complete (or weakly NP-hard), if there is an algorithm for the problem whose running time is polynomial in the dimension of the problem and the magnitudes of the data involved (provided these are given as integers), rather than the base-two logarithms of their magnitudes.
A problem is said to be NP-hard or NP-complete in the strong sense (strongly NP-complete or NP-hard), if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the input.
近似比
定义(近似比) 设A是一个优化问题的近似
算法, A具有近似比 p(n), 如果
其中n是输入大小, C是A产生的解的代价, C*是优化解的代价.
组合方法
近似比：
(1) 常数
(2) 不存在近似比
(3) 问题规模的函数
(4) PTAS 和 FPTAS
问题：
(1) vertex cover
(2) Steiner tree
(3) TSP
(4) set cover
(5) knapsck
顶点覆盖问题：极大(最大)匹配数是最小顶点覆盖的下界！
算法：发现图G的一个极大匹配，输出匹配顶点集合！
该算法是近似比为2的近似算法
下界技术：极大(最大)匹配数是最小顶点覆盖的下界！
算法：发现图G的一个极大匹配，输出匹配顶点集合！
该算法是近似比为2的近似算法
1、该算法的近似比能通过更好地分析被改善吗？
2、利用上面的下界技术，能设计更好的近似算法吗？
3、是否存在其它的下界技术，能设计更好的近似算法吗？
通用图上的货郎担问题
输入
完全无向图G=(V,E);
代价函数C: E→非负整数集合
输出
具有最小代价的Hamilton环
定理：对任何函数f(n)，对货郎担问题不存在近似比为f(n)的近似算法，除非P=NP
算法1：近似比为2
算法2：近似比为3/2
近似算法-组合方法
Steiner tree - 近似比为常数
Set cover - 近似比为问题规模的函数
Subset sum - FPTAS
0-1 knapsack - FPTAS
Bin packing - PTAS
U={a,b,c,d,e,f,g,h,i,j,k,l}
F={S1={a,b,c,d,e,f},S2={e,f,h,i},
S3={a,d,g,j}, S4={b,e,g,h,k},
S5={c,f,i,l}, S6={j,k}}
近似模式
定义4 (近似模式) 一个优化问题的近似模式是一个以问题实例I和>0为输入的算法. 对于任意固定, 近似模式是一个(1+)-近似算法.
近似算法-线性规划方法
Linear programming
Dual-fitting method
Rounding method
Primal-dual schema method
线性规划简介
生产安排模型：某工厂要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示，表中右边一列是每日设备能力及原材料供应的限量，该工厂生产一单位产品Ⅰ可获利2元，生产一单位产品Ⅱ可获利3元，问应如何安排生产，使其获得最多？
营养配餐模型：假设一个成年人每天需要从食物中获取3000KJ的热量、55g蛋白质和800mg的钙。如果市场上有四种食品可选择，各种食品每千克所含热量、营养成分及市场价格如下表。问如何选择才能在满足营养的前提下，使得购买食品的费用最小？
求解线性规划的方法
Simplex algorithm of Dantzig
Ellipsoid algorithm, following Khachiyan
Interior point methods, following Karmarkar
在实际中,如何使用近似算法
遇到NP-hard问题怎么办？
1、如果问题的规模很小, 可以使用指数级算法圆满地解决该问题
2、某些NP-hard问题的算法在平均情况下仍然具有多项式时间，在实际中的效率仍然很高
3、找到该问题的目前最好的近似算法
4、没有近似算法，只能使用启发式策略
今天文章更新完毕，希望大家共同努力一起进步，多交流，点点关注。更多文章，在如下链接，
晓强DL：GloVe: Global Vectors for Word Representationzhuanlan.zhihu.com
晓强DL：NLP入门必读系列之WORD2VECTORzhuanlan.zhihu.com
晓强DL：分支限界法zhuanlan.zhihu.com
晓强DL：第五章 回溯法（Backtrack）zhuanlan.zhihu.com
晓强DL：第五章、第六章补充Tree Searching Strategieszhuanlan.zhihu.com
晓强DL：第四章 贪心算法(Greedy Algorithms)zhuanlan.zhihu.com
晓强DL：第三章 动态规划(Dynamic Programming )zhuanlan.zhihu.com
晓强DL：第二章 递归与分治zhuanlan.zhihu.com
晓强DL：计算机算法设计与分析第一章 算法概述zhuanlan.zhihu.com
晓强DL：计算理论与计算模型zhuanlan.zhihu.com
晓强DL：图像处理必读论文之AlexNetzhuanlan.zhihu.com
晓强DL：图像处理必读论文之二：VGG网络zhuanlan.zhihu.com
晓强DL：Opencv图像处理(一)zhuanlan.zhihu.com
晓强DL：OpenCV图像处理（二）zhuanlan.zhihu.com
晓强DL：Opencv图像处理(三)zhuanlan.zhihu.com
晓强DL：Opencv图像处理 （四）zhuanlan.zhihu.com
