七章演算法
❶ 計算方法
《計算方法》內容共分七章，內容主要包括：插值理論、方程求根、線性代數方程組的解法、數值積分、常微分方程數告團顫襪敗值解法和矩陣特徵值與特徵向量的計算，各章均配有一定量的習題，書末附有答案，《計算方法》選材適度、通俗易懂，為了適應不同要求的需要，安排了一定量的選學內容.對於加「*」的內容可酌情取捨。
第九章 自治微分方程穩定區域的計算
參考文獻
❷ 第七章：概率和樸素貝葉斯
近鄰演算法 又稱為被動學習演算法。這種演算法只是將訓練集的數據保存起來，在收到測試數據時才會進行計算。
貝葉斯演算法 則是一種主動學習演算法，它會根據訓練集構建起一個模型，並用這個模型來對新的記錄進行分類，因此速度會快很多。
貝葉斯演算法的兩個優點：能夠給出分類結果的置信度；以及它是一種主動學習演算法。
用 P( h ) 來表示事件 h 發生的概率；
用 P( h | D ) 來表示 D 條件下事件 h 發生的概率。
P( h ) 表示事件 h 發生的概率，稱為 h 的先驗概率；
P( h | d ) 稱為後驗概率，表示在觀察了數據集 d 之後，h 事件發生的概率是多少。
貝葉斯法則描述了 P( h )、P( h | D )、P( D )、以及P( D | h )這四個概率之間的關系：
在數據挖掘中，我們通常會使用這個公式去判斷不同事件之間的關系。
例： 我們要為一家銷售電子產品的公司發送宣傳郵件，共有筆記本、台式機、平板電腦三種產品。我們需要根據目標用戶的類型來分別派送這三種宣傳郵件。有一位居住在 88005 地區的女士，她的女兒在讀大學，並居住在家中，而且她還會參加瑜伽課程，那我們應該派發哪種郵件？
我們用D來表示這位客戶的特徵：
因此我們需要計算以下三個概率：
選擇概率最大的結果。
如果我們有 h1, h2, ... hn，它們相當於不同的類別
在計算出以上這些概率後，選取最大的結果，就能用作分類了。這種方法叫最大後驗估計，記為h MAP 。
H 表示所有的時間，所以 h ∈ H 表示「對於集合中的每一個事件」。整個公式的含義就是：對於集合中的每一個事件，計算出 P( h | D) 的值，並取最大的結果。
對於所有的事件，公式的蔽伏彎分母都是 P( D ) ，因此即便只計算 P( D | h )P( h )，也可以判斷出廳跡最宏悶大的結果。
例： 已知這種癌症在美國的感染率是 0.8%。血液檢驗的結果有陽性和陰性兩種，且存在准確性的問題：如果這個人患有癌症，則有 98% 的幾率測出陽性；如果他沒有癌症，會有 97% 的幾率測出陰性。Ann 到醫院做了血液檢測，呈陽性。
描述語言的公式表示：
美國有 0.8% 的人患有這種癌症：P( 癌症 ) = 0.008
99.2% 的人沒有患有這種癌症：P( ┐癌症 ) = 0.992
對於患有癌症的人，他的血液檢測結果返回陽性的概率是 98%：P( 陽性 | 癌症 ) = 0.98
對於患有癌症的人，檢測結果返回陰性的概率是 2%：P( 陰性 | 癌症 ) = 0.02
對於沒有癌症的人，返回陰性的概率是 97%：P( 陰性 | ┐癌症 ) = 0.97
對於沒有癌症的人，返回陽性的概率是 3%：P( 陽性 | ┐癌症 ) = 0.03
貝葉斯法則計算：
P( 陽性 | 癌症 )P( 癌症 ) = 0.98 * 0.008 = 0.0078
P( 陽性 | ┐癌症 )P( ┐癌症 ) = 0.03 * 0.992 = 0.0298
分類結果是她不會患有癌症
用到不止一個前提條件時，計算這樣的概率只需將各個條件概率相乘即可：
P( 買綠茶 | 88005 & 買有機食品 ) = P( 88005 | 買綠茶 )P( 買有機食品 | 買綠茶 )P( 買綠茶 ) = 0.6 * 0.8 * 0.5 = 0.24
P( ┐買綠茶 | 88005 & 買有機食品 ) = P( 88005 | ┐買綠茶 )P( 買有機食品 | ┐買綠茶 )P( ┐買綠茶 ) = 0.4 * 0.25 * 0.5 = 0.05
P( i500 | 健康、中等水平、熱情一般、適應） = P( 健康 | i500 )P( 中等水平 | i500 )P( 熱情一般 | i500 )P( 適應 | i500 )
使用樸素貝葉斯計算得到的概率其實是真實概率的一種估計，而真是概率是對全量數據做統計得到的。
大部分情況下，這種估計都是接近於真實概率的。但但真是概率非常小時，這種抽樣統計的方法就會有問題了。
在樸素貝葉斯中，概率為 0 的影響是很大的，甚至會不顧其他概率的大小。此外，抽樣統計的另一個問題是會低估真實概率。
上式中的 nc 可能為 0，解決方法是將公式變為：
決定常數 m 的方法有很多，我們這里使用值的類別作為 m ，比如投票有贊成和否決兩種類別，所以 m 就為 2。p 則是先驗概率，比如贊成和否決的概率分別是 0.5，那麼 p 就是 0.5。
樸素貝葉斯演算法使用的是分類型數據，在貝葉斯方法中，我們會對事物進行計數，這種計數則是可以度量的。
我們可以劃定幾個范圍作為分類，如：
劃分類別後，就可以應用樸素貝葉斯演算法了。
標准差是用來衡量數據的離散程度的，如果所有數據都接近於平均值，那標准差也會比較小。
對所有的數據進行統計，得到的便是總體標准差。
無法獲取總體的數據，只能選取一部分樣本，這時計算得到的就是樣本標准差。
68% 的數據會標准差為 1 的范圍內，95% 的數據會落在標准差為 2 的范圍內：
用希臘字母 μ （讀「謬」）來表示平均值，σ （讀「西格瑪」）來表示標准差。
例（ e 是自然常數，約等於 2.718 ）：
實現簡單（只需計數即可）
需要的訓練集較少
運算效率
無法學習特徵之間的相互影響
實現也比較簡單
不需要按特定形式准備數據
需要大量內存保存訓練集數據
處理訓練集較大的情況，包括推薦系統、蛋白質分析、圖片分類等。
參考原文原文 http://guidetodatamining.com/
參考譯文來自 @egrcc 的 https://github.com/egrcc/guidetodatamining
❸ 計算機考研：數據結構常用演算法解析(7)
第七章：
對於無向圖，e的范圍是：
數據結構中所討論的圖都是簡單圖，任意兩結點間不會有雙重的邊。
對於有向圖，e的范圍是：
圖的各種存儲結構
鄰接矩陣很方便訪問任意兩點的邊，但是不方便計算其鄰接點。在深度和廣度遍歷中廣泛的需要求某點的鄰接點。所以鄰接矩陣只在Floyed和Prim和Dijstra中採用。
鄰接表能很方便的求某頂點的鄰接點，索引對於與遍歷有關的演算法大多都採用鄰接表。如深度、廣度、拓撲排序、關鍵路徑。但他也有不足的地方，就是不方便求入度或是那些薯早握點可以到他的操作。所以有人引進逆鄰接表。最後人們把這兩種表結合到一起就是十字鏈表和鄰接多重表。一個是存儲有向圖，另一個是存儲無向圖。
在十字鏈睜歷表和鄰接多重表很方便求鄰接點的操作和對應的逆操作。所以實際應用中，凡是能用鄰接表實現的一定能用十字鏈表和鄰接多重表實現。並且它們的存儲效率更高。
1.鄰接矩陣(有向圖和無向圖和網)又稱為數組表示法
typedef struct
{ vextype vexs[maxn]; ∥頂點存儲空間∥
adjtype A[maxn][maxn]; ∥鄰接矩陣∥
int vexnum,arcnum; //圖的頂點數和邊數
GraphKind Kind; //圖的類型
} mgraph;
2.鄰接表(有向圖和無向圖和網)
typedef struct node ∥邊
{ int adj; int w; ∥鄰接點、權∥
struct node *next; ∥指向下一弧或邊∥
}linknode;
typedef struct ∥頂點類型∥
{ vtype data; ∥頂點值域∥
linknode *farc; ∥指向與本頂點關聯的第一條弧或邊∥
}Vnode;
typedef struct
{
Vnode G[maxn]; ∥頂點表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
邊結點
datafirstarc
頂點結點
3.十字鏈表(有向圖和有向網)
headvextaivexhlinktlinkinfo
邊結點
datafirstinfirstout
頂點結點
4.鄰接多重表(無向圖)
markivexjvexilinkjlinkinfo
邊結點
datafirstedge
頂點結點
有向無環圖(DAG)：是描述含有公共子式的表達式的有效工具。二叉樹也能表示表達式，但是利用有向無環圖可以實現對相同子式的共享，從而節省存儲空間。
頂點的度：
無向圖：某頂點V的度記為D(V)，代表與V相關聯的邊的條數
有向圖：頂點V的度D(V)=ID(V)+OD(V)
強連通分量:在有向圖中，若圖中任意兩頂點間都存在路徑，則稱其是強連通圖。圖中極大 強連通子圖稱之為強連通分量
「極大」在這里指的是：往一個連通分量中再加入頂點和邊，就構不成原圖中的一個 連通子圖，即連通分量是一個最大集的連通子圖。有向圖的連通就是指該有向圖是強連通的。
考研有疑問、不知道如何總結考研考點內容、不清楚數慶考研報名當地政策，點擊底部咨詢官網，免費領取復習資料：https://www.87dh.com/xl/
❹ 數據結構復習總結第七章圖
第七章圖
圖的概念
圖G是由頂點集V和邊集E組成 頂點集是有窮非空集 邊集是有窮集;
G中每條邊都有方向稱有向圖;有向邊稱弧;邊的始點稱弧尾;邊的終點稱弧頭;G中每條邊都沒有方向的稱無向圖
頂點n與邊數e的關系 無向圖的邊數e介於 ~n(n )/ 之間 有n(n )/ 條邊的稱無向完全圖襪芹;
有向圖的邊數e介友好判於 ~n(n )之間 有n(n )條邊的稱有向完全圖;
無向圖中頂點的度是關聯與頂點的邊數;有向圖中頂點的度是入度與出度的和
所有圖均滿足 所有頂點的度數和的一半為邊數
圖G(V E) 如V 是V的子集 E 是E的子集 且E 中關聯的頂點均在V 中 則G (V E )是G的子圖
在有向圖中 從頂點出發都有路徑到達其它頂點的圖稱有根圖;
在無向圖中 任意兩個頂點都有路徑連通稱連通圖;極大連通子圖稱連通分量;
在有向圖中 任意順序兩個頂點都有路徑連通稱強連通圖;極大連通子圖稱強連通分量;
將圖中每條邊賦上權 則稱帶權圖為網路
圖的存儲結構
鄰接矩陣表示法
鄰接矩陣是表示頂點間相鄰關系的矩陣 n個頂點就是n階方陣
無向圖是對稱矩陣;有向圖行是出度 列是入度
鄰接表表示法
對圖中所有頂點 把與該頂點相鄰接的頂點組成一個單鏈表 稱為鄰接表 adjvex|next 如要保存頂點信息加入data;
對所有頂點設立頭結點 vertex|firstedge 並順序存儲在一個向量中;vertex保存頂點信息 firstedge保存鄰接表頭指針
鄰接矩陣表示法與鄰接表表示法的比較
) 鄰接矩陣是唯一的 鄰接表不唯一;
) 存儲稀疏圖用鄰接表 存儲稠密圖用鄰接矩陣;
) 求無向圖頂點的度都容易 求有向圖頂點的度鄰接矩陣較方便;
) 判斷是否是圖中的邊 鄰接矩陣容易 鄰接表最壞時間為O(n);
) 求邊數e 鄰接矩陣耗時為O(n^ ) 與e無關 鄰接表的耗時為O(e+n);
圖的遍歷
圖的深度優先遍歷
圖的深度優先遍歷類似與樹的前序遍歷 按訪問頂點次序得到的序列稱DFS序列
對鄰接表表示的圖深度遍歷稱DFS 時間復雜度為O(n+e); 對鄰接矩陣表示的圖深度遍歷稱DFSM 時間復雜度為O(n^ );
圖的廣度優先遍歷
圖的廣度優先遍歷類似與樹的層次遍歷 按訪問頂點次序得到的序列稱BFS序列
對鄰接表表示的圖廣度遍歷稱BFS 時間復雜度為O(n+e); 對鄰接矩陣表示的圖廣度遍歷稱BFSM 時間復雜度為O(n^ );
生成樹和最小生成樹
將沒有迴路的連通圖定義為樹稱自由樹
生成樹
連通圖G的一個子圖若是一棵包含G中所有頂點的樹 該子圖稱生成樹
有DFS生成樹和BFS生成樹 BFS生成樹的高度最小
非連通圖生成的是森林
最小生成樹
將權最小的生成樹稱最小生成樹 (是無向圖的演算法)
普里姆演算法
) 確定頂點S 初始化候選邊集T[ ~n ];formvex|tovex|lenght
) 選權值最小的T[i]與第 條記錄交換;
) 從T[ ]中將tovex取出替換以下記錄的fromvex計算權;若權小則替換 否則不變;
) 選權值最小的T[i]與第 條記錄交換;
) 從T[ ]中將tovex取出替換以下記錄的fromvex計算權;若權小則替換 否則不變;
) 重復n 次
初始化時間是O(n) 選輕邊的循環執行n k次 調整輕邊的循環執行n k;演算法的時間復雜度為O(n^ ) 適合於稠密圖
克魯斯卡爾演算法
) 初好改始化確定頂點集和空邊集;對原邊集按權值遞增順序排序;
) 取第 條邊 判斷邊的 個頂點是不同的樹 加入空邊集 否則刪除;
) 重復e次
對邊的排序時間是O(elog e);初始化時間為O(n);執行時間是O(log e);演算法的時間復雜度為O(elog e) 適合於稀疏圖
最短路徑
路徑的開始頂點稱源點 路徑的最後一個頂點稱終點;
單源最短路徑問題 已知有向帶權圖 求從某個源點出發到其餘各個頂點的最短路徑;
單目標最短路徑問題 將圖中每條邊反向 轉換為單源最短路徑問題;
單頂點對間最短路徑問題 以分別對不同頂點轉換為單源最短路徑問題;
所有頂點對間最短路徑問題 分別對圖中不同頂點對轉換為單源最短路徑問題;
迪傑斯特拉演算法
) 初始化頂點集S[i] 路徑權集D[i] 前趨集P[i];
) 設置S[s]為真 D[s]為 ;
) 選取D[i]最小的頂點加入頂點集;
) 計算非頂點集中頂點的路徑權集;
) 重復 )n 次
演算法的時間復雜度為O(n^ )
拓撲排序
對一個有向無環圖進行拓撲排序 是將圖中所有頂點排成一個線性序列 滿足弧尾在弧頭之前 這樣的線性序列稱拓撲序列
無前趨的頂點優先
總是選擇入度為 的結點輸出並刪除該頂點的所有邊 設置各個頂點入度時間是O(n+e) 設置棧或隊列的時間是O(n) 演算法時間復雜度為O(n+e)
無後繼的頂點優先
總是選擇出度為 的結點輸出並刪除該頂點的所有邊 設置各個頂點出度時間是O(n+e) 設置棧或隊列的時間是O(n) 演算法時間復雜度為O(n+e) 求得的是逆拓撲序列
附二:
第七章圖
*************************************************************************************
圖的邏輯結構特徵就是其結點(頂點)的前趨和後繼的個數都是沒有限制的 即任意兩個結點之間之間都可能相關
圖GraphG=(V E) V是頂點的有窮非空集合 E是頂點偶對的有窮集
有向圖Digraph 每條邊有方向;無向圖Undigraph 每條邊沒有方向
有向完全圖 具有n*(n )條邊的有向圖;無向完全圖 具有n*(n )/ 條邊的無向圖;
有根圖 有一個頂點有路徑到達其它頂點的有向圖;簡單路徑 是經過頂點不同的路徑;簡單迴路是開始和終端重合的簡單路徑;
網路 是帶權的圖
*************************************************************************************
圖的存儲結構 ·鄰接矩陣表示法 用一個n階方陣來表示圖的結構是唯一的 適合稠密圖 ·無向圖 鄰接矩陣是對稱的
·有向圖 行是出度 列是入度
建立鄰接矩陣演算法的時間是O(n+n^ +e) 其時間復雜度為O(n^ )
·鄰接表表示法 用頂點表和鄰接表構成不是唯一的 適合稀疏圖 ·頂點表結構 vertex | firstedge 指針域存放鄰接表頭指針
·鄰接表 用頭指針確定 ·無向圖稱邊表;
·有向圖又分出邊表和逆鄰接表;
·鄰接表結點結構為 adjvex | next
時間復雜度為O(n+e) 空間復雜度為O(n+e)
圖的遍歷 ·深度優先遍歷 藉助於鄰接矩陣的列 使用棧保存已訪問結點
·廣度優先遍歷 藉助於鄰接矩陣的行 使用隊列保存已訪問結點
*************************************************************************************
生成樹的定義 若從圖的某個頂點出發 可以系統地訪問到圖中所有頂點 則遍歷時經過的邊和圖的所有頂點所構成的子圖稱作該圖的生成樹
最小生成樹 圖的生成樹不唯一 從不同的頂點出發可得到不同的生成樹 把權值最小的生成樹稱為最小生成樹(MST)
構造最小生成樹的演算法 ·Prim演算法的時間復雜度為O(n^ )與邊數無關適於稠密圖
·Kruskal演算法的時間復雜度為O(lge) 主要取決於邊數 較適合於稀疏圖
*************************************************************************************
最短路徑的演算法 ·Dijkstra演算法 時間復雜度為O(n^ ) ·類似於prim演算法
*************************************************************************************
拓撲排序 是將有向無環圖G中所有頂點排成一個線性序列 若 ∈E(G) 則在線性序列u在v之前 這種線性序列稱為拓撲序列
拓撲排序也有兩種方法 ·無前趨的頂點優先 每次輸出一個無前趨的結點並刪去此結點及其出邊 最後得到的序列即拓撲序列
lishixin/Article/program/sjjg/201311/23751