分类目录归档:计算机

DjVu文档格式

  本文地址:http://sokoban.ws/blog/?p=3188 DjVu格式知道了也有很长时间,基本都是每次碰到需要打开DjVu文档,才临时下载安装一个阅读器,然后到下一次重装电脑系统前,几乎没有使用过第二次。最近才花点功夫了解这个格式的来龙去脉。 (一) DjVu是法语Déjà vu(中文意思:似曾相识、即视感)的谐音。 DjVu 是扫描纸质书实现电子化的首选格式。具有文件小、分辨率高的特点。 (二) DjVu的历史比我想象的长,是源于最早1996年由AT&T实验室开发的技术。后来格式标准被卖给了LizardTech。而LizardTech后来也被收购,成为日本Celartem公司的子公司。 (三) LizardTech 公司为了提高DjVu的竞争力,不但格式标准是公开的,而且把实现这个标准的代码也开源了。在此基础上形成了DjVuLibre这一自由软件项目。 普通用户一般只需要使用一个DjVu格式的阅读软件。DjVuLibre项目的DjVu阅读软件名为DjVuLibre DjView。因为DjVuLibre项目主要是在Linux环境开发,默认的图像界面使用x11框架。为了方便其他系统的用户,也单独发布基于Qt框架的DjVuLibre DjView,能在macOS和Windows等环境使用。 在Windows系统上,另有基于DjVuLibre DjView的WinDjView,图形界面换用更为原生Windows API。 LizardTech也发行商业版的DjVu制作软件,称为Document Express Enterprise。  

发表在 计算机, 读书 | 留下评论

Kindle Paperwhite 上运行 SokoPlayer HTML5

  本文地址:http://sokoban.ws/blog/?p=2946 亚马逊的电子阅读器Kindle Paperwhite的显示屏使用的是一种电子墨水技术,和液晶显示屏相比,有不少的优点,但也有一个缺点是刷新慢,不适合玩游戏。即便如此,Kindle Paperwhite (Kindle 系列第七代)的系统也配备了一个具有完整功能,甚至支持HTML5的浏览器。我编写的网页推箱子程序 SokoPlayer HTML5 亦可在上面运行。

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

LaTeX 排版软件系统

  本文地址:http://sokoban.ws/blog/?p=2927 TeX/LaTeX排版系统是由美国计算机学家Donald Knuth于1978年开发的,这套系统的一个长处在于复杂数学公式的输入,主要用于包括数学、计算机科学、物理等学科的学术论文的书籍的排版。我最早于2003年准备本科毕业论文时开始使用,也断断续续用了有13年了。最近才对这个系统有了更多一些的认识。一个重要的原因是 LaTeX 排版软件系统主要构成都基本属于自由软件,其发行方式更像 Linux 系统。而我大概从Win98时代才开始熟悉计算机使用,对自由软件的那一套方式比较陌生。过去几年进行了一些和推箱子游戏相关的编程,也用过一段时间Ubuntu系统,有助于我重新认识TeX/LaTeX软件系统。 首先要明确几个概念。第一个就是系统的核心:排版引擎。排版系统的引擎就好比编程语言的编译器,有许多不同的实现。包括最早的Knuth的原版TeX,早期TeX/LaTeX引擎一般把源文件(.tex文件)编译为.dvi文章,然后再转换为.ps和.pdf文件。现在感觉更多人使用的是pdfLaTeX引擎,直接把.tex文件编译为.pdf文件。 由于LaTeX系统由包括排版引擎和其他大大小小的扩展宏包等等众多软件包联合组成,所以要得到一个可以直接使用的单一软件,通常是安装某个发行版。最核心的发行版是TeX Live,其他发行版大多在TeX Live基础上再进一步打包。比如我最早使用的就是中国人维护的发行版CTeX,这一发行版对中文的支持较好。最近我又使用了另一个面向Windows系统的发行版MiKTeX,和面向Mac系统的发行版MacTeX。 第三个重要的概念就是专门面向.tex源文件的文本编辑器。一般的发行版都包含有一个tex文本编辑器。此类编辑器一般带有编译按钮,能直接调用排版引擎对源文件进行编译,并打开编译后的dvi或pdf文件。有点类似于编程语言的集成开发编译环境。CTeX发行版集成的是共享软件WinEdt,MiKTeX的默认编辑器是TeXworks,MacTeX则是TeXShop。 当然,要真正使用这套排版系统,还需要略微学习一下LeTeX的一些常用命令。就如学习编程语言一样。 由于TeX系统从一开始就设计得扩展性很强,很多学术出版商都提供不同风格的期刊论文扩展宏包。比如Elsevier出版集团就提供了基于LeTeX之上的elsarticle.cls宏包,供投稿作者使用。并且,Elsevier还要求投稿文章使用BibTeX宏包的方式来处理参考文献。BibTeX的方式是把参考文献用特定格式保存在.bib文件中,供主源文件.tex引用。我之前一直只知道用\begin{thebibliography}命令方式,把参考文献直接写在.tex源文件里面。 用BibTeX的好处就是方便于和其他文献管理软件交换数据。常见的文献管理软件有Mac系统的BibDesk、被Elsevier收购的Mendeley、还有Nature杂志推荐的ReadCube等等。 TeX系统除了善于处理数学公式,也非常善于画图。以前我一直使用PSTricks宏包,但这种方式必须先编译为ps文件,和pdfLaTeX引擎不兼容。所以,最近我又学习了一下和pdfLaTeX兼容的TikZ/PGF宏包,其功能和PSTricks一样强大。于是,2016年8月17日,我编写的《HTML5图论小工具》新增输出TikZ代码功能。  

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

