《初等算法》中文版

1,780 views
Skip to first unread message

Xinyu LIU

unread,
Apr 1, 2016, 6:46:53 AM4/1/16
to pon...@googlegroups.com
今天完成了最后附录的审校,终于完成了。

2014年7月诺基亚散伙时,我正好写完了英文版。实在没有想到竟然花了这么长时间才算完成中文版。
这期间修改了很多错误。但是仍然会有许多没有来得及改正的地方。

2015年6月我到亚马逊工作后,再也没有足够的时间能继续写了,只是勉强完成了翻译。
我特别感谢那些长期在TL和github上关注,并指出我错误的那些朋友。

我没有能及时给你们一个epub或者适合电子阅读的版本,很是过意不去。

就这样吧,这本书告一段落。

Larry, LIU Xinyu
https://github.com/liuxinyu95/AlgoXY

e^(πi)+1 = 0

Ernest He

unread,
Apr 1, 2016, 6:47:58 AM4/1/16
to pon...@googlegroups.com
辛苦!
赞!

Regards
--

---
您收到此邮件是因为您订阅了Google网上论坛上的“TopLanguage”群组。
要退订此群组并停止接收此群组的电子邮件,请发送电子邮件到pongba+un...@googlegroups.com
要查看更多选项,请访问https://groups.google.com/d/optout

Xinyu LIU

unread,
Apr 1, 2016, 6:48:47 AM4/1/16
to pon...@googlegroups.com

zipper Andy

unread,
Apr 6, 2016, 10:54:48 PM4/6/16
to pongba
辛苦了

Zoom.Quiet

unread,
Apr 6, 2016, 11:38:10 PM4/6/16
to TopLanguage]列表
坚持就是胜利!
非常赞! 又有的学了...
--
Life's Pathetic, Let's Pythonic! 人生苦短, Python是岸!
俺: http://zoomquiet.io
授: http://creativecommons.org/licenses/by-sa/2.5/cn/
怒: 冗余不做,日子甭过!备份不做,十恶不赦!
KM keep growing environment culture which promoting organization be learnning!

Zoom.Quiet

unread,
Apr 6, 2016, 11:38:53 PM4/6/16
to TopLanguage]列表
Edition: 0.6180339887498949
嗯哼,这是向高爷爷制敬哪

Xinyu LIU

unread,
Apr 7, 2016, 11:42:03 PM4/7/16
to pon...@googlegroups.com
的确是受到了他老人家用PI做LeTeX版本的启发。

Larry, LIU Xinyu
https://github.com/liuxinyu95/AlgoXY

e^(πi)+1 = 0


Edition: 0.6180339887498949
嗯哼,这是向高爷爷制敬哪
--

---
您收到此邮件是因为您订阅了 Google 网上论坛的“TopLanguage”群组。

Xinyu LIU

unread,
Apr 23, 2016, 6:41:51 PM4/23/16
to pon...@googlegroups.com
CSDN写blog还有审查.....还是TL方便。

公元9世纪,也就是是中国唐朝的时代,在阿拉伯文明的中心——巴格达,有一位来自东方的大学者刚刚完成了一本著作。书名叫做《还原与对消的科学》(Kitab al-Jabr wa-l-Muqabala)。它讲述了如何解二次以内的方程。人们用这本书的拉丁文简称Al-Jab,创造了一个词Algebra1859年,李善兰与英国传教士伟列亚力创造性地将其翻译为“代数”。

遗憾的是,没有人知道这位侨居在巴格达的数学家的真正名字。人们只知道他来自一个名叫花剌子模的东方国家。感谢金庸先生,《射雕英雄传》让这个国家的名字得以普及。如今的乌兹别克斯坦的撒马尔罕,还立有这位数学家的雕像。于是来自(Al)花剌子模(Khwarimi)的人,Al-Khwarimi(阿尔-花剌子密)就成了这位数学家的名字。它的拉丁文译法为Algorithm,中文译作“算法”。

