Nov 6

 

在算法导论中对求解最大流问题给出了一般性的解决方法,但并没有涉及到具体的实现。在这里我还是重新的对求解最大流的思想进行一般性的描述,然后再给出具体的实现。

      Ford-Fulkerson方法依赖于三种重要思想,这三个思想就是在上一篇网络流基础中提到的:残留网络,增广路径和割。Ford-Fulkerson方法是一种迭代的方法。开始时,对所有的u,v∈V有f(u,v)=0,即初始状态时流的值为0。在每次迭代中,可通过寻找一条“增广路径”来增加流值。增广路径可以看成是从源点s到汇点t之间的一条路径,沿该路径可以压入更多的流,从而增加流的值。反复进行这一过程,直至增广路径都被找出来,根据最大流最小割定理,当不包含增广路径时,f是G中的一个最大流。在算法导论中给出的Ford-Fulkerson实现代码如下:

     FORD_FULKERSON(G,s,t)
     1   for each edge(u,v)∈E[G]
     2        do f[u,v] <— 0
     3            f[v,u] <— 0
     4   while there exists a path p from s to t in the residual network Gf
     5        do cf(p) <— min{ cf(u,v) : (u,v) is in p }
     6        for each edge(u,v) in p
     7             do f[u,v] <— f[u,v]+cf(p)         //对于在增广路径上的正向的边,加上增加的流
     8                  f[v,u] <— -f[u,v]                //对于反向的边,根据反对称性求

     第1~3行初始化各条边的流为0,第4~8就是不断在残留网络Gf中寻找增广路径,并沿着增广路径的方向更新流的值,直到找不到增广路径为止。而最后的最大流也就是每次增加的流值cf(p)之和。在实际的实现过程中,我们可以对上述代码做些调整来达到更好的效果。如果我们采用上面的方法,我们就要保存两个数组,一个是每条边的容量数组c,一个就是上面的每条边的流值数组f,在增广路径中判断顶点u到v是否相同时我们必须判断c[u][v]-f[u][v]是否大于0,但是因为在寻找增广路径时是对残留网络进行查找,所以我们可以只保存一个数组c来表示残留网络的每条边的容量就可以了,这样我们在2~3行的初始化时,初始化每条边的残留网络的容量为G的每条边的容量(因为每条边的初始流值为0)。而更新时,改变7~8行的操作,对于在残留网络上的边(u,v)执行c[u][v]-=cf(p),而对其反向的边(v,u)执行c[v][u]+=cf(p)即可。

      现在剩下的最关键问题就是如何寻找增广路径。而Ford-Fulkerson方法的运行时间也取决于如何确定第4行中的增广路径。如果选择的方法不好,就有可能每次增加的流非常少,而算法运行时间非常长,甚至无法终止。对增广路径的寻找方法的不同形成了求最大流的不同算法,这也是Ford-Fulkerson被称之为“方法”而不是“算法”的原因。下面将给出Ford-Fulkerson方法的具体实现细节:

int c[MAX][MAX];  //残留网络容量
int pre[MAX];  //保存增广路径上的点的前驱顶点
bool visit[MAX];

int Ford_Fulkerson(int src,int des,int n){   //src:源点 des:汇点 n:顶点个数
     int i,_min,total=0;
     while(true){
         if(!Augmenting_Path(src,des,n))return total; //如果找不到增广路就返回,在具体实现时替换函数名
         _min=(1<<30);
         i=des;
         while(i!=src){   //通过pre数组查找增广路径上的边,求出残留容量的最小值
             if(_min>c[pre[i]][i])_min=c[pre[i]][i];
             i=pre[i];
         }
         i=des;
         while(i!=src){    //再次遍历,更新增广路径上边的流值
             c[pre[i]][i]-=_min;
             c[i][pre[i]]+=_min;
             i=pre[i];
         }
         total+=_min;     //每次加上更新的值
     }
}

 


 

Edmonds-Karp算法实际上就是采用广度优先搜索来实现对增广路径的p的计算,代码如下:

bool Edmonds_Karp(int src,int des,int n){
     int v,i;
     for(i=0;i<n;i++)visit[i]=false;
     front=rear=0;     //初始化
     que[rear++]=src;
     visit[src]=true;
     while(front!=rear){     //将源点进队后开始广搜的操作
         v=que[front++]; 
         
//这里如果采用邻接表的链表实现会有更好的效率,但是要注意(u,v)或(v,u)有任何一条
         //边存在于原网络流中,那么邻接表中既要包含(u,v)也要包含(v,u)

         for(i=0;i<n;i++){ 
             if(!visit[i]&&c[v][i]){  
//只有残留容量大于0时才存在边
                 que[rear++]=i;
                 visit[i]=true;
                 pre[i]=v;
                 if(i==des)return true;   //如果已经到达汇点,说明存在增广路径返回true
             }
         }
     }
     return false;
}


