# 参考文献 [1] Algorithmics, The Spirit of Computing, D. Harel, Y. Feldman，电子版。 [2] Computational Thinking, J. M. Wing, CACM, Vol. 49, No. 3, 2006。 [3] How to Think Like a Computer Scientist, Learning with Python，A. Downey，电子版。 [4] Learning Python, M. Lutz，电子版。 [5] Python Programming: An Introduction to Computer Science，J. Zell，电子版。 [6] Tkinter 8.4 reference: a GUI for Python, J. Shipman，电子版。 [7] [http://en.wikipedia.org/](http://en.wikipedia.org/) [8] Python 3 程序开发指南（第二版），M. Summerfield 著，王弘博等译，人民邮电出版社。 [9] 问题求解与编程概念（第 6 版），M. Sprankle 著，张晓明等译，清华大学出版社。 [10] 面向对象的思考过程（原书第二版），M. Weisfeld 著，杨会珍等译，中国水利水电出版 社。 [11] 计算机算法与程序设计实践，董东、周丙寅编著，清华大学出版社。 [12] 计算方法教程，凌永祥，陈明逵，西安交通大学出版社。 [13] 生物信息学——机器学习方法，皮埃尔巴尔迪等著，张东辉译，中信出版社。 [14] 计算物理学，马文淦，中国科学技术大学出版社。 [15] 数字文明：物理学和计算机，郝柏林，张淑誉著，科学出版社。

### 3.5 事件 事件描述符是一个字符串，由修饰符、类型符和细节符三个部分构成： ``` <修饰符>-<类型符>-<细节符> ``` 类型符 事件类型有很多，下面列出较常用的类型符： Activate 构件从无效状态变成激活状态。 Button 用户点击鼠标按键。具体按键用细节符描述。 ButtonRelease 用户释放鼠标按键。在多数情况下用这个事件可能比 Button 更好，因为如果用户无意 点击了鼠标，可以将鼠标移开构件再释放，这样就不会触发该构件的点击事件。 Configure 用户改变了构件（主要是窗口）大小。 Deactivate 构件从激活状态变成无效状态。 Destroy 构件被撤销。 Enter 用户将鼠标指针移入构件的可见部分。 FocusIn 构件获得输入焦点。通过 Tab 键或 focus_set()方法可使构件获得焦点。 FocusOut 输入焦点从构件移出。 KeyPress 用户按下键盘上的某个键。可简写为 Key。具体按键用细节符描述。 KeyRelease 用户松开按键。 Leave 用户将鼠标指针移开构件。 Motion 用户移动鼠标指针。 修饰符 下面是常用的修饰符： Alt 用户按下并保持 alt 键。 Control 用户按下并保持 control 键。 Double 在短时间内连续发生两次事件。例如<Double-Button-1>表示快速双击鼠标左键。 Shift 用户按下并保持 shift 键。 Triple 在短时间内连续发生三次事件。 细节符 鼠标事件的细节符用于描述具体绑定的是哪一个鼠标键，1、2、3 分别表示左、中、右 键。 键盘事件的细节符用于描述具体绑定的是哪一个键。对键的命名有多种方式，它们分别对应于 Event 对象中的如下几个属性： char 如果按下 ASCII 字符键，此属性即是该字符；如果按下特殊键，此属性为空串。 keycode 键码，即所按键的编码。注意，键码未反映修饰符的情况，故无法区分该键上的不同字 符，即它不是键上字符的编码，故 a 和 A 具有相同的键码。 keysym 键符。如果按下普通 ASCII 字符键，键符即是该字符；如果按下特殊键，此属性设置 为该键的名称（是个字符串）。 keysym_num 键符码，是等价于 keysym 的一个数值编码。对普通单字符键来说，就是 ASCII 码。与 键码不同的是，键符码反映了修饰符的情况，因此 a 和 A 具有不同的键符码。 除了可打印字符，常见的特殊按键的键符包括：Alt_L，Alt_R，BackSpace，Cancel， Caps_Lock，Control_L，Control_R，Delete，Down，End，Escape，F1～F12，Home，Insert， Left，KP_0～KP_9，Next，Num_Lock，Pause，Print，Prior，Return，Right，Scroll_Lock， Shift_L，Shift_R，Tab，Up 等等。 常用事件 根据以上介绍的事件描述符的组成，可以构造如下常用事件： + <Button-1>：左键点击 + <Button-2>：中键点击 + <Button-3>：右键点击 + <Double-Button-1>：左键双击 + <Triple-Button-1>：左键三击 + <B1-Motion>：左键按下并移动，每移一点都触发事件 + <B2-Motion>：中键按下并移动，每移一点都触发事件 + <B3-Motion>：右键按下并移动，每移一点都触发事件 + <ButtonRelease-1>：左键按下并释放 + <ButtonRelease-2>：中键按下并释放 + <ButtonRelease-3>：右键按下并释放 + <Enter>：进入按钮区域 + <Leave>：离开按钮区域 + <FocusIn>：键盘焦点移到构件或构件的子构件上 + <FocusOut>：键盘焦点从本构件移出 a：用户按下小写字母“a” 可打印字符（字母、数字和标点符号）都类似字母 a 这样使用。只有两个例外：空格键 对应的事件<space>，小于号对应的事件是<less>。 + <Shift-Up>：同时按下 Shift 键和↑键。 + 与<Shift-Up>类似的还有利用 Shift、Alt 和 Ctrl 构成的各种组合键，例如<Control-a>， + <Control-Alt-a>等等。 + <Key>：按下任意键。 + 具体按下的键值由传递给回调函数的事件对象的 char 属性提供。如果是特殊键，char 属性值为空串。注意，如果输入上档键（如@#$%^&*之类），当按下 Shift 键时就触发了<Key> 事件，再按下上档键又会触发<Key>。 + <Configure>：构件改变大小或位置。构件的新尺寸由事件对象的 width 和 height 属性传递。 事件对象 每个事件都导致系统创建一个 Event 对象，该对象将被传递给事件处理程序，从而事件 处理函数能够从该对象的属性获得有关事件的各种信息。事件对象的属性包括： x，y 鼠标点击位置坐标（相对于构件左上角），单位是像素。 x\_root，y\_root 鼠标点击位置坐标（相对于屏幕左上角），单位是像素。 num char 鼠标键编号，1、2、3 分别表示左、中、右键。 如果按下 ASCII 字符键，此属性即是该字符；如果按下特殊键，此属性为空串。 keycode 所按键的编码。注意，此编码无法区分该键上的不同字符，即它不是键上字符的编码。 keysym 如果按下普通 ASCII 字符键，此属性即是该字符；如果按下特殊键，此属性设置为该 键的名称（是个字符串）。 keysym_num：这是 keysym 的数值表示。对普通单字符键来说，就是 ASCII 码。 width，height 构件改变大小后的新尺寸（宽度和高度），单位是像素。仅适用于<Configure>事件。 widget 生成这个事件的构件实例。

### 3.4 对话框 GUI 的一个重要组成部分是弹出式对话框，即在程序执行过程中弹出一个窗口，用于与 用户的特定交互。Tkinter 提供了若干种标准对话框，用于显示消息、选择文件、输入数据 和选择颜色。 tkMessageBox 模块 本模块定义了若干种简单的标准对话框和消息框，它们可通过调用以下函数来创建：askokcancel、askquestion、askretrycancel、askyesno、showerror、showinfo 和 showwarning。 这些函数的调用语法是： ``` function(title, message, options) ``` 其中 title 设置窗口标题，message 设置消息内容（可用\n 显示多行消息），options 用于设置 各种选项。 这些函数的返回值依赖于用户所选择的按钮。函数 askokcancel、askretrycancel 和 askyesno 返回布尔值：True 表示选择了 OK 或 Yes，False 表示 No 或 Cancel。函数 askquestion 返回字符串 u"yes"或 u"no" ，分别表示选择了 Yes 和 No 按钮。 参数 options 可设置以下选项： ``` default = constant ``` 指定缺省按钮。其中 constant 的值可以取 CANCEL、IGNORE、NO、OK、RETRY 或 YES。如果未指定，则第一个按钮（"OK"、"Yes"或"Retry"）将成为缺省按钮。 ``` icon = constant ``` 指定用什么图标。其中 constant 的值可以取 ERROR、INFO、QUESTION 或 WARNING。 ``` parent = window ``` 指定消息框的父窗口。如果未指定，则父窗口为根窗口。关闭消息框时，焦点返回到父 窗口。 tkFileDialog 模块 本模块定义了两种弹出式对话框，分别用于打开文件和保存文件的场合。通过调用函数askopenfilename 和 asksaveasfilename 来创建所需对话框，调用语法是： ``` function(options) ``` 如果用户选择了一个文件，则函数的返回值是所选文件的完整路径；如果用户选择了“取 消”按钮，则返回一个空串。参数 options 可用的选项包括： ``` defaultextension = string ``` 缺省文件扩展名。string 是以"."开头的字符串。 ``` filetypes = [(filetype,pattern),...] ``` 用若干个二元组来限定出现在对话框中的文件类型。每个二元组中的 filetype 指定文件 类型（即扩展名），pattern 指定文件名模式。这些信息将出现在对话框中的“文件类型”下 拉框中。 ``` initialdir = dir ``` 指定初始显示的目录路径。缺省值为当前工作目录。 ``` initialfile = file ``` 指定在“文件名”域初始显示的文件名。 ``` parent = window ``` 指定对话框的父窗口。缺省值为根窗口。 ``` title = string ``` 指定对话框窗口的标题。 tkSimpleDialog 模块 本模块用于从用户输入数据。通过调用函数 askinteger、askfloat 和 askstring 弹出输入对 话框。这些函数的调用语法是： ``` function(title, prompt, options) ``` 其中 title 指定对话框窗口的标题，prompt 指定对话框中的提示信息，options 是一些选项。 返回值是用户输入的数据。参数 options 可设置的一些选项包括： ``` initialvalue = value ``` 指定对话框输入域中的初始值。 ``` minvalue = value ``` 指定合法输入的最小值。 ``` maxvalue = value ``` 指定合法输入的最大值。 tkColorChooser 模块 本模块提供选择颜色的对话框。通过调用函数 askcolor 即可弹出颜色对话框： ``` result = askcolor(color,options) ``` 其中参数 color 指定显示的初始颜色，缺省值为淡灰色。参数 options 可设置的选项包括： ``` title = text ``` 指定对话框窗口的标题，缺省为“颜色”。 ``` parent = window ``` 指定对话框的父窗口。缺省为根窗口。 如果用户点击“确定”按钮，返回值为元组(triple, color)，其中 triple 是包含红绿蓝分量的 三元组(R, G, B)，各分量值的范围是[0,255]，color 是所选颜色（Tkinter 颜色对象）。如果用 户点击“取消”按钮，则返回值为(None, None)。

