残存的骄傲

Leave a reply

记得一年级的时候，蔡诗人在讲座上愤愤不平地对台下说，“求是科学班的同学，就应该做一点有品位的研究”；记得二年级的时候，周老板在给我们单独开会时有些瞧不起地对我们说，“你们这些人，就是喜欢给自己留后路，不成功便成仁又能怎样”；记得三年级的时候，导师摇摇头对我说，“你们从来就应该是为了接受挑战而来，而不是总想着对自己有怎样怎样的好处。” 诸位老师的期望其实更可以说是一种骄傲感，一种支持我们勇往直前的骄傲感。四年一晃而过，不知多少人心中尚留有这种骄傲，或许有些人就从未有过这种骄傲。
今年初得知许多同辈人即将踏入社会，又惊闻同辈中有人奉子成婚，而自己还远没有做出离开象牙塔的打算，也庆幸家中父老早已对我形成了会读书的印象，无人摆出各种灵魂拷问。
若我全身而退，或许是不够资格在BAT当上一个一流开发者，但至少能混迹于滔滔码海，在移动互联网的风头下过上还算体面的生活。抑或凭借身怀比CS出身者更强的理论功底，手握超越数学出身者的动手能力，投奔小牛，追风热门方向，出来混个三流学者或者去做个比卖命的码农高级些的所谓研发员。再不济，回末流二线城市某大专教书，虽然不算体面甚至些许有点狼狈，但至少衣食居住无忧，工作清闲而无波澜……

然而正是因为这种骄傲，我不甘于这样终其一生；也正因为这种骄傲，注定了我不愿意成为那种只求无过不求有功的螺丝钉——这个社会最不缺的就是螺丝钉。
记得导师在我面前多次提起，他觉得现在的年轻人常常眼高手低。这种骄傲的最大威胁，并非来自于那些被认为碾压众人的同辈们——在我看来他们不过是偏序集中的极大元，而我和他们很可能根本就不在一个链上面，因此丝毫也没有什么可以自卑。而更重要的是是否有充足的底气来支撑这种骄傲。

丘成桐说，“假如你不準備做好的科學家，就永遠也做不了一個好的科學家。不過是不是講，你想做一個好的科學家，你就可以做個好的科學家呢？當然不是，你還要有很多其他的因素在裏面”。

除了某人说的所谓天分与运气，剩下该做的也许无非就是多做些习题，多认真准备些讨论班，多读些论文吧……

显然，骄傲也并不是没有代价的。让人留下美好回忆的时光总是短暂的，毕竟不是所有人都愿意冒风险去面对未来的不确定性，更何况是在没有任何承诺和预期的情况下。显然，杰米扬的汤并不招人喜欢。在骄傲的鞭策之外，即使是无畏地坚持，我仍然会坚持吧。

点集拓扑笔记（一）

Leave a reply

1.关于拓扑基（Basis）的定义

$S$ 的一个子集族 $\mathcal{B}$ ，也就是a collection of subset，把一些子集拿出来作为一个集合（亦即 $\mathcal{P}(S)$ 的子集）。是一个拓扑基(Basis)当且仅当其满足下列条件：

任意 $S$ 中的元素 $x$ ， $\mathcal{B}$ 中都可以找到一个子集 $B$ ，使得 $x$ 在 $B$ 中。
$\mathcal{B}$ 任意两个元素 $B_1, B_2$ ，在它们交集 $B_1 \cap B_2$ 中的任何一个元素 $x$ ，都可以在 $\mathcal{B}$ 中找到一个子集 $B'$ ，这个子集 $B' \subset B_1 \cap B_2$ ，并且 $x$ 在 $B'$ 中。

由这个基生成的拓扑 $\mathcal{T}$ ，是由如下方式定义的开集组成的：

一个集合 $X$ 如果是开集，当且仅当其中每一个元素 $x$ ，在 $\mathcal{B}$ 中都能找到一个 $S$ 的子集 $B$ ，使得 $B \subset X$ ，且 $x \in B$ 。

