作者归档:admin

2017年中山大学运动会环校长跑和100米

  本文地址:http://sokoban.ws/blog/?p=3888 上一次参加校运会是2015年,去年没有参加。10月28日碰见学院书记,他对我说:杨超你要报名校运会。于是我就又一次报名100米。 11月19日,早上7点起床。8点到达中大北门。今年的环校长跑路线略有改变,距离长了一点点达到2公里。但这种集体慢跑速度起不来,相当于散步。 开幕式后,11点参加了100米。第二次参加校运会100米,成绩为15秒13,比前年还慢。平时很少练这种短距离全力冲刺跑,感觉就是难以积极调动力量和摆腿频率。

发表在 健身 | 留下评论

跑步总结:第八个半年

  本文地址:http://sokoban.ws/blog/?p=3868 最近六个月跑量如下: 2017年5月:36公里(珠海4周+广州10k+别克10k) 2017年6月:30公里(珠海5周) 2017年7月:0公里 2017年8月:5公里(环合肥翡翠湖) 2017年9月:0公里 2017年10月:25公里(下班跑回家1.5k共5次+校园中轴线3k+英东体育场5k共3次) 半年合计:96公里 体重变化如下: 经过一个学期珠海跑步,6月底体重降到60公斤以下。7月底59公斤左右;8月底60+公斤;国庆长假后一度63+公斤;10月底62+公斤。 手表 两个GPS手表已经坏了多时,今年的跑步几乎全部都是使用手机APP虎扑跑步来记录。 于是,10月又买了个100多元的EZON石英表,福建产,只具备一般的跑表功能。另有电波校时功能,能接受商丘授时中心的信号,在23层楼顶测试手动校时成功(石英表已经极其准了,校时一次就可以长时间关闭每天自动电波校时功能)。之前使用过卡西欧的日本电波表,才知道原来我们也有民用电波授时。  

发表在 健身 | 留下评论

关卡无限大的推箱子

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=3853 通常我们玩的推箱子关卡都是有限大小的,一般不超过50×50。因为最近读了不少关于不可判定(undecidable)问题的文章,很自然就问这样一个问题:我们已经知道有限大小的推箱子问题是可判定的,且知道其计算复杂度为PSPACE-complete;若考虑无限大小的推箱子关卡,即关卡占据整个平面,允许有可数无限个(countable)箱子和目标点,那么问题是不是也变成了不可判定的? 比较著名的不可判定问题有: 图灵机的停机问题; 希尔伯特的Entscheidungsproblem问题,即一阶谓词逻辑系统的判定问题; 王浩瓷砖(Wang Tile)问题; 希尔伯特第十问题,即判定丢番图问题是否有解; 计算Busy Beaver数; 元胞自动机(Cellular Automata)的可逆性; ……等等。 现在,我们可以给这个列表又添加一个新问题:无限大小的推箱子问题。这个结论,早在1997年,Culberson证明推箱子是PSPACE完全问题时,就顺带指出了。因为Culberson的证明就是用推箱子关卡来模拟图灵机,从而把LBA问题(线性空间的图灵机)归约为推箱子问题。在往前走一步,自然任何一个潜在无限长纸带的图灵机也可以用占满整个平面的无限大小的推箱子关卡来模拟,从而把停机问题归约为推箱子问题。 这就证明了关卡无限大的推箱子是不可判定的。Culberson甚至指出,若限制只有有限个箱子没有归位(其余可数个箱子一开始都处于目标点),问题仍然是不可判定的,或者说是不可计算的。 这从另外一个方面也体现了推箱子有多难。      

发表在 推箱子, 数学, 计算机 | 留下评论