### 3.3 各种构件的属性 除了标准属性，每种构件类还有独特的属性。这里仅以 Button 类为例列出按钮构件的 常用属性，其他构件类仅列出类名，具体有哪些属性请查阅 Tkinter 参考资料。 Button 构造器：`Button(parent, option = value, ... )` 常用选项： + anchor：指定按钮文本在按钮中的位置（用方位值表示）。 + bd 或 borderwidth：按钮边框的宽度，缺省值为 2 个像素。 + bg 或 background：背景色。 command：点击按钮时调用的函数或方法。 + default：按钮的初始状态，缺省值为 NORMAL，可改为 DISABLED（不可用状态）。 + disabledforeground：不可用状态下的前景色。 + fg 或 foreground：前景色（即文本颜色）。 + font：按钮文本字体。 height：按钮高度（对普通按钮即文本行数）。 + justify：多行文本的对齐方式（LEFT，CENTER，RIGHT）。 + overrelief：当鼠标置于按钮之上时的 3D 风格，缺省为 RAISED。 padx：文本左右留的空白宽度。 + pady：文本上下留的空白宽度。 relief：按钮边框的 3D 风格，缺省值为 RAISED。 + state：设置按钮状态（NORMAL，ACTIVE，DISABLED）。 + takefocus：按钮通常可成为键盘焦点（按空格键即为点击），将此选项设置为 0 则不能成为 键盘焦点。 + text：按钮上显示的文本，可以包含换行字符以显示多行文本。 + textvariable：与按钮文本关联的变量（实为 StringVar 对象），用于控制按钮文本内容。 + underline：缺省值为-1，意思是按钮文本的字符都没有下划线；若设为非负整数，则对应, 位置的字符带下划线。 + width：按钮宽度（普通按钮以字符为单位）。 Checkbutton Entry Frame Label LabelFrame Listbox Menu Menubutton Message OptionMenu PanedWindow Radiobutton Scale Scrollbar Spinbox Text Toplevel

### 3.2 构件的标准属性 Tkinter 为所有构件提供了一套标准属性，用来设置构件的外观（大小、颜色、字体等） 和行为。 设置构件的长度、宽度等属性时可选用不同的单位。缺省单位是像素，其他单位包括 c（厘米）、i（英寸）、m（毫米）和 p（磅，约 1/72 英寸）。 颜色 多数构件具有 background（可简写为 bg）和 foreground（可简写为 fg）属性，分别用于 指定构件的背景色和前景（文本）色。颜色可用颜色名称或红绿蓝（RGB）分量来定义。 所有平台都支持的常见颜色名称有"white"、"black"、"red"、"green"、"blue"、"cyan"、"yellow"、"magenta"等，其他颜色如 LightBlue、Moccasin、PeachPuff 等等也许依赖于具体的安装平台。颜色名称不区分大小写。大多数复合词组成的颜色名称也可以在使用单词间加 空格的形式，如"light blue"。 通过 RGB 分量值来指定颜色需使用特定格式的字符串："#RGB"、"#RRGGBB"、 "#RRRGGGBBB"和"#RRRRGGGGBBBB"，它们分别用 1～4 个十六进制位来表示红绿蓝分 量值，即分别将某颜色分量细化为 16、256、4096 和 65536 级。如果读者不熟悉十六进制， 可以用下面这个方法将十进制数值转换成颜色格式字符串，其中宽度可选用 01～04： ``` my_color = "#%02x%02x%02x" % (128,192,200) ``` 字体 多数构件具有 font 属性，用于指定文本的字体。一般情况下使用构件的缺省字体即可， 如果实在需要自己设置字体，最简单的方法是使用字体描述符。 字体描述符是一个三元组，包含字体族名称、尺寸（单位为磅）和字形修饰，其中尺寸 和字形修饰是可选的。当省略尺寸和字形修饰时，如果字体族名称不含空格，则可简单地用 字体族名称字符串作为字体描述符，否则必须用元组形式（名称后跟一个逗号）。例如下列 字体描述符都是合法的： ``` ("Times",10,"bold") ("Helvetica",10,"bold italic") ("Symbol",8) ("MS Serif",) "Courier" ``` Windows 平台上常见的字体族有 Arial、Courier New（或 Courier）、Comic Sans MS、Fixedsys、Helvetica（同 Arial）、MS Sans Serif、MS Serif、Symbol、System、Times New Roman（或 Times）和 Verdana 等。字形修饰可以从 normal、bold、roman、italic、underline 和 overstrike 中选用一个或多个。 除了字体描述符，还可以创建字体对象，这需要导入 tkFont 模块，并用 Font 类来创建 字体对象。在此不详述。 边框 Tkinter 的所有构件都有边框，某些构件的边框在缺省情形下不可见。边框宽度用 borderwidth（可简写为 border 或 bd）设置，多数构件的缺省边框宽度是 1 或 2 个像素。可 以用属性 relief 为边框设置 3D 效果，可用的 3D 效果有'flat'或 FLAT、'groove'或 GROOVE、 'raised'或 RAISED、'ridge'或 RIDGE、'solid'或 SOLID、'sunken'或 SUNKEN（见图 8.28）。  图 8.28 按钮边框 3D 效果 文本 标签、按钮、勾选钮等构件都有 text 属性，用于指定有关的文本。文本通常是单行的， 但利用新行字符\n 可以实现多行文本。多行文本的对齐方式可以用 justify 选项设置，缺省 值是 CENTER，可用值还有 LEFT 或 RIGHT。 图像 很多构件都有 image 属性，用于显示图像。例如命令按钮上可以显示图像而不是文本，标签也可以是图像而非文本，Text 构件可以将文本和图像混合编辑。 image 属性需要一个图像对象作为属性值。图像对象可以用 PhotoImage 类来创建，图像 的来源可以是.gif 等格式的图像文件。 例如： ``` >>> root = Tk() >>> img ＝ PhotoImage(file="d:\mypic.gif") >>> Button(root,image=img).pack() ```

### 3.1 构件属性值的设置 Tkinter 构件对象有很多属性，这些属性的值可以在创建实例时用关键字参数指定（未 指定值的属性都有缺省值）： ``` <构件类>(<父构件>,<属性>=<值>,...) ``` 也可以在创建对象之后的任何时候通过调用对象的 configure（或简写为 config）方法来更改 属性值： ``` <构件实例>.config(<属性>=<值>,...) ``` 构件类还实现了一个字典接口，可使用下列语法来设置和查询属性： ``` <构件实例>["<属性>"] = <值> value = <构件实例>["<属性>"] ``` 由于每个赋值语句都导致对 Tk 的一次调用，因此若想改变多个属性的值，较好的做法 是用 config 一次性赋值。 有些构件类的属性名称恰好是 Python 语言的保留字（如 class、from 等），当用关键词 参数形式为其赋值时，需要在选项名称后面加一个下划线（如 class_、from_等）。

## 3 Tkinter 编程参考

