计算机算法与程序设计

章节摘录

插图：第1章 绪论计算机算法与程序设计（Computer Algorithm and Programming Design）是计算机科学技术领域研究的重要基础课程，目前在各个高校普遍开设的本科课程，已成为众多理工科专业学生所喜爱的选修课之一。算法（algorithm）是一组有限规则，即为某个特定问题提供了计算机求解的运算序列。通俗点说，就是计算机解题的过程。算法分为并行算法和“传统意义”上的单处理器计算机上执行的算法，本书重点研究后者，重点讲述构成算法与程序的基本方法，解题思路，求解过程，求解效果的优劣分析等重要特征。本章主要内容：1.1节算法研究的意义，列举多个实例，详细讨论“算法，的概念和研究算法的意义；1.2节算法与程序，讲述算法如何逐步求精，实现程序设计；1.3节算法的描述工具，讨论算法的伪代码表示，说明算法的精确描述工具；l.4节算法的复杂性分析，简要介绍算法分析技术，研究时间复杂度与空问复杂度分析；1.5节常用数学分析公式，提出在算法分析中实施计算的一些必备数学基础，这些方法将会帮助设计和分析算法。1.1 算法研究的意义随着信息技术的发展，计算机算法与程序设计的普及，依据其难易等级，已从大学本科课程、研究生基础教学扩展到中学、高职高专教育；尤其是计算机信息类ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，ACM—ICPC），中学信息学奥林匹克国际竞赛，已从计算机算法与程序设计研究的高端到低端全面展开。其目的是培养学生良好的程序设计技巧和熟练的算法分析能力，能够开发出高效率的有效高级语言程序。

前言

“计算机算法与程序设计”（computer algorithm and programming design）是计算机科学技术领域研究的重要基础课程，己成为众多理工科专业学生所喜爱的必修课之一。众所周知，计算机系统软件和应用软件，如操作系统、高级语言编译器、数据库管理系统及各种计算机应用软件，无论是单机环境的系统软件，还是分布式、并行计算软件都是程序设计的结晶，当然都离不开算法的设计与实现。计算机系统中的任何软件，都是按特定的算法进行设计并且编写必需的程序源代码予以实现的。算法性能的好坏，直接决定了所实现软件性能的优劣。对于算法的设计除了需要考虑算法自身的功能外，还需考虑算法的时空复杂度，关键是设计一个功能强、效率高、时空复杂性低的优化算法并用程序实现。因此，计算机算法与程序设计是计算机科学与技术的一个核心问题，也是大学计算机专业本科生的一门重要的专业基础课程。本书的内容选材适当，循序渐进，互相衔接，逐步展开，具有系统性、先进性和实用性。（1）系统性。系统深入地介绍计算机专业基础课程“算法设计与分析”的理论知识；全面地讲解程序设计对于算法的设计与实现。全书包括：算法基础，数据抽象与数据结构，初等数论，组合数学初步；讲述了递归与分治策略，动态规划，贪心算法，搜索技术，图论算法；进一步研究了计算几何，排序算法；最后给出了程序设计典型实例。（2）先进性。计算机应用领域专家、优秀的重点高校教师、ACM-ICPC国际大学生程序设计竞赛金牌教练，近年的科研与教学的积累与提炼，内容体系先进性与计算机算法、程序设计的有机结合的研究成果与经验结晶。

内容概要

朱青，博士，中国人民大学信息学院副教授，高级CCF会员：曾于2004年3月-9月在美国加州大学圣迭戈分校UCSD作访问学者。在2007年1月-3月作为访问学者到香港中文大学合作研究。2006年获教育部宝钢优秀教师奖，2005年获中国人民大学优秀教师奖，2005年国家精品课程奖、北京市精品课程奖、2008年中国人民大学教学改革奖等奖励。中国人民大学ACM-ICPC（ACM国际大学生程序竞赛）代表队总教练，曾获亚洲赛区金牌，带队进入世界总决赛。主要研究方向：网格与并行计算，分布式系统可信与安全技术、高性能数据库与信息检索、Web Service计算。

书籍目录

