Dih3 与 S3

Standard

Dih3是3阶二面体群,S3是3阶置换群。

二面体群是由“旋转1/n 2 Pi”和翻转生成的有2n个元素的群,如下图就是一个三阶二面体群

facetable

称旋转一次为x,翻转叫y,那么这个群由${1,x,x^2,y,y x,y x^2}$组成,而这个群与对称群S3同构:

Dih3 1 x x^2
S3 偶逆序 (1,2,3) (2,3,1) (3,2,1)
Dih3 翻转 y x y x^2 y
S3 奇逆序 (3,2,1) (1,3,2) (2,1,3)

上述对应原则是:图形翻转<->数列翻转 旋转一次<->数列向左推

当n大于3时 Dih(n) 就不和 S(n) 同构了,不过依旧是单同态的,这就是说我们依旧可以用整数n元组来表示Dih(n),这很好理解:旋转一次相当于是将整数元组整体向前推(1,2,..,n)->(2,…n,1)而反射操作则相当于是改变了元组的方向,旋转不改变相对方向,故行列式为1,反射则会,故行列式为-1

指数函数族

Standard

我们熟悉的一类函数其实就是复指数函数的组合,熟悉这种组合形式对理解这些函数的特性有很大的帮助。我从网络上摘了几个图片,文末给出出处。

注:图中的x都是复数,ln是复指数函数的反函数(因为指数函数是周期函数,所以让$$ln$$为$$e^{z}=\rho e^{\theta i} $$(限定在$$\theta <2\pi $$范围内)的反函数)

e^x = \sum_{n = 0}^{\infty} {x^n \over n!} = 1 + x + {x^2 \over 2!} + {x^3 \over 3!} + {x^4 \over 4!} + \cdots

"\begin{align}<br

图片来源:

http://en.wikipedia.org/wiki/Inverse_trigonometric_functions

http://www.efunda.com/math/exp_log/exp2trig_hyper.cfm

字符串信息的压缩——后缀自动机

Standard

前两天学习了后缀自动机,这真是个好玩的数据结构,其核心是用等价类替换原来的元素来除去冗余信息。这算是篇学习总结,内容基本是我对一些文章的重新表述,我的文笔和排版(以后一定要用latex= =)实在有待提高!

后缀自动机可以在线性的时间内解决很多字符串问题,如字符串匹配、不是子串的字典序最小的串等等

Continue reading

Dilworth 定理

Standard

今天想起高中搞算法竞赛的时候的一个题目:NOIP1999导弹拦截。当时并不明白第二问的做法为什么是正确的,现在又看了一遍离散数学书后总算知道了。这个问题的第二问是要求出一个序列最少能被多少个不上升序列覆盖,比如\((1,4,3,2,6,7)\)可以分解成\((1,4,6,7),(3),(2)\)这三段不上升序列,并且这是最少的划分,而通过Dilworth定理就可以得出这最少划分数和这个序列的最长不升子序列长度的关系,比如,在刚才这个例子中\((4,3,2)\)是最长不升子序列,它的长度也是3。

Dilworth定理更加一般的阐述了这种对应的关系,接下来介绍这个定理:

首先,定义“\(\leq\)”是一个偏序关系(例如集合的包含关系、正整数的整除关系都是偏序关系),下面的例子阐述的是\(A=(1,2,3,5,6,10,15,30,60)\),\(B=(1,2,3,4,6,8,12,24)\)以及\(C=A\cup B\)整除关于整除关系的哈斯图(从下往上看,每条连线上面的元素意味着能被下面的元素整除,并且传递关系被省略不写)

哈斯图

