新書推薦：
《
德国天才4：断裂与承续
》
售價：NT$
500.0
《
妈妈的情绪，决定孩子的未来
》
售價：NT$
194.0
《
推拿纲目
》
售價：NT$
1836.0
《
精致考古--山东大学实验室考古项目论文集（一）
》
售價：NT$
1112.0
《
从天下到世界——国际法与晚清中国的主权意识
》
售價：NT$
347.0
《
血色帝国：近代英国社会与美洲移民
》
售價：NT$
265.0
《
海外中国研究·王羲之：六朝贵族的世界（艺术系列）
》
售價：NT$
811.0
《
唐宋绘画史 全彩插图版
》
售價：NT$
449.0
|
| 內容簡介： |
|
在信息时代，计算思维是解决复杂工程问题的重要思维方式，计算机则是求解问题的重要工具。本书以计算机经典问题求解为导向，通用算法思维和编程能力培养为目标，引入ACM国际大学生程序设计竞赛的有益元素，组织教材的理论教学和编程实践两方面的内容。本书主要内容包括计算机问题求解的经典算法模型和设计范式，包括计算机问题求解中常用的数据结构、枚举算法、递归与分治策略、动态规划、贪心算法和搜索技术。除了强调经典的问题原型和算法原理，本书兼顾编程实践能力，力图使得学生面对复杂问题时既能想到还能做到。
|
| 關於作者： |
|
李清勇，北京交通大学计算机与信息技术学院教授，研究领域为人工智能和大数据，涵盖计算机视觉、模式识别、机器学习和数据挖掘等学科方向，尤其专注于表面缺陷检测、多媒体内容分析与检索、低秩稀疏表示模型和聚类分析等，其研究成果应用于高速铁路和气象观测等行业。获得"北京市高校青年英才计划人选，北京市教学成果奖一等奖等。
|
| 目錄：
|
目 录
第1章 计算机问题求解概述 1
1.1 问题与问题实例 1
1.2 计算机问题求解周期 2
1.3 算法与程序 5
1.4 算法复杂性分析 5
1.4.1 空间复杂性 6
1.4.2 时间复杂性 7
习题1 15
第2章 程序设计语言与数据结构 16
2.1 程序设计语言的盲点 16
2.1.1 long不够长 17
2.1.2 double不够准 19
2.1.3 递归不够快 25
2.2 基本数据结构 26
2.2.1 线性表 26
2.2.2 栈和队列 30
2.2.3 树和二叉树 36
2.2.4 优先队列和堆 44
2.2.5 图 45
2.2.6 并查集 47
2.3 标准模板库 49
2.3.1 模板的基本概念 49
2.3.2 标准模板库概述 51
2.3.3 标准模板库应用 52
习题2 63
第3章 枚举算法 69
3.1 枚举的基本思想 69
3.2 模糊数字 70
3.3 真假银币 72
3.4 m钱n鸡 75
3.5 数字配对 77
3.6 绳子切割 79
3.7 石头距离 81
习题3 84
第4章 递归与分治 90
4.1 递归程序 90
4.2 分治法的基本原理 94
4.3 合并排序 96
4.4 逆序对问题 100
4.5 快速排序 102
4.6 最接近点对问题 106
4.7 指数运算 111
4.8 二分查找 113
习题4 114
第5章 动态规划 122
5.1 动态规划的基本思想 122
5.1.1 动态规划的基本要素 124
5.1.2 动态规划的求解步骤 125
5.2 矩阵连乘 126
5.3 最优二叉搜索树 131
5.4 多段图最短路径 136
5.5 最长公共子序列 140
5.6 0-1背包问题 143
5.7 最大上升子序列 146
习题5 149
第6章 贪心算法 155
6.1 贪心算法的基本要素 155
6.2 活动安排问题 157
6.3 小数背包问题 161
6.4 最优前缀码 164
6.5 单源最短路径 169
6.6 最小生成树 174
6.6.1 Prim算法 175
6.6.2 Kruskal算法 178
习题6 182
第7章 搜索技术 187
7.1 问题的状态空间表示 187
7.2 深度优先搜索 189
7.3 广度优先搜索 191
7.4 回溯算法 193
7.4.1 回溯算法的基本原理和框架程序 193
7.4.2 装载问题的回溯算法 199
7.4.3 圆排列问题 203
7.5 分支限界 206
7.5.1 分支限界法的基本原理 206
7.5.2 装载问题的分支限界法 208
7.6 启发式搜索 211
7.6.1 启发式搜索基本原理 211
7.6.2 装载问题的启发式搜索 215
习题7 217
附录A 复杂度分析的数学基础 225
附录B 常用C语言和STL函数 235
附录C 程序设计竞赛和OnlineJudge介绍 241
附录D 教学资源 244
参考文献 245
|
| 內容試閱：
|
前言
2006年3月，美国卡内基梅隆大学计算机科学系主任周以真（Jeannette M. Wing）教授在美国计算机权威期刊《Communications of the ACM》上首先提出了计算思维（Computational Thinking）的概念。周教授认为：计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。她还认为，计算思维是每个人的基本技能，不仅属于计算机科学家。我们应当使每个学生在培养解析能力时不仅掌握阅读、写作和算术（Reading, wRiting and aRithmetic，3R），还要学会计算思维。正如印刷出版促进了3R的普及，计算机也以类似的正反馈促进了计算思维的传播，计算机逐渐成为了当今问题求解的最重要工具。
1．计算机与问题求解
在20世纪40年代，为了求解军事领域复杂的炮弹弹道计算问题，科学家发明了第一台电子计算机ENIAC（Electronic Numerical Integrator And Computer）。随着计算机计算能力的增强，计算机被广泛应用到了社会生活的各个领域。大到宇宙探测、基因图谱绘制，小到日常工作、生活娱乐，无不需要计算机的支持。
作为问题求解的一个有力工具，计算机尽管没有思维，只能机械地执行指令，但它运算速度快、存储容量大、计算精度高。如果能够设计有效的算法和程序，充分利用这些优点，计算机就能成为问题求解的一个利器。
（1）运算速度快是计算机最重要的特点之一
很多问题尽管比较复杂，但仍然存在求解的方法，只是这些方法往往计算量比较大，计算过程较为繁杂，人们难以在可以接受的时间内手工求解。
如用1, 2, 3, 4, 5, 6, 7, 8, 9九个数字拼成一个九位数，每个数字使用一次且仅用一次，要求得到的九位数的前3位、中间3位和最后3位构成的三位数的比值为1∶2∶3。192384576就是一个符合该要求的数，因为192∶384∶576 = 1∶2∶3。
对于这样的问题，很容易想到的一个求解方案是：列举所有可能的九位数123456789987654321，并逐个验证是否符合比值要求。理论上，这是一个可行的办法，可是几乎没有人愿意这样做。因为这样的九位数总共有9! = 362880个，即使每秒验证一个数（对于人工验证，这已经是很快的速度了！），也需要100多个小时。
但是，计算机实现同样的笨方法效果就大不一样。考虑用一个数组 保存九位数的各位数字， 分别代表前三位数、中间三位数和最后三位数，用STL（Standard Template Library）中的函数next_permutation计算九个数字的下一个排列。当某个排列（也即是一个九位数）满足比例要求 时，则输出该九位数。下面是解决此问题的C代码，在普通的计算机上运行该程序，需要的时间还不到0.1秒。
void NineNumber {
int x , y , z;
int d[9]={1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9};
do{
x=d [0] * 100 d [1] * 10 d [2];
y=d [3] * 100 d [4] * 10 d [5];
z=d [6] * 100 d [7] * 10 d [8];
ify==x * 2 ＆＆ z==x * 3
cout＜＜x＜＜y＜＜z＜＜endl;
} while next_permutationd , d 9; STL中的函数，得到下一个排列
}
（2）存储容量大是计算机的另一个重要特点
人们很容易记住10以内两个数的乘积，也就是小学数学中的九九乘法表。如果要求人们记住100以内的任意两个数的乘积，普通人可能会觉得记忆不够。但对于计算机来说，这就是小菜一碟，一个100100的二维数组就可以把百百乘法表保存下来。
人们常说的内存、硬盘、光盘、U盘等都是存储器，可以通俗地理解为计算机的记忆部件。容量的基本单位是字节（Byte，简称B），其他单位有KB 、MB 、GB 等。容量越大，可以存储的数据就越多，其记忆力就越强。百百乘法表如果用一个100100的二维int型（假设一个int型整数占2字节）数组保存，它仅需要占用20 000字节（少于20KB）的空间。相比现在计算机动辄数GB的内存容量来说，百百乘法表的存储开销有点微不足道。
需要特别指出的是，运算速度快、存储容量大仅仅是计算机硬件系统的两个突出特点。在实际问题求解过程中，只有硬件平台远远不够，人们需要针对问题设计不同的算法，并把算法转化为计算机可以运行的程序。
2．计算机问题求解的知识体系
计算机问题求解的本质是把特定领域中特定问题的求解过程转换为一个计算机可以执行的程序。在这个转换过程中，除了必要的领域专业知识，问题求解者还需要掌握计算机算法设计方面的知识，主要包括：高级程序设计语言、数据结构和算法。这些知识构成了计算机问题求解的核心知识体系。
在计算机教学体系中，高级程序设计语言数据结构和算法是相互承接的课程。从计算机问题求解的角度看，这三门课程的知识相互交叉、相互支撑。高级程序设计语言和数据结构是算法设计的基础，高效的算法和数据结构需要用某种高级程序设计语言去实现；一个好程序不仅需要编程技巧，更需要合理的数据结构和高效的算法。
程序设计语言是问题求解的基本工具。随着计算机技术的发展，程序设计语言经历了一个从低级程序设计语言到高级程序设计语言的发展历程。机器语言和汇编语言等面向特定的体系结构和指令系统，在计算机发展的早期应用较多。随着形式语言理论、编译技术的发展，与目标机器无关的高级程序设计语言（如CC、Java等）逐渐成为程序设计的主流。本书约定的程序设计语言是CC。需要注意的是，程序设计语言并不等于程序设计，程序设计的目的是表达程序设计者的思想，按照计算机能理解的方式描述需要让计算机完成的工作，而程序设计语言只是表达这种思想的工具。程序设计的关键之处在于明确数据在计算机中的表达形式，以及确定如何将输入转化为输出的一系列计算步骤，而这些都需要数据结构和算法理论的指导。
数据结构是问题求解的基础要素。数据是信息的载体，无论是待求解问题的输入输出，还是问题求解过程中产生的中间量；无论是简单的量（如单个数值），还是复杂的对象，它们在计算机中都是以数据的形式存储的。在问题求解时，为满足数据存储的结构化要求并提高程序执行效率，人们首先面临的问题是怎样合理地组织、存储和加工这些数据。常用的数据结构有线性表、栈、队列、树、图、哈希表等。数据结构的设计和应用不是一个教条化的过程，同一个问题也许可以运用不同的数据结构求解，而且它们求解的效率往往不一定相同。另外，有些问题可能没有现成的数据结构直接套用，需要人们综合运用基本数据结构组合成新的数据结构。无论是已有数据结构的选择还是新数据结构的设计，人们都需要应用算法设计方面的知识。
算法设计是问题求解的关键要素。简单地说，算法可以理解为将问题输入转化为问题答案的一系列计算步骤。算法必须满足正确性和复杂性要求。首先，算法执行结果必须正确，它能正确无误地把每一个问题实例的正确答案求解出来。其次，算法的复杂度要适中。计算机系统的资源（包括运行时间和存储空间）是有限的，因此算法必须在有限的资源条件下正确地求解问题。同样的问题，某些算法执行结果可能不正确，某些算法执行结果正确无误。即使执行结果都正确的不同算法，它们的执行效率可能也不尽相同，如有些算法需要几个小时，甚至几天，有些算法仅仅需要几秒或几分钟。算法设计是一个灵活的、创造性的过程，甚至可以认为是一个艺术创造过程。有些算法是现实生活中人们解决问题时所用办法的升华和抽象，有些算法是数学理论和数学模型的体现及具体化。人们需要掌握经典的算法思想及其应用技巧，也要学会怎样针对特定问题设计和创造新算法。
3．本书的内容和结构
本书是一本介绍怎样综合运用算法设计理论和技术进行问题求解的实用性教材，主要介绍算法设计原理和方法，同时对运用算法求解问题时涉及的CC程序设计细节，尤其是影响算法准确性和复杂性的编程要点和技巧也进行了详细阐述。数据结构往往是算法设计和实现的基础，特别是一些高级数据结构本身就体现了很强的算法思维，因此本书不仅单独设立了程序设计语言与数据结构一章介绍数据结构，在介绍具体算法时也会交叉讨论相应的数据结构知识。本书包括7章，组织如下。
第1章介绍计算机问题求解和算法的基本概念，然后着重阐述算法复杂度分析的基本理论和方法。
第2章介绍程序设计与数据结构相关内容。程序设计和数据结构是算法设计的重要支撑，本章重点介绍程序设计的三个盲点，以及常用的基本数据结构及其用法。
第3章介绍枚举算法。大道至简，枚举算法是一种最朴素、最简单的算法思想，但在具有卓越运算速度的计算机系统中，它却是常常被忽视的问题求解利器。本章重点阐述怎样直接和间接运用枚举算法求解问题。
第4章介绍递归和分治。凡治众如治寡，分数是也，分治策略是分析和解决复杂问题最常用的策略之一。本章根据分治算法的求解步骤把分治策略归纳为三类，并结合具体实例阐述每类策略的设计思想、适用范围及实现要点。
第5章介绍动态规划。动态规划是最具有创造性的一种算法，归约、分治等思维方法都在动态规划算法框架中得到了很好的体现。本章重点讨论基于划分和约简策略的动态规划的原理和运用技巧。
第6章介绍贪心算法。这种类似瞎子爬山的策略如果运用适当，能够快速地产生最优解。本章将给出一些典型的贪心算法问题，并探讨贪心算法的正确性证明。
第7章介绍搜索技术。搜索是求解一些难解问题的常用策略，它把问题求解转换为状态空间图中的路径探索过程，究其本质，搜索是一种枚举
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
