Wednesday, September 21, 2011
最近在写一本暂名为《动态规划的思考艺术》的书。为了写书，也在读国外的关于动态规划的学术著作。 前几天读了一本成于上世纪七十年代的 The Art and Theory of Dynamic Programming 的前八章（即涉及确定性动态规划的全部章节），并做了一些笔记。深深感到，动态规划这个话题，一方面是相当趣味的理论，另一方面又是难以言说的艺术。那本书中，作者在大量的例子中穿插了大量的书后附有答案的习题，还特别强调，要想学会学好动态规划，光看例题是不够的，看完习题马上就翻答案也是不行的，必须对习题进行了独立的思考后，再翻看答案对照，才可能学好动态规划。 动态规划并没有什么深奥的数学基础，我这几天在看的去年刚刚出版的 Dynamic Programming: Foundations and Principles 一书中就将动态规划的数学基础归纳为几个及其简单（所以也就极其灵活）的式子，然后展开了详细的数学的分析与讨论。（值得一提的是，这本书分为两个部分，第一部分题为Science，第二部分题为Art。） 动态规划很简单，它的要素被作者在第三章中字字珠玑地归纳为五句话： A sequence consisting of elements denoting the stages of the decision-making process. A set whose elements represent the state of the process in each stage. A collection of sets where each set contains elements designating the feasible decisions pertaining to [...]
Wednesday, September 21, 2011
下载地址在 http://love-oriented.com/pack/pack2beta1.pdf 全文各章语言均有更新，更新最大的章节是 3.4，提供了多重背包可行性问题的一种简明的O(VN)解法。 本文IOIFORUM首发，欢迎转载，但请保留出处。
Monday, September 19, 2011
（本文是 http://llvm.org/releases/2.9/docs/GettingStarted.html 的阅读笔记。） LLVM的安装包分为三部分，LLVM工具包，LLVM-GCC，测试集。 自己编译LLVM三者都需要，但在主流平台上都有编译好的binary。 讲了LLVM的安装，没发现什么特别需要注意的。 LLVM的目录结构 llvm/examples: 很多有用的代码示例 llvm/include llvm/include/llvm LLVM头文件 llvm/include/llvm/Support 支持LLVM工具的头文件，但不和LLVM的功能密切相关 llvm/include/llvm/Config configure脚本生成的头文件，主要是Unix/C中标准头文件的包装。 llvm/lib 大部分的源代码都在这里，LLVM中几乎所有的代码都以库的形式存在 llvm/lib/VMCore/ llvm/lib/AsmParser/ llvm/lib/BitCode/ llvm/lib/Analysis/ llvm/lib/Transforms/ llvm/lib/Target/ llvm/lib/CodeGen/ llvm/lib/Debugger/ llvm/lib/ExecutionEngine/ llvm/lib/Support/ llvm/lib/System/ llvm/projects 并非LLVM一部分，但与LLVM共同发布的项目 llvm/runtime 需要LLVM-GCC编译 llvm/test llvm/tools 各种使用LLVM命令行工具 llvm/utils 帮助开发LLVM的命令行工具
Also filed in
|
Tagged 编译, LLVM
|
Friday, September 16, 2011
《寻寻觅觅 道阻且长》是《动态规划的思考艺术》的一部分，《背包问题九讲》的续作，讲解了动态规划中的寻路(path-finding)问题。 目前的完成状态如上图所示（只完成了目录的框架的一部分），现诚征我每写完一节即可第一时间看到的试读者。需要的人数非常少，且要求比较高，请谨慎申请。要求如下： 和我以前就认识。也就是说，在你申请之前我就听说过你的名字或网名，和我在三次元中见过面更佳。 能为我的文章提出建设性批评意见。这一条不好考核，目前的考察方法是：请针对《背包问题九讲》alpha1版本尽最大努力提出您的建设性意见，我会根据意见的有价值程度进行评估。 能尽保密义务。我会每天一次将最新草稿发送给试读者，但试读者必须保证不发送给任何其它人。
Thursday, September 15, 2011
四年前，我曾经有过一个写一系列DP相关文章的宏伟计划，但当时这个计划仅完成了第一部《背包问题九讲》就因为我感到个人能力不足的原因中止了。 现在，我打算将这个暂命名为“动态规划的思考艺术”的文章系列重新启动。其第一步便是用LaTeX重新修订那部广为传播并被做成过各种格式各种版本的“背包九讲”。 现在我已经完成了用LyX将九讲的原始文本输入并略加修饰的第一步，于是发布一个 alpha1 版本。下载地址在： http://love-oriented.com/pack/pack2alpha1.pdf 欢迎阅读并帮忙指正错漏之处，捉到的bugs较多或较大的同学有机会提前预览本系列将来的文章。