Matrix67 |
2008-09-11 12:34 | 
查看更多：http://www.sciencemuseum.org.uk/images/I046/10314758.aspx
Aug
20
Daisuke Minematsu和他的同学们发现，Josephus问题中也隐藏着分形图形。Josephus问题是初学编程的人必然会接触到的一个问题——n个人围成一圈进行1到k报数，每次报到k的人退出游戏（离开这个圆圈），那么最后剩下的那个人是谁。在这里，我们考虑一个Josephus问题的变种：双向Josephus问题。双向Josephus问题中有两个交替进行的报数进程，其中一个按顺时针方向踢出每第k个人，另一个进程则逆时针踢出每第k个人。两个进程交替进行，直到最后只剩一人为止。假如n=10, k=3的话，第一个退出的人是#3，第二个退出的人是#8，第三个退出的人是#6，以后分别是4, 10, 9, 5, 1, 7，最后剩下的人是2。我们用S(n,k)来表示在相应的n值和k值的情况下最后剩下的那个人的编号，对于每个固定的k值，函数S的图象竟然都是一个分形图形。右图是S(n,4)所对应的图象，你可以非常清楚地看到这个图象的自相似性。你可以自己用Mathematica来验证一下。
Aug
6
Apr
22
Stetson大学的一个非常可爱的MM（以后本Blog将简称她为Stetson MM）和我分享了一个很神奇的东西。她们正在做一个线性代数的课题研究，题目的大致意思是“用矩阵来构造分形图形”。Stetson MM叫我试着做下面这个实验：对于一个坐标点(x,y)，定义下面4个矩阵变换：
然后，初始时令(x,y)等于(0,0)，按照 T1 - 85%, T2 - 6%, T3 - 8%, T4 - 1% 的概率，随机选择一个变换对该点进行操作，生成的点就是新的(x,y)；把它画在图上后，再重复刚才的操作，并一直这样做下去。我心里觉得奇怪，这为什么会得到分形图形呢？于是我写了一个简单的Mathematica程序：
list = {{0, 0}};
last = {{0}, {0}};
For[i = 0, i < 50000, i++, r = Random[];
If[r < 0.85, last = {{0.83, 0.03}, {-0.03, 0.86}}.last + {{0}, {1.5}},
If[r < 0.91, last = {{0.2, -0.25}, {0.21, 0.23}}.last + {{0}, {1.5}},
If[r < 0.99, last = {{-0.15, 0.27}, {0.25, 0.26}}.last + {{0}, {0.45}},
last = {{0, 0}, {0, 0.17}}.last + {{0}, {0}}
]
]
];
list = Append[list, First[Transpose[last]]];
]
ListPlot[list, PlotStyle -> PointSize[0.002]]
程序运行的结果真的是令我大吃一惊：竟然真的是一个分形图形！！我不禁再次对数学产生了一种崇敬和畏惧感！！
Feb
15
今年一月份，California的一个数学艺术展览会上出现了这样一种神奇的三维图形。放出图片之前，你能根据下面的文字描述想象出这个图形的样子吗？
给定一个单位大小的立方体，在其中5个面的中心放置一个边长为1/2的小立方体；这5个小立方体中的每一个都有5个面露在外面，在这25个面中的每一个面中心再向外拼接一个边长为1/4的小立方体；然后每个1/4小立方体的5个暴露在外的面上再放置1/8大小的立方体……不断迭代下去后，最终会形成一个什么样的三维图形？
上图就是按照要求迭代11次的样子，里面那个斜着放的红色立方体是最初的那个单位立方体，外面拼接了5个橙色立方体，每个橙色立方体外面又拼接了5个黄绿黄绿的小立方体……最终的形状大致是一个四棱锥，上面有很多三角形的洞，这些被挖去的部分恰好组成了最经典的分形图形——Sierpinski三角形。这是由艺术家Robert Fathauer发现的，在展览上的名字叫做Fractal Crystal No.1。
查看更多：http://www.bridgesmathart.org/art-exhibits/jmm08/
Feb
6
Menger海绵(Menger Sponge)是三维空间中的经典分形图形，是Sierpinski地毯的三维扩展，最先由数学家Karl Menger提出。它的构造完全仿照Sierpinski地毯的构造方法，只是把平面上的地毯改成了空间中的海绵：把立方体分成27个小立方体，挖掉每一面中心和整个立方体中心共7个小立方体，对剩下的20个立方体递归地进行操作。它的Hausdorff维度为(ln20)/(ln3)，约等于2.726833。你能想象出它的截面是什么样子的吗？偶然发现这样一个奇图，发上来与大家分享：
图片来源：http://flickr.com/photos/sbprzd/1432723128/
Jan
12
SETI@home可以在杂乱的射电数据中搜寻独特的讯号，你能在大街上的嘈杂声中清晰分辨出一个尖细的女声大叫“亚美蝶”。这些现象都表明，有时对集合里的所有元素进行整体考察可以很快找出我们所要找的个体。去年我们搞合唱比赛时，我又想到了一个绝佳的例子：你可以在合唱声中清楚地听到是否有人跑调。考虑这样一个问题，假如合唱团里有一个人唱歌始终走调，但我听不出来是谁走调，只能听出当前正在唱歌的人中是否有唱走调了的人。那么，我如何才能迅速地揪出那个唱走调的人？利用经典二分法，我们可以在log2(n)次合唱后找出唱走调了的人。每一次，我都把剩下的人平均分成两组，然后选其中一组来合唱：如果听不到走调的声音，这一组的人就全部过关；如果听到有人走调，那另一组里的人都可以被排除了。递归地对剩下的组进行同样的操作，log2(n)次操作后必定可以找出那个唱歌走调的人。
现在的问题变得有些麻烦了。假如我们知道合唱队里有一个人唱歌爱跑调，但他不是总会跑调。具体地说，他只有1/2的概率唱错，但其余1/2的时间里他却唱得很准。现在，传统的二分法不再适用了，因为没有走调声已经不能起到排除的作用了。你能想出多少种可行的算法来找出那个人？下面提出一些可行的方法，你认为哪种方法更好？你能求出这些算法所需要的检测次数的期望值各是多少吗？
1. 不断地随机生成一个大小为n/2的子集并对其进行检测，直到某次不能通过检测为止，然后递归地对其进行操作。
2. 所选的子集大小为n/2是最优的吗？把上面这种方法的n/2改成n/a，常数a的最优值是多少？
3. 检测次数的期望值还可以更小吗？我们想到，每次都重新生成一个新的集合其实并不科学，新集合本身是否包含老鼠屎也是得碰碰运气的。因此，对方法1的一个合理改进是：把集合平均划分为两个部分，交替对它们进行检测直到某次检测没通过为止，然后对该组递归操作下去。这种方法真的比前两种好吗？它所需要的期望次数是多少？
4. 尝试对方法3进行改进。如果把集合平均划分成3份并循环进行检测，效果会不会更好一些？
1. 选取的子集有1/2的概率覆盖了我们要找的那个人，子集里有他而他这次恰好又唱走调了则有1/4的概率。因此，不管规模有多大，平均需要4次才能把规模缩小一半。因此，检测次数的期望值为4*log2(n)。为了方便比较期望值的大小，后面的答案我们一律表示成一个常数乘以log2(n)的形式。
2. 类似地，平均需要2a次检测才能把规模缩小到原来的1/a，因此总共花费的检测次数为2a*log2(n)/log2(a)。对函数求导，可得当a为e时函数值达到最小。此时的检测次数期望值为2e*log2(n)/log2(e)≈3.7683 * log2(n)。
3. 这个就经典了。设方法3里把规模缩小一半所需要的检测的期望次数为m，下面我们来看m应该等于多少。把n个人平均分成两组，我们要找的老鼠屎有1/2的概率在第一组，有1/2的概率在第二组。因此，第一次就测出问题来有1/4的可能，第二次就测出问题也有1/4的可能。对于剩下的1/2种情况，局面变得又和最开始一样，只是平均需要的检测次数比原来多了2。根据期望值的定义，有m=(1/4)*1 + (1/4)*2 + (1/2)*(m+2)，解得m=3.5。总的检测次数就是3.5 * log2(n)，它比前面两种方法都要好。你可能不同意上面求m的方法。这没啥，如果你不断对m进行迭代，你会发现展开出来的式子就是最标准的期望值定义。
4. 类似地，有m=(1/6)*1 + (1/6)*2 + (1/6)*3 + (1/2)*(m+3)，解得m=5。于是，把规模缩小到原来的1/3平均需要5次检测，总的检测次数为5*log2(n)/log2(3)≈3.1546 * log2(n)。
题目来源：IBM Ponder This Dec07
原文还从熵的角度探寻了问题的最优算法，感兴趣的读者可以去看一看
Jan
9
从2007年分形艺术大赛(Benoit Mandelbrot Fractal Art Contest)中选了几个自己感觉不错的图与大家分享。
图片按以下三个原则来选取：
1. 严格符合分形图形的定义
2. 与以往的分形图形风格很不一样
3. 很好看:)
查看全部获奖作品：http://www.fractalartcontests.com/2007/winners.php
查看全部参赛作品：http://www.fractalartcontests.com/2007/entries.php
