動態規劃演算法硬幣收集問題論文

A. 如何准備互聯網公司面試（演算法相關）

書籍： 《演算法導論》 這本是大部頭，很多人都看不完。我本人也並沒有看完，它跟了我這么多年，完全是屬於常看常新的牛書。每一次看，都發現會有新的收獲。比如，以前並不知道求K位數或者中位數有平均為O(n)復雜度的演算法。看到了別的地方的參考資料，才知道，原來《算導》上專門有一小節講這個內容。我基本上是本科比較集中的看了一遍，研一的時候又集中的看了一遍，才算是粗略的看完。但是其實，很多理論性的，以及圖論一部分依然還是沒有看完。個人推薦，先從簡單的開始，挑選比較熟悉的一些偏重與數據結構方面的知識作為起點。這本書的習題非常重要，要是有時間，能夠全部做完，那絕對是能夠神功在手了。其實，集中把，第二部分（排序），第三部分（數據結構），第四部分（高級設計，我基本主要看動態規劃和貪心），第五部分（高級數據結構，B樹和二項堆，並差集），第六部分（圖演算法，最大流部分較難，自己可以看情況掌握）。這些部分可以先從演算法本身開始，偽代碼全部看懂。因為演算法導論講的很詳細，而且有來龍去脈，基本不會有太大難度。數學證明，推薦大家掌握，但是，突擊或者第一次，可以選擇性的看看。我自己是重復看，才把證明看掉的。第一次看的時候，基本都跳過了。不過，證明和習題是精髓！希望如果有時間，一定要補回來。 《編程之美》《挑戰編程》 這本書絕對是將全中國企業，或者說是一部分懶惰的企業面試題庫提升了一個檔次的一本神書。網路面我師兄的時候，我師兄直接把有一道題的最優解答出來了。但是，那個面試官顯然是不知道最優解，一直在引導我師兄答出，這本書裡面的第四個解。呵呵。書很不錯。全部看一遍並不難。說個不好聽的，可以背下來，而且相信我，基本上絕對有用！比如說，n!後面有多少個0。我相信，你們今年面試或者筆試，一定會碰到這道題。《挑戰編程》大家可以自行考慮一下吧，這個完全是針對acm競賽的，不過，看看題也不錯。 《編程珠璣》 業界神書嘛。習題全部做完就是了。其實都是些小東西，但是，基本上一步步考察你的解決問題的能力。個人覺得，最常用的就是bit map做排序或者去重，拓展一下就是bloom filter，我當時都是在這本書裡面看到的。 《演算法技術手冊》 這本書貌似出鏡不多。書很薄，代碼寫的非常好，其實基本上全部都是基礎演算法和數據結構的實現。但是，它牛逼就在於，代碼寫的太好了，基本上，看一遍，絕對能背下來。面試基礎很重要。基本上每個筆試或者面試，都會考一個100行以內的小程序。比如，給定一棵樹，以及其中一個節點x，要求出這棵樹的中序遍歷序列中，x的後續節點，非遞歸實現。這種題非常簡單，但是，真正寫對的，其實並不多。《STL源碼剖析》《C標准庫》 都不厚。挑著看一遍非常舒服。特別是，看看STL每個數據結構迭代器類型啊，紅黑書如何實現啊。C標准庫，最常見的，比如strcpy()和memcpy()有什麼區別啊。特別是，STL，看過之後，對泛型還是能有一定了解的。《C專家編程》《Effective c++》《深度探索C++對象模型》 第一本比較簡單，可以當八卦書看。後兩本其實也沒啥好說的，其實都是些業界公認的牛書。我再重復一遍也沒什麼意義。但是，的確，考察基本上也就都是這么幾本書上面的東西。基本上後兩本主要側重看c++對象方面的一些指示，特別是多態相關的。 《具體數學》《組合數學》 這兩本其實可以看作修身養性的書。我當時是時間比較充裕的時候看完的。純突擊，大家就可以跳過了。但是，看完真的很有用。比如說，你們就可以跟面試官扯約瑟夫環的構造解了（這道題我覺得80%會遇到），直接推推公式，就不用寫模擬代碼了。《組合數學》也是，很多筆試一般會有些小智力題。不過，其實一般的題目，不看這本書也可以搞定。所以，這兩本僅供參考。大家有興趣的時候，可以翻翻。《Linux內核源碼剖析》《Linux環境高級編程》…… 要是有機會，能看看最好。因為很多公司都會考察Linux相關的知識。最少要會點腳本，一些簡單的Linux命令，以及正則表達式什麼的。要是能聊聊內核源碼或者驅動開發什麼的東西，面試官肯定更加喜歡了。 知識： c & c++ 首先要知道c和c++的區別。常考的有const的用法，一些生僻關鍵字比如extern，static的用法。 結構體與類的差別。類裡面的字對齊問題，也就是說一個類到底有多大。以及一個空的類有多大。 虛函數以及多態相關的顯然是重點。比如析構函數什麼時候需要寫成虛函數，構造函數是否可以是虛函數。 int a[10]; a 和 &a的區別。 java java我並不熟。但是基本上肯定會考一些虛擬機相關的，以及GC等知識。然後，一般招聘的java程序員都會問到很多多線程編程的東西，以及hadoop！這個絕對是重點，淘寶絕對就是問這個的。 操作系統 這個看工作崗位的實際要求。基本的進程線程區別==肯定是會問到的。要是要求高一些，就會問很多多線程編程的問題。一些競爭死鎖等基礎知識，一些進程調度的演算法，最近的kernel好像用的是CFS調度演算法。shell編程，如何讀取程序堆棧，寫一些core mp的讀取程序等等的。 數據結構 基本上所有的排序都要會寫。與樹有關的操作都要會些非遞歸版本。圖一般考的不多。Flood-Fill演算法等等。查找中位數。B樹和紅黑書最好要掌握，不用會寫，能扯扯基本就行。KMP，這個很有可能考！而且的確真的不好懂。要是實在不行，背下來吧。哈哈。 網路 這個其實比較基礎了。我個人網路方面的知識並不好。但是各種協議的基礎，幾次握手啊，一些操作系統的api實現到底是單工還是雙工用的是TCP還是UDP。我個人網路純粹靠拼RP。 資料庫 資料庫非常重要。基本的SQL肯定是要會的。最常見有一道題，inner join和out join的區別。MySQL是重點，基本上很多企業都是問這個。然後，網路扯多了會跟你扯MySQL引擎 的一些東西。這些我就不太懂了。要是能准備的話，或者說的確是做這方面的，就可以著重多准備下。 大規模數據處理這一塊絕對是重點！而且本身不是一個系統的學科分支。但是，基本上幾家大公司都會問這方面的。推薦先讀讀google那幾篇論文。Page Rank那一篇，然後Map Rece好像有幾篇吧。Big Table什麼的。推薦一個網址。這篇貌似是轉載的，我以前找到的源地址現在找不到了。處理這一類問題基本上思路都是，哈希，map rece以及bit map等等的。對了，推薦看一下外排序以及相關的敗者樹。這些都是大規模數據處理的一些典型問題。掌握了這些其實也就夠了。這塊有點屠龍之技的感覺，特別是對於學生，基本沒有誰能有機會把這些代碼實現出來。但是，沒辦法，這些公司就是喜歡考。看完那篇博客的，然後再自行查找一些資料，基本就夠了。萬變不離其中，而且，這些東西，沒辦法考那麼難的。 推薦一個博客吧，作者收集了100+道面試題，並且全部給出了代碼。把這個全部看完，基本上很多面試筆試，都是這些原題。 推薦Top Language裡面的今天我們思考系列，好幾年前的了。看大牛的思考過程，非常有幫助。希望自己能多想想再看答案。注意，google group好像有時被牆。 我把發芽網的題庫版塊也掃了一遍。 還有好多一時想不起來了。

