分类目录归档:数学与算法

数学与算法

SICP 读书笔记 - 构造抽象数据

SICP中的基础抽象数据与本科看过的一本算法书中提到的ADT有异曲同工之妙,即对数据用过程进行封装,数据的具体表现形式隐藏在过程接口下,用SICP的原话,这叫“抽象屏障”。如此,可以在保持操作接口不变的情况下,调整内部的数据实现形式。

相对于基础抽象数据与后面的带标志数据,让人震撼的是后面的数据导向的程序设计,这完全就是“代码确定规则,数据实现策略”的真实写照。即将由于程序属于一种逻辑范畴,一旦固定便难以只执行一种特定逻辑的局限性,通过数据(易调整,易加,易减)对程序进行边界扩展。用SICP中的原话:“可加性”,即可扩展性。目前,这种设计范式还不是特别熟悉,只是偶尔用一下,但其精髓还需要学习。

采用数据导向设计风格将通用型操作的系统实现了一把,在实现复数时看到TCP/IP协议栈分层的影子,由于SICP在80年代初即已在MIT作为教案被使用,因此可见分层思想影响之深远。其分层思路为:由于复数有两种形式(例如协调栈中某层有多种协议),因此,在打上复数标记“complex”前,需要将其具体复数类型(rectangular还是polar)打上。这样在查找操作表时,可由复数找到相关的复数计算,然后由具体复数类型找到其具体的计算方式。

在通用型操作的系统实现中,还发现了一个特殊的设计,但书中并没有着重强调,觉得这个设计也是数据导向设计的精髓之处:即操作所需要的参数类型作为查表中的维度。即二维表中:第一维是操作类型名,第二维是操作参数类型列表;两维确定唯一的操作过程。

后续添加扩展操作时,由数据导向设计带来的“可加性”之震撼,对得起近三个月晚上都献给SICP。读到后续的扩展跨类型操作时,看到“强制”策略,不免想到流式计算系统TM中使用ChunkFile向RefFile强制转换的策略。即进行跨类型操作时,可将“低“层次类型转换为”高“层次类型,这样就可以采取统一的操作进行处理(前提是类型间存在继承关系)。

后面提到的猜想:对类型的通用型操作处理,在没有知识表示与自动推理的帮助下,仅仅通过程序设计语言很难办到。首先,不清楚这里的知识表示与自动推理的准确定义是什么,不过看到这里,想到了公司最近在做的项目:类SQL-【ANTLR】->C++完成复杂统计报表的表达与计算是否在理论上就有障碍。

SICP 读书笔记 - 构造过程抽象

一、求平方根问题
 
虽然,以前使用递归解决过问题,但从未像使用scheme一样,如此直观地编写递归过程。
这也是一种自上而下地分解问题、解决问题的思维方式,即将一个复杂的问题按过程进行拆解。
递归求解问题,需要有一种接近解和结束递归的机制,否则计算过程将无限地递归下去。
接近解的机制是由数据性质决定的,即按照(y+x/y)/2递归下去,将无限地从x/2接近x的平方根;
而这个问题比较有意思的是,结束解的方式:
第一种,也是最容易想到的方式就是比较当前解与上一次解之间的差值,差值越小说明越接近解,因此可以取一个极小数作为阀值,如0.0001,当差值小于此阀值时,即表示可以接受当前解作为待求的平方根。
换句话说,这是一种用绝对距离来判断当前解是否接近真实解。从字面上也可以理解,绝对距离只针对某一区域有效。比如,如果求0.00001的平方根,那么很明显用0.0001这个绝对距离去度量针对0.00001的平方根的前后两次解,是不准确的(粒度太大)。因为由于接近解的分布非常密集,以至于任意相邻两个解的距离都会大于0.0001,从而无法得到较精确的解。
按理说,求一个大数,如果采用0.0001作为阀值终止计算,应该是可以了,实际是也存在问题。
原因就在于计算机实质是一种离散模型计算,这就导致计算机在表达实数集合时,只能妥协地采取地离散化表示。
即计算计中的浮点数(符号位:阶数:尾数)无法像数轴一样将所有的实数表达出来,对于大的浮点数,由于尾数数位有限,能将整数部分表达出来就错了,有时可能整数部分都要截断。
因此,如果一个数的平方根恰好为 计算机无法表达的数字,且其前后相邻的浮点数差值又大于0.0001,或甚至相差的都是整数部分,而非小数部分(小数表达不出来了)。这样,在递归计算时,可能就会在真实值左右来回计算,前后两次差值永远不会小于阀值。
仅从数学上说,一个绝对的阀值只会影响一侧的实数集计算,
即任意选一个数作为阀值,只会影响比其更小数的求解,但由于计算机的限制,对大数也产生了影响。
那么如何才能避免这个问题呢?
这时就体现了数学的魅力,我不用绝对距离,因为绝对距离只适用于特定区域。
由于上述公式是无限地逼近,相邻数之间的距离会越来越近,即(y1-y2)越来越小,同时由于上面推理我们知道这个差值会在实数的两个端相对于固定阀值不是太小就是太大。但无论你在哪个区域,如果快要接近解时,相对于那个区域的数值而言,变化会越来越小。即取其变化率:|y1-y2|/y1,即当前相对于上一个解变化了多少。以此来作为判断递归终止就将上述两个问题FIX掉了。