有的定义中会说，把基中任意元素（即那些 $S$ 的子集）拿出来取并，再把所有这些并作为开集，得到的就是基生成的拓扑。这个定义其实跟上面的是等价的。对于满足上面定义的开集 $X$ ，我们它里面把每个元素 $x$ 对应的那些子集 $B$ 拿出来取并集，就得到了 $X$ ，因为每个 $B$ 都包含在 $X$ 里面，并起来不会超出 $X$ 的范围，而且 $X$ 中的每个元素都被覆盖到了。对于满足这个定义的那些开集 $X$ ，我取了一些基中元素并起来得到 $X$ ， $X$ 里面每一个元素 $x$ 肯定属于我取的某一个基中元素 $B$ ，因为取了并集，所以 $B$ 里面的所有元素都被并进了 $X$ 里面，所以 $B$ 也必然包含在 $X$ 里面。

Introduction To Galois Theory 复习笔记

Leave a reply

打算开始跟Cousera上面的HSE的Introduction To Galois Theory了，用某些人的话说就是在这里立一个flag，督促自己坚持下去。去年自己在SCW的讨论班上太水了实在有点对不起宋神，要是SCW亲自带肯定要把我赶跑。

第0篇先复习整理一下一些定义

P.S.俄罗斯大妈的英语听的实在有些难受……

Ring（环）: A set R with operation '+' and '*' with:

$(R,+)$ is an abelian group （阿贝尔群/交换群）
$(R,*)$ is a monoid （幺半群）
'*' is distributive （分配律）with respect to '+'

其中第二条也就是把group去掉可逆的性质。

最简单的例子就是整数集合 $\mathbb{Z}$ ，在我们通常意义的加法和乘法下，在不引入余数和分数的情况下 $3\div 2$ 的结果是没有定义。

An ideal (理想) I of a ring R

ideal在ring里面的地位相当于subgroup在group里面的地位，因为我们考虑一般的ring，'*'不一定是communicative的，所以有left ideal和right ideal之分。

A left idea I of a ring R: A subset I of R

$(I, +)$ is a subgroup of $(R, +)$
$\forall i \in I, r \in R$ , $r*i \in I$

Archlinux下Nginx、PHP配置

Leave a reply

pacman -S nginx php php-fpm

1	pacman -S nginx php php-fpm

修改nginx配置文件/etc/nginx/nginx.conf

    server {
        listen       80;
        server_name  localhost;

        #charset koi8-r;

        #access_log  logs/host.access.log  main;

        location / {
            root   /usr/share/nginx/html;
           #index  index.html index.html index.php
            index  index.html index.html index.php;
        }

        #error_page  404              /404.html;

        # redirect server error pages to the static page /50x.html
        #
        error_page   500 502 503 504  /50x.html;
        location = /50x.html {
            root   /usr/share/nginx/html;
        }

        # proxy the PHP scripts to Apache listening on 127.0.0.1:80
        #
        #location ~ \.php$ {
        #    proxy_pass   http://127.0.0.1;
        #}

        # pass the PHP scripts to FastCGI server listening on 127.0.0.1:9000
        #
        location ~ \.php$ {
	   #root           html;
            root           /usr/share/nginx/html;
	   #fastcgi_pass   127.0.0.1:9000
            fastcgi_pass   unix:/run/php-fpm/php-fpm.sock;	    
            fastcgi_index  index.php;
	    fastcgi_param  SCRIPT_FILENAME  $document_root$fastcgi_script_name;
	   #fastcgi_param  SCRIPT_FILENAME  /scripts$fastcgi_script_name;
            include        fastcgi_params;
        }

        # deny access to .htaccess files, if Apache's document root
        # concurs with nginx's one
        #
        #location ~ /\.ht {
        #    deny  all;
        #}
    }