## 2 Tkinter 画布方法 本节罗列 Canvas 对象的方法，供需要的读者编程时参考。具体用法请查阅参考资料。 创建图形项的方法 + create_arc(<限定框>, <选项>)：创建弧形，返回标识号 + create_bitmap(<位置>, <选项>)：创建位图，返回标识号 + create_image(<位置>, <选项>)：创建图像，返回标识号 + create_line(<坐标序列>, <选项>)：创建线条，返回标识号 + create_oval(<限定框>, <选项>)：创建椭圆形，返回标识号 + create_polygon(<坐标序列>, <选项>)：创建多边形，返回标识号 + create_rectangle(<限定框>, <选项>)：创建矩形，返回标识号 + create_text(<位置>, <选项>)：创建文本，返回标识号 + create_window(<位置>, <选项>)：创建窗口型构件，返回标识号 操作画布上图形项的方法 + delete(<图形项>)：删除图形项 + itemcget(<图形项>, <选项>)：获取某图形项的选项值 + itemconfig(<图形项>, <选项>)：设置图形项的选项值 + itemconfigure(<图形项>, <选项>)：同上 + coords(<图形项>)：返回图形项的坐标 + coords(<图形项>, x0, y0, x1, y1, ..., xn, yn)：改变图形项的坐标 + bbox(<图形项>)：返回图形项的界限框（坐标） + bbox()：返回所有图形项的界限框 + canvasx(<窗口坐标 x>)：将窗口坐标 x 转换成画布坐标 x + canvasy(<窗口坐标 y>)：将窗口坐标 y 转换成画布坐标 y + type(<图形项>)：返回图形项的类型 + lift(<图形项>)：将图形项移至画布最上层 + tkraise(<图形项>)：同上 + lower(<图形项>)：将图形项移至画布最底层 + move(<图形项>, dx, dy)：将图形项向右移动 dx 单位，向下移动 dy 单位 + scale(<图形项>, <x 比例>, <y 比例>, <x 位移>, <y 位移>)：根据比例缩放图形项 查找画布上图形项的方法 下列方法用于查找某些项目组。对每个方法，都有对应的 addtag 方法。不是处理 find 方法返回的每个项目，而是为一组项目增加一个临时标签、一次性处理所有具有该标签的项 目、然后删除该标签，常常可以得到更好的性能。 + find_above(<图形项>)：返回位于给定图形项之上的图形项 + find_all() ：返回画布上所有图形项的标识号构成的元组，等于 find_withtag(ALL) + find_below(<图形项>)：返回位于给定图形项之下的图形项 + find_closest(x, y)：返回与给定位置最近的图形项，位置以画布坐标给出 + find_enclosed(x1, y1, x2, y2)：返回被给定矩形包围的所有图形项 + find_overlapping(x1, y1, x2, y2)：返回与给定矩形重叠的所有图形项 + find_withtag(<图形项>)：返回与给定标识匹配的所有图形项 操作标签的方法 + addtag_above(<新标签>, <图形项>)：为位于给定图形项之上的图形项添加新标签 + addtag_all(<新标签>)：为画布上所有图形项添加新标签，即 addtag_withtag(<新 标签>, ALL) + addtag_below(<新标签>, <图形项>)：为位于给定图形项之下的图形项添加新标签 + addtag_closest(<新标签>, x, y)：为与给定坐标最近的图形项添加新标签 + addtag_enclosed(<新标签>, x1, y1, x2, y2)：为被给定矩形包围的所有图形项添 加新标签 + addtag_overlapping(<新标签>, x1, y1, x2, y2) ：为与给定矩形重叠的所有图 形项添加新标签 + addtag_withtag(<新标签>, <标签>)：为具有给定标签的所有图形项添加新标签 + dtag(<图形项>, <标签>)：为给定图形项删除给定标签 + gettags(<图形项>：返回与给定图形项关联的所有标签

## 1 Python 异常处理参考 本节简单罗列 Python 语言中与异常处理有关的常用语句形式及用法。 发生错误时通常由系统自动抛出异常，但也可由程序自己抛出并捕获。 捕获并处理异常：try-except 发生错误时，如果应用程序没有预定义的处理代码，则由 Python 的缺省异常处理机制 来处理，处理动作是中止应用程序并显示错误信息。如果程序自己处理异常，可编写 try-except 语句来定义异常处理代码。详见前面各节。 手动抛出异常：raise 异常可以由系统自动抛出，也可以由我们自己的程序手动抛出。Python 提供 raise 语句 用于手动抛出异常。下面的语句抛出一个 ValueError 异常，该异常被 Python 的缺省异常处 理程序捕获： ``` >>> raise ValueError Traceback (most recent call last): File "<stdin>", line 1, in <module> ValueError ``` 除了错误类型，raise 语句还可以带有错误的描述信息： ``` >>> raise ValueError, "Wrong value!" Traceback (most recent call last): File "<stdin>", line 1, in <module> ValueError: Wrong value! ``` 当然也可以由程序自己处理自己抛出的异常，例如 ``` >>> try: raise ValueError except ValueError: print "Exception caught!" Exception caught! ``` 用户自定义异常 前面程序例子中抛出的都是 Python 的内建异常，我们也可以定义自己的异常类型。为 此目的，需要了解 Python 的异常类 Exception 以及类、子类、继承等面向对象程序设计概念， 这些概念将在第 x 章中介绍。这里我们用下面的简单例子演示大致用法，以使读者先获得一 个初步印象： ``` >>> class MyException(Exception): pass ``` 这是一个类定义，它在 Python 内建的 Exception 类的基础上定义了我们自己的异常类 MyException。虽然语句 pass 表明我们并没有在 Exception 类的基础上添加任何东西，但 MyException 确实是一个新的异常类，完全可以像 Python 内建的各种异常一样进行抛出、捕 获。例如： ``` >>> try: raise MyException except MyException: print "MyException caught!" MyException caught! ``` 确保执行的代码：try-finally 一般来说，发生异常之后，控制都转到异常处理代码，而正常算法部分的代码不再执行。 Python 的异常处理还允许我们用 try-finally 语句来指定这样的代码：不管是否发生异常，这 些代码都必须执行。这种机制可以用来完成出错后的扫尾工作。例如： ``` >>> try: x = input("Enter a number: ") print x finally: print "This is final!" Enter a number: 123 123 This is final! ``` 本例中，我们为 x 输入了一个正常数值 123，故 try 语句块没有发生异常，显示 123 后 又执行了最后的 print 语句。为什么不写成如下形式呢？ ``` x = input("Enter a number: ") print x print "This is final!" ``` 区别在于，当发生错误时，这种写法就有可能未执行最后的 print 语句，而 try-finally 的写法则在发生异常的情况下也会确保执行最后的 print 语句。例如我们再次执行上面的语 句： ``` >>> try: x = input("Enter a number: ") print x finally: print "This is final!" Enter a number: abc This is final! Traceback (most recent call last): File "<stdin>", line 2, in <module> File "<string>", line 1, in <module> NameError: name 'abc' is not defined ``` 可见，由于输入数据错误，导致 try 语句块发生异常而无法继续，但 finally 下面的 语句却得到了执行。仅当 finally 部分确保执行之后，控制才转到（缺省）异常处理程序 来处理捕获到的异常。 一般形式：try-except-finally 这种形式的异常处理语句综合了 try-except 和 try-finally 的功能。首先执行 try 部分，如 果一切正常，再执行 finally 部分。try 部分如果出错，则还是要执行 finally 部分，然后再由 except 部分来处理异常。

# 附录

## 11.6 练习 1\. 举例说明计算机在你的专业领域中的应用。 2\. 利用本书中学到的知识去解决一个你专业领域的问题。 3\. 假如你是 X 专业的，现在有“计算 X 学”吗？如果有，该学科的研究内容是什么？

## 11.5 计算经济学 计算经济学（computational economics）是计算机科学与经济和管理科学相结合而形成 的交叉学科，其主要研究领域包括经济系统的计算模型、计算计量经济学、计算金融学等， 目的是利用计算技术和数值方法来解决传统方法无法解决的问题。这里，我们特别考虑建模 问题，简单介绍基于代理的计算经济学。 基于代理的（agent-based）模型是用于模拟自治个体的行为和相互作用的计算模型，目 的是从整个系统的层面来评估这些个体相互作用所产生的效果。基于代理的计算经济学（ACE）将经济过程建模为一个由相互作用的代理所构成的动态系统，并应用数值方法来模 拟系统的运行。ACE 中的“代理”是指按照一定的规则行事、并且相互作用的对象，可以 表示个体（如一个人）、社会群体（如一家公司）、生物体（如农作物）或物理系统（如交通 系统）。建模者要做的事情是为由多个相互作用的代理组成的系统提供初始条件，然后就不 加干涉地观察系统如何随时间而演化。系统中的代理完全通过相互作用来驱动系统向前发 展，没有任何外部强加的平衡条件。 ACE 方法的一个应用领域是资产定价。计算模型涉及许多代理，每个代理可以从一组 预测策略中选择特定策略去行事，比如预测股票价格。根据预测的结果，会影响代理们的资 产需求，而这又会影响股票价格。通过对模型的分析，可以获得有用的结果，例如，当代理 改变预测策略时，经常会引发资产价格的大波动。又如，有经济学家认为 ACE 可能对理解 最近的金融危机也是有用的方法。 总之，计算机科学的建模技术为计算经济学提供了非常有用的方法和工具。

