小谈无限

朋友给讲了个1+2+3… = 1/12的故事…

其实没那么复杂啦,我讲个简易版的…以前写在百度空间上的文章,现在百度空间关闭了…再写一下

证明1+2+4… = -1

S = 1 + 2 + 4 + 8 …
2S = 2 + 4 + 8 … = S – 1
2S = S – 1
S = -1

这个证明的问题在于2S = S – 1, 并不仅仅有一个解-1,还有两个不明显的解,就是正负无穷大啦~

Min-cut and metric

来水一篇blog…

[link](http://ttic.uchicago.edu/~harry/teaching/pdf/lecture1.pdf)

Min-cut列出方程

$$\min \sum cap(e) \times dist(e)$$
$$dist(v,u) + dist(u, w) \ge dist(v, w)$$
$$dist(s,t) = 1$$
$$dist(v, u) = 0 or 1$$

然后松弛成LP问题

$$\min \sum cap(e) \times dist(e)$$
$$dist(v,u) + dist(u, w) \ge dist(v, w)$$
$$dist(s,t) \ge 1$$
$$dist(v, u) \ge 0$$

问题是松弛成LP问题之后,求出的解可能是分数,如何求出最小割.

方法就是把所有点按照和s点的距离排序,然后枚举前i项形成的点集形成的割,其中最小的就是最小割.

证明在给的pdf链接里面~ 这个方法可以推广到The Multicut Problem,得到一个2-approximation algorithm~

[The Multicut Problem](http://www.cs.cmu.edu/~anupamg/adv-approx/lecture18.pdf)

debian

#debian

上次折腾debian忘记留档了,又折腾了一遍…

##wifi驱动

我的本本是bcm系列,教程在这里

https://wiki.debian.org/wl

##chrome标签乱码

少字库的原因

apt-get install ttf-wqy-microhei ttf-wqy-zenhei xfonts-wqy

##桌面

gnome3在我本本上直接崩溃,可以选gnome-fallback-session,以前还挺好的,用了用感觉变成半残品.现在用xfce.