B. 演算法分析與設計的作品目錄

第一部分基礎工具
第1章演算法分析
1.1演算法的分析方法學
1.1.1偽代碼
1.1.2隨機存取機(RAM)模型
1.1.3統計基本操作的數量
1.1.4遞歸演算法分析
1.2漸近符號
1.2.1大O符號
1.2.2與大「O」相關的漸近符號
1.2.3漸近表示的重要性
1.3數學概覽
1.3.1求和
1.3.2對數和指數
1.3.3簡單證明技術
1.3.4概率基礎
1.4演算法分析案例研究
1.4.1二次時間前綴平均值演算法
1.4.2線性時間前綴平均值演算法
1.5平攤方法
1.5.1平攤技術
1.5.2擴展數組實現分析
1.6實驗
1.6.1實驗組織
1.6.2數據分析和可視化
1.7習題
基礎題
創新題
程序設計
1.8本章注記
第2章基本數據結構
2.1棧和隊列
2.1.1棧
2.1.2隊列
2.2向量、表和序列
2.2.1向量
2.2.2表
2.2.3序列
2.3樹
2.3.1樹抽象數據類型
2.3.2樹的遍歷
2.3.3二叉樹
2.3.4表示樹的數據結構
2.4優先隊列和堆
2.4.1優先隊列抽象數據類型
2.4.2PQ排序、選擇排序和插入排序
2.4.3堆數據結構
2.4.4堆排序
2.5字典與散列表
2.5.1無序字典ADT
2.5.2散列表
2.5.3散列函數
2.5.4壓縮映射
2.5.5沖突處理模式
2.5.6通用散列
2.6Java示例：堆
2.7習題
基礎題
創新題
程序設計
2.8本章注記
第3章查找樹和跳躍表
3.1有序字典和二叉查找樹
3.1.1有序表
3.1.2二叉查找樹
3.1.3二叉查找樹中的查找
3.1.4二叉查找樹中的插入
3.1.5二叉查找樹中的刪除
3.1.6二叉查找樹的性能
3.2AVL樹
3.2.1更新操作
3.2.2性能
3.3深度有界查找樹
3.3.1多路查找樹
3.3.2(2,4)樹
3.3.3紅黑樹
3.4伸展樹
3.4.1伸展
3.4.2伸展過程的平攤分析
3.5跳躍表
3.5.1查找
3.5.2更新操作
3.5.3跳躍表的概率分析
3.6Java示例：AVL樹和紅黑樹
3.6.1AVL樹的Java實現
3.6.2紅黑樹的Java實現
3.7習題
基礎題
創新題
程序設計
3.8本章注記
第4章排序、集合和選擇
4.1歸並排序
4.1.1分治法
4.1.2歸並排序和遞歸方程
4.2集合抽象數據類型
4.2.1簡單的集合實現
4.2.2具有union-find操作的劃分
4.2.3基於樹的劃分實現
4.3快速排序
4.4基於比較的排序下界
4.5桶排序和基數排序
4.5.1桶排序
4.5.2基數排序
4.6比較排序演算法
4.7選擇
4.7.1剪枝-查找法
4.7.2隨機化快速選擇
4.7.3隨機化快速選擇分析
4.8Java示例：原位快速排序
4.9習題
基礎題
創新題
程序設計
4.10本章注記
第5章基本技術
5.1貪心法
5.1.1背包問題
5.1.2任務調度
5.2分治法
5.2.1分治遞歸方程
5.2.2整數相乘
5.2.3矩陣相乘
5.3動態規劃
5.3.1矩陣鏈乘
5.3.2一般技術
5.3.30-1背包問題
5.4習題
基礎題
創新題
程序設計
5.5本章注記
第二部分圖演算法
第6章圖
6.1圖抽象數據類型
6.2圖的數據結構
6.2.1邊表結構
6.2.2鄰接表結構
6.2.3鄰接矩陣結構
6.3圖的遍歷
6.3.1深度優先查找
6.3.2雙連通分量
6.3.3廣度優先查找
6.4有向圖
6.4.1遍歷有向圖
6.4.2傳遞閉包
6.4.3DFS和垃圾收集
6.4.4有向無環圖
6.5Java示例：深度優先查找
6.5.1修飾模式
6.5.2DFS引擎
6.5.3模板方法設計模式
6.6習題
基礎題
創新題
程序設計
6.7本章注記
第7章加權圖
7.1單源點最短路徑
7.1.1Dijkstra演算法
7.1.2Bellman-Ford最短路徑演算法
7.1.3有向無環圖中的最短路徑
7.2所有頂點對之間的最短路徑
7.2.1動態規劃最短路徑演算法
7.2.2利用矩陣相乘計算最短路徑
7.3最小生成樹
7.3.1Kruskal演算法
7.3.2Prim-Jarník演算法
7.3.3Bar?vka演算法
7.3.4MST演算法比較
7.4Java示例：Dijkstra演算法
7.5習題
基礎題
創新題
程序設計
7.6本章注記
第8章網路流和匹配
8.1流和割
8.1.1流網路
8.1.2割
8.2最大流
8.2.1剩餘容量和增大路徑
8.2.2Ford-Fulkerson演算法
8.2.3Ford-Fulkerson演算法分析
8.2.4Edmonds-Karp演算法
8.3最大二分匹配
8.4最小代價流
8.4.1增大迴路
8.4.2連續最短路徑
8.4.3修改權值
8.5Java示例：最小代價流
8.6習題
基礎題
創新題
程序設計
8.7本章注記
第三部分網際網路演算法
第9章文本處理
9.1串和模式匹配演算法
9.1.1串操作
9.1.2蠻力模式匹配
9.1.3Boyer-Moore演算法
9.1.4Knuth-Morris-Pratt演算法
9.2trie
9.2.1標准trie
9.2.2壓縮trie
9.2.3後綴trie
9.2.4搜索引擎
9.3文本壓縮
9.3.1赫夫曼編碼演算法
9.3.2修正貪心法
9.4文本相似性測試
9.4.1最長公共子序列問題
9.4.2應用動態規劃求解LCS問題
9.5習題
基礎題
創新題
程序設計
9.6本章注記
第10章數論和密碼學
10.1與數有關的基本演算法
10.1.1基本數論的一些事實
10.1.2歐幾里得GCD演算法
10.1.3模運算
10.1.4模指數運算
10.1.5模乘法逆元
10.1.6素性測試
10.2密碼計算
10.2.1對稱加密模式
10.2.2公鑰密碼系統
10.2.3RSA密碼系統
10.2.4El Gamal密碼系統
10.3信息安全演算法和協議
10.3.1單向散列函數
10.3.2時間戳和認證字典
10.3.3硬幣拋擲和比特承諾
10.3.4安全電子傳輸(SET)協議
10.3.5密鑰分發和交換
10.4快速傅里葉變換
10.4.1本原單位根
10.4.2離散傅里葉變換
10.4.3快速傅里葉變換演算法
10.4.4大整數相乘
10.5Java示例：FFT
10.6習題
基礎題
創新題
程序設計
10.7本章注記
第11章網路演算法
11.1復雜性測度和模型
11.1.1網路協議棧
11.1.2消息傳遞模型
11.1.3網路演算法的復雜性測度
11.2基本分布式演算法
11.2.1環網上的領導人選舉
11.2.2樹網上的領導人選舉
11.2.3廣度優先查找
11.2.4最小生成樹
11.3廣播路由和單播路由
11.3.1廣播路由的洪泛演算法
11.3.2單播路由的距離矢量演算法
11.3.3單播路由的鏈路-狀態演算法
11.4多播路由
11.4.1逆向路徑轉發
11.4.2中心樹
11.4.3Steiner樹
11.5習題
基礎題
創新題
程序設計
11.6本章注記
第四部分其他主題
第12章計算幾何
12.1范圍樹
12.1.1一維范圍查找
12.1.2二維范圍查找
12.2優先查找樹
..