## 11.4 计算化学 化学在传统上一直被认为是一门实验科学，但随着计算机技术的应用，化学家成为大规 模使用计算机的用户，化学科学的研究内容、方法乃至学科的结构和性质随之发生了深刻变 化。计算化学（computational chemistry）是化学和计算机科学等学科相结合而形成的交叉学 科，其研究内容是如何利用计算机来解决化学问题。计算化学这个术语早在 1970 年就出现 了，并且在上世纪 70 年代逐步形成了计算化学学科。 因此，计算化学可以帮助实验化学家，或者挑战实验化学家来找出全新的化学对象。 有些化学问题是无法用分析方法解决的，只能通过计算来解决。计算化学一般用于解决 数学方法足够成熟从而能在计算机上实现的问题。计算化学有两个用途：一是通过计算来与 化学实验互为印证、互为补充；一是通过计算来预测迄今完全未知的分子或从未观察到的化 学现象，或者探索利用实验方法不能很好研究的反应机制。 计算化学的研究内容很多，我们简单介绍化学数据库和分子模拟（或分子建模），前者 是关于化学信息表示、存储和查找的，后者是研究化学系统结构和运动的。 化学数据库是专门存储化学信息的数据库，其中的化学信息可以是化学结构、晶体结构、 光谱、反应与合成、热物理等类型的数据。以化学结构数据为例，学过中学化学课程的人都 知道，化学家通常用直线表示原子之间的化学键，利用化学键将若干原子连接在一起，形成 了分子结构的二维表示。这种表示对化学家来说是理想的、可视的，但对化学数据的计算机 处理来说是很不合适的，尤其是对数据的存储和查找。为此，需要建立分子结构的计算机表 示，如小分子可以用原子的列表或 XML 元素表示，而大分子（如蛋白质）可用氨基酸序列 来表示。当今一些大的化学结构数据库存储了成百万的分子结构数据（存储量高达 TB 级）， 可以方便而高效地查找信息。 分子模拟利用计算机程序来模拟化学系统的微观结构和运动，并用数值计算、统计方法 等对系统的热力学、动力学等性质进行理论预测。宏观化学现象是无数个分子（原子）的集 体行为，一般通过统计方法来研究。然而，化学统计力学通常仅适用于“理想系统”（如理 想气体、完美晶体等），量子力学方法也不适用于动力学过程和有温度压力变化的系统。作 为替代方法，分子模拟将原子、分子按经典粒子处理，提供了化学系统的微观结构、运动过 程以及与宏观性质相关的数据和直观图象，从而能在更一般的情形下研究系统行为。分子模 拟有两种主要方法，一是基于粒子运动的经典轨迹的分子动力学方法，一种是基于统计力学 的蒙特卡洛方法。分子模拟技术不仅在计算化学中有用，而且还可用于药物设计和计算生物 学中的分子系统（从小的化学系统到大的生物分子）。 计算化学内部还包括量子化学计算、化学人工智能、化学 CAD 和 CAI 等领域，可以解 决识别化学结构与性质之间的相关性、化合物的有效合成、设计能与其他分子按特定方式进 行反应的分子（如新药设计）等问题。解决问题过程中所用到的计算化学方法有些是高度精 确的，更多的则是近似的。计算化学的目标是使计算误差极小化，同时保证计算是可行的。

## 11.3 计算物理学 计算物理学（computational physics）研究利用计算机来解决物理问题，是计算机科学、 计算数学和物理学相结合而形成的交叉学科。如今，计算物理已经与理论物理、实验物理一 起构成了物理学的三大支柱。 物理学旨在发现、解释和预测宇宙运行规律，而为了更准确地做到这一点，今天的物理 学越来越依赖于计算。首先，很多物理问题涉及海量的实验数据，依靠手工处理根本无力解决。例如在高能物理实验中，由于实验技术的发展和测量精度的提高，实验规模越来越大， 实验数据也大幅增加，只能利用计算机来处理实验数据。其次，很多物理问题涉及复杂的计 算，解析方法或手工数值计算无法解决这样的计算问题。例如电子反常磁矩修正的计算，对 四阶修正的手工解析技术已经相当繁杂，而对六阶修正的计算已经包含了 72 个费曼图，手 工解析运算已不可能完成。同样只能利用计算机来解决问题。 在物理学中运用计算思维，使我们可以利用数值计算、符号计算和模拟等方法来发现和 预测物理系统的特性和规律。 解决物理问题时，通常在获得描述物理过程的数学公式后，需要进行数值分析以便与实 验结果进行对照。对于复杂的计算，手工数值分析是不可能的，只能采用数值方法利用计算 机来计算。 有些物理问题不是数值计算问题，需要利用计算机的符号处理能力来解决。例如，理论 物理中的公式推导，就是纯粹的符号变换。有时即使是数值计算问题，由于精度要求很高， 导致计算耗时很长甚至无法达到所需精度，这时可以利用符号计算来推导出解析形式的问题 解。又如，有时数值方法是病态的，如果能将数值计算改成解析计算，则可以得到有意义的 结果。 统计物理中有个自回避随机迁移问题，它是在随机漫步中加上了一个限制，即以后的步 子不能穿过以前各步所走过的路径。这样的问题不像一般的迁移问题那样可以用微分方程来 描写系统的统计行为，计算机模拟几乎是唯一的研究方法。计算机模拟不受实验条件、时间 和空间的限制，只要建立了模型，就能进行模拟实验，因而具有极大的灵活性。下面通过一 个实例来介绍模拟方法在计算物理学中的应用。 热平衡系统的模拟 为了研究一个包含 N 个粒子的热系统，原则上只要了解每个粒子的运动，就能弄清楚 粒子和粒子之间的每一次相互作用。但由于粒子数目太大，要想计算 N 个粒子的轨迹以及 N(N-1)对相互作用，是非常困难的。 然而，对于处于平衡态的热系统，虽然系统的微观特性总是在变动，但其宏观特性则是 恒定不变的，体现为具有恒定的温度。系统的微观状态由每个粒子的速度等物理量来刻划， 粒子间的相互作用会导致微观状态改变；而系统的宏观状态是微观状态的集体特性，表现为 系统的总能量（或温度等）。统计物理学认为，虽然微观状态可能没有规则，但宏观状态服 从统计规律。对于处于平衡态的理想气体而言，虽然微观相互作用可导致粒子能量的重新分 配，但系统的总能量保持不变。 考虑一个由三个粒子组成的小系统 S。假设共有 4 份能量在这三个粒子之间交换，则能 量分布可以有以下 15 种状态：(4,0,0)、(0,4,0)、(0,0,4)、(3,1,0)、(3,0,1)、(1,3,0)、(0,3,1)、(1,0,3)、(0,1,3)、(2,2,0)、(2,0,2)、(2,1,1)、(0,2,2)、(1,2,1)、(1,1,2)。这里元组(a,b,c)表示三个粒子各 自获得的能量。每种微观状态都有自己的出现概率，例如从这 15 种微观状态可见，一个粒 子占有全部能量的概率为 3/15 = 0.2。S 的平衡特性由概率较高的微观状态决定，而通过随 机抽样方法（蒙特卡洛方法）可以有效地产生高可能性微观状态，从而可以用来评估 S 的 平衡特性。 我们引入一个“demon”来与系统 S 发生相互作用。作用方式是：令 demon 与 S 中某 个随机选择的粒子进行相互作用，并试着随机改变该粒子的状态（对气体来说就是改变粒子 的速度）；如果这个改变导致粒子能量减少，则执行这个改变，并将少掉的能量传递给 demon； 如果这个改变导致粒子能量增加，则仅当 demon 有足够能量传递给粒子时才执行这次改变。 按这种方式，每次产生新的微观状态时，系统 S 的能量加上 demon 的能量保持不变。 具体地，将 demon 加入到 S（包含三个微观粒子）中后，宏观状态仍为 4 份能量。新系统“S+demon”的 demon 为 0 能量的状态共有 15 个，正对应于原始系统 S 的那 15 个状态。 如果尝试改变一个微观状态使得某个粒子减少一份能量，则将那份能量转给 demon，这样就 使原始系统变成了具有 3 份能量的系统，而 demon 具有 1 份能量。与这种情况对应的微观 状态有 10 个，即(3,0,0)、(0,3,0)、(0,0,3)、(2,1,0)、(2,0,1)、(1,2,0)、(0,2,1)、(1,0,2)、(0,1,2)和(1,1,1)。由此可见，如果实施一系列的微观状态随机改变，将发现 demon 具有 1 份能量与 具有 0 份能量的相对概率为 10/15 = 2/3。也就是说，当 demon 扰乱小系统 S 时，S 仍然处于 原来的宏观能量的可能性更大，而不是处于某个较低能量。 同理，如果 demon 具有 2 份能量，则 S+demon 系统具有 6 个微观状态；如果 demon 具 有 3 份能量，则组合系统具有 3 种微观状态；如果 demon 拥有全部 4 份能量，则组合系统 只有一种微观状态。这几种情形对应的相对概率分别为 6/15、3/15 和 1/15。 一般地，对于一个宏观系统，当产生大量的微观状态改变之后，其中 demon 拥有能量 E 的微观状态，与 demon 拥有 0 能量的微观状态数目之比是随 E 的升高而呈指数形式下降的， 具体公式为  其中 k 是玻尔兹曼常数，T 是宏观系统的温度。以我们的小系统 S 为例，p(Ed=1) / p(Ed = 0) 约为 2/3。 总之，计算物理学依据理论物理提供的物理原理和数学方程，针对实验物理提供的实验 数据，进行数值计算或符号计算，从而为理论研究提供数据、帮助分析实验数据和模拟物理 系统。

