算法设计与分析_朱大铭，马绍汉著_9787040258714

　　《算法设计与分析》是普通高等教育“十一五”国家级规划教材。
　　《算法设计与分析》以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机科学与技术专业的学生提供广泛而坚实的计算机基础知识。主要内容包括算法分析技术，算法设计技术，P类，NP类及NPC类，证明问题属于NPC类的技术，NPC问题子问题的复杂性，拟多项式变换和图灵归约，NP-难解问题近似算法，近似算法设计技术，等等。
　　《算法设计与分析》包括了算法与复杂性领域的主要内容，可以作为高等学校计算机专业高年级本科生和研究生学习计算机算法设计的教材，也可供广大工程技术人员和自学者学习参考。

　　计算机是一种现代化的信息处理工具，它对信息进行处理并提供所需结果，其结果取决于所接受的信息及相应的处理算法。算法是以计算机能够理解的语言描述的解题过程。当算法作用于所求解问题的给定输入集或作用于问题自身的描述上，将产生唯一确定的有限动作序列。此序列或终止于给定问题的解，或终止于对此输入信息无解。对于给定的问题，基于对其的深刻理解，可设计出解答该问题的一个算法。在这个意义上，设计算法是将有关问题的知识，转化为解决问题的智慧。知识诚可贵，智慧价更高。设计算法就是揭示所研究问题的基本特征，以寻求其解答策略的过程，这是一项艰苦的创造性工作。
　　对于给定的问题，有可能设计出多个算法，但不同的算法质量会不一样。衡量算法质量的主要因素是算法执行所耗费的时间和所需存储空间，以及算法适用范围等。对算法质量的分析研究称为算法分析。算法设计和算法分析是计算机科学的核心基础。国内外大学的计算机专业中，都将“算法设计与分析”作为专业基础课。
　　近半个世纪以来，算法研究始终是计算机科学的一个研究热点。以E.W.Dijkstra、S.A.Cook、R.M.Karp、J.H.Hopcroft及R.E.Tarjan等为代表的一批计算机科学家，以创造性工作推动着算法研究不断深入发展。在研究过程中，算法理论研究与软件技术研究之间产生了鸿沟，使得算法研究缺乏足够的实验支持，而实验工作又没有充分的理论分析。这种现状引起了人们的忧虑。在1996年的ACM计算理论学术年会（STOC‘96）上，一些计算机科学家提出“算法工程”的概念，强调研究算法实现技术的重要性，呼吁算法研究者应重视理论与实践的结合，将算法设计、分析、实现、测试及改进等过程一体化、工程化。这种研究思路越来越受到人们的关注，促使算法研究健康发展。
　　本书原稿写于20世纪80年代中期、笔者在山东大学为计算机专业研究生讲授“算法设计与分析”课程期间，先后几经修改，于1992年定稿并由山东大学出版社正式出版。此后一直使用本书作为计算机科学与技术专业的学位课教材，由笔者和朱大铭教授共同为研究生讲授，效果尚好。经过20多年的研究沉淀，算法设计与分析虽然没有太多变迁，但其研究内容更加丰富和成熟。这期间我们始终坚持在这个研究方向上从事教学和科研工作，连续主持了10多项国家自然科学基金课题，培养了一批博士、硕士研究生。为适应培养创新型人才的需要，经过反复酝酿，决定由朱大铭教授执笔，重新修改编著这本书，增加近10年来的研究成果，使之能反映21世纪以来算法设计与分析的研究现状。可以说，本书是山东大学计算机科学与技术学院两代人坚持不懈、刻苦努力完成的。在本书写作过程中，得到朱洪教授的指导和帮助，在此表示感谢。
　　本书主要面向计算机相关专业的高年级本科生和研究生。全书共分8章，其中：第1、2章讨论算法分析技术和算法设计技术；第3、4、5、6章论述NP-完全性理论，特别强调多项式变换和多项式图灵归约的方法及应用；第7章论述NP-难解问题近似算法的基本概念和设计NP-难解问题近似算法的基本方法；第8章讨论近似算法设计的基本理论与技术。
　　算法研究是一项富有挑战性的工作，对提高计算机学科的研究水平极为重要，希望能有更多的有识之士投身这项工作。由于我们学术水平有限，本书内容必有疏漏、欠妥、谬误之处，敬请读者指正。

你还可能感兴趣

我要评论