王浩瓷砖(Wang Tile)

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=3795 王浩(Hao Wang)是著名的美籍华人数学家、逻辑学家、哲学家。他1921年生于山东济南,1943年毕业于西南联合大学,1948年在美国哈佛大学获得哲学博士学位,1995年在美国纽约逝世。王浩是哥德尔(Kurt Gödel)的好朋友。创立了NP完全理论、证明了SAT是第一个NP完全问题的著名计算机学家Stephen Cook,则是王浩的学生。 王浩(1921-1995) 为了研究一阶谓词逻辑的可判定性问题(即希尔伯特的Entscheidungsproblem问题),1961年,王浩提出了瓷砖问题,后来被他的学生Robert Berger称为王浩瓷砖(Wang Tile)问题。任意给定一组有限个正方形的瓷砖,每个瓷砖的每条边都用一种颜色标记。用这组瓷砖去铺整个平面,每种瓷砖都有无限的供给。要求铺设时,任意两块瓷砖相邻的边的颜色要相同。并且,只允许瓷砖平移,不能够旋转或者镜面反射。王浩问:能否用这组瓷砖平铺整个无限的平面? 如下图是一组13个正方形的王浩瓷砖。 如下图那样平铺。 自王浩在1961年提出瓷砖问题,直到今天还引出许多研究。可以说这是一个非常有趣而深刻的问题。 一开始,王浩猜测,任意给定一组瓷砖,要么可以铺满整个平面,并且一定有一种周期的平铺方案;要么不能平铺整个平面。如果这个猜测是对的,那就意味着存在一个确定性的算法去判别每一组王浩瓷砖是否可以铺满整个平面。 王浩还发现了王浩瓷砖可以用来模拟图灵机。由此,王浩证明了,若对王浩瓷砖问题作出一些限制,如原点必须铺某一块瓷砖,或是坐标轴上的瓷砖预先铺设好等等,则王浩瓷砖问题是不可判定的(undecidable)。即不存在确定的算法去回答平铺是否能够实现。 从可计算性和计算复杂度看来,王浩瓷砖问题远远难于PSPACE完全的推箱子问题(Sokoban)。因为王浩瓷砖问题是不可计算的。而推箱子问题是可计算的,而且在可计算的问题里面,推箱子问题也远还不是最难的。 不久,1964年,王浩的学生Robert Berger在其博士论文The Undecidability of the Domino Problem中证明了即使没有对原点或是坐标轴的限制,王浩瓷砖问题(无限制的王浩瓷砖问题又被称为domino problem)也还是不可判定的。Robert Berger的博士论文还发表在1965年的Memoirs of the American Mathematical Society。 为了证明domino problem是不可判定的,Robert Berger也构造出第一组只有非周期铺满方案(aperiodic tiling)平面的王浩瓷砖。但是,这组瓷砖由惊人的20426个瓷砖组成。这也否定了王浩认为总是存在周期性的铺满方案的猜测。 也就是说,不可判定的证明主要基于两个核心事实:一是只能非周期铺满平面的王浩瓷砖组(an aperiodic set of Wang … 继续阅读

发表在 数学, 计算机 | 留下评论

量子计算机能快速求解推箱子关卡吗?

  作者:杨超 本文地址:http://sokoban.ws/blog/?p=3757 量子计算机常被大众媒体描述得十分神奇,甚至有科学家也添油加醋,如 David Deutsch 的 The Fabric of Reality 一书。用量子计算机能设计出快速求解推箱子关卡的算法吗?我在读了David Deutsch的书后,对此问题颇感兴趣。这个月,阅读了不少相关文献,找到了答案。答案是否定的。 首先,制造出通用的量子计算机仍然有极大的工程技术困难。 第二,再看看理论上,量子算法能干什么。最有名的量子算法就是Peter Shor的整数分解算法,这一算法使得基于大数分解比较困难的公钥加密算法岌岌可危。Shor的算法是1994年提出(Shor因此获得哥德尔奖Godel Prize),历史也没有太长。想要知道这一算法与传统计算机算法有何不同,可读Scott Aaronson的博文 《Shor, I’ll do it》。Scott Aaronson生于1981年,才36岁,是德州大学奥斯汀分校的教授,在理论计算机科学特别是计算复杂度理论方面有非常高的造诣。他博文中对Shor算法的核心解释得深入浅出。关键是整数分解还是有某种规律,量子算法恰恰能更好地利用这一规律,一定程度上避免了暴力穷举。 要注意的是,整数分解并非特别难的问题。在基于传统计算机(图灵机)的计算复杂度理论中,整数分解被认为不属于P,但也只是比P问题略难一些,介于P和NP-Complete之间,且更靠近P。因此,量子算法能快速分解大数也只是情理之中。 知道量子算法是怎么做的,能做什么,就更好地理解量子算法不能做什么。Scott Aaronson博客的站名banner位置有这么一段话,澄清大众对量子计算的误解: If you take just one piece of information from this blog: Quantum computers would … 继续阅读

发表在 推箱子, 数学, 算法, 计算机 | 留下评论

读书笔记(十七)再读 The Theory of Almost Everything

  本文地址:http://sokoban.ws/blog/?p=3747 读了费曼的《QED:The Strange Theory of Light and Matter》之后,非常有兴趣地把 The Theory of Almost Everything 这本我读过的 Kindle 书再读一遍。虽然此书之前读过并写了读书笔记,这次再读,很多内容毫无印象。可能上次一目十行读得太快,也可能是读完费曼的书后,之前读不懂的地方现在读懂了。读不懂当然印象不深。 总的来说,The Theory of Almost Everything 一书力图把理论物理中的数学尽可能浅显的解释清楚,读了之后不但对基础物理有更多的了解,而且对数学也能有更深的认识;对理论物理和数学之间的联系也会有新的体会。 虽然一开始重读爱不释手,读到最后两章(第11、12章)也索然无味了,花了四天的零散时间,虎头蛇尾读完第二遍。的确是温故而知新,比第一遍的收获更多。下面简单罗列12章的内容。 第1章,介绍经典物理学中物质和场的观点。如气体对容器的压力是由气体分子无规则运动造成。牛顿的引力场和麦克斯韦的经典电磁场的概念。 第2章,介绍狭义相对论中时间和空间融合为时空。又介绍物理中对称性和守恒的联系。 第3章,介绍薛定谔方程和量子力学的产生,可解释元素周期表和化学变化。 第4章,光有粒子特性,爱因斯坦解释光电效应的工作得到诺贝尔物理奖。反之,电子也有场的特性,甚至C60分子都有衍射现象。作者不厌其烦的重复阐述的量子力学的概率的世界观,区别于牛顿的机械世界观。这是一个重要的现代物理主流观点。自由意志由此成为可能? 第5章,狄拉克的理论预言正电子。介绍费曼的QED理论。 第6章,介绍施温格的理论,被戴森证明和费曼的QED等价。费曼、施温格和一个日本人因此获得诺贝尔物理奖。不管是费曼的理论,还是施温格理论,他们建立的相对量子场论(relativistic quantum field theory)都是有悖常识、难以理解的(即其数学理论只是描述了事件发生的概率)。这和牛顿力学与拉格朗日力学所体现出不同的物理哲学有类似之处。 第7章,云室或对撞机实验中,大量新粒子的发现。 第8章,盖尔曼提出夸克模型。丁肇中发现Charm夸克(第四种夸克)是夸克模型一大重要支持,因此得诺贝尔物理奖。关于强相互作用的QCD因此建立。 第9章,作者又花了许多笔墨解释了如何人为的建立一个类似于QED、QCD的相对量子场论(relativistic quantum field theory)。关于弱相互作用的相对量子场论就是这样建立的。弱相互作用主要体现有:beta裂变、太阳核聚变等等。QED和弱相互作用还能统一成一个相对量子场论,这工作也得到了诺贝尔物理学奖。 第10章,至此,可以复述完整的标准模型理论。该理论缺点:怎么有10多个人为的常数?为何恰有三组基本费米子(up、down夸克、电子、中微子是一组)?但基本和宇宙学的发现吻合。另介绍了我们所在世界的一大重要现象:宇称不守恒。杨振宁、李政道因此得诺贝尔物理学奖,吴健雄做实验证实。 … 继续阅读

发表在 读书 | 留下评论

读书笔记(十六)QED – The Strange Theory of Light and Matter

  本文地址:http://sokoban.ws/blog/?p=3732 量子电动力学(QED)是基本粒子的标准模型(Standard Model of Particles)中最先发展成熟的学问。后来的量子色动力学(QCD)也是参照QED发展起来的。早就听说诺贝尔物理奖得主费曼(1918-1988)的QED – The Strange Theory of Light and Matter 是一本经典之作,这两天终于花点时间读完,对标准模型(SM)的理解又深入了一些。此书写于1985年,但由于这理论早已很成熟,可能还没有能超越此书的科普性的读物。 费曼首先在第一章介绍了他的物理哲学。他认为自然(Nature)是难以理解的,量子电动力学能非常好地描述自然,并且和精心设计的无数实验惊人的吻合。但是很多时候只能以概率的方式预测,比如说4%的光子被玻璃反射,96%的光子会透过玻璃。但具体到一个光子究竟是反射还是穿透,无法预测。他认为自然就是这样,荒诞无法理解。QED原则上能解释所有电磁现象,包括基于此的化学、生物学等等。 第二章和第三章分别介绍了光子和电子。介绍了在各种现象如反射、衍射等等,QED是如何计算的,其中的困难在哪里,还简单提及了重整化(Renormalization)。计算的困难在于用费曼图(Feynman diagram)来展示的各种潜在的情况太多。这样的一套理论也难怪会出现平行宇宙的解释,虽然费曼不持这种观点。 第四章总结了一下QED理论的缺陷。又略提及了强弱相互作用以及引力的理论。 作为补充,又略读了之前下载过的另一诺贝尔物理奖得主Frank Wilczek发表在2000年8月Physics Today期刊上的QCD Made Simple一文。  

发表在 读书 | 留下评论

庆祝推箱子比赛第一百期

  本文地址:http://sokoban.ws/blog/?p=3720 我们的推箱子比赛举办了第100期,可喜可贺。为此,anian特别邀请20603设计了主关,副关也是丹麦DrFogh为100期特别设计的。 除此之外,anian还另外特别设计了《百花齐放》关卡。关卡发到sokoban.org, 长期有效,欢迎大家提交答案。这个关卡代表了一种特殊的类型,就是用推箱子来模拟另外一个orimaze的游戏,且模拟得相当紧凑。 我又邀请了青年漫画家小矛为100期画了新的墙纸。小矛在2012年也为我们设计过一张墙纸。两张墙纸都可以在这里下载。

发表在 推箱子 | 留下评论

写在推箱子比赛第一百期之际

  本文地址:http://sokoban.ws/blog/?p=3627 作者:杨超 接触推箱子这个游戏已经近20年,发起在线推箱子比赛至今已8年有余。比赛每月一期,现在正进行第100期。由于这个比赛,使得我业余持续地关注推箱子游戏,并且推箱子游戏也持续地给我带来很大的乐趣。趁着第一百期之际,谈谈推箱子是什么,以及推箱子给我所带来的精神上的快乐。 一、推箱子是什么? 推箱子是一种成本极其低的智力消遣活动。早在推箱子出现之前,姜长英在1949年《论消遣》一文就分析过平民化的科学消遣的好处。最近看到《三联生活周刊》特约作者“土摩托”袁越在新浪微博问答中也表达了类似的观点:“……精神追求的成本越来越低了……我觉得这才是人类的未来,因为这是一种低成本满足所有人的唯一方式……”。 所以,以推箱子为爱好的朋友是非常幸福的,这玩意几乎不需要花钱。因为推箱子是一款纯软件产品。只要一个计算机系统足够开放和普遍,它上面一定会出现优秀且免费的推箱子软件,如Windows系统,如安卓系统。即便比较封闭的系统,如掌上游戏机、电子词典、电视机、机顶盒等等,都会出现推箱子。 我们举办网上的推箱子比赛的服务器成本也相当低。两个域名(sokoban.cn 和 sokoban.ws)加上租用服务器虚拟空间,平均每个月只要约28元,只相当吃一顿快餐。这么低的成本就可以把分散在全国乃至全世界各地的顶尖推箱子爱好者聚在一起,举办全世界水平最高的推箱子比赛,可算奇迹了。 这主要还是得益于电子计算机和互联网的快速发展。就最近来说,触屏式的智能手机只用了不到十年,就发展得非常成熟了,几乎取代了台式电脑,成为人们上网的主要设备。就我自己而言,微信等APP已经成为我获取信息的最重要渠道之一。很多跑步活动的信息我都是最先从微信获得,甚至就在微信中完成报名的。 因此,2014年7月,比赛网站也开通了微信订阅号,主要推送比赛开始等相关信息。继《推箱子加加》之后,愉翁又为安卓平台发布了《推箱快手》这款功能强大的APP。而苹果手机因系统较为封闭,虽是智能手机的引领者,却一直未见优秀的推箱子软件出现在该平台。 二、推箱子给我带来的快乐 下面罗列一些在推箱子中得到的快乐,其中很多事情做成了之后当时能高兴好几天。 为了测试各种平台下的推箱子,尝试了不同的操作系统。特别是编译运行了早期Linux平台下的XSokoban。为此至少连续使用了三年Linux的一个发行版Ubuntu作为平时工作生活的主要桌面系统。近三四年又以苹果的macOS X为主要的工作系统,因此对三大桌面系统Windows, macOS, Linux都算是比较熟悉了。甚至连PC-BSD, Solaris等非主流系统都安装试运行过几次。有了在不同的操作系统下的使用经验,对什么是操作系统的理解,比以前只会使用Windows时有了更深的认识。最近anian又告知有一款相当不错的Linux下KDE桌面的推箱子Sokoban SG,尚没有时间和精力测试。 学习并使用了多种编程语言。使用得比较多的语言是C、JavaScript、PHP。比较满意且花的功夫比较多的是用C编写的USokoban,用JavaScript编写的HTML5浏览器平台下的SokoPlayer HTML5,以及用服务器端编程语言PHP编写的比赛网站sokoban.cn以及关卡分享平台sokoban.org等。其它还尝试过写Firefox浏览器插件,用Python也写了一个简单的推箱子等等。后来因跑步和小孩出生,没有太多业余时间写程序了,但有些程序至今还时不时需要维护,如在第99期比赛时,还修正了比赛网站的一个bug:对副关的答案没有做“至少一推”的检验。 学习使用LAMP技术建设网站。LAMP是比较成熟的开源建站技术,租用服务器建站成本和技术难度都不算高。但是工信部对个人建立网站的管理时紧时松,为了比赛顺利进行,我还是在2011年初按工信部规定为比赛网站备了案。一开始只注册了sokoban.ws这个差强人意的域名,后来又注册到sokoban.cn和sokoban.org两个域名真是喜出望外。对整个互联网是如何运转的也有了些更深的认识。 琢磨了一些推箱子相关的算法。写USokoban时,实现了一个简单的解关器,掌握了解关器的一些基本算法。后来为了优化SokoPlayer HTML5推一个箱子的提示和寻径,想到了运用图论中找割点的算法,大大提高了计算的速度。 研究了推箱子及其变种的计算复杂度。计算了一系列具有指数长度答案的关卡所需要的精确步数。搞明白了推箱子问题的计算复杂度为什么是PSPACE完全的,还证明了推箱子的一个新变种也是PSPACE完全的,发表在学术期刊Theoretical Computer Science上面。 此外,关于推箱子的编关和解关,我几乎没有太多研究,还有许多宝藏有待今后挖掘。可见,推箱子是可以作为一生的爱好,不断地给人带来欢乐。  

发表在 推箱子, 数学, 算法, 编程, 计算机 | 留下评论

智能电视上运行《SokoPlayer HTML5》

    本文地址:http://sokoban.ws/blog/?p=3690 昨天,在海信智能电视上安装了第三方APP,测试了安卓版《推箱子加加》。今天,2017年6月21日,进一步测试在安卓电视上安装网页浏览器。我国的有线电视生态比较特殊。之前虽然没有电视,也从新闻中隐约知道,广电总局多次打压网络机顶盒。如在2015年,广电总局发布《关于依法严厉打击非法电视网络接收设备违法犯罪活动的通知》,禁止网络机顶盒提供视频聚合类APP或硬件服务(必须有全国牌照才行,如华数、上海文广、CIBN等。我的海信电视也是通过华数提供的牌照,提供预安装的视频聚集点播服务)。于是我对智能电视系统的封闭程度如何,能否随意安装第三方APP等不是特别乐观。经过一番网络搜索调研,发现《电视家浏览器》看上去还不错。于是,便和昨天一样,通过u盘和ES文件管理器,成功安装《电视家浏览器》,访问了比赛网站 http://sokoban.cn ,并运行了《SokoPlayer HTML5》,通过遥控器上下左右控制光标,可以完美地进行游戏。下面是一些图片。 注:发现最近对比赛网站首页微调后,在 Windows 10的默认浏览器Microsoft Edge中,右侧微信和QQ二维码和中栏有覆盖重叠。没想到在这个安卓TV版《电视家浏览器》中有同样的问题。在Firefox中则显示正常。此问题有待修正。(补充:2017年7月8日,修正了这个bug,把第二栏和第三栏交换)

发表在 推箱子, 计算机 | 留下评论