## 11.2 生物信息学 计算生物学（computational biology）研究如何用计算机来解决生物学问题，主要研究内 容包括对生物系统的数学建模、对生物数据的分析、模拟等。本节介绍计算生物学的一个分 支——生物信息学①。 生物信息学（bioinformatics）主要研究生物信息的存储、获取和分析，这里所说的生物 信息主要是指基因组信息。近年来，通过庞大的项目合作，生物学家对人类基因组和其他生 物的基因组进行测序，获得了大量的数据。针对以指数方式增长的数据，生物信息学应用算 法、数据库、机器学习等技术，来解决 DNA 和蛋白质序列的分析、序列分类、基因在序列 中的定位、不同序列的比对、蛋白质结构及功能的预测和新药物新疗法的发现等问题。生物 信息学已成为处于生命科学和计算机科学前沿的一门有战略意义的学科，对医学、生物技术 以及社会的许多领域都有重要影响。 生物信息的表示 为了利用计算机来处理生物信息，首先要将生物信息表示成计算机中的数据。例如，听上去很复杂的 DNA 和蛋白质的链状分子，出乎意料地很容易表示——用符号序列即可。 DNA 是由 4 种单体，即以 A（腺嘌呤）、C（胞嘧啶）、G（鸟嘌呤）、T（胸腺嘧啶）代 表的 4 中核苷酸聚合成的生物大分子。蛋白质是另一类由 20 种单体，即以 A、C、D、W 等 表示的 20 种氨基酸聚合成的大分子。在链状分子的特定位置上，只能出现某种确定的单体（“字符”），而不是几种可能字符的组合，因此分子链可以用一维的、不分岔的。有方向的 字符序列来表示。例如，DNA 分子可表示成如“AGTGATG”一样的字符序列。 测定 DNA 和蛋白质链状分子的字符序列是从微观结构研究生物的出发点。 除了序列数据，生物信息还包括结构和功能数据、基因表达数据、生化反应通路数据、表现型和临床数据等。 生物信息数据库 数据库技术是管理大量数据的计算机技术，目的是使用户能够方便、高效地访问大量数据。过去数十年间，随着人类基因组测序工程和其他生物测序项目的完成或推进，以及诸如 DNA 微阵列等高效实验技术的出现，产生并积累了大量的生物信息（如前面所说的核苷酸 序列和氨基酸序列），因此需要利用数据库技术将这些信息组织、存储起来。有了生物信息 数据库，生物学家们通过易用的 GUI 来访问数据库，既可以读取数据，也可以添加新数据 或者修订老数据。当然，更重要的工作是利用各种算法来处理数据库中的生物数据。生物学 未来的新发现很可能是通过分析数据库中的生物数据获得的，而非仅仅依赖于传统的实验。 > ① 也有说生物信息学和计算生物学是一回事的。 互联网上有很多生物数据库，例如 EMBL（核苷酸序列数据库）、GenBank（基因序列 数据库）、PDB（蛋白质数据库）等等。 生物数据分析 建立了生物信息数据库之后，生物学家接下来的研究重点就转向了数据分析。庞大的生 物信息数据库对数据分析技术提出了具有挑战性的问题，人工分析 DNA 序列早已成为不可 能完成的任务，传统的计算机算法也越来越显示出不足，这促使生物信息学去寻求新的算法 来解决问题。 序列分析是生物信息学的主要研究内容。例如，通过分析数据库中的成千上万种有机体 的 DNA 序列，可以识别特定序列的结构和功能、特定序列在不同物种之间的不同形式、相 同物种内部特定序列的不同形式。又如，通过对一组序列进行比较，可以发现功能之间的相 似性或者物种之间的联系。还可以在一个基因组中搜索蛋白质编码基因、RNA 基因和其他 功能序列，可以利用 DNA 序列来识别蛋白质。 下面介绍基因组比对的基本思想和方法。当生物学家通过实验获得了一个基因序列，他 接着就要确定这个基因序列的功能。为此，他以这个基因序列作为输入，到基因序列数据库 中去搜索与之相似的、已知功能的基因序列，因为生物学家认为基因序列相似意味着功能相 似。一种衡量基因序列相似性的方法是基因组比对（genome alignment），该方法将两个基 因序列对齐（如果序列长度不同可以在序列中插入一些空白位置），然后为对齐的每一对（代 表核苷酸的）字符打分，所有分数的总和就是两个序列的相似度。例如，对于两个基因序列 AGTGATG 和 GTTAG，适当插入空白（用下划线字符“_”表示）后可以按如下方式对准： ``` A G T G A T G _ G T T A _ G ``` 假如按如下规则打分： | | A | C | G | T | _ | | --- | --- | --- | --- | --- | --- | | A | 5 | -1 | -2 | -1 | -3 | | C | -1 | 5 | -3 | -2 | -4 | | G | -2 | -3 | 5 | -2 | -2 | | T | -1 | -2 | -2 | 5 | -1 | | _ | -3 | -4 | -2 | -1 | | 则该对准方案的得分为 14。当然也可以按别的方式对准，但上面给出的对准方案是得分最高的。这个最优对准方案可以利用动态规划算法求得。 另外，计算机科学中最新的机器学习和数据挖掘技术能够实现更复杂的数据分析，很自然地成为当今生物信息学所倚重的方法。机器学习和数据挖掘的领域界线并不明显，它们都 是关于从大量数据中发现知识、模式、规则的技术。具体技术包括神经网络、隐马尔可夫模 型、支持向量机、聚类分析等，这些技术都非常适合生物信息的分析和处理。例如，对大量 蛋白质序列进行聚类分析，可以将所有蛋白质序列分组，使得同组的蛋白质序列非常相似， 而不同组的蛋白质非常不相似。

