課程學習歸納總結(0228)
2019-11-06 08:50:37
供稿：網友
概率論與數理統計
概率
古典概型的兩個特征： 有限性和等可能性。其中有限性表明的是古典概型的實驗結果是有限的，等可能性表示的是每個實驗結果在一次試驗中出現的概率相等。古典概型同時也叫做等可能概型。那么此處幾何概型呢？幾何概型的特征： 等可能性。 其相對于古典概型少了實驗結果有限的限制；幾何概型對應于于一維表示的是直線段的長度，在二維中表示的是一定區域的面積，在三維中表示的是一定空間的體積，同時如果升級到更高的維度也具有一定的物理意義，但是由于認知的局限性，因此無法將其進行直觀化的描述；概率的統計意義具有三點：非負性，規范性以及有限可加性。其中，非負性表示的是對于任何一個可能的事件其概率一定為整數，規范性指的是必然事件的概率為1，有限相加性指的是如果事件之間兩兩互斥，那么其和事件的概率與各個事件發生的概率的和相等。我們如果在相同的條件下進行了N次重復性實驗，在這N次重復性實驗中，事件A發生的次數為N(a),那么后者與前者的比值表示的是事件A發生的頻率。當實驗的重復次數足夠多時，我們可以用頻率的穩定值來表示事件A發生的概率。其中，一般頻率用f來表示，概率仍然使用P來進行表示。計算機算法設計與分析
遞歸與分治策略
直接或者是間接調用自身的算法稱之為遞歸算法。并非一切遞歸函數都可以使用非遞歸的形式進行定義。能否舉出具體的實例化結果；當一個函數和它的一個變量由函數自身定義時，那么稱這個函數為雙遞歸函數。如Ackerman函數。遞歸的優勢在于遞歸算法結構清晰，可讀性強，且容易使用數學歸納法證明算法的正確性，因此為設計算法、調試程序帶來了很大的方便；遞歸的缺點在于遞歸算法的運行效率較低，無論是耗費的事件還是占用的存儲空間都比非遞歸算法要多。思考：如果一個算法是遞歸的，那么可以通過什么方式來增強其算法的運行效率以及減小空間資源的消耗呢？通常在一個算法調用另外一個算法時，系統需要在調用算法之前完成三件事情： 1).將所有實參指針、返回地址等信息傳遞給被調用算法； 2).為被調用算法的局部變量分配存儲區； 3).將控制轉移到被調用算法的入口。在從被調用算法返回調用算法時，系統也需要相應地完成三件事： 1). 保存被調用算法的計算結果； 2). 釋放分配給調用算法的數據區； 3). 依照被調用算法保存的返回地址將控制轉移到調用算法。綜上所述，在一個算法調用另外一個算法時，首先要留一條后路–返回地址，同時也要為被調用算法需要的局部變量分配新的空間，同時將程序控制權交給被調用算法；而從被調用算法中返回到調用算法需要完成的三件事情則是首先將被被調用算法申請的局部變量的空間進行釋放，同時將被調用算法的計算結果返回給調用算法，同時將程序的控制權交給調用算法。分治法的基本思想：分治法的基本思路是將一個規模為N的問題分解為k個規模較小的子問題，然后使用遞歸的方法將這些子問題分別求解，最后將各個子問題的解進行合并就得到了原問題的解。分治法的適用條件： 1). 原問題的規模減小時更容易求解； 2). 原問題可以劃分為同類的小規模問題； 3). 子問題的解可以合并為原問題的解； 4). 分解出來的子問題之間相互獨立；其中分治法與貪心法以及動態規劃的明顯差異是后兩者不需要子問題的解可以合并為原問題的解，同時獨立性不好時也可以采用動態規劃的方式。在用分治法設計算法時，最好使子問題的規模大致相同；根據遞歸式判斷算法運行時間的方法有三種，分別為： 1). 猜測法。 T(n) = 4 T(n/2) + n, 2). 遞歸樹 T(n) = T(n/2) + T(n/4) + n ^2, 3). 主定理，分三種情況進行分析
