学习前福利
一.数据库
1. 数据库范式
设计关系数据库时，遵从不同的规范要求，设计出合理的关系型数据库，这些不同的规范要求被称为不同的范式（Normal form NF），各种范式呈递次规范，越高的范式数据库冗余越小。
目前关系数据库有六种范式：第一范式（1NF）、第二范式（2NF）、第三范式（3NF）、巴斯-科德范式（BCNF）、第四范式(4NF）和第五范式（5NF，又称完美范式）。一般数据库只要满足第三范式足以。
1.1第一范式（每列为单独属性）
所谓第一范式（1NF）是指在关系模型中，对于添加的一个规范要求，所有的域都应该是原子性的，即数据库表的每一列都是不可分割的原子数据项，而不能是集合，数组，记录等非原子数据项。在任何一个关系数据库中，第一范式（1NF）是对关系模式的设计基本要求，一般设计中都必须满足第一范式
1.2第二范式（候选码不部分决定）
第二范式是指在1NF的基础上，非码属性必须完全依赖于候选码（在1NF基础上消除非主属性对主码的部分函数依赖）。第二范式（2NF）要求数据库表中的每个实例或记录必须可以被唯一地区分。选取一个能区分每个实体的属性或属性组，作为实体的唯一标识。例如在员工表中的身份证号码即可实现每个一员工的区分，该身份证号码即为候选键，任何一个候选键都可以被选作主键。在找不到候选键时，可额外增加属性以实现区分。
第二范式（2NF）要求实体的属性完全依赖于主关键字。所谓完全依赖是指不能存在仅依赖主关键字一部分的属性，如果存在，那么这个属性和主关键字的这一部分应该分离出来形成一个新的实体，新实体与原实体之间是一对多的关系。为实现区分通常需要为表加上一个列，以存储各个实例的唯一标识。简而言之，第二范式就是在第一范式的基础上属性完全依赖于主键。选课表中主关键字是学号+课号，此时如果表中加入学生姓名之类，即由主关键字（候选码）中的一部分（学号）决定，不满足第二范式。
1.3第三范式（依赖关系不传递）
第三范式（3NF）是第二范式（2NF）的一个子集，即满足第三范式（3NF）必须满足第二范式（2NF）。简而言之，第三范式（3NF）要求一个关系中不包含已在其它关系已包含的非主关键字信息。例如，存在一个部门信息表，其中每个部门有部门编号（dept_id）、部门名称、部门简介等信息。那么在员工信息表中列出部门编号后就不能再将部门名称、部门简介等与部门有关的信息再加入员工信息表中。如果不存在部门信息表，则根据第三范式（3NF）也应该构建它，否则就会有大量的数据冗余。简而言之，第三范式就是属性不依赖于其它非主属性，也就是在满足2NF的基础上，任何非主属性不得传递依赖于主属性。工号决定部门编号，部门编号决定部门信息，此为传递依赖。
数据库范式
二.算法
1.贪心算法
大部分算法基于以下四种思想：
1.动态规划
2.分而治之（递归思想）
3.贪心算法
4.暴力穷举
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。假设一个问题比较复杂，暂时找不到全局最优解，那么我们可以考虑把原问题拆成几个小问题（分而治之思想），分别求每个小问题的最优解，再把这些“局部最优解”叠起来，就“当作”整个问题的最优解了。
贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。求最小生成树和Prim算法和Kruskal算法都是漂亮的贪心算法。
#实例1 找零钱问题：
#要求找零张数最少，输入价格，输出面额。
class Solution:
def zhaoling(self, nums):
money = [50, 20, 10, 5, 1]
result = 100 - nums
for i in money:
if result >= i:
count = result // i
result = result - count * i
print("{}元的{}张".format(i,count))
else:
print("找零完毕")
s = Solution()
print(s.zhaoling(52))
#实例2 分糖果问题：
#要求每人至少一个，评分比相邻高的糖果要多，
#输入评分列表，输出至少需要的糖果数
class Solution:
def fentang(self, grade):
result = [1]
for index in range(1, len(grade)):
if grade[index] > grade[index - 1]:
result.append(result[index - 1] + 1)
elif grade[index] < grade[index - 1]:
result.append(result[index - 1] - 1)
else:
result.append(result[index - 1])
judge = min(result)
if judge <= 0:
for index in range(0, len(result)):
result[index] = result[index] + 1 - judge
return result
s = Solution()
print(s.fentang([1, 2, 1]))
print(s.fentang([2, 1, 2]))
print(s.fentang([6,8,10,4,4,3,2,1]))
2. 0-1背包问题--动态规划
3.梯度下降法
梯度下降算法是一种非常古老的经典的求极小值的算法，在机器学习领域使用较为广泛。
人下山
关于梯度下降算法的直观理解，以一个人下山为例。比如刚开始的初始位置是在红色的山顶位置，那么现在的问题是该如何达到蓝色的山底呢？按照梯度下降算法的思想，它将按如下操作达到最低点：
第一步，明确自己现在所处的位置
第二步，找到相对于该位置而言下降最快的方向
第三步， 沿着第二步找到的方向走一小步，到达一个新的位置，此时的位置肯定比原来低
第四部， 回到第一步
第五步，终止于最低点
按照以上5步，最终达到最低点，这就是梯度下降的完整流程。因为上图并不是标准的凸函数，往往不能找到最小值，只能找到局部极小值。所以可以用不同的初始位置进行梯度下降，来寻找更小的极小值点，当然如果损失函数是凸函数就没必要了。
凸函数
一元函数
一元函数导数公式
二元函数
对于二元函数，ｚ＝ｆ（ｘ，ｙ），它对ｘ和ｙ的偏导数分别表示如下：
函数在ｙ方向不变的情况下，函数值沿ｘ方向的变化率
函数在ｘ方向不变的情况下，函数值沿ｙ方向的变化率
有了以上的了解，我们分别知道了函数在单独在ｘ和ｙ方向上的变化率
现在有一个问题，我想知道函数在其他方向上的变化率怎么办？
其实是可以做到的，我们都学过，在一平面中，任意一向量都可以用两个不共线的基向量表示，也就是说任意一方向上的变化，都可以分解到ｘ和ｙ两个方向上。
比如，我想求ｕ方向上的变化率，根据导函数的定义
其中α是ｕ方向与ｘ正方向的夹角
极限存在，可用洛必达法则，分子分母同时对▲ｕ求导
令：
这是一个自变量是α的函数，我们将其命名为方向导数，其表明随着α的不同，方向不同，函数的变化率不同。
至此，我们推出了，方向导数的概念，还记得我们的梯度下降算法的第二步是什么吗？
”找到相对于该位置而言下降最快的方向“
而我们的方向导数，本身代表的就是函数变化率与方向的关系，也就是说我们需要利用方向导数，找到使得函数变化率最大的方向
那么，问题来了，在哪一个方向上变化率最大呢？
寻找函数变化率最大的方向－梯度
则：
θ是两个向量的夹角
显然，当θ＝０时，取得最大方向导数，也就说随着α的改变，当两个向量Ａ和Ｉ是平行的时候，取得最大方向导数，而此时Ｉ的方向就是下式的方向：
我们把上式称之为梯度，所以梯度方向是函数变化率最大的方向，更本质的说是函数增长最快的方向
所以，当我们需要最小化损失函数时，只需要使损失函数沿着负梯度前行，就能使损失函数最快下降。
网友评论