## 11.1 计算数学 计算数学是关于通过计算来解决数学问题的科学。这里所说的“计算”既包括数值计算， 也包括符号计算；这里所说的“数学问题”可能来自纯数学，更可能是从各个科学和工程领 域抽象出来的。计算数学包括很多分支，其中最核心、应用最广的是数值方法。 数值方法 数值方法（numerical method，也称计算方法、数值分析等）是利用计算机进行数值计 算来解决数学问题的方法，其研究内容包括数值方法的理论、分析、构造及算法等。很多科 学与工程问题都可归结为数学问题，而数值方法对很多基本数学问题建立了数值计算的解决 办法，例如线性代数方程组的求解、多项式插值、微积分和常微分方程的数值解法等等。 数值方法的构造和分析主要借助于数学推导，这是数学思维占主导的部分。例如，一元 二次方程的求根公式实际上给出了方程的数值解法，该公式完全是通过数学推导得出的；而 通过对该公式的分析，可以了解实数根是否存在等情形。如果问题不存在有限的求解代数式， 可以通过数学推导来寻求能得到近似解的代数式，例如将积分转化为求和。 数值方法最终要在计算机上实现，这是计算思维占主导的部分。有人也许会认为，对于 数值计算问题，只要有了求解问题的数学公式，再将这些公式翻译成计算机程序，问题就迎 刃而解，所以数值方法的关键是数学推导，而计算思维在其中并没有什么作用。是不是这样 呢？仍以一元二次方程 ax2+bx+c=0 的求解问题为例。这个问题的求解求根公式是已知的：  这个公式可以直接了当地翻译成 Python 程序（程序 3.5）： ``` import math a, b, c = input("Enter the coefficients (a, b, c): ") discRoot = math.sqrt(b * b - 4 * a * c) root1 = (-b + discRoot) / (2 * a) root2 = (-b - discRoot) / (2 * a) print "The solutions are:", root1, root2 ``` 下面是此程序的一次执行结果： ``` Enter the coefficients (a, b, c): 1,-(9+10**18),9*10**18 The solutions are: 1e+18 0.0 ``` 可见，计算机求解方程 x\*\*2 -(9+10\*\*18)x + 9x10\*\*18 = 0 所给出的根是 10\*\*18 和 0，而非正确的 10\*\*18 和 9。对于这个结果，传统的数学是无法解释的，只有明白了计算机的能力和限制，才能给出解释。计算思维在计算方法中的意义，由此可见一斑。 利用数值方法解决科学与工程问题大体要经过三个步骤。第一步是为问题建立数学模型，即用合适的数学工具（如方程、函数、微积分式等）来表示问题；第二步是为所建立的 数学模型选择合适的数值计算方法；第三步是设计算法并编程实现，这里要着重考虑计算精 度和计算量等因素，以使计算机能够高效、准确地求解问题。在计算机上执行程序得到计算 结果后，若结果不理想，多半是因为所选数值方法不合适，当然也可能是数学模型不合适。 在模型正确、编程正确的前提下，计算结果完全取决于数值方法的选择。 本节只简单介绍计算机的能力和限制是如何影响计算方法的选择的。 误差 正如前述一元二次方程求解例子所显示的，一个正确的数学公式在计算机上却得不到正 确的、精确的结果，这种现象主要是由误差引起的。科学与工程计算中的误差有多种来源， 其中建立数学模型和原始数据观测两方面的误差与计算方法没有关系，与计算方法有关的是 截断误差和舍入误差。 截断误差是在以有限代替无限的过程中产生的，例如计算 ex 的泰勒展开式  时只能选取前面有限的 n 项，得到的是 ex 的近似值，前 n 项之后的部分就是截断误差。 舍入误差是因计算机内部数的表示的限制而导致的误差。在计算机中能够表示的数与数 学中的数其实是不一样的：计算机只能表示有限的、离散的数，而数学中的数是无限的、连 续的。以有限表示无限，以离散表示连续，难免造成误差。例如 Python 中有如下出人意料 的数值计算结果： ``` >>> 1.2 - 1 0.19999999999999996 ``` 由于浮点数内部表示的限制，1.2 - 1 的结果并非精确的 0.2。又如，积分计算问题  是连续系统问题，由于计算机不能直接处理连续量，因此需要将连续的问题转化为离散的问 题来求解。一般常用离散的求和过程来近似求解积分①。  舍入误差的控制 计算机内部对数的表示构成一个离散的、有限的数集，而且这个数集对加减乘除四则运算是不封闭的，即两个数进行运算后结果会超出计算机数集的范围。这时只好用最接近的数 来表示，这就带来了舍入误差。因此，应当控制四则运算的过程，尽量减小误差的影响。 在加减法运算中，存在所谓“大数吃小数”的现象，即数量级相差较大的两个数相加减 时，较小数的有效数字会失去，导致结果中好像没做加减一样。例如 ``` >>> 10**18 + 9.0 1e+18 ``` > ① 据说积分号就是从 S（sum）演变而来的符号。 由此可知，当有多个浮点数相加减时，应当尽量使大小相近的数进行运算，以避免大数 “吃”小数。例如，设 x1 = 0.5055×104，x2 = x3 = ... = x11 = 0.4500（假设计算机只能支持 4 位有效数字），要计算诸 xi 的总和。一种算法是将 x1 逐步与 x2 等相加，这样每次加法都是大 数加小数，按计算机浮点计算的规则：x1 + x2 ＝ 0.5055×104 + 0.000045×104 ＝ 0.505545×104＝0.5055×104，即产生了舍入误差 0.45。如此执行 10 次加法之后，结果仍然是 0.5055×104，误差积累至 10×0.45 ＝ 4.5。另一种算法是让相近数进行运算，如 x11 + x10 = 0.9000， 在一直加到 x1，执行 10 次加法之后得到总和 0.5060×104，没有舍入误差。这个例子再次显 示了“次序”在计算中的重要意义：数学上毫无差别的两种次序在计算机中却带来截然不同 的结果，就像我们在第 3 章中计算 231-1 时采用 230-1+230 这个次序一样。 当两个相近的数相减时，会引起有效数字的位数大大减少，误差增大。为了避免这种结 果，通常可以改变计算方法，将算式转化成等价的另一个计算公式。例如：  在除法运算中，应当避免除数接近于零，或者除数的绝对值远远小于被除数的绝对值的 情形，因为这两种情形都会使舍入误差增大，甚至使结果溢出。解决办法仍然是转化为等价 算式。例如：  这里，不同计算公式的选择就如同上述不同计算次序的选择，虽然在数学上结果是一样 的，但在计算机中却存在很大差别。 计算量 站在计算机的角度，对数值方法主要关注的是算法的效率和精度。算法的效率由算法复 杂度决定，数值方法中通常用浮点乘除运算（flop）的次数来度量算法效率，称为算法的计 算量。计算量越小，效率就越高。 当一个算法的计算量很大，并不意味着它能提高计算结果的准确度，相反倒有可能使舍 入误差积累得更多，可谓费力不讨好。利用数学推导来简化计算公式，或者利用计算机的运 算及存贮能力来巧妙安排计算步骤，都可以减少计算量，使计算更快、更准确。 例如，设 A、B、C 分别是 10×20、20×50、50×1 的矩阵，我们来考虑如何计算 ABC。 一种算法是先算 AB，再乘 C，计算量为 10500flops；另一种算法是先算 BC，再用 A 乘， 计算量为 1200flops。显然后一种算法大大优于前一算法，再次显示了“次序”的妙处。 又如，考虑如何计算 x64。一种算法是将 64 个 x 逐步相乘，计算量为 63flops；另一算 法利用  其中 x\*\*2k（k＝2，4，8，16）的计算都可以利用前一步算出的结果，即  这样计算量可以降至 10flops。 有些数值算法甚至会使计算量大到失去实际意义的地步，就如 Hanoi 塔问题的算法对较 大问题规模不可行一样。例如求解 n 元线性方程组的克莱默法则对于较大 n 就是不可行的方 法，因为其计算量是(n+1)(n-1)(n!)+n；而高斯消去法的计算量仅为 n3/3+n2-n/3，是非常高 效的算法。 病态与良态问题 有些问题的解对初始数据非常敏感，数据的微小变化会导致计算结果的剧烈变化，这种 问题称为病态问题，反之称为良态问题。例如多项式 p(x) = x2+x-1150 在 100/3 和 33 处的值 分别为-5.6 和-28，数据变化只有 1%，而结果变化了 400%。又如下面这个方程组  的解是 x1 ＝ x2 ＝ x3 ＝1，当将各个系数舍入成两位有效数字，与原来的系数虽然差别不 大，但方程组的解却变成了 x1 ≈ -6.22，x2 ＝38.25，x3 ＝ -33.65。 相反，下面这个方程组  的解为 x1 =2，x2 = -2。若对其常数项-2 做微小扰动改为-2.005，则解变成 1.999 和-2.002， 与原来的解差别很小。可见这个问题是良态的。 数值方法主要研究良态问题的数值解法。由于实际问题的数据往往是近似值，或者是经 过舍入处理的，这相当于对原始数据的扰动，如果求解的是病态问题，则会导致很隐蔽的错 误结果。病态问题在函数计算、方程求根、方程组求解中都存在，它的计算或求解应当使用 专门的方法，或者转化为良态问题来解决。 数值稳定性 求解一个问题的数值方法往往涉及大量运算，每一步运算一般都会产生舍入误差，前面 运算的误差也可能影响后面的运算。一个数值方法如果在计算过程中能将舍入误差控制在一 定范围内，就称为数值稳定的，否则称为数值不稳定的。例如，考虑下面这个积分的计算：  根据上面这个递推式，可得出迭代算法：   这个算法是不稳定的，因为 I0 的舍入误差会随着迭代过程不断传播、放大。编程计算一下 可见，结果中甚至出现了负数，而根据原积分式可知 In 应该总是大于 0。 ``` >>> def f(): x = 0.1823 print "I0 =",x for n in range(1,101): x = -5 * x + 1.0 / n print "I"+str(n)+" =",x >>> f() I0 = 0.1823 I1 = 0.0885 I2 = 0.0575 I3 = 0.0458333333333 ... I97 = 1.36042495942e+63 I98 = -6.80212479709e+63 I99 = 3.40106239854e+64 I100 = -1.70053119927e+65 ``` 现在利用下列关系式  先对足够大的 n 取 I_n 的估计值，然后再计算 I_n-1、I_n-2、…、I₁。迭代算法如下：  这个算法可使误差逐渐减小，因此是数值稳定的，下面程序的运行结果验证了这一点。此例又一次显示了次序的重要性。 ``` >>> def g(): x = 0.001815 print "I100 =",x for n in range(100,0,-1): x = -x/5 + 1.0/(5*n) print "I"+str(n-1)+" =",x >>> g() I100 = 0.001815 I99 = 0.001637 I98 = 0.0016928020202 I97 = 0.00170225592249 ... I3 = 0.043138734089 I2 = 0.0580389198489 I1 = 0.0883922160302 I0 = 0.182321556794 ``` 综上所述，数值方法以利用计算机进行数值计算的方式来解决科学和工程中抽象出来的 数学问题。与纯数学方法不同，数值计算方法的构造和算法实现必须考虑计算机的能力和限 制，亦即计算思维的原则对计算方法具有重要影响。

# 第 11 章 计算+X 当代科学研究有三大支柱：理论、实验和计算。计算机技术的发展，为利用计算手段来 解决科学和工程问题提供了强大的支持。越来越多的领域（包括自然科学和社会科学领域） 利用计算来解决问题，将解决问题的方法从过去的定性分析发展成如今的定量计算。科学领 域与计算的结合促成了多种交叉学科的形成，如计算数学、计算物理学、计算化学、计算生 物学、计算材料学、计算经济学、计算语言学、计算考古学、计算犯罪学、计算免疫学等等。 各学科下面的子学科冠以“计算”前缀的更是数不胜数，如计算数学下面的计算几何、计算 数论、计算拓扑学，计算语言学下面的计算语义学、计算词汇学、计算幽默学等。 本章介绍一些典型的“计算+X”，以使读者初步了解计算和计算思维是如何帮助各专业 领域求解问题的。

## 10.7 练习 1\. 程序设计：找出最小自然数 n，n 满足条件“用 3 除余 2，用 5 除余 3，用 7 除余 4”。 2\. 设计递归算法来解决问题：求无序数值列表 L 的最大值和最小值。 3\. 改进线性搜索算法：在开始查找 x 之前，先在列表尾添加 x。这样查找 x 总能成功，但若 返回的索引是列表尾，则意味着原列表中没有 x。分析、比较这个改进版本与原版本的性能。 4\. 假如将“为问题 P 设计算法”本身作为问题，这个问题有没有算法？