server {

listen 80;

server_name localhost;

#charset koi8-r;

#access_log logs/host.access.log main;

location / {

root /usr/share/nginx/html;

#index index.html index.html index.php

index index.html index.html index.php;

}

#error_page 404 /404.html;

# redirect server error pages to the static page /50x.html

error_page 500 502 503 504 /50x.html;

location = /50x.html {

root /usr/share/nginx/html;

}

# proxy the PHP scripts to Apache listening on 127.0.0.1:80

#location ~ \.php$ {

# proxy_pass http://127.0.0.1;

# pass the PHP scripts to FastCGI server listening on 127.0.0.1:9000

location ~ \.php$ {

#root html;

root /usr/share/nginx/html;

#fastcgi_pass 127.0.0.1:9000

fastcgi_pass unix:/run/php-fpm/php-fpm.sock;

fastcgi_index index.php;

fastcgi_param SCRIPT_FILENAME $document_root$fastcgi_script_name;

#fastcgi_param SCRIPT_FILENAME /scripts$fastcgi_script_name;

include fastcgi_params;

}

# deny access to .htaccess files, if Apache's document root

# concurs with nginx's one

#location ~ /\.ht {

# deny all;

}

注意修改了的地方（12、34、36、39各行）都用注释保留了修改前的。

若出现File not found错误，则可能是由于34行未修改。若出现No input file specified错误，则可能是39行未修改。

修改php配置文件/etc/php/php.ini

在extension部分将

extension=gd.so
extension=mysql.so

1 2	extension=gd.so extension=mysql.so

等行之前的注释去除。

修改open_basedir路径

open_basedir = /srv/http/:/home/:/tmp/:/usr/share/pear/:/usr/share/webapps/:/usr/share/nginx/html

1	open_basedir = /srv/http/:/home/:/tmp/:/usr/share/pear/:/usr/share/webapps/:/usr/share/nginx/html

添加/usr/share/nginx/html

自动机理论学习笔记 CYK算法的python实现

Leave a reply

原载于 2013-12-13

CYK算法可以用来检验一个串是否属于某个上下文无关文法，运用了动态规划的思想，时间复杂度是 $O(n^3)$ 。

productions = {'S':{('A', 'B'),('B', 'C')},'A':{('B', 'A')},'B':{('C','C')},'C':{('A','B')}}
string = ['a','b','a','b','a', 'a']
l = len(string)
table = [[{'-'} for i in range(l)] for i in range(l)]
table[0][0] = {'A','C'}
table[1][1] = {'B'}
table[2][2] = {'A','C'}
table[3][3] = {'B'}
table[4][4] = {'A','C'}
table[5][5] = {'A', 'C'}
def get_entry(i, j):
    global table
    if(table[i][j]!={'-'}):
        return table[i][j]
    table[i][j] = set()
    for k in range(j-i):
        concate = {(p1,p2) for p1 in get_entry(i, i+k) for p2 in get_entry(i+k+1, j)}
        for c in concate:
            for (s1, s2) in productions.iteritems():
                if(c in s2):
                    table[i][j] |= {s1}
    return table[i][j]; 
get_entry(0,l-1)
for i in range(l):
    for j in range(i+1):
        print table[j][l-i+j-1],
    print

productions = {'S':{('A', 'B'),('B', 'C')},'A':{('B', 'A')},'B':{('C','C')},'C':{('A','B')}}

string = ['a','b','a','b','a', 'a']

l = len(string)

table = [[{'-'} for i in range(l)] for i in range(l)]

table[0][0] = {'A','C'}

table[1][1] = {'B'}

table[2][2] = {'A','C'}

table[3][3] = {'B'}

table[4][4] = {'A','C'}

table[5][5] = {'A', 'C'}

def get_entry(i, j):

global table

if(table[i][j]!={'-'}):

return table[i][j]

table[i][j] = set()

for k in range(j-i):

concate = {(p1,p2) for p1 in get_entry(i, i+k) for p2 in get_entry(i+k+1, j)}

for c in concate:

for (s1, s2) in productions.iteritems():

if(c in s2):

table[i][j] |= {s1}

return table[i][j];

get_entry(0,l-1)

for i in range(l):

for j in range(i+1):

print table[j][l-i+j-1],

深度优先搜索中图的边

Leave a reply

原载于 2013-07-12

最后修改于 2013-10-06

注：当时应该是有人在评论中指出了本文的一个错误，于是便有了第二版的修改，不过评论估计是无法找回了。

在一些算法中我们经常需要用到DFS树的性质。我们在这里DFS中原图边的类型进行一些归纳总结，方便诸位对DFS树加深理解。

原图中的边一共分为四种类型：

(1)树边(tree edge)

搜索树中存在的边。