二、分钱问题

这是在讲树型递归过程的一个例子,即其递归计算过程展开平面上像一棵树一样,而且树中存在重复计算过程。
实际上就是动态规划中的0-1背包高级算法问题,但在SICP中却用来讲递归计算过程,可见SICP的高度。
SICP中有一句话,觉得算是解决分钱问题的核心思想:
“递归地归约为对更少的钱或更少的硬币种类的问题”
具体为将任何一种分钱分钱划分为两个集合:
1. 采用除x类型硬币外,其它硬币来分钱y
2. 采用所有各类的硬币,来分钱y-(x),其中(x)代表x类型硬币的面额,即先使用x类型硬币分了一次,剩下的钱再进行分
这样,每次剩下的钱再用上述这两个步骤进行计算,一直递归下去。
如同Fibonacci递归一样:
对问题进行递归拆解,但最后都必须要进行退化处理,否则会一直递归拆解下去。
即什么是终点,终点的计算值是多少。
对于分钱问题而言,由于有两个变量,即当前硬币种类k,和剩余的钱y。
那么枚举来看,无非有:
k >0 && y=0,这时是钱已分完,但还剩下几种类型硬币没用,算一种分法,所以应该返回1
k >0 && y<0,  这时是钱不仅分完,而且还出现负数,即上一种硬币分钱时,钱根本不够分的,所以这种分法失败,返回0
k >0 && y>0,  这时表示分钱还没进行完,需要继续应用上述递归算法
k =0 && y=0,  这时表示,硬币类型也用完了,钱也分完了,算一种分法,所以返回1
k =0 && y<0,  这时表示,硬币类型用完了,但上一次分钱失败,返回0
k =0 && y>0,  这时表示,硬币类型用完了,但钱也没分返回,即这种分法失败,返回0
k <0             ,这时表示,不管还有没有钱,硬币类型上次就没有了,分钱失败,返回0
即退化处理条件归纳为:
if k < 0,返回0
else
   y = 0,返回1
   y < 0,返回0
另外一个需要分析的是书中对硬币类型的处理,其原话是
“过程first-denomination以可用的硬币种数作为输入,返回第一种硬币的币值。这里认为硬币已经从最大到最小排列好了,其实采用任何顺序都可以”
 
即从上面两个递归子过程可以看出,计算关心的硬币类型x的面值|x| 和 当前剩余钱数;
同时从后面的退化处理可以看出,还关心当前还有多少种硬币类型没有使用。
因此,我们可以对硬币类型固定一个顺序,在所有的递归过程中都保持这个顺序,
这样能保证在递归树中,从根到叶子,对硬币的使用不会重复。
同时为了取到硬币的面值,书中就有了first-denomination这个函数,即在一个固定的使用顺序中:
剩余硬币类型个数 与 其将要使用的类型硬币面值 的映射关系。
这里蕴含这样一个常理:
对于一种分钱方式中采用的硬币类型,不同类型的使用顺序并不影响分钱的最终结果。
所以才有上面“采用任何顺序都可以”。

有限自动机的字符串匹配

自动机虽然是通过很多数学知识来论证其正确性,但是其原理确很简单。这里通过加回忆之前的学习,简单介绍下自动机的字符串匹配原理。自动机的字符在完成前期的工作后,其字符串的匹配时间复杂度为O(n),其中n为目标串的字符数,即自动机的匹配搜索不需要回溯,其如何完成避免回溯工作的呢? 继续阅读