C. 常見的數學模型有哪些

1、生物學數學模型

2、醫學數學模型

3、地質學數學模型

4、氣象學數學模型

5、經濟學數學模型

6、社會學數學模型

7、物理學數學模型

8、化學數學模型

9、天文學數學模型

10、工程學數學模型

11、管理學數學模型

(3)動態規劃演算法硬幣收集問題論文擴展閱讀

數學模型的歷史可以追溯到人類開始使用數字的時代。隨著人類使用數字，就不斷地建立各種數學模型，以解決各種各樣的實際問題。

數學模型這種數學結構是藉助於數學符號刻劃出來的某種系統的純關系結構。從廣義理解，數學模型包括數學中的各種概念，各種公式和各種理論。

因為它們都是由現實世界的原型抽象出來的，從這意義上講，整個數學也可以說是一門關於數學模型的科學。從狹義理解，數學模型只指那些反映了特定問題或特定的具體事物系統的數學關系結構，這個意義上也可理解為聯系一個系統中各變數間內的關系的數學表達。

D. 生物信息學

一, 生物信息學發展簡介

生物信息學是建立在分子生物學的基礎上的,因此,要了解生物信息學,就

必須先對分子生物學的發展有一個簡單的了解.研究生物細胞的生物大分子的結

構與功能很早就已經開始,1866年孟德爾從實驗上提出了假設:基因是以生物

成分存在[1],1871年Miescher從死的白細胞核中分離出脫氧核糖核酸(DNA),

在Avery和McCarty於1944年證明了DNA是生命器官的遺傳物質以前,人們

仍然認為染色體蛋白質攜帶基因,而DNA是一個次要的角色.

1944年Chargaff發現了著名的Chargaff規律,即DNA中鳥嘌呤的量與胞嘧

定的量總是相等,腺嘌呤與胸腺嘧啶的量相等.與此同時,Wilkins與Franklin

用X射線衍射技術測定了DNA纖維的結構.1953年James Watson 和Francis

Crick在Nature雜志上推測出DNA的三維結構(雙螺旋).DNA以磷酸糖鏈形

成發雙股螺旋,脫氧核糖上的鹼基按Chargaff規律構成雙股磷酸糖鏈之間的鹼基

對.這個模型表明DNA具有自身互補的結構,根據鹼基對原則,DNA中貯存的

遺傳信息可以精確地進行復制.他們的理論奠定了分子生物學的基礎.

DNA雙螺旋模型已經預示出了DNA復制的規則,Kornberg於1956年從大

腸桿菌(E.coli)中分離出DNA聚合酶I(DNA polymerase I),能使4種dNTP連接

成DNA.DNA的復制需要一個DNA作為模板.Meselson與Stahl(1958)用實驗

方法證明了DNA復制是一種半保留復制.Crick於1954年提出了遺傳信息傳遞

的規律,DNA是合成RNA的模板,RNA又是合成蛋白質的模板,稱之為中心

法則(Central dogma),這一中心法則對以後分子生物學和生物信息學的發展都起

到了極其重要的指導作用.

經過Nirenberg和Matthai(1963)的努力研究,編碼20氨基酸的遺傳密碼