(2)前向边(forward edge)

将节点u与其在搜索树中的后代(descendant)v相连的非树边。

(3)后向边(back edge)

将节点u与其在搜索树中的祖先(ancestor)v相连的非树边。

(4)交叉边(cross edge)

其他不属于以上三类的边。

大家可以看到，上面四种边的定义涉及到了边与搜索树的关系。所以这里所说的原图中的边都是相对搜索树而言的，也就是说只有在搜索树确定了之后，讨论这四种边才是有意义的。

我们对无向图与有向图分别进行讨论。

1.无向图

考虑下图:

其对应的一种搜索树（森林）为：

蓝紫色带箭头的边为树边，表示的是DFS中递归调用的轨迹。由于无向图中前向边和后向边可以认为是等价的，所以红色、黄色虚线边既是前向边也是后向边。

无论以什么样的顺序进行DFS，无向图中都不会存在交叉边。例如假设4、6之间存在一条边（原图中蓝色虚线表示）。若4先于6被访问，那末，在访问4的时候，发现6没有被访问，则会于此对6进行访问，此时形成了父子关系；若6先被访问，则亦然。

边类型的判定

无向图中边类型的判定较为简单。树边就是递归调用经过的边。判断前向/后向边，则只需利用DFS记录顶点是否访问的标记。在访问某个顶点时，若发现一条边与另一个非父节点的已访问节点的相连，则这条边是后向边。

2.有向图

有向图中的情况则复杂一些。

考虑下图：

其对应的一种搜索树（森林）为：

蓝紫色边仍然是树边。此时，由于原图中(3, 1)变为了有向边，红色虚线边仅为后向边；同理，由于边(1, 4)有向，黄色虚线边仅为前向边。灰色虚线边则是交叉边。

边类型的判定

有向图中，由于边的类型较为复杂，无法直接根据顶点是否访问来进行判定。故需要维护每一个顶点的前序时间戳(Preordering)与后序时间戳(Postordering)。某个顶点的前序时间戳Pre[v]在到达这个顶点尚未进行任何操作时记录，后序时间戳Post[v]则在这个顶点访问完，弹栈之前记录。

据分析可得出以下判定规律：

(1) 递归调用轨迹边为树边。

(2) 对于非树边(u, v)，若有Pre[u]<Pre[v]且Post[u]>Post[v]，则(u, v)为前向边。

(3) 对于非树边(u, v)，若有Pre[u]>Pre[v]且Post[u]<Post[v]，则(u, v)为后向边。

(4) 对于非树边(u, v)，若有Pre[u]>Pre[v]且Post[u]>Post[v]，则(u, v)为交叉边。

(5) 不存在这样的边(u, v)，使得Pre[u]<Pre[v]且Post[u]<Post[v]。

Hello world!

1 Reply

之前本站点由于某些原因关闭了，现在找了新空间重新开放了，不过以前的文章暂时无法恢复。

以下测试一下公式与源码

#include <stdio.h>
int main()
{
  printf("Hello World!");
  return 0;
}

#include <stdio.h>

int main()

{

printf("Hello World!");

return 0;

}

$\hat{f}(\xi)=\int^{\infty}_{\infty}f(x)e^{-2\pi i x\xi}\mathrm{d}x$

时间过得好快啊，记得当年刚开始使用wordpress的时候加一个favicon还得用ftp上传到文件系统，然后手动调php代码，当时是什么都不会，只知道照葫芦画瓢，现在wordpress都可以直接在修改主题里面上传图片设置站点图标了。不过刚才给站点设置favicon的时候除了点小bug，总是提示js错误或者

There has been an error cropping your image.

1	There has been an error cropping your image.

搞了半天才发现是php-gd库没有安装……这个php-gd库具体是干什么的我也不清楚，只是知道它大概跟图像方面的有关。

Valley Of Resonance | 共鸣谷

Truth, Beauty and Justice

残存的骄傲

点集拓扑笔记（一）

1.关于拓扑基（Basis）的定义

Introduction To Galois Theory 复习笔记

Archlinux下Nginx、PHP配置

自动机理论学习笔记 CYK算法的python实现

深度优先搜索中图的边

1.无向图

Hello world!