## 10.6 不可计算的问题 到目前为止，我们讨论的所有问题都是可解的。有些问题的解法非常有效，有些问题的 解法则比较复杂。Hanoi 塔之类的问题称为难解问题，因为当问题规模较大时，相应算法需 要太多太多的时间（或空间）来完成计算，事实上是无效、不可行的解法。 现实中还存在比难解问题更麻烦的问题，那就是不可解问题。考虑这个场景：计算机正在执行一个程序，我们坐在边上等待程序结束。当过了很久程序还没结束时，我们该怎么办 呢？我们可能推测程序中出现了无穷循环，永远不会结束，这样我们就必须强行中断程序运 行甚至重启计算机。然而，我们并不能绝对肯定是出现了无穷循环，也许是因为计算太复杂 导致时间过长呢？这样的话，我们就该继续等待。显然，这是一个两难困境。我们设想，要 是有这么一个程序 P 就好了：P 的功能是以另一个程序 Q 的代码作为输入，并分析 Q 中是 否包含无穷循环。然而很遗憾，这样的程序 P 是不存在的！这个问题其实对应于图灵机的 停机问题，下面对此进行简要介绍。 图灵机 英国数学家 Alan Turing 于 1936 年发明了一种抽象机器用于研究计算的本质，人们称这 种机器为图灵机（Turing machine）。图灵机能够模拟算法式计算，即按预定的规则一步一步 执行基本指令的过程。现代计算机就是这样按照预定的程序一步一步执行指令的，因此可以 视为图灵机的具体实现。 人们为了进行计算，需要用到纸和笔。类似地，图灵机在“硬件”上由一条纸带和一个 读写头组成：纸带用于记录信息，读写头用于读写信息。纸带在读写头下移动，读写头即可 在纸带上写下符号（如 0 和 1）或读出符号。这有点类似磁带录音机中磁带与磁头的关系， 但与录音机的顺序录音或回放不同的是，图灵机的读写头和纸带受预定的规则（相当于我们 熟悉的程序）的控制。参见图 10.13。  图 10.13 图灵机的纸带和读写头 下面对图灵机进行更详细的描述。一个图灵机涉及以下一些要素： + 纸带：纸带被划分成一个个格子单元，单元中可以写入符号。纸带在向左、向右两 个方向上都是无限延伸的，即图灵机的存储能力不受限制。 + 读写头：用于读写纸带单元中的符号。纸带在读写头下可以向左或向右移动，每次 移动一个单元。当然也可以理解成纸带不动而读写头左右移动。 + 符号表：能够写入纸带的合法符号。具体用什么符号系统并不重要，正如现代计算 机基于二进制一样，只要提供 0 和 1 两个符号就足够从事任何计算。 + 状态：图灵机在任一时刻都处于某种状态，例如当前读写头下方是 0 或 1 即对应不 同状态。不同状态的数目是有限的。两个特殊状态分别是开始状态和停止状态。 + 指令：指令描述的是如何根据图灵机的当前状态以及当前读写头所读到的符号来控 制图灵机执行特定动作并转换为新的状态。形如： 当前状态，输入符号 ® 新状态，输出符号，移动读写头 预定的多条指令构成一个指令表（程序），它完全决定了图灵机的行为。图灵机的 运行就是按照指令表所确定的状态转换规则一步一步进行状态转换的过程。 下面我们设计一个对给定正整数 n 加 1 的图灵机。 【图灵机 T+1】T+1 的符号表仅由 0（表示空白）和 1 组成。正整数 n 在纸带上用 n 个连续单 元的 1 表示，例如 1、2、3 在纸带上分别表示为 1、11、111。读写头初始位置是在输入数 据 n 的左方，停止位置是在输出数据 n+1 的最后一位 1 之上。初始状态为 s1，停止状态为 s3。指令表如下： ``` s1, 0 => s1, 0, R s1, 1 => s2, 1, R s2, 0 => s3, 1, Stop s2, 1 => s2, 1, R ``` 假设输入数据是 3，则图 10.14 展示了 3+1 的计算过程。读写头里记录的是图灵机当前 状态。  图 10.14 计算 n+1 的图灵机 T+1（输入 n=3） 第 1 条指令的意义是：当图灵机 T+1 处于 s1 状态，并且读写头所读单元的内容是 0，那 么就保持 s1 状态，也不改动该单元的内容，然后读写头右移。第 3 条指令的意义是：当 T+1 处于 s2 状态，并且读写头所读单元里的内容是 0，那么就进入 s3 状态，将该单元内容改为 1， 然后停止。其他两条指令的意义请读者自行解读。从初始状态开始执行这些指令，经过 6 步状态转换，T+1 将终止，并且终止时纸带上的计算结果是 4 个连续的 1，表示正整数 4。 尽管图灵机是如此简单，但它的计算能力却非常强大。从上例可知，存在计算 n+1 的图灵机，由此不难想象可以设计出计算 n+m 的图灵机，进而可以设计出计算 n×m 的图灵 机，等等。注意，这里我们谈论图灵机的计算能力，并非针对它的计算速度或存储空间，因 为图灵机毕竟不是现实的计算机。研究图灵机是为了在理论上探索计算的能力和局限，例如 回答计算机科学的一个根本问题：究竟什么是可计算的？对此，Turing 和 Church 分别通过 研究图灵机和λ演算，得出了一个重要假设——Turing-Church 论题，其大致意思是：一个 问题是能行可计算的（即算法可计算），当且仅当该问题能用图灵机来计算。因此，图灵机 事实上给出了“算法计算”或“机械计算”的精确意义。 图灵机的强大计算能力有一个重要表现，那就是一个图灵机可以模拟另一个图灵机的工 作。如果将图灵机 T 1 的功能进行编码，然后输入给另一图灵机 T 2，那么 T 2 就能表现得像 T 1 一样。打个比方，这就像一个人可以模拟另一个人的行为一样。假设张三既懂加法又懂 乘法，并且他知道不懂乘法的李四总是错误地将 n×m 算成 n+m，那么当我们将 n 和 m 输 入给张三要他计算 n×m 时，他完全可以故意输出 n+m 来冒充李四。 既然一个图灵机可以模拟另一个图灵机的行为，那我们就可以设计一个通用图灵机，它 可以模拟任何图灵机的行为。对此读者应不陌生，因为我们在第 1 章就说过，现代计算机是通用计算机，给它安装不同的程序，就能完成不同的功能。图 10.15 展示了如何用通用图灵 机 UT 来模拟某个特定图灵机 T：将 T 的行为（指令表）用 0/1 序列进行编码得到 Tcode， 连同 T 的输入数据 data 一同输入给 UT，然后 UT 即可对 Tcode 进行解码，并针对 data 来模 拟 T 的行为。  图 10.15 通用图灵机 UT 模拟特定图灵机 T 如果用函数来表示图灵机，则 UT 模拟 T 的行为可表示为 ``` UT(Tcode,data) = T(data) ``` 停机问题 对任何给定的图灵机 T，以及输入数据 data，T 可能停机，也可能不停机。上面计算 n+1 的图灵机 T+1 显然总是能停下来的，因为正整数 n 在纸带上表示为 n 个连续的 1，T+1 的第二 条指令要求读写头只要读到 1 就不断向右移，因此最终会读完这有限个数的 1，并读到连续 1 右方的第一个 0，第三条指令会将这个 0 改写为 1，并停机。 一个图灵机也很容易不停机。例如这样一条指令就有可能令图灵机无法终止： ``` s1, 0 => s1, 0, NoMove ``` 即，在 s1 状态读到 0 时，保持 s1 状态和单元内容 0 不变，并且读写头也不移动。如果一个 图灵机进入到 s1 状态并且恰好读到 0，那么这个图灵机就将永远处于这个状态而不停机。不难看出，这条指令的行为与 Python 中的无穷循环语句 ``` while True: pass ``` 是一样的。顺便说明一下，pass 是 Python 语言的一条语句，功能是什么都不做。 我们当然希望设计的图灵机能正确地完成计算并停机，可现实经常不能如我们所愿，就 像我们编写的程序经常陷入无穷循环而不能终止一样。更让人烦恼的是，当图灵机（或程序） 一直在执行而不终止时，我们并不知道它是否陷入无穷循环了！现实中，我们只能通过运行 时间长短的经验来判断到底是什么情况，但这毕竟是不可靠的。有没有办法来检验图灵机是 否停机呢？也就是说，能不能设计这样的通用图灵机 HT，它的输入是另一个图灵机 T（的 编码）和 T 的输入 data，它的功能是判断 T 在 data 上执行后是否停机：如果是，则 HT 输出 1 并停机；如果不是，则 HT 输出 0 并停机。亦即，HT 是判断其他任意图灵机是否终止的 图灵机。 上述 HT 是否存在？这就是所谓停机问题（Halting problem）。Turing 的一个重要成果就 是证明了 HT 不存在！下面我们用程序设计的术语来非形式地描述这个证明。 从程序设计角度看，停机问题就是要编一个程序 halt，它读入另一个程序 prog 的源代 码，并判断 prog 是否导致无穷循环。由于 prog 的行为不仅依赖于它的源代码，还依赖于它 的输入数据，因此为了分析 prog 的终止性，还要将 prog 的输入数据 data 交给 halt。由此可 得 halt 的规格说明： ``` 程序：停机分析程序 halt； 输入：程序 prog 的源代码，以及 prog 的输入数据 data； 输出：如果 prog 在 data 上的执行能终止，则输出 True，否则输出 False。 ``` 读者也许会觉得向程序 halt 输入另一个程序 prog 作为处理对象有点不可思议，但其实 这是非常普通的事情。例如，编译器（或解释器）就是这样的程序：将一个程序 P 的源代 码输入给编译器程序 C，C 可以分析 P 中是否有语法错误，有则报错，没有则输出 P 的目标 代码。 在停机问题中，正常情况下是想运行 prog(data)，但又不知道这个执行过程能不能终止， 于是希望将 prog 的代码和 data 交给停机分析程序 halt，由 halt 来判断 prog(data)的终止性。 由 halt 的程序规格可见，halt 总是能得出结论并终止的，从而避免了直接执行 prog(data)时 无法确切知道它是否能终止的困扰。 设计 halt 程序的初衷可以理解，可惜这个程序是编不出来的。我们用反证法来证明这个 结论，即先假设存在程序 halt，然后推导出矛盾来。 假如我们已经设计出了停机分析程序 halt，其参数是两个字符串：prog 是被分析的程序 的源代码，data 是 prog 的输入数据。 ``` def halt(prog,data): …… # 分析 prog 代码，如果对 prog 输入 data 时运行能终止 return True …… # 如果 prog 运行在 data 上不能终止 return False ``` 利用 halt 的功能，我们可以编出如下这个奇妙的程序： ``` def strange(p): result = halt(p,p) if result == True: # 即 p(p)终止 while True: pass else: # 即 p(p)不终止 return ``` 运行 strange(strange),结果如何? 函数 strange()有一个字符串类型的形参 p，调用时需传递一个程序给它，不妨假设所传 递的程序也是以一个字符串数据作为输入。strange 首先调用 halt(p,p)，这里的关键技巧是， 传递给函数 halt 的形参 prog 和 data 的实参都是 p，亦即我们要分析程序 p 以它自己为输入 数据时——即 p(p)——运行是否终止。strange 根据 halt(p,p)的分析结果来决定自己接下去怎 么做：如果结果为 True，即 p(p)能终止，则 strange 进入一个无穷循环；如果结果为 False， 即 p(p)不终止，则 strange 就结束。 strange 程序看上去有点费解，但只要 halt 存在，strange 在编程方面显然没有任何问题。 接下来是证明过程的最美妙的部分：假如将 strange 自身的源代码输入给 strange 时会发生什 么？更确切地，strange(strange)能否终止？ 我们参照上面的 strange 代码来分析。假如调用 strange(strange)不终止，那必然是因为 执行到了代码中条件语句的 if result == True 部分，即 halt(strange,strange)返回了 True，这又 意味着 strange 以 strange 为输入时运行能终止！另一方面，假如调用 strange(strange)能终止， 那必然是因为执行到了条件语句的 else 部分，即 halt(strange,strange)返回了 False，这又意味 着 strange 以 strange 为输入时运行不能终止！总之，我们得到了如下结论： 若 strange(strange)不终止，则 strange(strange)终止； 若 strange(strange)终止，则 strange(strange)不终止。 这样的结论在逻辑上显然是荒谬的。导致这个矛盾的原因在于我们假设了 halt 的存在，并利 用了 halt 的功能。至此，我们证明了编写 halt 程序是不可能完成的任务，即停机问题是一个 不可解问题。 停机问题不可解的证明过程具有非常深刻的意义，它告诉我们算法式计算具有本质上的 局限性。计算机虽然在各行各业解决了很多问题，但是确实存在计算机不能解决的问题。

