天勤计算机考研笔记

PV操作中经典的生成者(producer)和消费者(consumer)问题：

0.复杂度：时间复杂度不是表示一个程序的运行时间，而是当问题规模扩大之后，程序需要的时间增长的有多快。

例如：四则运算，无论数据变得多大，程序的时间复杂度都为o(1);冒泡排序，数据扩大2倍，时间变4倍，程序的时间复杂度为o($n^2$)

P问题:Polynomial-Problem,有一个确定型图灵机在多项式内解决的问题。

NP问题:Non-deteministic polynomial(非确定性多项式) problem,能在多项式时间内验证某个猜想答案的正确性，但可能在无法再多项式时间内解决。比如：数独，很容易就确定一个答案是否正确，但确找不到一个公式来描述其规律。

所以现在面临的困难就是：P=NP？翻译过来就是能多项式时间内验证一个问题，是否能在多项式时间内解决一个问题？这也是千禧年世界七大数学难题之一。目前数学界倾向于不等，其中很重要的原因就是发现了NP-Complete。

NP-Complete:需要满足两个条件：1.它本身是个NP问题。2.所有的NP问题都可以约化到NP-complete。也就是说如果能证明NP-Complete=P，那么就基本可以证明NP=P。某种意义上说，NP-Complete问题就是NP问题中最难的那类。

比如：3SAT问题

NP-hard：只需要满足NP-Complete的第二个条件。所以NP-hard要比NP-Complete范围更广，复杂度可能更高。比如：Turing Halting Problem。

参考资料

(1) 什么是P问题、NP问题和NPC问题

(2)怎么理解 P 问题和 NP 问题？ - Kimmi Meow的回答 - 知乎

机器学习基石在证明过程中的思想，可以类比于集合论的思想，比如$f$是最完美的模型(函数)，那么$h$是假设函数空间(hypothesis set)$H$中的某个假设函数，$g$则是最接近$f$的那个$h$。

机器学习真的可行吗？

我们举个例子：

最近在看林轩田机器学习基石，作为对ML基础的进一步学习。在2-Learning to Answer Yes_No中，以一个例子来总结解释一下PLA（感知学习算法）的修正过程，以及一些证明。

PLA

PLA的主要思想：逐步修正。

图中坐标原点位于正方形中心位置，样本数据线性可分，决策边界满足$w^{T}x=0$，注意下面谈到的$w$和$x$都是向量。

step-0：初始化$w=0$

Data Structures and Sequences