现在先给出一个最基本的EK实现,以后会陆续将其他算法实现添加上来O(∩_∩)O~

Sep 19

 

目录  · · · · · ·

出版者的话
专家指导委员会
译者序
前言
第1章 什么是组合数学
1.1 例:棋盘的完美覆盖
1.2 例:切割立方体
1.3 例:幻方
1.4 例:四色问题
1.5 例:36军官问题
1.6 例:最短路径问题
1.7 例:Nim取子游戏
1.8 练习题
第2章 鸽巢原理
2.1 鸽巢原理:简单形式
2.2 鸽巢原理:加强形式
2.3 Ramsey定理
2.4 练习题
第3章 排列与组合
3.1 四个基本的计数原理
3.2 集合的排列
3.3 集合的组合
3.4 多重集的排列
3.5 多重集的组合
3.6 练习题
第4章 生成排列和组合
4.1 生成排列
4.2 排列中的逆序
4.3 生成组合
4.4 生成r组合
4.5 偏序和等价关系
4.6 练习题
第5章 二项式系数
5.1 Rascal公式
5.2 二项式定理
5.3 一些恒等式
5.4 二项式系数的单峰性
5.5 多项式定理
5.6 牛顿二项式定理
5.7 再论偏序集
5.8 练习题
第6章 容斥原理及应用
6.1 容斥原理
6.2 具有重复的组合
6.3 错位排列
6.4 带有禁止位置的排列
6.5 另外的禁排位置问题
6.6 莫比乌斯反演
6.7 练习题
第7章 递推关系和生成函数
7.1 一些数列
7.2 线性齐次递推关系
7.3 非齐次递推关系
7.4 生成函数
7.5 递归和生成函数
7.6 一个几何的例子
7.7 指数生成函数
7.8 练习题
第8章 特殊计数序列
8.1 Catalan数
8.2 差分序列和Stirling数
8.3 分拆数
8.4 一个几何问题
8.5 格路径和Schrodr数
8.6 练习题
第9章 二分图中的匹配
9.1 一般问题表述
9.2 匹配
9.3 互异代表系统
9.4 稳定婚姻
9.5 练习题
第10章 组合设计
10.1 模运算
10.2 区组设计
10.3 Steiner三元系统
10.4 拉丁方
10.5 练习题
第11章 图论导引
11.1 基本性质
11.2 欧拉迹
11.3 Hamilton路径和Hamilton圈
11.4 二分多重图
11.5 树
11.6 Shsnnon开关游戏
11.7 再论树
11.8 练习题
第12章 有向图及网络
12.1 有向图
12.2 网络
12.3 练习题
第13章 再论图
第14章 Polya计数法
练习题的答案与提示
参考文献
索引
Sep 9

  数学不仅揭示真理,也给人极度的美感——如同雕塑般的冷艳与严肃。这种美不需要利用人性的弱点,也不需要绘画或音乐那样华丽的包装。它是极其纯洁的,就完美性而言只有最伟大的艺术才能与之相比。

——罗素(Russel),1902

Sep 9

  20世纪90年代美国数学界掀起了微积分教学改革的浪潮,其目的是教会学生自己思考与解决实质性问题,而不仅仅是背诵公式与进行机械的代数操作。本书有类似的但更大的目标,意在引导你进行数学思考与体验独立知识发现的惊喜。我们选择的话题——数论,尤其适合我们的意图。自然数1,2,3,……具有多种漂亮的模式与关系,其中许多可谓一目了然,但其余的是如此难以捉摸以致人们诧异它们是否被真正引起注意。数学实验仅需要纸与笔,但基于少量例子作出的猜想可能是错误的。一个人最终确信他的数值例子反映了一般真理需要有说服力的例证。本书将引导你通过潜伏鲜艳数论花朵的丛林,同时鼓励你去调查、分析、猜测与最终证明你自己的美妙数论结果。

  本书初稿用作布朗大学Jeff Hoffstein教授在20世纪90年代早期建立的课程Math 42的教材。课程Math 42用于吸引那些对标准微积分系列课程兴趣不大的非理科专业学生,同时说服他们去学习一些大学数学,目的在于创建一个类似于“莫扎特(Mozart)的音乐”或“伊丽莎白女王时代的戏剧”课程,引导听众通过对某一特殊方面的系统学习而对整体上的主题与方法有所了解。课程Math 42取得了极大的成功,既吸引了它拟定的读者群也吸引了想听点不同于传统的大讲座或压缩饼干式课程的理科大学生。

  阅读本书需要的预备知识很少。熟悉高中代数是必要的,而会编写计算机程序的读者将会从产生大量的数据和执行各种算法获得乐趣,但实际上读者仅需一个简单的计算器。微积分的一些概念有时被提到,但基本上不怎么用它。尽管如此,我们仍要提醒读者,要想真正欣赏数论,必须有渴求知识和探索问题的愿望,不怕做试验,不怕犯错误并从中吸取教训,有面对挫折的勇气以及坚持到最后胜利的恒心与毅力。具备这些素质的读者将在学习数论以及欣赏生活方面有较大的回报。