得到了破譯.限制性內切酶的發現和重組DNA的克隆(clone)奠定了基因工程

的技術基礎.

正是由於分子生物學的研究對生命科學的發展有巨大的推動作用,生物信息

學的出現也就成了一種必然.

2001年2月,人類基因組工程測序的完成,使生物信息學走向了一個高潮.

由於DNA自動測序技術的快速發展,DNA資料庫中的核酸序列公共數據量以每

天106bp速度增長,生物信息迅速地膨脹成數據的海洋.毫無疑問,我們正從一

個積累數據向解釋數據的時代轉變,數據量的巨大積累往往蘊含著潛在突破性發

現的可能,"生物信息學"正是從這一前提產生的交叉學科.粗略地說,該領域

的核心內容是研究如何通過對DNA序列的統計計算分析,更加深入地理解DNA

序列,結構,演化及其與生物功能之間的關系,其研究課題涉及到分子生物學,

分子演化及結構生物學,統計學及計算機科學等許多領域.

生物信息學是內涵非常豐富的學科,其核心是基因組信息學,包括基因組信

息的獲取,處理,存儲,分配和解釋.基因組信息學的關鍵是"讀懂"基因組的核

苷酸順序,即全部基因在染色體上的確切位置以及各DNA片段的功能;同時在

發現了新基因信息之後進行蛋白質空間結構模擬和預測,然後依據特定蛋白質的

功能進行葯物設計[2].了解基因表達的調控機理也是生物信息學的重要內容,根

據生物分子在基因調控中的作用,描述人類疾病的診斷,治療內在規律.它的研

究目標是揭示"基因組信息結構的復雜性及遺傳語言的根本規律",解釋生命的遺

傳語言.生物信息學已成為整個生命科學發展的重要組成部分,成為生命科學研

究的前沿.

二, 生物信息學的主要研究方向

生物信息學在短短十幾年間,已經形成了多個研究方向,以下簡要介紹一些

主要的研究重點.

1,序列比對(Sequence Alignment)

序列比對的基本問題是比較兩個或兩個以上符號序列的相似性或不相似

性.從生物學的初衷來看,這一問題包含了以下幾個意義[3]:

從相互重疊的序列片斷中重構DNA的完整序列.

在各種試驗條件下從探測數據(probe data)中決定物理和基因圖

存貯,遍歷和比較資料庫中的DNA序列

比較兩個或多個序列的相似性

在資料庫中搜索相關序列和子序列

尋找核苷酸(nucleotides)的連續產生模式

找出蛋白質和DNA序列中的信息成分

序列比對考慮了DNA序列的生物學特性,如序列局部發生的插入,刪除(前

兩種簡稱為indel)和替代,序列的目標函數獲得序列之間突變集最小距離加權

和或最大相似性和,對齊的方法包括全局對齊,局部對齊,代溝懲罰等.兩個

序列比對常採用動態規劃演算法,這種演算法在序列長度較小時適用,然而對於海

量基因序列(如人的DNA序列高達109bp),這一方法就不太適用,甚至採用算

法復雜性為線性的也難以奏效.因此,啟發式方法的引入勢在必然,著名的

BALST和FASTA演算法及相應的改進方法均是從此前提出發的.

2, 蛋白質結構比對和預測

基本問題是比較兩個或兩個以上蛋白質分子空間結構的相似性或不相似性.

蛋白質的結構與功能是密切相關的,一般認為,具有相似功能的蛋白質結構一般

相似.蛋白質是由氨基酸組成的長鏈,長度從50到1000~3000AA(Amino Acids),

蛋白質具有多種功能,如酶,物質的存貯和運輸,信號傳遞,抗體等等.氨基酸

的序列內在的決定了蛋白質的3維結構.一般認為,蛋白質有四級不同的結構.

研究蛋白質結構和預測的理由是:醫葯上可以理解生物的功能,尋找docking

drugs的目標,農業上獲得更好的農作物的基因工程,工業上有利用酶的合成.

直接對蛋白質結構進行比對的原因是由於蛋白質的3維結構比其一級結構

在進化中更穩定的保留,同時也包含了較AA序列更多的信息.

蛋白質3維結構研究的前提假設是內在的氨基酸序列與3維結構一一對應

(不一定全真),物理上可用最小能量來解釋.

從觀察和總結已知結構的蛋白質結構規律出發來預測未知蛋白質的結構.同

源建模(homology modeling)和指認(Threading)方法屬於這一范疇.同源建模用

於尋找具有高度相似性的蛋白質結構(超過30%氨基酸相同),後者則用於比較

進化族中不同的蛋白質結構.

然而,蛋白結構預測研究現狀還遠遠不能滿足實際需要.

3, 基因識別,非編碼區分析研究.

基因識別的基本問題是給定基因組序列後,正確識別基因的范圍和在基因組

序列中的精確位置.非編碼區由內含子組成(introns),一般在形成蛋白質後被丟

棄,但從實驗中,如果去除非編碼區,又不能完成基因的復制.顯然,DNA序

列作為一種遺傳語言,既包含在編碼區,又隱含在非編碼序列中.分析非編碼

區DNA序列目前沒有一般性的指導方法.

在人類基因組中,並非所有的序列均被編碼,即是某種蛋白質的模板,已

完成編碼部分僅占人類基因總序列的3~5%,顯然,手工的搜索如此大的基因序

列是難以想像的.

偵測密碼區的方法包括測量密碼區密碼子(codon)的頻率,一階和二階馬爾

可夫鏈,ORF(Open Reading Frames),啟動子(promoter)識別,HMM(Hidden

Markov Model)和GENSCAN,Splice Alignment等等.

4, 分子進化和比較基因組學

分子進化是利用不同物種中同一基因序列的異同來研究生物的進化,構建進

化樹.既可以用DNA序列也可以用其編碼的氨基酸序列來做,甚至於可通過相

關蛋白質的結構比對來研究分子進化,其前提假定是相似種族在基因上具有相似

性.通過比較可以在基因組層面上發現哪些是不同種族中共同的,哪些是不同的.

早期研究方法常採用外在的因素,如大小,膚色,肢體的數量等等作為進化

的依據.近年來較多模式生物基因組測序任務的完成,人們可從整個基因組的角

度來研究分子進化.在匹配不同種族的基因時,一般須處理三種情況:

Orthologous: 不同種族,相同功能的基因