描述整除关系的哈斯图(图片来源

在A集合中\((30,15,5,1)\)之中任何两个元素都是“可比的”(在这个例子当中意味着一方可以被另一个整除,比如15能被5整除),我们把元素集合的这样一个子集称之为“”。而5不能被3、2整除,反之也不能,所以5和3、2是不可比的,一个反链指的是一个任何两个不同的元素都不可比的集合,比如在A中\({5,3,2}\)就是一个反链(实际上也是A种最长的反链,另外\({15,10,6}\)也是最长的反链)。集合的一个链划分指的是将集合分成若干个交为空的链,并且使得它们的并是整个集合,比如对于A集合来说\((1,5,10,30),(3,15),(2,6)\)构成了一个链划分(这个划分中链的个数是所有划分中最少的)

Dilworth定理:集合中 最长的 反链长度  等于  把集合 链划分 的 最小 链个数。

在C集合中,{8, 10, 12, 15}是个最长的反链,而C可以被链划分成 { {5, 15}, {1, 10, 30, 60}, {3, 6, 12}, {2, 4, 8, 24} }。

另外Dilworth定理也意味着:

集合中 最长的 链长度  等于  把集合 反链划分 的 最小 反链个数。(反链划分的定义和链划分类似)

现在回头看把一个序列划分成最少的不上升子序列的问题——显然,“小于等于”和“大于”关系在某全序集合A(全序意味着集合中任意元素可比)上是互补的,也就是说在偏序集\(<A,\leq>\)中的最大反链长其实就是\(<A,>>\)中的最大链长,也就是说要求出不升序划分(链最少的不升序链划分)就等于是求最长上升序列的长度!于是问题就解决了。

练习题

 

拓扑空间(Topological Space)的定义

Standard

拓扑这个词经常被我碰到,出现在各种地方:图论的拓扑排序算法、拓扑空间、拓扑学、拓扑结构、拓扑图……也经常看到书里面提到有关“拓扑”的东西,比如说欧拉给出的点数、面数、楞数的关系啦、哥尼斯堡七桥问题啦……算是对“拓扑”有一点了解。“不关心具体的属性而只关心形状的几何、很抽象的东西”这是我之前对“拓扑”的认知。 现在,我开始看《拓扑学》这本书之后,总算对“拓扑”有了一个大致的印象。

从拓扑的角度来看,一个水杯和一个“甜甜圈”是一样的(图片来自维基百科)

从拓扑的角度来看,一个水杯和一个“甜甜圈”是一样的(图片来自维基百科)

先来看看“拓扑”这个奇怪的词到底是什么——拓扑是Topo-的音译,所以想理解它的意思就一定要查Topo-这个前缀的来历!

topo-

1.

a combining form meaning “place,” “local,” used in the formation of compound words:

topography; topology.
combining form of Greek tópos place, commonplace

看来“拓扑”从希腊语tópos而来,代表地方、位置,这样就好理解了,它和空间有关系。但我们经常讲的几何(Geometry)又有什么关系呢?简而言之,几何拥有“局部”的结构,所谓局部就是拥有无穷小,而拓扑拥有全局结构。或者说,几何是连续的,而拓扑是离散。就拿上述的杯子来说,我们熟悉的几何学(在欧几里得空间内的几何学)侧重于研究它的局部——角度、长度、表面积(看起来是整体的量,但实质上是很多个面积微元的和),体积(体积微元的求和)……而从拓扑空间来看,我们就会注重研究它整体的特征——洞数、整体的连续性……实际上,我们熟悉的几何学所研究的量都是在拓扑性质的基础上定义的,也就是说拓扑性质是普通几何量的基础(没有连续性的概念我们就无法定义许多上述几何的量),因此拓扑是很抽象的。

那么,让我们看看拓扑空间究竟是怎样定义的:
一个拓扑空间是一个二元组(X,S),X是一个集合,S是由一些X的子集构成的集合,并且满足下面的性质
1.任意S的元素(X的子集)的并依然属于S.
2.有限个S的元素的交依然属于S.
3.空集和X本身属于S

通常,我们将S的元素x称之为“开集”,x在X中的补集称之为”闭集”(稍后我们会看到如果集合的元素是实数,开集就是开区间,闭集就是闭区间、如果是实数对,那么一个开区域就是开集,闭区域就是闭集)

举个例子:
另A={1,2,3,4,5,6} B={{1,2,3,4,5,6} ,{1,2,3,5,6},{1,2,3,6},{2,3,5,6},{1,3,6},{2,3,6},{2,5,6},{3,6},{2,5} ,{2} ,{5} ,∅}
那么(A,B)就是一个拓扑空间。

再举个大家熟悉的在实数轴和实数平面上的例子:

线段的交

线段的交

AB是R的一个子集,CD也是。那么(R, {AB,CD,CB,∅,R})就是一个拓扑空间

三个圆的交

三个圆的交

A、B、C是R^2的一个子集(满足不等式(x-xi)^2+(y-yi)^2<=r^2)

那么(R^2, {A,B,C,ac,ab,bc,abc,∅,R^2} )也是一个拓扑空间(注意ab是A和B的交,依此类推)

参考文献:

几何和拓扑: https://en.wikipedia.org/wiki/Geometry_and_topology

拓扑空间:https://en.wikipedia.org/wiki/Topological_space

http://dictionary.reference.com/browse/topo-?s=ts

任意多边形面积求法的证明

Standard

对于一个边不自交的多边形,其面积等于沿着顺时针或逆时针方向遍历多边形端点,每遍历到相邻两点(用向量表示)叉积模长之和的一半的绝对值。

For any polygon, the area of it is half of the sum of the modulus of all adjacents points’ cross product in clockwise or counterclockwise.

证明:

proof:

我们先来看看由一条不自交的闭合曲线围成的面积如何来求

Firstly, let we see how to compute the area of an enclosed curve (not cross itself) in 2-D.

对于“简单的图形”我们可以直接用一元积分算出来,而稍稍复杂的可以通过二重积分算出,也可以运用格林公式转化为求曲线积分。

For a ‘simple region’, we can compute its area using single variable directly. As for a complicated one, double integral can figure it out, or use green formula to convert to line integral.

正式的证明如下:

formal proof:

多边形面积求法证明

多边形面积求法证明

附:面积的严格定义见这里

PS: The rigorous defination of area see here.