Sep 9

 

译者序
中文版序
前言
引言
第1章  什么是数论
第2章  勾股数组
第3章  勾股数组与单位圆
第4章  高次幂之和与费马大定理
第5章  整除性与最大公因数
第6章  线性方程与最大公因数
第7章  因数分解与算术基本定理
第8章  同余式
第9章  同余式、幂与费马小定理
第10章  同余式、幂与欧拉公式
第11章  欧拉必函数与中国剩余定理
第12章  素数
第13章  素数计数
第14章  梅森素数
第15章  梅森素数与完全数
第16章  幂模m与逐次平方法
第17章  计算模m的k次根
第18章  幂、根与不可破密码
第19章  素性测试与卡米歇尔数
第20章  欧拉φ函数与因数和
第21章  幂模p与原根
第22章  原根与指标
第23章  模p平方剩余
第24章  -1是模p平方剩余吗?2呢
第25章  二次互反律
第26章  哪些素数可表成两个平方数之和
第27章  哪些数能表成两个平方数之和
第28章  方程X4+Y4=Z4
第29章  再论三角平方数
第30章  佩尔方程
第31章  丢番图逼近
第32章  丢番图逼近与佩尔方程
第33章  数论与虚数
第34章  高斯整数与唯一因子分解
第35章  无理数与超越数
第36章  二项式系数与帕斯卡三角形
第37章  斐波那契兔子问题与线性递归序列
第38章  Ο,多美的一个函数
第39章  连分数的混乱世界
第40章  连分数、平方根与佩尔方程
第41章  生成函数
第42章  幂和
第43章  三次曲线与椭圆曲线
第44章  有少量有理点的椭圆曲线
第45章  椭圆曲线上模p的点
第46章  模p的挠点系与不好的素数
第47章  亏量界与模性模式
第48章  椭圆曲线与费马大定理
附录A  小合数的分解
附录B  6000以下的素数表
参考文献
索引
Sep 8

 

目录  · · · · · ·

前言
符号表
何谓数论
第1章 整数
1.1 数和序列    良序性质    丢番图逼近
1.2 和与积
1.3 数学归纳法
1.4 斐波那契数
1.5 整除性  1.若c|a,c|b,则c|(ma+nb)  带余除法a=bq+r  用良序性质证明带余除法  用q=[a/b],r=a-b[a/b]来证明关于最大整数函数的一个有用的性质
第2章 整数的表示法和运算
 2.1 整数的表示法
 2.2 整数的计算机运算
 2.3 整数运算的复杂度
第3章 素数和最大公因子
3.1 素数    最基本的素性检验是试除法
3.2 素数的分布
3.3 最大公因子  互素  (a+cb,b)=(a,b)  线性组合ma+nb,基于1.5整除性的1  最大公因子是线性组合中最小的正整数(基于良序性质)的证明  两两互素
3.4 欧几里得算法  拉梅定理
3.5 算术基本定理
3.6 因子分解法和费马数  奇数n=ab=s^2-t^2  费马数Fn=2^(2^n)+1的每个素因子都形如2^(n+2)k+1  费马数互素  F0F1F2···Fn-1=Fn-2
3.7 线性丢番图方程  d=(a,b),若d|c,则ax+by=c有无穷整数解
第4章 同余
 4.1 同余引言  m|(a-b),则a和b模m同余,记a≡b(mod m)  定理4.4 ac≡bc(mod m),d=(c,m),则a≡b(mod m/d)    
(c,m)=1,且ac≡bc(mod m),则a≡b(mod m)  a≡b(mod m1),···,则a≡b(mod [m1,m2,···,mk])
 4.2 线性同余方程
 4.3 中国剩余定理
 4.4 求解多项式同余方程
 4.5 线性同余方程组
 4.6 利用波拉德方法分解整数
第5章 同余的应用
 5.1 整除性检验
 5.2 万年历
