`
buliedian
  • 浏览: 1186951 次
  • 性别: Icon_minigender_2
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论
阅读更多

如何看待算法

摘自:《HOW TO THINK ABOUT ALGORITHMS 》BY JEFF EDMONDS
刘建文略译(http://blog.csdn.net/keminlau


HOW TO THINK ABOUT ALGORITHMS

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: 这种做法有助于看清算法设计的本质而不至于掉进问题堆中找不着北)这样做也有助于训练读者的抽象思维能力。著者也试图绕开严格的形式证明而帮助读者深刻理 解为什么算法的正确性是明显和理所当然的。著者通过使用一些详尽清晰和对二三年级的计算机科学的学生可理解的方式达到这个目的,为他们将来算法创新打下基 础。

Abstraction is when you translate the equations, the rules, and the underlying essences of the problem not only into a language that can be communicated to your friend standing with you on a streetcar, but also into a form that can percolate(浸透; 渗出) down and dwell(居住; 踌躇) in your subconscious(下意识, 潜意识). Because, remember, it is your subconscious that makes the miraculous(奇迹的; 不可思议的) leaps(跳跃, 急变) of inspiration, not your plodding(沉重缓慢的, 单调乏味的) perspiration(汗, 努力, 流汗) and not your cocky(骄傲的, 自大的) logic. And remember, unlike you, your subconscious does not understand Java code.

抽象思维能力表现为一种潜意识态度而不是简单对知识的运用。转换公式、规则和问题的本质为语言表达并与人交流只是知识的运用,是能力的浅层次 获得;能力的深层次获得是浸透入我们的潜意识里。因为,我们思维时候,灵感的跳跃是来自潜意识的驱使,不是机械式的努力和强人逻辑所能得到的。还有,和你 (显意识)不一样,你的潜意识是不明白JAVA代码的。

kemin:合格的算法设计者或者抽象思维能力的潜意识层获得有什么可操作的标准吗?

PREFACE

To the Educator and the Student
This book is designed to be used in a twelve-week, third-year algorithms course. The goal is to teach students to think abstractly about algorithms and about the key algorithmic techniques used to develop them.

本书编写有两个目的,第一,教育学生抽象地看待算法;第二,教育学生开发(设计)算法的关键技术。

Meta-Algorithms : Students must learn so many algorithms that they are sometimes overwhelmed(受不起, 不敢当 ). In order to facilitate their understanding, most textbooks cover the standard themes of iterative algorithms, recursion, greedy algorithms, and dynamic programming.Generally, however,when it comes to presenting the algorithms themselves and their proofs of correctness, the concepts are hidden within optimized code and slick(光滑的) proofs. One goal of this book is to present a uniform and clean way of thinking about algorithms. We do this by focusing on the structure and proof of correctness of iterative and recursive meta-algorithms, and within these the greedy and dynamic programming meta-algorithms. By learning these and their proofs of correctness, most actual algorithms can be easily understood. The challenge is that thinking about meta-algorithms requires a great deal of abstract thinking.

为了成为合格的算法设计者,学生得研究大量的算法例子,而这个数量往往超出了一般学生所能接受的程度。为了帮助同学们理解算 法,一般的教材都会讲述标准的主题,如迭代算法、递归、贪心算法和动态规则等。但结果常常是只给出优化的代码和漂亮的证明,得到这些代码和证明背后的原理 却没有讲。这些原理就本书的中心——元算法。掌握了元算法就通晓了大部分的算法例子,唯一的代价就是大量的抽象思维。

Abstract Thinking : Students are very good at learning how to apply a concrete code to a concrete input instance. They tend, however, to find it difficult to think abstractly about the algorithms. I maintain that the more abstractions a person has from which to view the problem, the deeper his understanding of it will be, the more tools he will have at his disposal(安排, 配置, 支配 ), and the better prepared he will be to design his own innovative ways to solve new problems. Hence, I present a number of different notations, analogies, and paradigms within which to develop and to think about algorithms.

学生一般都善于学习为具体问题实例套用具体算法代码,但却很难抽象地看待算法。我 发现,如果一个人他越能抽象地看待要处理的问题,他就越能深刻地理解问题的本质,也越有更多的解决问题的工具,也越容易独自创新。为了训练出这样的抽象思 维能力,我使用了一特别的教学方式:different notations, analogies, and paradigms。

Way of Thinking : People who develop algorithms have various ways of thinking and intuition that tend not to get taught. The assumption, I suppose, is that these cannot be taught but must be figured out on one's own. This text attempts to teach students to think like a designer of algorithms.

人在设计算法时的思维方式和直觉是无法教的,必须由自己慢慢调整。本书设法引导同学们的思维向算法设计师方向调整。

Not a Reference Book : My intention is not to teach a specific selection of algorithms for specific purposes. Hence, the book is not organized according to the application of the algorithms, but according to the techniques and abstractions used to develop them.

我的目的不是给一个特定的问题讲授一个特定的算法,所以本书不是根据算法的应用来组织的,而是根据算法设计的技术和抽象方法来组织的。

Dreaming : I would like to emphasis the importance of thinking, even daydreaming, about the material. This can be done while going through your day –while swimming, showering, cooking, or lying in bed. Ask questions. Why is it done this way and not that way? Invent other algorithms for solving a problem. Then look for input instances for which your algorithm gives the wrong answer. Mathematics is not all linear thinking.
If the essence of the material, what the questions are really asking, is allowed to seep(渗出, 漏, 渗流 ) down into your subconscious then with time little thoughts will begin to percolate up. Pursue these ideas. Sometimes even flashes of inspiration appear.

我必须强 调对材料的思考和联想的重要性。这种思考可以随时随地的进行。“为什么如此而不是那样呢?”。试着为问题开发新的算法,找出你的算法有可能错误处理的问题 实例。记住,数学不能使用简单的线性思维。注意,如果我们问中了一个本质的问题,那么它就很可能进入我们的潜意识。因此对思想的追捕,即便是瞬间的灵思, 是非常重要的。

  • Kemin says: a.如果我的猜测是对的话,学习的本质是让知识上升为态度,显意识进入潜意识,那么什么样的显意识知识才有助于逻辑进化,又需要多少这样的知识呢?
  • Kemin says: a.从心理一层看,一些东西能进入人的潜意识的前提是对心灵的莫大的触动;首先这个触动没法量化;第二,触动的根源又是什么呢?我们知道小时候留下的心灵创伤应该是当时生理或心理上非常惧怕的东西造成的。惧怕的原因是需要和不需要,需要是进入人的潜意识的动力源?!
  • Kemin says: a.其实不必夸大态度和潜意识的神秘性,它们应该也是基于我们可掌握可触摸的知识和显意识的。只是改变态度所要的知识量和知识种类确实还是未知。目前只知道知识量很大,知识种类应该是系统的。

Introduction From determining the cheapest way to make a hot dog to monitoring the workings of a factory, there are many complex computational problems to be solved. Before executable code can be produced, computer scientists need to be able to design the algorithms that lie behind the code, be able to understand and describe such algorithms abstractly, and be confident that they work correctly and efficiently. These are the goals of computer scientists.

计算机科学家的职责:计算机科学家的职责和能力在于,第一,抽象地描述解决计算问题(computational problems)的算法;第二,证明算法的正确性;第三,证明算法的有效性。

A Computational Problem: A specification of a computational problem uses preconditions and postconditions to describe for each legal input instance that the computation might receive, what the required output or actions are. This may be a function mapping each input instance to the required output. It may be an optimization problem which requires a solution to be outputted that is “optimal” from among a huge set of possible solutions for the given input instance. It may also be an ongoing system or data structure that responds appropriately to a constant stream of input.

怎么定义一个计算问题?计算问题的文字规定(specification)是由前置条件 (preconditions )和后置条件(postconditions)两部分组成,它们分别描述计算问题的合法输入和期望的输出。每一个输入实例都函数映射一个期望的输出。但不 是所有的计算问题的每一个输入实例有唯一的输出,像最优化问题,一个输入有多个输出,里边有一个最优的。

Kemin said: b.有意思,“问题”的答案也有从无到有,从有到好的模式;而且可根据这个模式对“问题”分类。如,判定问题就是“有没有”,“有”了之后,答案是单值、 复合值还是有结构的值分出了数值问题和组合问题;“有”了之后再评价就是“好”的问题,单一好是最佳值问题;组合好是最优化问题。

Example: The sorting problem is defined as follows:
Preconditions: The input is a list of n values, including possible repetitions.
Postconditions: The output is a list consisting of the same n values in non-decreasing order.


An Abstract Data Type : Computers use zeros and ones, ANDs and ORs, IFs and GOTOs. This does not mean that we have to. The description of an algorithm may talk of abstract objects such as integers, reals, strings, sets, stacks, graphs, and trees; abstract operations such as “sort the list,” “pop the stack,” or “trace a path”; and abstract relationships such as greater than, prefix, subset, connected, and child. To be useful, the nature of these objects and the effect of these operations need to be understood. However, in order to hide details that are tedious or irrelevant, the precise implementations of these data structure and algorithms do not need to be specified. For more on this see Chapter 3.

抽象数据类型:计算机使用最原始的数据(0和1)和操作(ANDs 、ORs、 IFs 和 GOTO)工作,但这并不意味着我们也要。算法可使用抽象的对象(像整数、实数、字符串、栈、图和树)、抽象的操作(像排序、弹出弹入、跟踪)和抽象的关 系(大于、先于、子集、连通和后代)进行描述。当然,这些抽象的东西最后还是要被转为计算机理解的原始形式,这是算法和数据结构具体实现的话题,第三章有 讲述。

Running Time : It is not enough for a computation to eventually get the correct answer. It must also do so using a reasonable amount of time and memory space. The running time of an algorithm is a function from the size n of the input instance given to a bound on the number of operations the computation must do. (See Chapter 23.) The algorithm is said to be feasible if this function is a polynomial like Time(n) = O(n^2), and is said to be infeasible if this function is an exponential like Time(n) = O(2^n). (See Chapters 24 and 25 for more on the asymptotic of functions.)
To be able to compute the running time , one needs to be able to add up the times taken in each iteration of a loop and to solve the recurrence relation defining the time of a recursive program. (See Chapter 26 for an understanding of ∑( i=1,n) i = Θ(n^2),and Chapter 27 for an understanding of T(n) = 2T(n/2 ) +n = Θ(n logn).)

算法光能给出正确的计算结果是不够的,它必须在合理的时间和空间内完成才是有用的。为了估算算法的时间复杂度,必需合计循环内基本操作的次数(看26章并理解式子 :∑( i=1,n) i = Θ(n^2) ) 和解出递归算法递归关系(看27章并理解式子:T(n) = 2T(n/2 ) +n = Θ(n logn))。

Meta-algorithms : Most algorithms are best described as being either iterative or recursive. An iterative algorithm (Part One) takes one step at a time, ensuring that each step makes progress while maintaining the loop invariant. A recursive algorithm (Part Two) breaks its instance into smaller instances, which it gets a friend to solve, and then combines their solutions into one of its own.

大部分算法都是迭代或递归的形式。迭代算法通过每步保持循环不变量而不断向前推进,最终达到目标状态,解决问题;递归算法则把问题分解为相同结构规模小一点的问题,并通使用一些辅助的算法解决小问题,最后合并为一个解决方案。

Optimization problems (Part Three) form an important class of computational problems. The key algorithms for them are the following.

最优化问题是计算问题中最重要的一类,本书中涉及的最优化算法有:贪心算法、回溯算法、动态规划、归约算法和随机算法。
Greedy algorithms (Chapter 16) keep grabbing the next object that looks best.
Recursive backtracking algorithms (Chapter 17) try things and, if they don't work, backtrack and try something else.
Dynamic programming (Chapter 18) solves a sequence of larger and larger instances, reusing the previously saved solutions for the smaller instances, until a solution is obtained for the given instance.
Reductions (Chapter 20) use an algorithm for one problem to solve another.
Randomized algorithms (Chapter 21) flip coins to help them decide what actions to take. Finally, lower bounds
(Chapter 7) prove that there are no faster algorithms.

分享到:
评论

相关推荐

    理性看待算法战争

    什么是算法战争?这篇出自国防科技大的文章系统的阐述了什么是“算法战争”,看见算法的力量

    中科大算法导论

    这是一门有趣的课程,算法给了我们一个看待世界和看待生活的新方式,从中学到的不仅是让计算机做事情的方式,还有“递归”、“分治”“优化”、“剪枝”等等一系列可能改变生活的思维方法。 “算法设计与分析”需要...

    算法导论(part2)

    这些变化可以说不太大,也可以说很大,具体要看读者怎么看待这些变化了。 快速地浏览一遍目录,就会发现,第1版中的多数章节在第2版中都出现了。在第2版中,去掉了两章和一些节的内容,增加了三章新的内容。除了这...

    算法导论(part1)

    这些变化可以说不太大,也可以说很大,具体要看读者怎么看待这些变化了。 快速地浏览一遍目录,就会发现,第1版中的多数章节在第2版中都出现了。在第2版中,去掉了两章和一些节的内容,增加了三章新的内容。除了这...

    粒子群算法 C#版本 由C++改编

    由C++版本的粒子群算法改编成C#版本 已在VS2008中成功运行。不过程序仍有改进的地方。 程序仅供参考使用,请勿作为标准PSO算法看待。

    一种基于参考点约束支配的NSGA-III算法

    设计一种基于参考点的约束支配关系(RPCDP),将可行解与不可行解作为一个整体看待,进而综合考虑它们的收敛性、多样性和可行性,并基于此提出用于解决约束高维多目标优化问题的NSGA-III算法.将所提出算法与著名的3种约束...

    非线性最小二乘问题与Levenberg–Marquardt算法详解

    一直以来,各路大神们提出了各种各样的优化算法,很多都是一脉相承,不断创新的,所以最好不要孤立地看待这些算法。目前来说,Levenberg–Marquardt 法可以说是求解非线性最小二乘问题的标准算法了,也就是应用十分...

    算法公平,算法判别-研究论文

    其次,通过从歧视法的角度看待这个问题,本文认识到计算决策者提出的问题与歧视法已经演变为控制的历史性、制度性歧视非常相似,这是对这个问题真正新颖的说法的回应因为它涉及计算机化的决策。 第三,该论文通过...

    罗浩.ZJU | 如何看待 2020 届校招算法岗「爆炸」的情况?

    点击上方“机器学习算法工程师”,选择“星标”公众号 第一时间获取价值内容 作为20届CV方向校招的...关于这几年算法找工作的变化 17届的时候基本上已经确立了深度学习的地位,那个时候基本只要跑过深度学习就能找到

    论文研究-关联规则隐藏算法的研究.pdf

    数据挖掘能从不同角度、不同抽象层上看待数据,这将潜在地影响数据的私有性和安全性。着重介绍了关联规则数据挖掘中的规则隐藏算法,提出了一个改进的关联规则隐藏算法OSA,该算法综合采用项的添加和约束方法来降低...

    从信息泄露视角看待密码应用_密码应用与访问行为模式保护.pdf

    但是虽然密码算法本身具有可证明安全性,但是在应用中产生的信息泄露,依然使其容易被破解。密码应用正面临的新挑战,保护隐私迫在眉睫。 密码应用面临的新挑战 加密是保护隐私泄露的根本办法,很多满足应用需求的...

    如何正确看待人工智能.docx

    如何正确看待人工智能全文共3页,当前为第1页。如何正确看待人工智能全文共3页,当前为第1页。如何正确看待人工智能 如何正确看待人工智能全文共3页,当前为第1页。 如何正确看待人工智能全文共3页,当前为第1页。 1...

    算法工作分配对公平感知和生产力的影响:来自现场实验的证据-研究论文

    特别是,人们越来越担心算法可能会重现甚至放大人类历史上表现出的不平等,这就要求研究人们如何看待相对于替代决策方法的算法决策的公平性。 我们研究了算法(与基于人类的)任务分配过程如何改变任务接收者的公平...

    人工智能算法综述(一).pdf

    从整个历史的长河去看待,也许是⼀些莫名其妙或者残忍⾄极的怪事⽽已" 2017-2018 这两年因为⼀些爆炸式的AI应⽤,导致⼜把公众的视野转向这个⽅向发展,⾃图灵提出"图灵测试"之后,AI已 经爆发了两次热潮,相应的也...

    论文研究-基于属性的聚类算法在医生医疗质量评价系统中的应用研究.pdf

    以数据结构的角度看待数据挖掘的研究对象, 对数据挖掘的重要工具——聚类做了深入的论述, 把聚类分为基于数据元素的Q 型聚类和基于属性的R 型聚类, 着重讨论了R 型聚类, 论述了相关的概念、技术和算法。最后介绍了...

    算法风险评估的制度寿命-研究论文

    孤立地看待工具中的公平或偏见等问题,忽略了对开发和部署工具的机构和政治体系的重要全局考虑。 本文以加利福尼亚州 2017 年货币保释改革法案 (SB 10) 为例,分析了风险评估法规如何创建框架,在该框架内政策制定...

    基于统计平均算法的管道类系统相关失效可靠性模型

    基于统计平均算法的管道类系统相关失效可靠性模型,郝广波,谢里阳,将管道类连续系统离散成单元当作串联系统看待,重点讨论了管道类连续系统的强度分散性的影响因素:材料自身的不均匀性和材料质量�

    Adaboost目标跟踪算法.

    摘要从两类模式分类技术的角度看待视频序列中的目标跟踪问题,提如一种基予Adaboost学习技术的跟踪算 法

    属性赋权的K-Modes算法优化* (2012年)

    K-Modes算法在聚类过程中对每一个属性都同等看待,而在实际应用中,很多数据集仅有几个重要属性对聚类起作用。为了考虑不同属性对聚类的不同影响,将K-Modes聚类算法与属性权重的最优化结合起来,提出一种属性自动...

     一种改进的距离度量的聚类算法

    针对传统的K均值聚类分析,不考虑对象中每个变量在聚类过程中体现作用的不同,而是统一看待,用这样计算的距离来表示两个对象的相似度并不确切。文中提出了一种基于距离度量的聚类算法,算法使用新的距离度量代替了K...

Global site tag (gtag.js) - Google Analytics