第1章 绪论1.1 算法研究的意义1.2 算法与程序1.3 算法的描述工具1.4 算法的复杂性分析1.4.1 时间复杂度1.4.2 空间复杂度1.5 常用数学分析公式第2章 数据抽象与数据结构2.1 数据抽象概念2.1.1 数据结构的基本概念和术语2.1.2 数据抽象2.2 基本数据结构2.2.1 线性表与向量2.2.2 链表2.2.3 栈和队列2.2.4 二叉树2.2.5 图2.3 关键数据结构拓广2.3.1 哈希表2.3.2 并查集（等价类）2.3.3 线段树2.3.4 二叉堆第3章 初等数论3.1 数论基础3.1.1 素数与算术基本定理3.1.2 最大公约数与最小公倍数3.2 同余方程3.2.1 同余方程概念3.2.2 中国剩余定理3.3 数论函数3.3.1 欧拉函数3.3.2 积性函数3.4 素数和整除3.4.1 筛法求素数3.4.2 整数Ⅳ的因子函数3.5 高精度计算第4章 组合数学初步4.1 加法原理与乘法原理4.2 鸽笼原理和Ramsey数4.3 递推关系和生成函数4.3.1 Fibonacci数4.3.2 Catalan数4.3.3 第二类Stirlin9数4.4 排列组合4.4.1 字典序排列4.4.2 组合算法4.4.3 二项式系数4.5 容斥原理4.5.1 容斥原理的概念4.5.2 错排问题4.6 Polya定理及其应用第5章 递归与分治策略5.1 递归概念5.1.1 递归与递归调用5.1.2 递归应用5.2 分治法概述5.2.1 分治法基本思想5.2.2 分治算法设计和特点5.3 分治法的基本应用5.3.1 最大最小值5.3.2 Strassen矩阵乘法5.4 分治法解骑士周游5.5 大整数乘法5.5.1 常规大整数乘法5.5.2 分治法解大整数乘法5.6 棋盘覆盖问题第6章 贪心算法6.1 贪心算法概述6.1.1 贪心举例6.1.2 贪心算法的理论基础6.1.3 贪心算法与动态规划算法的区别6.2 背包问题6.3 机器任务调度算法6.3.1 多机调度问题6.3.2 活动安排问题6.4 最小生成树6.4.1 普里姆（Prim）算法6.4.2 克鲁斯卡尔（Kruskal）算法6.5 哈夫曼（Huffman）树及其应用6.5.1 Huffman树6.5.2 哈夫曼编码6.5.3 Huffman算法的正确性第7章 动态规划7.1 动态规划算法思想7.1.1 动态规划最优决策原理7.1.2 动态规划求解步骤7.1.3 动态规划的数学抽象7.2 矩阵连乘问题7.3 最长子序列探索7.3.1 最长递增子序列7.3.2 最长公共子序列7.4 多段图的最短路径7.5 资源分配问题7.6 树状动态规划第8章 搜索技术8.1 盲目搜索算法8.1.1 对分搜索8.1.2 DFS与BFS搜索算法8.1.3 盲目搜索算法应用8.2 回溯算法8.3 启发式搜索8.3.1 启发式搜索策略8.3.2 A*算法8.4 博弈问题8.4.1 博弈树8.4.2 极小极大搜索法8.5 α-β剪枝技术第9章 图论算法9.1 基本概念和定理9.1.1 可行遍性问题9.1.2 平面图9.1.3 独立集、覆盖与支配集9.2 最短路径9.2.1 Diikstra算法9.2.2 Floyd算法求一对点最短路径9.3 道路和回路9.3.1 欧拉道路和欧拉回路9.3.2 哈密尔顿图和货郎担问题9.4 网络流算法9.4.1 基本概念9.4.2 最大流问题9.4.3 最小费用流9.5 二分图相关问题9.5.1 二分图的最大匹配9.5.2 二分图的最佳匹配第10章 计算几何10.1 计算几何基本问题10.1.1 矢量与线段10.1.2 几何计算公式10.2 点与线段的关系10.2.1 点与线段的距离10.2.2 线段与直线的交点10.3 多边形10.3.1 多边形基本概念10.3.2 点与多边形的关系10.4 凸包问题10.4.1 判断凸包10.4.2 寻找凸包10.5 欧拉定理及其应用.第11章 排序11.1 排序基础11.2 比较排序法11.2.1 插入排序11.2.2 冒泡排序11.2.3 简单选择排序11.3 基于分治策略的排序算法11.3.1 快速排序11.3.2 归并排序11.4 堆排序11.4.1 树状选择排序11.4.2 堆排序11.5 基数排序11.6 排序小结第12章 算法与程序经典实例12.1 计算机算法设计实例12.2 国际竞赛程序实例分析

编辑推荐

《计算机算法与程序设计》是由清华大学出版社出版的。

作者简介

将本科“计算机算法与程序设计”课程与大学生程序设计竞赛有机地结合是新时期教学改革、培养实用型计算机优秀人才的创新。《计算机算法与程序设计》既系统深入地介绍算法设计的理论知识，又详尽地将其应用于实际编程，做到理论与实践的统一。

书中首先从理论的角度介绍了算法基础，数据抽象与数据结构，初等数论，组合数学初步；讲述了递归与分治策略，动态规划，贪心算法，搜索技术，图论算法；进一步研究了计算几何，排序算法；最后从实践的角度给出了程序设计典型实例及详细解析。

图书封面

---

 计算机算法与程序设计下载

---