我们的前辈在发展代数时,大约经历了三个阶段:文辞代数,简字代数、和符号代数。早期的解方程方法,如花剌子密著作中的方法,使用详细的文字描述解题的步骤,直到16世纪,文辞代数仍然是主流的代数描述手段。后来古希腊的丢翻图,逐渐使用了一些符号简记方法,发展了简字代数。现代的符号代数在莱布尼茨时达到了顶峰。极大了提高了数学语言的严谨性和表达能力。

可是反观我们现在的算法描述和很多计算机语言,似乎仍然停留在文辞代数阶段。这一想法是我在2013年时逐渐形成的。那时距离开始写作《初等算法》一书,已经过去了好几年了。

2005年前后,我经过一番曲折的道路,从C++template meta programming,经由Lisp方言Scheme,开始使用Haskell来试着编写程序。这是一门纯函数式编程语言,往往引导使用者用“代数”的方式思考和解决问题。但是深入下去,我发现需要解决一个问题。Dijsktra说“程序=算法+数据结构”。大量的已有算法和数据结构都是用命令式的描述和实现的,我们需要发展一套函数式的算法和数据结构。从那时起,我开始试着用多种语言实现《算法导论》一书中的算法。2009年的时候我把这些工作放到了github上,希望更多的人能从中受益。

幸运的是,已经有前人认识到这一问题了。卡耐基梅隆大学的Chris Okasaki在读博士的时候,就发展出了很多函数式数据结构。他的博士论文后来出版成为一本书《Purely functional data structure》。其中用Standard ML给出了一系列的实现。牛津大学的Richard Bird出版了《Pearls of functional algorithm design》针对很多问题,给出了对应的函数式算法。

站在这些成果的基础上,我得以把一些常见的基本算法整理出来,同时给出命令式和函数式描述,方便大家对照参考。书中给出了一些例子代码,包括Haskell, C, C++, Python,以及Lisp方言Scheme的。

2014年夏天的时候,这本书的英文稿大部分完成了。我接受了一些朋友的建议,开始将其译为中文。到20164月的时候,中文版也基本完成了。它们在github上可以获得:

https://github.com/liuxinyu95/AlgoXY/tree/zh-cn

最近几年,我的思路发生了一些转变。从2013年开始,我逐渐开始读一些和数学相关的书籍,开始是一些趣题集,后来是一些数学家的逸闻趣事,和科普读物。偶尔也看看范畴论(Category theory)。我逐渐认为计算机科学,以及算法终究还是数学的一个分支。回顾读书期间,我们的数学教学也许忽略了一些东西,例如帮助学生了解数学的历史,培养趣味性和幽默感等等。

如果再次重写《初等算法》这本书,也许不需要放入那些例子程序。而是可以加入更多数学元素,突出一下趣味性。如果有时间,我打算给中小学读者写一本名叫“Unplug”的书,不插电,不用电脑,不编写程序来解决生活中的问题。

当然,也有另一个可能,就是为了迎合主流的读者,将这本书用ScalaJava 8重写一遍。不过未来无法预测,很多时候,我们像布朗运动中的分子,只是迈着“醉汉的脚步”不断前行。

Yongwei Wu

unread,
Apr 23, 2016, 11:02:02 PM4/23/16
to pon...@googlegroups.com
王垠的观点似乎跟你恰恰相反。我不完全同意,不过,贴出来对比看看可能也挺有意思:

http://www.yinwang.org/blog-cn/2015/07/04/math

我认为数学和编程在基本方法论上确实存在巨大区别。明显可以看到,数学基础的东西在编程中不一定可以简单表达,编程中基础的东西在数学中不一定可以简单表达。
> --
>
> ---
> 您收到此邮件是因为您订阅了Google网上论坛上的“TopLanguage”群组。
> 要退订此群组并停止接收此群组的电子邮件,请发送电子邮件到pongba+un...@googlegroups.com
> 要查看更多选项,请访问https://groups.google.com/d/optout



--
Wu Yongwei
URL: http://wyw.dcweb.cn/

Xinyu LIU

unread,
Apr 24, 2016, 12:18:01 AM4/24/16
to pon...@googlegroups.com

Larry, LIU Xinyu
https://github.com/liuxinyu95/AlgoXY

e^(πi)+1 = 0



--

---
您收到此邮件是因为您订阅了 Google 网上论坛的“TopLanguage”群组。