围棋、推箱子和计算复杂度

  本文地址:http://sokoban.ws/blog/?p=2330 作者:杨超 这个月,2016年3月,Google 的 DeepMind 团队开发的围棋程序 AlphaGo 在韩国首都以 4:1 战胜世界冠军围棋九段李世石。早在近20年前,IBM 的国际象棋程序“深蓝”就已经战胜人类冠军。而围棋棋盘比较大,人们普遍认为人类对计算机程序的优势在围棋项目还可以保持比较长的时间。而这次 Google 团队的胜利,证明了其实开发一个战胜人类的下围棋程序并没有那么难,而是开发这样的程序没有太大的直接收益,哪怕是国际象棋和围棋这样就有悠久历史传统和广泛的群众基础和关注度的棋类。 围棋究竟有多难?我们拿它和推箱子来比较一下。恰好我刚刚完成了用三篇博文来介绍推箱子问题的计算复杂度:推箱子是PSPACE完全问题。 为了从计算复杂度方面和推箱子问题比较,我们需要准确地定义一下什么叫围棋问题。 虽然人们常说围棋的变化很多,但是无论变化有多少,终究是一个有限的数。所有有限步内能分出胜负的、没有隐藏信息、也没有运气成分的二人棋类游戏,一定有一方有必胜策略(或者必和策略)。打个比分说,19路围棋按照中国的贴目规则也许是先手有必胜策略。那么我们所说的围棋问题,就是对于任意的n x n棋盘上下的围棋,如何设计一个算法来确定究竟是先手必胜还是后手必胜?或者等价地说,先手究竟有没有必胜策略?(即这是一个回答“是”或者“否”的问题)通常的19路棋盘围棋是围棋问题的一个实例。要回答这个问题,除了穷举所有的对弈变化之外,人们暂时还没能找到其它规律来判断谁有必胜策略。对围棋而言,穷举所需要的时间随着棋盘 n 的增大,是成指数增长的。事实上,已经有文献证明,按日本规则,围棋问题是EXPTIME完全问题(见[1,2],该文章作者猜测,若按中国规则,围棋问题可能更难,成为指数空间完全问题)。也就是说,在指数时间可解的问题里面,围棋问题是最困难的其中一个。除了围棋,其它一些棋类问题如国际象棋、西洋跳棋(checkers)都被证明是EXPTIME完全问题。其中8×8棋盘的西洋跳棋在使用计算机花了近20年的穷举计算后,在2007年被证明双方都采取完美策略一定是和棋。 所以,从计算复杂度来看,包括围棋在内的许多棋类游戏比推箱子要难一个层次。计算复杂度的几个概念(EXPTIME、PSPACE、NP、P)的关系可用下图表示。虽然还没有从理论上严格证明,但是一般认为,从内到外,这四类问题的计算复杂度是严格地越来越难。 更有甚者,围棋问题的一些子问题,如征子能否成功问题在文献中被证明是PSPACE完全问题[3]。而围棋残局收官问题,则是PSPACE难的[4]。也就是说围棋问题的某些子问题就已经和推箱子问题一样难了。 那么,为什么比推箱子更难的围棋都已经开发出能战胜人类的程序,但是比围棋还容易一些的推箱子,我们却没有看到优秀的推箱子求解程序能够解出较大的、箱子数目较多的关卡呢?我想主要有以下这么一些因素。 首先,开发推箱子求解程序比开发下围棋程序更加无利可图。目前看到的一些求解程序基本都是个人单打独斗编写的,运行在个人电脑上,而且都是作为业余兴趣进行的。尚未看到有软件类企业或者研究团队投入较大资源来开发。作为对比,Google的AlphaGo程序投入了至少20人的开发团队,和李世石对战时动用了上千个CPU和GPU同时计算。 其次,AlphaGo虽然战胜了人类,但是并没有回答我们前面所定义的围棋问题,也就是说并不知道是否先手必胜。战胜人类并不需要穷遍所有变化,比判断19路围棋谁有必胜策略稍微容易一些。而一个推箱子关卡求解程序从某种意义上必须回答出推箱子问题,一般来说,必须穷遍所有路经才能判断一个关卡无解。而找到一个答案,除了穷举剪枝之外也还没有见到有人提出新的算法思路。 比较令人好奇的是,如果投入更多的人力和计算机运算资源,计算机求解推箱子能达到一个什么样的水平呢?能解出多大的关卡?解大关卡能比人解得更快吗? 第83期推箱子比赛,我们也借着这个机会,由麦英兄设计了一关AlphaGo关卡。这一关计算机能解出来吗? [参考文献] 1.  J. M. Robson, The complexity of Go, Proc. IFIP (1983) … 继续阅读

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

