资源描述：
《数学基础回顾》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、简单的数学基础回顾整数的整除和同余整数的唯一分解定理欧拉函数与欧拉定理NP完全问题一、整数的整除和同余（1/3）两个整数的和、差、积仍然是整数。但是用一个不等于零的整数去除另一个整数的商却不一定是整数。欧几里德（Eulid）定理：a，b是两个整数，其中b≠0，则存在唯一的整数q及r，使得a＝bq﹢r0≤r＝∣b∣即a必在下面序列的某两项之间：{……，-2∣b∣，-∣b∣，0，∣b∣，2∣b∣，3∣b∣，……}q称作a被b除得出的不完全商，r称作a被b除得出的余数（非负最小余数），如果r=0，称b整除a，记作b
2、a,否则称b不整除a，记作?一、整数的整除和同余(
3、2/3)辗转相除法：设有整数a,b(b≠0),由欧几里德定理，有下列等式：a＝bq1﹢r10＜r1＜∣b∣b＝r1q2﹢r20＜r2＜r1…………………………………………rn-2＝rn-1qn﹢rn0＜rn＜rn-1rn-1＝rnqn+1﹢rn+1rn+1=0定理：a,b,c是任意三个不全为零的整数，且a=bq﹢c，其中q为整数，则(a,b)=(b,c)。（rn）一、整数的整除和同余(3/3)定义：给定一个正整数m，如果用它去除两个整数a、b所得的余数相同，则称a、b对模数m同余，记作a≡b(modm)。a≡b(modm)叫做同余式。性质：a≡b(modm)的
4、充分必要条件是m
5、a-b，即存在整数k使得a=km+b。一次同余方程是指ax≡b(modm)其中m>1。如果x=x0满足上式，称为同余方程的解，将0,1,……,m-1代入同余方程进行验算，可求出同余方程的解，但是当m很大时，计算量很大。二、整数的唯一分解定理质数定义：大于1，正因素只有1和它本身。若p是质数，a是任意整数，则p
6、a或（p,a）=1若p是质数，p
7、ab，则p
8、a或p
9、b质数的判别有：简单法、莱梅法、普罗兹法、……，概率法(Rabin等）定理：任意大于1的整数都能唯一分解成质数的乘积，即对任意一个整数a>1，有a=p1p2……pn，p1≤p2≤……
10、≤pn其中p1，p2，……pn都是质数，而且唯一。（当a很大时，分解计算量很大！）三、欧拉函数与欧拉定理(1/2)欧拉函数：ω(n)定义在正整数集合上的函数,ω(n)的值等于0,1,……n-1中与n互质的数的个数。例：ω(1)=1，ω(2)=1，ω(3)=2当p是质数时，ω(p)=p-1若p,q互质，则ω(pq)=ω(p)ω(q)若p是质数，k是正整数，则ω(pk)=pk-pk-1三、欧拉函数与欧拉定理(2/2)欧拉定理：若（a,m）=1，则aω(m)≡1(modm)费马小定理：若p为质数，则ap≡a(modp)四、NP完全问题1/3算法：用计算机求解一类问题
11、的方法。但是许多问题是不可解的。（我们讨论的是可解的问题）。算法时间复杂性：用算法所执行的加减乘除比较等初等运算的次数。表示为：TA=T(n,I)其中A为算法，n为输入规模，I为具体输入。大O的概念：f(n),g(n)是从自然数到实数上的函数，如果存在常数c，n0,使得当n>n0时，f(n)≤g(n)，则称f(n)有上界，g(n)是它的一个上界，记为：f(n)=Og(n)。简单的判断方法：lim(n→∞)(f(n)/g(n))=c<∞?同样可以定义“下界”、“同阶”四、NP完全问题2/3存在多项式时间算法的问题称作是易解的。（如线性查找）反之，不存在多项式时间
12、算法的问题称作是难解的（如Hanoi问题）。P类问题：所有能够用多项式时间算法求解的判定问题的集合（如质数判断问题）。NP类问题：可在多项式时间求解的不确定性算法判定问题的集合（如背包问题）。不确定性算法：计算执行到某一步，试探所（不是一个接一个）有选择（所有子算法独立运行），当其中一个选择错误，则停止该选择运行，当其中一个求出解，则停止所有选择运行。因为确定性算法是不确定性算法的特例，所以P包含于NP中。（问题P=NP?）四、NP完全问题3/3多项式变换：设X1、X2是两各个判定问题，若存在多项式确定算法A使得任意X1中的一个实例x1变换到X2中的实例x2，
13、并且当且仅当x1判定“Y”时，x2也判定为“Y”，称X1可多项式变换为X2，记作X1∝X2，算法A叫做X1到X2的多项式变换。NP完全问题：设X是一个判定问题，对任意的X0∈NP都有X1∝X，则称X是NP难度的。若X是NP难度的，且X∈NP，则称X是NP完全的。典型的NP完全问题：背包问题、哈密尔顿回路问题、旅行商判定问题……。Review整数的整除和同余整数的唯一分解定理欧拉函数与欧拉定理NP完全问题