Xinyu LIU

unread,
Apr 24, 2016, 1:00:29 AM4/24/16
to pon...@googlegroups.com
我记得第一次看高德纳先生的《具体数学》的时候,看到约瑟夫计数问题(Josephus counting out)[1]。恰巧在上中学时,我在计算机编程兴趣小组用BASIC解过这道题。当看到Knuth给出递归定义后,从编程意义上,这道题目就算已经解决了。如果追求完美,可能最多再加上一点复杂度分析。

但是高德纳先生接下来的做法,让我印象深刻。他不仅推导了解析解,还进一步分析了用二进制表示人数后的简化形式。那一瞬间,相信读者会有一种“unplug”的感觉。约瑟夫计数问题究竟是计算机问题还是是数学问题呢?

另一个例子,是我在写最后一章时,讲的那个倒水问题的例子。给一个9升桶,一个4升桶,要获得6升水。数学家Polya给的解法,其实是一种思考策略。并不能算是真正意义上的solution,这题目可以编程解。但是当看到每个桶中的水无论如何变化,总是9x+4y的线性组合,进而通过扩展欧几里得方法求得x与y,就知道如何倒水后。不由得让人思考: 古老的欧几里得算法,究竟是数学方法?还是计算机方法呢?

这两个问题类似,可能仁者见仁,智者见智。我们在英语中总看到这样的说法math and science。例如说Bill Gate捐款支持贫困地区儿童学习数学和自然科学。数学是一门伴随着我们祖先进化起来的一门学问,从数数,到测量,这些实用的功能,到抽象思考,超越宇宙的极限追求。

[1] https://en.wikipedia.org/wiki/Josephus_problem#History

Larry, LIU Xinyu
https://github.com/liuxinyu95/AlgoXY

e^(πi)+1 = 0


2016-04-23 20:01 GMT-07:00 Yongwei Wu <wuyo...@gmail.com>:

--

---
您收到此邮件是因为您订阅了 Google 网上论坛的“TopLanguage”群组。

Yongwei Wu

unread,
Apr 24, 2016, 3:14:46 AM4/24/16
to pon...@googlegroups.com
任何学科都可能有共通的地方,像计算机和数学/逻辑那就更不用说了。但我们日常用编程解决的问题确实大部分都和数学没多大关系;或者说,数学相关的问题只是其中的一小部分而已。

个人的感觉,编程中最难的东西在两个方面:

  • 解决未知的东西。系统提供的API可能跟文档描述的不完全一致,或者我们理解常常有误。硬件的行为需要通过实验来建模。在高流量的情况下,系统、运行库的行为可能出现某些异常。等等。
  • 克服方案的复杂度。一开始的代码可以解决问题,但随着后续代码的添加和人员的流动,软件的复杂度终于到了一个没人敢声称完全理解、没人敢随便动的地步。

这两个难点都不是数学所能解答的。软件工程的很多方法,就是为了解决这些问题。这些方法论,也基本上和数学扯不上什么关系。

高德纳认为自己首先是个数学家,他当然更关心数学和编程联系紧密的方面。必须看到,编程的很多方面是在一般意义上的数学之外的。

Wkong

unread,
May 11, 2016, 6:10:16 AM5/11/16
to pongba
有道理,学科本身是人为划分的,而自然的规律作为规律就存在那里,无论你怎么看他。
就像盲人摸象,同样的问题,不同人会看到不同的角度和内容。
Forget about the outside, but not escape.

linu...@gmail.com

unread,
May 12, 2016, 3:41:35 AM5/12/16
to pon...@googlegroups.com
国内有一些科学课老师一直在致力于做小学生的算法探索。有个老师把这个叫做生活算法,用算法的思路解决生活问题,通过生活中的问题,提炼算法。主要是训练学生的计算思维。

这个也是目前国外这些年小学生编程语言开始火的一个基础。
白清杰 (Born Bai)

Mail: linu...@gmail.com

Wkong

unread,
May 12, 2016, 5:54:20 AM5/12/16
to pongba
有相关资料吗?教小孩子挺好的,从小训练算法逻辑思维。挺有意思的。
Reply all
Reply to author
Forward
0 new messages