Paralogous: 相同種族,不同功能的基因

Xenologs: 有機體間採用其他方式傳遞的基因,如被病毒注入的基因.

這一領域常採用的方法是構造進化樹,通過基於特徵(即DNA序列或蛋白

質中的氨基酸的鹼基的特定位置)和基於距離(對齊的分數)的方法和一些傳統

的聚類方法(如UPGMA)來實現.

5, 序列重疊群(Contigs)裝配

根據現行的測序技術,每次反應只能測出500 或更多一些鹼基對的序列,

如人類基因的測量就採用了短槍(shortgun)方法,這就要求把大量的較短的序列

全體構成了重疊群(Contigs).逐步把它們拼接起來形成序列更長的重疊群,直

至得到完整序列的過程稱為重疊群裝配.從演算法層次來看,序列的重疊群是一個

NP-完全問題.

6, 遺傳密碼的起源

通常對遺傳密碼的研究認為,密碼子與氨基酸之間的關系是生物進化歷史上

一次偶然的事件而造成的,並被固定在現代生物的共同祖先里,一直延續至今.

不同於這種"凍結"理論,有人曾分別提出過選擇優化,化學和歷史等三種學說

來解釋遺傳密碼.隨著各種生物基因組測序任務的完成,為研究遺傳密碼的起源

和檢驗上述理論的真偽提供了新的素材.

7, 基於結構的葯物設計

人類基因工程的目的之一是要了解人體內約10萬種蛋白質的結構,功能,

相互作用以及與各種人類疾病之間的關系,尋求各種治療和預防方法,包括葯物

治療.基於生物大分子結構及小分子結構的葯物設計是生物信息學中的極為重要

的研究領域.為了抑制某些酶或蛋白質的活性,在已知其蛋白質3級結構的基礎

上,可以利用分子對齊演算法,在計算機上設計抑制劑分子,作為候選葯物.這一

領域目的是發現新的基因葯物,有著巨大的經濟效益.

8, 其他

如基因表達譜分析,代謝網路分析;基因晶元設計和蛋白質組學數據分析等,

逐漸成為生物信息學中新興的重要研究領域;在學科方面,由生物信息學衍生的

學科包括結構基因組學,功能基因組學,比較基因組學,蛋白質學,葯物基因組

學,中葯基因組學,腫瘤基因組學,分子流行病學和環境基因組學.

從現在的發展不難看出,基因工程已經進入了後基因組時代.我們也有應對

與生物信息學密切相關的如機器學習,和數學中可能存在的誤導有一個清楚的認

識.

三, 生物信息學與機器學習

生物信息的大規模給數據挖掘提出了新課題和挑戰,需要新的思想的加入.

常規的計算機演算法仍可以應用於生物數據分析中,但越來越不適用於序列分析問

題.究竟原因,是由於生物系統本質上的模型復雜性及缺乏在分子層上建立的完

備的生命組織理論.

西蒙曾給出學習的定義:學習是系統的變化,這種變化可使系統做相同工作

時更有效[4].機器學習的目的是期望能從數據中自動地獲得相應的理論,通過采

用如推理,模型擬合及從樣本中學習,尤其適用於缺乏一般性的理論,"雜訊"

模式,及大規模數據集.因此,機器學習形成了與常規方法互補的可行的方法.

機器學習使得利用計算機從海量的生物信息中提取有用知識,發現知識成為可能

[5].

機器學習方法在大樣本,多向量的數據分析工作中發揮著日益重要的作用,

而目前大量的基因資料庫處理需要計算機能自動識別,標注,以避免即耗時又花

費巨大的人工處理方法.早期的科學方法—觀測和假設----面對高數據的體積,

快速的數據獲取率和客觀分析的要求---已經不能僅依賴於人的感知來處理了.因

而,生物信息學與機器學習相結合也就成了必然.

機器學習中最基本的理論框架是建立在概率基礎上的,從某種意義來說,是

統計模型擬合的延續,其目的均為提取有用信息.機器學習與模式識別和統計推

理密切相關.學習方法包括數據聚類,神經網路分類器和非線性回歸等等.隱馬

爾可夫模型也廣泛用於預測DNA的基因結構.目前研究重心包括:1)觀測和

探索有趣的現象.目前ML研究的焦點是如何可視化和探索高維向量數據.一般

的方法是將其約簡至低維空間,如常規的主成分分析(PCA),核主成分分析

(KPCA),獨立成分分析(Independent component analysis),局部線性嵌套(Locally

Linear embedding).2)生成假設和形式化模型來解釋現象[6].大多數聚類方法可

看成是擬合向量數據至某種簡單分布的混合.在生物信息學中聚類方法已經用於

microarray數據分析中,癌症類型分類及其他方向中.機器學習也用於從基因數

據庫中獲得相應的現象解釋.

機器學習加速了生物信息學的進展,也帶了相應的問題.機器學習方法大多

假定數據符合某種相對固定的模型,而一般數據結構通常是可變的,在生物信息

學中尤其如此,因此,有必要建立一套不依賴於假定數據結構的一般性方法來尋

找數據集的內在結構.其次,機器學習方法中常採用"黑箱"操作,如神經網路

和隱馬爾可夫模型,對於獲得特定解的內在機理仍不清楚.

四, 生物信息學的數學問題

生物信息學中數學佔了很大的比重.統計學,包括多元統計學,是生物信息

學的數學基礎之一;概率論與隨機過程理論,如近年來興起的隱馬爾科夫鏈模型

(HMM),在生物信息學中有重要應用;其他如用於序列比對的運籌學;蛋白質

空間結構預測和分子對接研究中採用的最優化理論;研究DNA超螺旋結構的拓

撲學;研究遺傳密碼和DNA序列的對稱性方面的群論等等.總之,各種數學理

論或多或少在生物學研究中起到了相應的作用.

但並非所有的數學方法在引入生物信息學中都能普遍成立的,以下以統計學

和度量空間為例來說明.

1, 統計學的悖論

數學的發展是伴隨悖論而發展的.對於進化樹研究和聚類研究中最顯著的悖

論莫過於均值了,如圖1:

圖1 兩組同心圓的數據集

圖1是兩組同心圓構成的數據集,顯然,兩組數據集的均值均在圓點,這也

就說明了要採用常規的均值方法不能將這兩類分開,也表明均值並不能帶來更多

