Matrix67 |
2007-10-31 15:57 | 
三角运算(%i1) trigexpand(sin(10*x+y));
(%o1) cos(10 x) sin(y) + sin(10 x) cos(y)
(%i2) trigexpand(sin(2*x));
(%o2) 2 cos(x) sin(x)
(%i3) trigsimp(2*cos(x)^2+sin(x)^2);
2
(%o3) cos (x) + 1
(%i4) trigreduce(-sin(x)^2+3*cos(x)^2+x);
cos(2 x) cos(2 x) 1 1
(%o4) -------- + 3 (-------- + -) + x - -
2 2 2 2
代数推理(%i1) assume(x>0,y<-1,z>=0);
(%o1) [x > 0, y < - 1, z >= 0]
(%i2) assume(a<b and b<c);
(%o2) [b > a, c > b]
(%i3) facts();
(%o3) [x > 0, - 1 > y, z >= 0, b > a, c > b]
(%i4) is(a>c);
(%o4) false
(%i5) is(z-y>0);
(%o5) true
(%i6) is(z-x>0);
Maxima was unable to evaluate the predicate:
z - x > 0
-- an error. Quitting. To debug this try debugmode(true);
(%i7) prederror:false;
(%o7) false
(%i8) is(z-x>0);
(%o8) unknown
(%i9) forget(a<b);
(%o9) [b > a]
(%i10) is(a>c);
(%o10) unknown
级数计算(%i1) sum(i,i,1,5);
(%o1) 15
(%i2) sum(i^2,i,1,5);
(%o2) 55
(%i3) sum(1/2^i,i,1,inf);
inf
====
\ 1
(%o3) > --
/ i
==== 2
i = 1
(%i4) sum(1/2^i,i,1,inf),simpsum;
(%o4) 1
(%i5) sum(1/i^2,i,1,inf),simpsum;
2
%pi
(%o5) ----
6
(%i6) sum(1/i,i,1,inf),simpsum;
(%o6) inf
微积分(%i1) limit(1/x,x,inf);
(%o1) 0
(%i2) limit(sin(x)/x,x,0);
(%o2) 1
(%i3) limit(sin(x),x,inf);
(%o3) ind
(%i4) diff(3*x^2+x+5/x,x);
5
(%o4) 6 x - -- + 1
2
x
(%i5) diff(sin(x)*tan(x),x);
2
(%o5) cos(x) tan(x) + sec (x) sin(x)
(%i6) diff(%e^(a*x),x);
a x
(%o6) a %e
(%i7) integrate(sin(x)^3,x);
3
cos (x)
(%o7) ------- - cos(x)
3
(%i8) integrate(x^3,x,1,3);
(%o8) 20
(%i9) taylor(%e^x,x,0,3);
2 3
x x
(%o9)/T/ 1 + x + -- + -- + . . .
2 6
(%i10) taylor(sin(x),x,0,5);
3 5
x x
(%o10)/T/ x - -- + --- + . . .
6 120
(%i11) taylor(sqrt(x+1),x,1,3);
2 3
sqrt(2) (x - 1) sqrt(2) (x - 1) sqrt(2) (x - 1)
(%o11)/T/ sqrt(2) + --------------- - ---------------- + ----------------
4 32 128
+ . . .
(%i12) ratsimp(%);
3 2
sqrt(2) x - 7 sqrt(2) x + 43 sqrt(2) x + 91 sqrt(2)
(%o12) -----------------------------------------------------
128
矩阵运算(%i1) f[i,j]:=i+j;
(%o1) f := i + j
i, j
(%i2) genmatrix(f,3,3);
[ 2 3 4 ]
[ ]
(%o2) [ 3 4 5 ]
[ ]
[ 4 5 6 ]
(%i3) g[i,j]:=i-2^j;
j
(%o3) g := i - 2
i, j
(%i4) genmatrix(g,3,3);
[ - 1 - 3 - 7 ]
[ ]
(%o4) [ 0 - 2 - 6 ]
[ ]
[ 1 - 1 - 5 ]
(%i5) %o2+%o4;
[ 1 0 - 3 ]
[ ]
(%o5) [ 3 2 - 1 ]
[ ]
[ 5 4 1 ]
(%i6) %o2.%o4;
[ 2 - 16 - 52 ]
[ ]
(%o6) [ 2 - 22 - 70 ]
[ ]
[ 2 - 28 - 88 ]
(%i7) %o2^^3;
[ 360 474 588 ]
[ ]
(%o7) [ 474 624 774 ]
[ ]
[ 588 774 960 ]
(%i8) x:matrix([17, 3],[-8, 11]);
[ 17 3 ]
(%o8) [ ]
[ - 8 11 ]
(%i9) x^^-1;
[ 11 3 ]
[ --- - --- ]
[ 211 211 ]
(%o9) [ ]
[ 8 17 ]
[ --- --- ]
[ 211 211 ]
想了解更多请阅读官方文档：
http://maxima.sourceforge.net/docs/manual/en/maxima.html
做人要厚道
转贴请注明出处
这个Blog里曾经多次提到过超强数学软件Mathematica，但目前为止我还没发现它的Linux版，Wine似乎也没有用。其实，在Linux下也有很多类似于Mathematica的数学软件，其中Maxima是我用的最多的一个。这里简单介绍一下Maxima的各个函数供大家参考，也方便我自己今后查询。
安装：sudo apt-get install maxima maxima-share
运行：maxima
退出：quit();
基本运算(%i1) 2+3;
(%o1) 5
(%i2) 5*6;
(%o2) 30
(%i3) %+2;
(%o3) 32
(%i4) %o1*%o3;
(%o4) 160
(%i5) 4/7+3/4;
37
(%o5) --
28
(%i6) float(%);
(%o6) 1.321428571428571
(%i7) 2^32;
(%o7) 4294967296
(%i8) 30!;
(%o8) 265252859812191058636308480000000
(%i9) float(sqrt(2));
(%o9) 1.414213562373095
三角函数和对数函数(%i1) float(sin(1));
(%o1) 0.8414709848079
(%i2) sin(%pi/2);
(%o2) 1
(%i3) sin(%pi/2)+cos(%pi/3);
3
(%o3) -
2
(%i4) float(sec(%pi/3)+csc(%pi/3));
(%o4) 3.154700538379252
(%i5) log(1);
(%o5) 0
(%i6) float(log(10));
(%o6) 2.302585092994046
(%i7) log(%e);
(%o7) 1
(%i8) log(2^a);
(%o8) log(2) a
(%i9) %e^log(2);
(%o9) 2
变量操作(%i1) a^2-b^2;
2 2
(%o1) a - b
(%i2) a:3;
(%o2) 3
(%i3) a^2-b^2;
2
(%o3) 9 - b
(%i4) b:2;
(%o4) 2
(%i5) a^2-b^2;
(%o5) 5
(%i6) kill(a);
(%o6) done
(%i7) kill(b);
(%o7) done
(%i8) a^2-b^2;
2 2
(%o8) a - b
函数操作(%i1) f(x):=x^2-1;
2
(%o1) f(x) := x - 1
(%i2) f(2);
(%o2) 3
(%i3) f(100);
(%o3) 9999
(%i4) float(f(2/3));
(%o4) - 0.55555555555556
(%i5) a:4/5;
4
(%o5) -
5
(%i6) f(a);
9
(%o6) - --
25
多项式运算（展开、合并、化简和消元）(%i1) expand((a+b)^3);
3 2 2 3
(%o1) b + 3 a b + 3 a b + a
(%i2) factor(a^2-b^2);
(%o2) - (b - a) (b + a)
(%i3) ratsimp((x^2-1)/(x+1));
(%o3) x - 1
(%i4) eliminate([x^2+x*y+z=0,3*x+5*y+z=0,x-y-2*z^2=1],[y,z]);
4 3 2
(%o4) [- x (8 x - 2 x + 19 x - 50 x + 25)]
解方程(%i1) solve(x^2-3*x+4/x=5,x);
sqrt(5) + 1 sqrt(5) - 1
(%o1) [x = - -----------, x = -----------, x = 4]
2 2
(%i2) funcsolve(f(n)*(n+1)+2*n=1-f(n)/n,f(n));
n (2 n - 1)
(%o2) f(n) = - -----------
2
n + n + 1
(%i3) solve([x+3*y=10,1/x+x*y=4],[x,y]);
sqrt(69) - 9 4 sqrt(3) sqrt(23) - 34
(%o3) [[x = 1, y = 3], [x = - ------------, y = -----------------------],
2 9 sqrt(3) sqrt(23) - 75
sqrt(69) + 9 4 sqrt(3) sqrt(23) + 34
[x = ------------, y = -----------------------]]
2 9 sqrt(3) sqrt(23) + 75
(%i4) solve(x^2+b*x+c=0,x);
2 2
sqrt(b - 4 c) + b sqrt(b - 4 c) - b
(%o4) [x = - ------------------, x = ------------------]
2 2
(%i5) find_root(x^x=2,x,1,2);
(%o5) 1.559610469462369
(%i6) find_root(sin(x)=x/2,x,0.1,%pi);
(%o6) 1.895494267033981
数论相关(%i1) mod(100,7);
(%o1) 2
(%i2) primep(3214567);
(%o2) true
(%i3) next_prime(200);
(%o3) 211
(%i4) factor(1001);
(%o4) 7 11 13
(%i5) factor(30!);
26 14 7 4 2 2
(%o5) 2 3 5 7 11 13 17 19 23 29
(%i6) gcd(200,780);
(%o6) 20
(%i7) binomial(7,4);
(%o7) 35
(%i8) fib(7);
(%o8) 13
画函数图像(%i1) plot2d(x^3+2*x^2-3,[x,-2,2]);
*** X11 output driver not found, switching to dumb terminal!
*** If you want to use the X11 output, please install the gnuplot-x11 package
14 ++-------+--------+--------+--------+-------+--------+--------+-------++
+ + + + + + x^3+2*x^2-3 $$$$$$ $
12 ++ $+
| $ |
10 ++ $ ++
| $ |
| $ |
8 ++ $ ++
| $ |
6 ++ $$ ++
| $$ |
4 ++ $$ ++
| $$ |
2 ++ $$ ++
| $$$ |
| $$ |
0 ++ $$$ ++
| $$$$ |
-2 ++$$$$$$$$$$$$$$$$$$$$$$$$$$ $$$$$ ++
$$ + + $$$$$$$$$$$$$$$$ + + + +
-4 ++-------+--------+--------+--------+-------+--------+--------+-------++
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
(%o1)
你可以通过安装gnuplot-x11让maxima在X上画图，安装方法是：sudo apt-get install gnuplot-x11
maxima也可以画3D图像，比如执行下面代码可以画出sin(x)cos(y)的图像，我就不贴图了，大家自己试试。plot3d(sin(x)*cos(y),[x,-2,2],[y,-2,2]);
做人要厚道
转贴请注明出处
今年恰逢PKU数学文化节十周年，其间开办的很多讲座我都去了。去听讲座的人好像都是数院的，我恐怕是唯一一个中文系的。考虑到我和中文系的MM没有共同话题，因此每一次听讲座时我都会顺便四处打望，看看有没有数院的美女，下来可以和她“交谈”一下。有趣的是我的做法与常人所想的恰好相反：据说数院的已经盯上中文系的MM了，而我一个中文系的竟然反过来去找数院的MM。
昨天有一个关于非欧几何的讲座，这是目前所有的讲座中最为精彩的一次。讲座里提到了Poincaré的一个双曲几何模型，感觉非常有意思，在这里和大家分享一下。
在所有的双曲几何模型中，Poincaré的圆盘模型可能是最有趣的一个。这个双曲世界存在于一个有限的平面区域里，整个世界限制在一个单位圆的范围内。这个世界中有两个最重要的物理定律：一，假如某物体X离原点O距离为d，那么该物体的温度为1-d^2；二，物体的大小与温度成正比。这样，假如某个人从这个世界的中心走向边缘，那么他的温度会从1慢慢变成0，同时整个人慢慢变小。他自身大小改变的同时周围的物体也等比例地放大或缩小，而这个世界里的人视野有限，看不见远处的东西，因此他不会觉得自己变小了或者变大了。因此，在这个世界里，物理学家们能够很轻易地发现第一定律，但要发现第二定律则非常具有挑战性，探索第二定律的过程必然很曲折，并且很可能出现哥白尼时代的故事。
对于我们来说，这个世界是有界的；但对于这个世界中的人来说，这个世界是无穷大的。因为离原点越远，人就越小，于是相对来说他们所看到的空间也就越大。当人的位置趋于边界时，物体大小趋于0，此时的空间将变得无穷大，因此这个世界中的物体永远无法到达边界。同时，离原点越远的话越接近“绝对零度”，这将非常不适宜生物的生存，因此人们大多居住在原点，离原点越远城市规模越小，更远的地方则完全没有开发过，只适合于疯狂的冒险家进行极限运动。于是这个世界中的物理学家很自然地得到这个结论：世界是无穷大的。
下面就神奇了。现在，考虑某个人想从A点走到B点。如果按照红色的线段直直地走过去，所走的路程并不是最短的，因为这条路线离原点较远。聪明的人会发现，我先往原点方向走一点，然后再到B点去，这样走的路程更短一些。我们猜想，最短路线很可能是一条偏向于原点的弧线（就好像原点把直线段“吸”过去了一样）。之所以产生这种奇怪的现象是因为，离原点越远物体就越小，人的步子也变小了，相对来说实际空间就变大了。因此，对我们来说距离相等的两点，对他们来说离原点越远其实际距离越大。因此，我们有必要重新定义这个双曲世界中“距离”的概念。由于物体大小与1-d^2成正比，因此我们可以定义，如果在离原点距离为d的位置上有一个充分小的位移，在我们看来距离为Δx，那么在这个世界中的实际距离就是Δx/(1-d^2)。这样就可以算出，从A到B的最近路线是一条垂直于边界的圆弧（蓝色的那条）。于是在这个世界中，“直线段”已经不再是我们熟悉的直线段了，而是一条条的弧线（还包括整个圆的直径）。而我们眼中的直线，在他们看来就是曲线。
这个世界中的几何满足欧式几何的前面四个公设，但不满足第五公设。比如，两点确定一条直线，因为过两点的圆弧只有一条垂直于这个世界的边界；而直线可以无限延长，因为离边界越近两点的实际距离越大，你永远走不到尽头。但是，这个世界不满足第五公设。从图2可以看到，过一点可以作无数条直线不与已知直线相交；从图3可以看到，三角形的内角和小于180度。下面这幅图片可以帮助你更好地理解这个双曲模型。这是该平面上的一个三角形剖分，里面的所有三角形都是等边三角形，而且所有这些三角形都是一样大的。你可以看到7个等边三角形共用一个顶点，这说明三角形的内角和小于180度。
另外值得一提的是，这个构想很适合写成一篇科幻小说。记得大刘的那篇科幻吗？一群电子器件诞生在某颗星球的内核，然后探索物理定律，历经重重困难，最终冲破了它们那个世界的“天然外壳”，看到了外面的世界，并相信我们整个宇宙也处于一个更大的星体内。这个双曲几何模型也很适合写出这样的小说来，比如以物理史书的方式叙述从古至今若干个传奇人物的故事，讲述他们是如何从一些奇怪的现象出发，通过各种试验证明自己的猜想，顶住社会各方面的压力，执著地探索宇宙的奥秘。小说中的人物可以带着读者一起进行探索，最后才告诉读者这个宇宙的本质是什么。
Matrix67原创
转贴请注明出处
来源：http://digg.com/celebrity/Pikachu_s_Vagina_Brings_Happiness_to_Children_sfw_pic
本来觉得digg上的东西到处被转载，因此不怎么发digg上的东西；没想到这次这么经典的图片居然没人转
图灵机是1936年Alan Turing提出的一个计算机模型。这种计算机由一个一维数组（或者叫磁带）构成，还有一个可以左右移动的指针。磁带上每个格子里都有一种颜色（共可从m种颜色中选择），指针本身则可以是n种状态中的一种。给定一个m*n的表格，你就定义了一个图灵机。这个表格告诉机器，如果当前指针的状态是x，它所指的格子的颜色是y，那么下一步机器应该把这个格子染成什么颜色，然后指针应该左移一位还是右移一位，指针的新状态又是什么。有了一个图灵机后，我们便可以把它当做一个计算机进行数据处理了。我们可以给这个图灵机编写一个初始状态（也就相当于现在所说的程序和数据），让它按照这个表格不断执行下去，对数据进行处理并“输出”适当的结果来。
能够模拟其它所有图灵机的图灵机叫做“通用图灵机”(UTM, Universal Turing Machine)。不是所有的图灵机都是通用的：很多图灵机只能完成一些特定的运算，而只有通用图灵机才能完成更一般的操作，是一台“通用的”机器。这些通用图灵机就像现代计算机一样，可以用来编程执行各种各样的操作，能实现现代计算机的各种功能。我们经常说一种程序语言是图灵完全的(Turing Complete)，指的就是这种语言等价于通用图灵机，能够执行任何一种复杂的数学运算。
50年代起，科学家们疯狂地寻找通用图灵机，所需要的颜色数和状态数越来越小。最好的结果是1967年由Marvin Minsky得到的，他发现了一个7,4通用图灵机，即一个只需要7种状态，4种颜色的通用图灵机。人们开始好奇，最简单的通用图灵机是什么样子的。2002年，Stephen Wolfram（没错，就是MathWorld的那个Wolfram）做出了一个重大的突破：他发现了一个2,5通用图灵机，并且给出了一个很可能是通用图灵机的2,3图灵机。很早以前人们就证明了，不存在2,2的通用图灵机；因此如果Wolfram提出的2,3图灵机是通用图灵机的话，它就是最小的通用图灵机了。但Wolfram始终不能证明这个2,3图灵机是通用的，于是在今年三月份用25000美元悬赏征解。
昨天，英国伯明翰大学的一名20岁在校大学生Alex Smith提交了一篇55页的论文，证明了Wolfram的2,3图灵机与另一个已知的通用机器等价，从而证明了2,3图灵机是最简单的通用图灵机，证实了这个很早就已经提出的猜想，解决了长期以来计算机科学界的一大疑问。这是一个意义非常重大的突破，无疑是信息学界中的一件激动人心的大事。
做人要厚道 转贴请注明出处
新闻来源：来源1 来源2
除了字符串匹配、查找回文串、查找重复子串等经典问题以外，日常生活中我们还会遇到其它一些怪异的字符串问题。比如，有时我们需要知道给定的两个字符串“有多像”，换句话说两个字符串的相似度是多少。1965年，俄国科学家Vladimir Levenshtein给字符串相似度做出了一个明确的定义叫做Levenshtein距离，我们通常叫它“编辑距离”。字符串A到B的编辑距离是指，只用插入、删除和替换三种操作，最少需要多少步可以把A变成B。例如，从FAME到GATE需要两步（两次替换），从GAME到ACM则需要三步（删除G和E再添加C）。Levenshtein给出了编辑距离的一般求法，就是大家都非常熟悉的经典动态规划问题。
在自然语言处理中，这个概念非常重要，例如我们可以根据这个定义开发出一套半自动的校对系统：查找出一篇文章里所有不在字典里的单词，然后对于每个单词，列出字典里与它的Levenshtein距离小于某个数n的单词，让用户选择正确的那一个。n通常取到2或者3，或者更好地，取该单词长度的1/4等等。这个想法倒不错，但算法的效率成了新的难题：查字典好办，建一个Trie树即可；但怎样才能快速在字典里找出最相近的单词呢？这个问题难就难在，Levenshtein的定义可以是单词任意位置上的操作，似乎不遍历字典是不可能完成的。现在很多软件都有拼写检查的功能，提出更正建议的速度是很快的。它们到底是怎么做的呢？1973年，Burkhard和Keller提出的BK树有效地解决了这个问题。这个数据结构强就强在，它初步解决了一个看似不可能的问题，而其原理非常简单。
首先，我们观察Levenshtein距离的性质。令d(x,y)表示字符串x到y的Levenshtein距离，那么显然：
1. d(x,y) = 0 当且仅当 x=y （Levenshtein距离为0 <==> 字符串相等）
2. d(x,y) = d(y,x) （从x变到y的最少步数就是从y变到x的最少步数）
3. d(x,y) + d(y,z) >= d(x,z) （从x变到z所需的步数不会超过x先变成y再变成z的步数）
最后这一个性质叫做三角形不等式。就好像一个三角形一样，两边之和必然大于第三边。给某个集合内的元素定义一个二元的“距离函数”，如果这个距离函数同时满足上面说的三个性质，我们就称它为“度量空间”。我们的三维空间就是一个典型的度量空间，它的距离函数就是点对的直线距离。度量空间还有很多，比如Manhattan距离，图论中的最短路，当然还有这里提到的Levenshtein距离。就好像并查集对所有等价关系都适用一样，BK树可以用于任何一个度量空间。
建树的过程有些类似于Trie。首先我们随便找一个单词作为根（比如GAME）。以后插入一个单词时首先计算单词与根的Levenshtein距离：如果这个距离值是该节点处头一次出现，建立一个新的儿子节点；否则沿着对应的边递归下去。例如，我们插入单词FAME，它与GAME的距离为1，于是新建一个儿子，连一条标号为1的边；下一次插入GAIN，算得它与GAME的距离为2，于是放在编号为2的边下。再下次我们插入GATE，它与GAME距离为1，于是沿着那条编号为1的边下去，递归地插入到FAME所在子树；GATE与FAME的距离为2，于是把GATE放在FAME节点下，边的编号为2。
查询操作异常方便。如果我们需要返回与错误单词距离不超过n的单词，这个错误单词与树根所对应的单词距离为d，那么接下来我们只需要递归地考虑编号在d-n到d+n范围内的边所连接的子树。由于n通常很小，因此每次与某个节点进行比较时都可以排除很多子树。
举个例子，假如我们输入一个GAIE，程序发现它不在字典中。现在，我们想返回字典中所有与GAIE距离为1的单词。我们首先将GAIE与树根进行比较，得到的距离d=1。由于Levenshtein距离满足三角形不等式，因此现在所有离GAME距离超过2的单词全部可以排除了。比如，以AIM为根的子树到GAME的距离都是3，而GAME和GAIE之间的距离是1，那么AIM及其子树到GAIE的距离至少都是2。于是，现在程序只需要沿着标号范围在1-1到1+1里的边继续走下去。我们继续计算GAIE和FAME的距离，发现它为2，于是继续沿标号在1和3之间的边前进。遍历结束后回到GAME的第二个节点，发现GAIE和GAIN距离为1，输出GAIN并继续沿编号为1或2的边递归下去（那条编号为4的边连接的子树又被排除掉了）……
实践表明，一次查询所遍历的节点不会超过所有节点的5%到8%，两次查询则一般不会17-25%，效率远远超过暴力枚举。适当进行缓存，减小Levenshtein距离常数n可以使算法效率更高。
Matrix67原创
做人要厚道 转贴请注明出处
看看下面两道题，它的解答非常简单，即使没学过信息学的人也可以想到答案。你能在多短的时间内想出问题的算法来？一小时？一分钟？一秒钟？
1. 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
2. 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法运算。
Solution:
1. 遍历链表，给每个元素赋一个0到1之间的随机数作为权重（像Treap一样），最后取出权重最大的k个元素。你可以用一个堆来维护当前最大的k个数。
2. 从前往后扫一遍，然后从后往前再扫一遍。也就是说，线性时间构造两个新数组，P[i]=A[1]*A[2]*...*A[i]，Q[i]=A[n]*A[n-1]*...*A[i]。于是，B[i]=P[i-1]*Q[i+1]。
突然想到，给别人(MM?)介绍信息学时，用这两道题当例子挺合适的。