### 10.5.2 算法分析实例 本节以本章介绍的若干算法为例来讨论对算法复杂性的分析。 搜索问题的两个算法 对于搜索问题，本章介绍了线性搜索和二分搜索两个算法。 线性搜索算法的思想是逐个检查列表成员，编码时可以用一个循环语句来实现。循环体 的执行次数取决于列表长度：如果列表长度为 n，则循环体最多执行 n 次。因此，如果列表 长度增大一倍，则循环次数最多增加一倍，算法执行的步数或实际运行时间最多增加一倍。 可见，线性搜索算法在最坏情形下的运行时间与输入列表的大小 n 呈线性关系，即复杂度为 O(n)，称为线性时间算法。 二分搜索算法的主体也是一个循环，但该循环不是逐个检查列表数据，而是每次检查位 于列表中点的数据，并根据该中点数据与要查找的数据的大小比较情况来排除掉左半列表或 右半列表。接着对保留下来的一半列表重复进行这个“折半”过程。显然，循环的次数取决 于输入列表能“折半”多少次。如果初始输入列表有 16 个数据，则第一轮循环后剩下 8 个数据，第二轮循环后剩下 4 个数据，第三轮后剩下 2 个，第四轮后只剩下 1 个数据。因此， 最多四轮循环后就能得出搜索结论：要么找到，要么不存在。一般地，如果输入规模为 n， 则二分搜索算法最多循环 log2n 次，即复杂度为 O(log2n)，称为对数时间算法。要说明的是， O(log2n)表示复杂度与问题规模 n 的对数成正比，至于这个对数是以 2 为底还是以 10 为底并 不重要，因此我们经常省略对数的底，写成 O(log n)。 O(n)与 O(log n)到底有多大差别？回到 10.2 中提到的猜数游戏，假如某甲心中想好一个1百万以内的数让某乙来猜。某乙从小到大逐个试猜（即线性搜索）的话，运气好猜 1 次就能命中，运气不好最多要猜 1 百万次。平均来说需要猜 50 万次才能猜中。而如果某乙每次 猜中间数（即二分搜索）的话，则最少猜 1 次，最多也不过猜 log21000000≈20 次就能猜中。 可见，随着 n 的增大，O(log n)远远优于 O(n)。 排序问题的两个算法 对于排序问题，本章介绍了选择排序和归并排序两个算法。 首先推导选择排序算法的步数与问题规模（即数据列表的长度）的关系。选择排序算法 首先找出全体数据中的最小值，并将该值作为结果列表的第一个成员。其次，算法从剩余数 据中找出最小值，并将该值作为结果列表的第二个成员。依此类推，直至产生有序列表。假 设列表初始大小为 n，为找出最小值，算法需检查每一个数据。接下来算法从剩余 n-1 个数 据中找出最小值，这需要检查 n-1 个数据；第三次循环从 n-2 个剩余数据中找出最小值。这 个过程一直继续到只剩 1 个数据为止。因此，选择排序需要执行的步数为  按照前述规则，可以看出选择排序算法所需的步数与数据列表大小的平方成正比，即算法复杂度为 O(n²)，称为二次方时间算法。 其次，我们来推导归并排序算法的步数与列表大小的关系。归并排序算法的基本思想是将列表一分为二，然后对两半数据各自排序，最后再合并成一个列表。其中对两个子列表的 排序又是通过递归调用归并排序来实现的，最终将分解到长度为 1 的列表，这时可直接进行 归并。由此可见真正的排序工作是在归并过程中完成的，该过程所做的只是将来自子列表的 数据按从小到大的顺序逐个复制到初始列表的合适位置。图 10.11 展示了对列表[0,5,7,2]进 行归并排序的过程。图中用虚线表示初始列表的递归分解过程，逐步分解后最终得到长度为 1 的列表。这些长度为 1 的列表再进行归并，逐步形成长度为 2、4 的有序的列表，图中用实线箭头表示归并时各数据的逐步到位过程。从图 10.11 容易分析出归并排序算法的步数。 从左向右，分解过程并不比较数据大小来排序，这部分工作可以忽略。接下来的归并过程包 含大量比较、复制操作，是整个算法的工作量的体现。归并过程分为 log2n 层，以逐步形成 长度为 2、22、23、…、n 的有序子列表①。又因为每一层归并都需要对全部 n 个数据进行处 理，所以归并排序算法的步数是“n×层数”，即具有复杂度 O(nlog n)，可称为 nlog n 时间 算法。  图 10.11 归并排序过程示意图 n² 与 nlog n 有多大差别呢？当 n 较小时，两者差距不大，选择排序算法甚至有可能还快 一些，因为它的代码更简单。但是，随着 n 的增大，log n 只是缓慢地增大，因此 n×log n 的增长速度远远低于 n×n。这就是说，对于大量数据，归并排序算法的性能远远好于选择 排序算法。 > ① 如果 n 不是 2 的幂，子列表的长度当然也不会都是 2 的幂。 Hanoi 塔算法 下面推导 Hanoi 塔问题的递归算法的步数与圆盘个数 n 的关系。与基于循环（迭代）的算法不同，递归算法不容易直接从代码形式上看出具体的操作步数。对于 Hanoi 塔递归算法， 我们可以直接考虑将 n 个圆盘从 A 柱移到 C 柱所需的移动次数。 根据算法的结构，为了移动 n 个圆盘，需要先将 n-1 个圆盘从最大圆盘上移开，然后移 动最大圆盘，最后再将 n-1 个圆盘移到最大圆盘上。假设 f(n)是移动 n 个圆盘所需的步数， 则应用一点中学数学知识很容易推导出  可见，Hanoi 塔算法的复杂度为 O(2n)，称为指数时间算法，这是因为问题规模的度量 n 出 现在步数公式的指数部分。 指数时间算法到底有多复杂呢？读者也许听说过“指数爆炸”这个名词，它表明指数时 间算法所需要的执行时间会随着问题规模的增长而迅速增长。在 Hanoi 塔故事中，即使僧侣 们 1 秒钟就能移动一步圆盘，并且每天都不休息，为了移动 64 个圆盘，也需要花费 264－1秒，即 5850 亿年！可见，指数时间算法只适用于解决小规模的问题。 总之，利用计算机解决问题时，需要考虑算法的时间复杂性，这是衡量问题难度和算法 优劣的一个重要指标。有些应用对于运行时间有较高要求，运行时间过长的话可能导致计算 结果过时、失效。图 10.12 给出了本章见过的各种算法复杂度的大致比较，图中横坐标表示 问题规模 n，纵坐标是算法执行时间（或步数）。虽然图中曲线不是很精确，但足以说明指 数时间和二次方时间算法是多么不适合大量数据，而其他几种复杂度的曲线则相当平缓。  图 10.12 各种算法复杂度比较