的數據的幾何性質.那麼,如果數據呈現類似的特有分布時,常有的進化樹演算法

和聚類演算法(如K-均值)往往會得錯誤的結論.統計上存在的陷阱往往是由於

對數據的結構缺乏一般性認識而產生的.

2, 度量空間的假設

在生物信息學中,進化樹的確立,基因的聚類等都需要引入度量的概念.舉

例來說,距離上相近或具有相似性的基因等具有相同的功能,在進化樹中滿足分

值最小的具有相同的父系,這一度量空間的前提假設是度量在全局意義下成立.

那麼,是否這種前提假設具有普適性呢

我們不妨給出一般的描述:假定兩個向量為A,B,其中,

,則在假定且滿足維數間線性無關的前提下,兩個

向量的度量可定義為:

(1)

依據上式可以得到滿足正交不變運動群的歐氏度量空間,這也是大多數生物信息

學中常採用的一般性描述,即假定了變數間線性無關.

然而,這種假設一般不能正確描述度量的性質,尤其在高維數據集時,不考

慮數據變數間的非線性相關性顯然存在問題,由此,我們可以認為,一個正確的

度量公式可由下式給出:

(2)

上式中採用了愛因斯坦和式約定,描述了變數間的度量關系.後者在滿足

(3)

時等價於(1),因而是更一般的描述,然而問題在於如何准確描述變數間的非線

性相關性,我們正在研究這個問題.

五, 幾種統計學習理論在生物信息學中應用的困難

生物信息學中面對的數據量和資料庫都是規模很大的,而相對的目標函數卻

一般難以給出明確的定義.生物信息學面臨的這種困難,可以描述成問題規模的

巨大以及問題定義的病態性之間的矛盾,一般從數學上來看,引入某個正則項來

改善性能是必然的[7].以下對基於這一思想產生的統計學習理論[8],Kolmogorov

復雜性[98]和BIC(Bayesian Information Criterion)[109]及其存在的問題給出簡要介

紹.

支持向量機(SVM)是近來較熱門的一種方法,其研究背景是Vapnik的統計

學習理論,是通過最大化兩個數據集的最大間隔來實現分類,對於非線性問題則

採用核函數將數據集映射至高維空間而又無需顯式描述數據集在高維空間的性

質,這一方法較之神經方法的好處在於將神經網路隱層的參數選擇簡化為對核函

數的選擇,因此,受到廣泛的注意.在生物信息學中也開始受到重視,然而,核

函數的選擇問題本身是一個相當困難的問題,從這個層次來看,最優核函數的選

擇可能只是一種理想,SVM也有可能象神經網路一樣只是機器學習研究進程中

又一個大氣泡.

Kolmogorov復雜性思想與統計學習理論思想分別從不同的角度描述了學習

的性質,前者從編碼的角度,後者基於有限樣本來獲得一致收斂性.Kolmogorov

復雜性是不可計算的,因此由此衍生了MDL原則(最小描述長度),其最初只

適用於離散數據,最近已經推廣至連續數據集中,試圖從編碼角度獲得對模型參

數的最小描述.其缺陷在於建模的復雜性過高,導致在大數據集中難以運用.

BIC准則從模型復雜性角度來考慮,BIC准則對模型復雜度較高的給予大的

懲罰,反之,懲罰則小,隱式地體現了奧卡姆剃刀("Occam Razor")原理,近

年也廣泛應用於生物信息學中.BIC准則的主要局限是對參數模型的假定和先驗

的選擇的敏感性,在數據量較大時處理較慢.因此,在這一方面仍然有許多探索

的空間.

六, 討論與總結

人類對基因的認識,從以往的對單個基因的了解,上升到在整個基因組水平

上考察基因的組織結構和信息結構,考察基因之間在位置,結構和功能上的相互

關系.這就要求生物信息學在一些基本的思路上要做本質的觀念轉變,本節就這

些問題做出探討和思索.

啟發式方法:

Simond在人類的認知一書中指出,人在解決問題時,一般並不去尋找最優

的方法,而只要求找到一個滿意的方法.因為即使是解決最簡單的問題,要想得

到次數最少,效能最高的解決方法也是非常困難的.最優方法和滿意方法之間的

困難程度相差很大,後者不依賴於問題的空間,不需要進行全部搜索,而只要能

達到解決的程度就可以了.正如前所述,面對大規模的序列和蛋白質結構數據集,

要獲得全局結果,往往是即使演算法復雜度為線性時也不能夠得到好的結果,因此,

要通過變換解空間或不依賴於問題的解空間獲得滿意解,生物信息學仍需要人工

智能和認知科學對人腦的進一步認識,並從中得到更好的啟發式方法.

問題規模不同的處理:

Marvin Minsky在人工智慧研究中曾指出:小規模數據量的處理向大規模數

據量推廣時,往往並非演算法上的改進能做到的,更多的是要做本質性的變化.這

好比一個人爬樹,每天都可以爬高一些,但要想爬到月球,就必須採用其他方法

一樣.在分子生物學中,傳統的實驗方法已不適應處理飛速增長的海量數據.同

樣,在採用計算機處理上,也並非依靠原有的計算機演算法就能夠解決現有的數據

挖掘問題.如在序列對齊(sequence Alignment)問題上,在小規模數據中可以採用

動態規劃,而在大規模序列對齊時不得不引入啟發式方法,如BALST,FASTA.

樂觀中的隱擾

生物信息學是一門新興學科,起步於20世紀90年代,至今已進入"後基因

組時代",目前在這一領域的研究人員均呈普遍樂觀態度,那麼,是否存在潛在

的隱擾呢

不妨回顧一下早期人工智慧的發展史[11],在1960年左右,西蒙曾相信不出

十年,人類即可象完成登月一樣完成對人的模擬,造出一個與人智能行為完全相

同的機器人.而至今為止,這一諾言仍然遙遙無期.盡管人工智慧研究得到的成

果已經滲入到各個領域,但對人的思維行為的了解遠未完全明了.從本質來看,

這是由於最初人工智慧研究上定位錯誤以及沒有從認識論角度看清人工智慧的

本質造成的;從研究角度來看,將智能行為還原成一般的形式化語言和規則並不

能完整描述人的行為,期望物理科學的成功同樣在人工智慧研究中適用並不現

實.

反觀生物信息學,其目的是期望從基因序列上解開一切生物的基本奧秘,從

