Press "Enter" to skip to content

Tag: 算法

算法创新能力随想

很多强好奇心的算法设计学习者在面对现成的精妙算法时总会有一样的疑问:“如此精妙,怎样想出来的?如果给我一个新问题,我能设计出如此精妙的算法来吗?”。这个问题好比如问:“这首歌这么好听,我能作出来吗?”。换句话说就是问:“我有算法设计的创新能力吗?”。要回答这个问题,得先回答两个更优先的问题,第一,如何理解创新;第二,算法设计者的设计能力是一种什么样的能力,有什么内容。

如何理解创新

创新能力属于较高级别的能力层次,按布卢姆的能力层次来看,应该要比综合应用能力更高一级的能力,也就是分析和综合。按我给出的比喻,分析(Analysis)+综合(synthesis) = 再学习 = 创新能力。那么创新能力层比应用能力高出些什么东西来呢?新!其实综合应用能力也会涉及分析和综合的思维操作,但思维操作的内容一般都是旧的已经熟悉的对象,相反创新思维中必有新事物参与思维推理。新事物来自新需求。

如何看待算法

There are many algorithm texts that provide lots of well-polished
(擦 亮的, 优美的, 精练的 ) code and proofs of correctness. Instead, this one presents insights, notations, and analogies to help the novice(新手, 初学者) describe and think about algorithms like an expert. It is a bit like a carpenter(木匠) studying hammers instead of houses. Jeff Edmonds provides both the big picture and easy step-by-step methods for developing algorithms, while avoiding the common pitfalls. Paradigms such as loop invariants and recursion help to unify ( 统一, 使成一体)a huge range of algorithms into a few meta-algorithms .

Part of the goal is to teach students to think abstractly. Without getting bogged(陷入泥沼) down in formal proofs, the book fosters(养育; 培养; 抚育) deeper understanding so that how and why each algorithm works is transparent. These insights are presented in a slow and clear manner accessible to second- or third-year students of computer science, preparing them to find on their own innovative ways to solve problems.

目前很多算法教材都只是提供大量优美精练代码和对这些代码的正确性证明,然而,要学会建造房子得学会使用锤子而不是光研究现成房子的结构,所以光有这些代码对初学者进化为 算法设计者 是不够的,或者说很难帮助初学者顺利快速演化成 算法设计专家 。本书设法弥补这方面的不足。著者在书中使用了一些设计模式(Paradigms ),比如循环不变量和递归,把大量算法归类成少量的元算法( meta-algorithms )。(KEMIN: 这种做法有助于看清算法设计的本质而不至于掉进问题堆中找不着北)这样做也有助于训练读者的抽象思维能力。著者也试图绕开严格的形式证明而帮助读者深刻理解为什么算法的正确性是明显和理所当然的。著者通过使用一些详尽清晰和对二三年级的计算机科学的学生可理解的方式达到这个目的,为他们将来算法创新打下基础。

组合算法和组合问题

什么是组合算法?

本书中我们的主兴趣是研究一些涉及组合结构的算法。这些算法可非形式地根据算法目的(desired purpose)进行分类:

生成(generation):构造某种类型的组合结构的全体

可构造的组合结构例子有集合(subsets)、排列、划分(partitions)、树和Catalan families。生成算法会根据指定的序关系列出所有的对象,这样的序如字典序(lexicographic order)。这种(在没有完全生成整个序列前就)预先对生成序列中某个对象定好

位置是很有价值的(desirable)。这样就引出了一个论题——评级排列(ranking)和它的反向(unranking),这个论题在二、三章详述。

对“问题”建模

Modeling is the art of formulating your application in terms of precisely described, well-understood problems. Proper modeling is the key to applying algorithmic design techniques to any real-world problem. Indeed, proper modeling can eliminate the need to design or even implement algorithms by
relating your application to what has been done before. Proper modeling is the key to effectively using the problem catalog in Part II of this book.

为问题或任务建造模型是一种艺术,问题的模型是问题的一种描述精确和易理解的形式。适当的建造模型是应用算法设计技术解决任何实际问题的关键,因为你可以复用过曾经使用过的建模经验。适当建模是有效使用本书第二部分的问题清单(problem catalog)的关键。