5.3 循环赛赛程
5.4 散列函数
5.5 校验位
第6章 特殊的同余式
6.1 威尔逊定理和费马小定理
6.2 伪素数
6.3 欧拉定理
第7章 乘性函数
7.1 欧拉函数
7.2 因子和与因子个数
7.3 完全数和梅森素数
7.4 莫比乌斯反演
第8章 密码学
8.1 字符密码
8.2 分组密码和流密码
8.3 取幂密码
8.4 公钥密码
8.5 背包密码
8.6 密码协议及应用
第9章 原根
9.1 整数的阶和原根
9.2 素数的原根
9.3 原根的存在性
9.4 指数的算术
9.5 用整数的阶和原根进行素性检验
9.6 通用指数
第10章 原根与整数的阶的应用
 10.1 伪随机数
 10.2 埃尔伽莫密码系统
 10.3 电话线缆绞接中的一个应用 
第11章 二次剩余
 11.1 二次剩余与二次非剩余
……
第12章 十进制分数与连分数
第13章 某些非线性丢番图方程
第14章 高斯整数
附录
参考文献
Sep 7

曾拥有同样笑容的我们

也已经过几度岁月

来不及欣赏过眼即逝的景色

挣扎着生存

舍去多余的自尊

温柔对待世界 wow

I gotta say

即使故作坚强

也无法独自生存

那天的约定

仍深刻内心深处

As life goes on

因为无法忘怀 yeah

Don't let it go

这广阔大地上的所有伙伴

Sep 5

何谓数论


人们研究数论是为了理解信息加密系统

数论是数学的一个分支,研究一类特殊数的性质和相互关系。

在数论所研究的数当中,最重要的是正整数集合。更具体地说,特别重要的是素数,即那些没有大于1并且小于自身的正因子的正整数。

数论的一个很重要的结果表明,素数是正整数的乘法结构的基石。这个叫做算术基本定理的结果告诉我们,每个正整数可以按递增次序唯一地写成素数的乘积。

整数


良序性质 每个非空的正整数集合都有一个最小元。这是能够帮助我们证明关于整数集合的许多结果的一个基本性质。

丢番图逼近 so what...

整数序列百科全书(The Encyclopedia of Integer Sequences).在网上可以找到这个清单的一个扩展版本和一个程序,可以用来寻找与输入的几个起始项匹配的序列。

数学归纳原理是证明与整数有关的结果的一个有效工具

整除性 一个整数可以被另一个整数整除的概念在数论中处于中心地位。

整数的表示法和运算


每个正整数都可以被表示为b的不同幂次的和,b被称为展开式的基(base)或根(radix)。我们称基为10的表示,为十进制(decimal)表示。基为2的表示被称为二进制(binary)表示,基为8的表示被称为八进制(octal)表示,基为16的表示被称为十六进制(hexadecimal)表示,或者简称为hex。系数aj被称为展开式的位(digit)。在计算机术语中二进制数字被称为比特(bit,是英文binary digit的缩写)

高精度(multiple precision)算法

素数和最大公因子


《Proofs from THE BOOK》 专门收录一些特别有洞察力,特别巧妙的证明的书。

最基本的素性检验是试除法,它是素数当且仅当它不能被任何一个小于sqrt(n)的素数整除。

如果两个整数a,b的最大公因子(a,b)=1,那么这两个数就被称为互素的。

当将两个整数除以它们的最大公因子后,我们将得到两个互素的整数。

两个不全为零的整数a,b的最大公因子是a,b线性组合最小的正整数

如果整数a,b互素,那么存在整数m,n使得ma+nb=1。

如果a,b是正整数,那么所有a,b线性组合与所有(a,b)倍数构成的集合相同。

Sep 1

  

仰望天空

唯有悲伤的歌声

和苍白的哀叹 回荡耳边

温柔洁白的光芒

却被风夺走 飘散遥远彼方

不再逃避 我已下定决心

留伴身边 感受你的温柔

不再移开目光

全部包容心胸

若这就是刺痛的真实

与你一同前行

直至那扭曲堵塞的

星之扉的另一方···

雨声不息

那是血红的雨滴

无法忆起 被其掩盖的足音

若伸手轻触你的指尖

便能感觉到 你的心跳

牵起你的手 再不放开

将你永远照亮 用这星辰之光

只要你展开双臂

一定会有所改变

因为 那就是真实

不要离我而去

留在我的身边

愿为你打开这扇星之扉

不再移开目光

全部包容心胸

若这就是刺痛的真实

与你一同前行

直至那扭曲堵塞的

星之扉的另一方···