結構上獲得生命的生理機制,這從哲學上來看是期望從分子層次上解釋人類的所

有行為和功能和致病原因.這類似於人工智慧早期發展中表現的樂觀行為,也來

自於早期分子生物學,生物物理和生物化學的成就.然而,從本質上來講,與人

工智能研究相似,都是希望將生命的奧秘還原成孤立的基因序列或單個蛋白質的

功能,而很少強調基因序列或蛋白質組作為一個整體在生命體中的調控作用.我

們因此也不得不思考,這種研究的最終結果是否能夠支撐我們對生物信息學的樂

觀呢 現在說肯定的話也許為時尚早.

綜上所述,不難看出,生物信息學並不是一個足以樂觀的領域,究竟原因,

是由於其是基於分子生物學與多種學科交叉而成的新學科,現有的形勢仍表現為

各種學科的簡單堆砌,相互之間的聯系並不是特別的緊密.在處理大規模數據方

面,沒有行之有效的一般性方法;而對於大規模數據內在的生成機制也沒有完全

明了,這使得生物信息學的研究短期內很難有突破性的結果.那麼,要得到真正

的解決,最終不能從計算機科學得到,真正地解決可能還是得從生物學自身,從

數學上的新思路來獲得本質性的動力.

毫無疑問,正如Dulbecco1986年所說:"人類的DNA序列是人類的真諦,

這個世界上發生的一切事情,都與這一序列息息相關".但要完全破譯這一序列

以及相關的內容,我們還有相當長的路要走.

（來源 ------[InfoBio.org | 生物信息學研討組]）http://www.infobio.org
生物信息學（Bioinformatics）是在生命科學的研究中，以計算機為工具對生物信息進行儲存、檢索和分析的科學。它是當今生命科學和自然科學的重大前沿領域之一，同時也將是21世紀自然科學的核心領域之一。其研究重點主要體現在基因組學(Genomics)和蛋白學(Proteomics)兩方面，具體說就是從核酸和蛋白質序列出發，分析序列中表達的結構功能的生物信息。

生物信息學是一門利用計算機技術研究生物系統之規律的學科。

目前的生物信息學基本上只是分子生物學與信息技術（尤其是網際網路技術）的結合體。生物信息學的研究材料和結果就是各種各樣的生物學數據，其研究工具是計算機，研究方法包括對生物學數據的搜索（收集和篩選）、處理（編輯、整理、管理和顯示）及利用（計算、模擬）。

1990年代以來，伴隨著各種基因組測序計劃的展開和分子結構測定技術的突破和Internet的普及，數以百計的生物學資料庫如雨後春筍般迅速出現和成長。對生物信息學工作者提出了嚴峻的挑戰：數以億計的ACGT序列中包涵著什麼信息？基因組中的這些信息怎樣控制有機體的發育？基因組本身又是怎樣進化的？

生物信息學的另一個挑戰是從蛋白質的氨基酸序列預測蛋白質結構。這個難題已困擾理論生物學家達半個多世紀，如今找到問題答案要求正變得日益迫切。諾貝爾獎獲得者W. Gilbert在1991年曾經指出：「傳統生物學解決問題的方式是實驗的。現在，基於全部基因都將知曉，並以電子可操作的方式駐留在資料庫中，新的生物學研究模式的出發點應是理論的。一個科學家將從理論推測出發，然後再回到實驗中去，追蹤或驗證這些理論假設」。

生物信息學的主要研究方向： 基因組學 - 蛋白質組學 - 系統生物學 - 比較基因組學

姑且不去引用生物信息學冗長的定義，以通俗的語言闡述其核心應用即是：隨著包括人類基因組計劃在內的生物基因組測序工程的里程碑式的進展，由此產生的包括生物體生老病死的生物數據以前所未有的速度遞增，目前已達到每14個月翻一番的速度。同時隨著互聯網的普及，數以百計的生物學資料庫如雨後春筍般迅速出現和成長。然而這些僅僅是原始生物信息的獲取，是生物信息學產業發展的初組階段，這一階段的生物信息學企業大都以出售生物資料庫為生。以人類基因組測序而聞名的塞萊拉公司即是這一階段的成功代表。
原始的生物信息資源挖掘出來後，生命科學工作者面臨著嚴峻的挑戰：數以億計的ACGT序列中包涵著什麼信息？基因組中的這些信息怎樣控制有機體的發育？基因組本身又是怎樣進化的？生物信息學產業的高級階段體現於此，人類從此進入了以生物信息學為中心的後基因組時代。結合生物信息學的新葯創新工程即是這一階段的典型應用。

E. 程序員演算法基礎——貪心演算法

貪心是人類自帶的能力，貪心演算法是在貪心決策上進行統籌規劃的統稱。

比如一道常見的演算法筆試題---- 跳一跳 ：

我們自然而然能產生一種解法：盡可能的往右跳，看最後是否能到達。
本文即是對這種貪心決策的介紹。

狹義的貪心演算法指的是解最優化問題的一種特殊方法，解決過程中總是做出當下最好的選擇，因為具有最優子結構的特點，局部最優解可以得到全局最優解；這種貪心演算法是動態規劃的一種特例。 能用貪心解決的問題，也可以用動態規劃解決。

而廣義的貪心指的是一種通用的貪心策略，基於當前局面而進行貪心決策。以 跳一跳 的題目為例：
我們發現的題目的核心在於 向右能到達的最遠距離 ，我們用maxRight來表示；
此時有一種貪心的策略：從第1個盒子開始向右遍歷，對於每個經過的盒子，不斷更新maxRight的值。

貪心的思考過程類似動態規劃，依舊是兩步： 大事化小 ， 小事化了 。
大事化小：
一個較大的問題，通過找到與子問題的重疊，把復雜的問題劃分為多個小問題；
小事化了：
從小問題找到決策的核心，確定一種得到最優解的策略，比如跳一跳中的 向右能到達的最遠距離 ；

在證明局部的最優解是否可以推出全局最優解的時候，常會用到數學的證明方式。

如果是動態規劃：
要湊出m元，必須先湊出m-1、m-2、m-5、m-10元，我們用dp[i]表示湊出i元的最少紙幣數；
有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1 ;
容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；
根據以上遞推方程和初始化信息，可以容易推出dp[1~m]的所有值。