再谈桌面操作系统

本文地址:http://sokoban.ws/blog/?p=984 在 上篇博文谈了以Ubuntu作为常用操作系统三年的体会。还不到半年,现在又变成使用Mac OS X和Windows 7更多了。 主要原因是过去三个月,软硬件使用有下面改变: 一、以前在Ubuntu上为佳能喷墨打印机安装驱动一直未成功。在Mac OS X上系统轻松自动安装驱动。 二、重拾慢跑习惯,买了新GPS手表Nike+ Sportwatch GPS记录跑步路径、步伐和心率等。而这手表只提供Mac和Win下的软件上传手表数据至Nike+网站社区。其它如Garmin 610等手表官方均只提供Mac和Win下管理软件。 据说有第三方程序可在Linux下提取手表数据。 三、买了计步腕带Fitbit Flex,和GPS手表的目的一样,是为了提醒自己少坐多动。据其统计数字,一般15分钟内步行1300步,慢跑则2500步。这玩意同样只提供了Mac和Win的数据上传软件。 四、买了个TomTom便携式导航仪,可每季度免费升级地图,但依然只提供Mac和Win的升级管理程序。 五、买星特朗天文望远镜送TheSkyX天文软件,可在Mac或Win下安装。当然 Linux下亦有功能相仿的自由软件。 六、虽LibreOffice可满足我几乎所有工作上的文档处理需求,但为方便和同事协同工作,还是买了微软的Office 365,可安装到5台Mac或Win电脑上。

发表在 见闻, 计算机 | 留下评论

Ubuntu 使用三年感受

  http://sokoban.ws/blog/?p=956 作者:杨超 2010年9月开始使用 Ubuntu,到今天已经三年,觉得非常好用。三大桌面操作系统 Windows、Linux 和 Mac OS X 都用过相当长的一段时间,还是觉得 Ubuntu 用的最顺手。目前家里使用的电脑是 Mac OS X 和 Ubuntu 12.04 双系统,办公则用 Win7 Home 和 Ubuntut 13.04 双系统[2013年10月21日,家里及办公电脑都升级到 Ubuntu 13.10]。除了要用网银、又或者是登录学校教务系统录入成绩等必须用 IE 的时候,登录Windows系统,其余时间都用 Ubuntu 为主。 最早大概2002年的时候,我就想尝试使用 Linux 系统,买了一个盒装的 Ret Hat Linux 8.0(见下图),安装倒是成功了,但可能是有些功能不会设置或是用不习惯,还是用回了 Windows。那时还是拨号上网的时代,获取网络帮助也没有现在那么方便,我没能跨过这个障碍。 … 继续阅读

发表在 见闻, 计算机 | 留下评论