似乎有些不對？ 平時我們找零錢有這么復雜嗎？
從貪心演算法角度出發，當m>10且我們有10元紙幣，我們優先使用10元紙幣，然後再是5元、2元、1元紙幣。
從日常生活的經驗知道，這么做是正確的，但是為什麼？

假如我們把題目變成這樣，原來的策略還能生效嗎？

接下來我們來分析這種策略：
已知對於m元紙幣，1，2，5元紙幣使用了a，b，c張，我們有a+2b+5c=m；
假設存在一種情況，1、2、5元紙幣使用數是x，y，z張，使用了更少的5元紙幣（z<c），且紙幣張數更少（x+y+z<a+b+c），即是用更少5元紙幣得到最優解。
我們令k=5*(c-z)，k元紙幣需要floor(k/2)張2元紙幣，k%2張1元紙幣；（因為如果有2張1元紙幣，可以使用1張2元紙幣來替代，故而1元紙幣只能是0張或者1張）
容易知道，減少(c-z)張5元紙幣，需要增加floor(5*(c-z)/2)張2元紙幣和(5*(c-z))%2張紙幣，而這使得x+y+z必然大於a+b+c。
由此我們知道不可能存在使用更少5元紙幣的更優解。
所以優先使用大額紙幣是一種正確的貪心選擇。

對於1、5、7元紙幣，比如說要湊出10元，如果優先使用7元紙幣，則張數是4；（1+1+1+7）
但如果只使用5元紙幣，則張數是2；（5+5）
在這種情況下，優先使用大額紙幣是不正確的貪心選擇。（但用動態規劃仍能得到最優解）

如果是動態規劃：
前i秒的完成的任務數，可以由前面1~i-1秒的任務完成數推過來。
我們用 dp[i]表示前i秒能完成的任務數 ；
在計算前i秒能完成的任務數時，對於第j個任務，我們有兩種決策：
1、不執行這個任務，那麼dp[i]沒有變化；
2、執行這個任務，那麼必須騰出來(Sj, Tj)這段時間，那麼 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；
比如說對於任務j如果是第5秒開始第10秒結束，如果i>=10，那麼有 dp[i]=max(dp[i], dp[5] + 1)； （相當於把第5秒到第i秒的時間分配給任務j）

再考慮貪心的策略，現實生活中人們是如何安排這種多任務的事情？我換一種描述方式：

我們自然而然會想到一個策略： 先把結束時間早的兼職給做了！
為什麼？
因為先做完這個結束時間早的，能留出更多的時間做其他兼職。
我們天生具備了這種優化決策的能力。

這是一道 LeetCode題目 。
這個題目不能直接用動態規劃去解，比如用dp[i]表示前i個人需要的最少糖果數。
因為（前i個人的最少糖果數）這種狀態表示會收到第i+1個人的影響，如果a[i]>a[i+1]，那麼第i個人應該比第i+1個人多。
即是 這種狀態表示不具備無後效性。

如果是我們分配糖果，我們應該怎麼分配？
答案是： 從分數最低的開始。
按照分數排序，從最低開始分，每次判斷是否比左右的分數高。
假設每個人分c[i]個糖果，那麼對於第i個人有 c[i]=max(c[i-1],c[c+1])+1 ; （c[i]默認為0，如果在計算i的時候,c[i-1]為0，表示i-1的分數比i高）
但是，這樣解決的時間復雜度為 O(NLogN) ，主要瓶頸是在排序。
如果提交，會得到 Time Limit Exceeded 的提示。

我們需要對貪心的策略進行優化：
我們把左右兩種情況分開看。
如果只考慮比左邊的人分數高時，容易得到策略：
從左到右遍歷，如果a[i]>a[i-1]，則有c[i]=c[i-1]+1；否則c[i]=1。

再考慮比右邊的人分數高時，此時我們要從數組的最右邊，向左開始遍歷：
如果a[i]>a[i+1], 則有c[i]=c[i+1]+1；否則c[i]不變；

這樣講過兩次遍歷，我們可以得到一個分配方案，並且時間復雜度是 O(N) 。

題目給出關鍵信息：1、兩個人過河，耗時為較長的時間；
還有隱藏的信息：2、兩個人過河後，需要有一個人把船開回去；
要保證總時間盡可能小，這里有兩個關鍵原則： 應該使得兩個人時間差盡可能小（減少浪費），同時船回去的時間也盡可能小（減少等待）。

先不考慮空船回來的情況，如果有無限多的船，那麼應該怎麼分配？
答案： 每次從剩下的人選擇耗時最長的人，再選擇與他耗時最接近的人。

再考慮只有一條船的情況，假設有A/B/C三個人，並且耗時A<B<C。
那麼最快的方案是：A+B去, A回；A+C去；總耗時是A+B+C。（因為A是最快的，讓其他人來回時間只會更長， 減少等待的原則 ）

如果有A/B/C/D四個人，且耗時A<B<C<D，這時有兩種方案：
1、最快的來回送人方式，A+B去；A回；A+C去，A回；A+D去； 總耗時是B+C+D+2A （減少等待原則）
2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；總耗時是 3B+D+A （減少浪費原則）
對比方案1、2的選擇，我們發現差別僅在A+C和2B；
為何方案1、2差別里沒有D？
因為D最終一定要過河，且耗時一定為D。

如果有A/B/C/D/E 5個人，且耗時A<B<C<D<E，這時如何抉擇？
仍是從最慢的E看。（參考我們無限多船的情況）
方案1，減少等待；先送E過去，然後接著考慮四個人的情況；
方案2，減少浪費；先送E/D過去，然後接著考慮A/B/C三個人的情況；（4人的時候的方案2）

到5個人的時候，我們已經明顯發了一個特點：問題是重復，且可以由子問題去解決。
根據5個人的情況，我們可以推出狀態轉移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);
再根據我們考慮的1、2、3、4個人的情況，我們分別可以算出dp[i]的初始化值：
dp[1] = a[1];
dp[2] = a[2];
dp[3] = a[2]+a[1]+a[3];
dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);

由上述的狀態轉移方程和初始化值，我們可以推出dp[n]的值。

貪心的學習過程，就是對自己的思考進行優化。
是把握已有信息，進行最優化決策。
這里還有一些收集的 貪心練習題 ，可以實踐練習。
這里 還有在線分享，歡迎報名。