『壹』 程序員的數學-讀書筆記
計數法分為 按位計數法 和 羅馬計數法
按位計數法常用的有2進制、8進制、10進制、16進制等幾種。
理論上多少進制在數學上都可以存在，瑪雅人用20進制，巴比倫人用10進制和60進制的混合計數法。瑪雅人20進制可能是和手腳趾加起來的數量有關。巴比倫人採用60進制也可能是因為記錄數字的黏土版比較難記錄文字記號，為了在大數的書寫上少佔位便採用了60進制。
從這一點來看，環境對文明和文化的形成真的是有決定性的影響。假如巴比倫人掌握了造紙術或者在竹子上書寫文字的話，60進制這種違反人類天性的計數方法一定不會出現。話說，漢莫拉比法典就是寫在黑色的玄武岩上的。能夠記錄的文字也就屈指可數吧。
作者提到了其實人也是可以採用2進制計數法的，可是同樣大小的數字用2進制書寫起來位數太多，一來書寫不方便，二來計算時易發生馬虎出現錯誤。而10進制的數天生就是順應人類人性的，即使是幼兒也可以通過數手指頭的方式來計數。
相反對於計算機的物理構造來講，0代表開關斷開，1代表開關連接，這種二極體的物理限制正好決定了計算機較為適用2進制。不過如果你想做出一個10進制的計算機也不是沒有可能的。
這一章比較有趣的是羅馬計數法，我以前也沒有接觸過超過20的羅馬數字，也不知道羅馬數字各個數位上的數字相加之和為數字本身所代表的量。例如：
反觀阿拉伯數字
由此引發作者在兩個程序領域上的思考：
關鍵詞：真值表、文氏圖、邏輯表達式、卡諾圖、三值邏輯、完整性、排他性
- 能夠判斷對錯的陳述句叫做命題（proposition）
邏輯非 --不是A
逆命題
逆否命題
德摩根定律
卡諾圖 （二燈游戲、三燈游戲引出）
未定義邏輯（undefined）
三值邏輯的德摩根定律
本章探討的是通過余數來解決存在規律、周期性的問題。通過規律和周期性的重復，將大問題簡化成容易解決的小問題。
首先作者通過解決星期幾問題，引入了余數的思考概念。
上面的問題在 大問題通過余數規律簡化為小問題 這個方法上表現的還不明顯，於是引入了第三個問題：1234567^7654321的個位數是多少。
以上三個問題是小學奧賽便涉及到的問題，然而其思想在解決真實面對的復雜問題或具象的實際問題時卻很好用。
將一個數字除以2，他的余數應該為0或者1二者之一。我們也可以叫 奇偶問題 。
書中有幾個案例：
這樣分析過來就很好解決七橋問題，確定每個點所連接的橋的點數，與上述結論做對比。
A點為3，B點為，C點為3，D點為3.
由此可以得出七橋問題不可能實現。這個問題的解決也是通過奇偶性來解決的。
作者舉了高斯求和的故事來講如何用數學歸納法來解決無窮數列的求和問題。
兩個小例子便是從0開始到N的和，以及1開始的奇數和。
數學歸納法 是證明[ 有關整數的斷言對於0以上的所有整數（0,1,2...）是否成立 ]所用的方法。
證明方法歸結為兩歩：
根據上述方法，假若某個假設成立，那麼P(0)成立，因為P(0)成立，所以P(0+1)即P(1)也成立。反復如此，對於無窮數列遵守這個規律的證明，就像多米諾骨牌，推到第一個，後面的都會按照第一個的規則倒下去。
然而要避免整個證明出錯，就要重視第二個步驟，也就是歸納。歸納在證明時一定要考慮 是否在所有定義條件下均成立 ，尤其要注意的是在P(0)的條件下是否實現。
課後對話很有意思：
計數是人類每天生活都要運用的方法。
計數的關鍵就在於 注意「遺漏」和「重復」
例如：
綜上，在計數時要發現事物的規則。
要 認清計數對象的本質
要 認清計數對象的本質
要 認清計數對象的本質
重要的事情說三遍。
將計數對象進行 歸納總結 ，使其作為普通規則來掌握。這樣一般不容易出錯。
接下來，作者在 加法法則 里寫到：
乘法法則 的概念比較有意思。
接下來，本章提到了置換、排列、組合3個概念。以下是幾個小例子。
最後提到的 重復組合 里的思考問題比較有趣。
解答的思想是：
這是一種典型的將復雜問題簡單化，並規律化的解答方法。
最後還是要強調下：
要 認清計數對象的本質
遞歸與歸納的區別
歸納（inctive） 是從個別性前提推出一般性結論。
本質上都是 將復雜問題簡化 ，但方向不同。
個人理解是
遞歸是發現第n項和前一兩項之間的關系，實證確定後，往回不斷遞推的一種個別性結論。
即這個結論不是在n為任何自然數時都成立的。需要注意n為0和1的兩項。
通過遞歸解決問題的線路是： 找到遞歸結構——建立遞推公式——找到解析式（只帶n的式子） ，如果不能以解析式的方式描述遞歸結構，也可以用遞推公式的方法描述。如下圖所示的漢諾塔的遞推公式：（它也可以描述成解析式的方式）
歸納所謂的個別性前提是指
斐波那契數列就是運用了遞歸的思想。通過研究和思考復雜問題，抓住事務本質，得到f(n)=f(n-1)+f(n-2)
所以當我們想要用遞歸的方法解決問題時，注意思考第n元素與前後元素的關系。由一個點推開，成一條貫穿始終的線。
利用帕斯卡三角形來研究Cnk=Cn-1(k-1) + Cn-1k的思考方式另闢蹊徑。將兩個加數假設成組合問題里含一個元素和不含那個元素的兩個情況。從而證明了式子。利用的便是組合的數學分析法。（這句話組合的意思不是數學意義上的）。
所以以上將復雜問題簡化的方法是遞歸解法之一，是為了在復雜問題中找到隱含的遞歸結構。其思路是：
通過思考一張1mm的紙，折多少次能夠有地月距離那麼厚，作者引出指數的概念。
這一章的內容比較簡單，對於 指數爆炸 大家應該都不陌生。而 對數 估計也很熟悉。之前接觸到的漢諾塔問題的解析式和斐波那契數列都屬於指數的范疇。
然而在解決 測試所有設定選項的程序時，檢查次數也是一個指數問題 。所以我們應該如何輕松的解決這類問題呢？
利用二分法查找
利用二分法，先詢問最中間的人，如果在左邊，就繼續在左邊的范圍內重復此項方法，直到找到罪犯。這便被稱為 2分法 。他和漢諾塔的解析式如出一轍，可以利用指數原理經過很少的步驟便可找到目標。
二分法本身也是 遞歸結構 ，經過n次詢問，可以在2^n-1人中確定目標。每判斷一次就可以查找近一半的對象。
二分法需要注意的是，所有元素一定要 按順序排列 ，這點至關重要。
指數思想也被用於加密的實現中。因為每多加密一位，暴力破解就需要指數次的運算能力的提升。原則上有限時間里根本不可能破解。指數以其數字的巨大增長能力在加密領域有基本性的作用。
對於指數問題的解決方法，主要有4種，但均不太容易應付規模大的數字。
作為指數函數的逆函數，文章涉及了對數。同時也簡單介紹了古代科學家用過的計算尺。
無窮可以分為 可數無窮 和 不可數無窮 。
所謂 可數無窮 是指 可以按照一定的規律或者表達方式來表達 。
即集合中所有元素都與正整數一一對應。如果每一個元素都可以與1.2.3....等數字對應，也就是說可以按規律表達出來就是可數無窮。
例如：
所以有不可數的集合嗎？
此時運用到了 對角論證法 和 反證法（也叫歸謬法）
假設我們要證明 所有整數數列的集合是不可數的 ，那麼反證就是 假設所有整數數列的集合是可數的 ，此處是運用的反證法。
現在我們按下圖的方式來列出所有整數數列，編號為k的整數列在表的k行。
如果按照圖中第k行的第k個元素ak單獨組出一組數列{a1,a2,a3......}的話，他也是應該包含在所有整數數列里的，然而並沒有，他是游離在所有整數數列之外的。此處得出矛盾，說明命題錯誤，命題 所有整數數列的集合是不可數的 為真。此方法被稱為 對角論證法
除此之外
-所有實數的集合是不可數的
-所有函數的集合也是不可數的
隨後書中討論到了不可解的問題
對於不可解的問題的定義是
事實上，不能寫成程序的函數是存在的。
有些函數不能用文字表達，而且要寫成程序的函數必須 嚴謹定義確切和文字表達 兩個概念。
停機問題
不可解問題的一例。定義是
有限時間並不指時間長短，而是指無論耗時多長，只要能有終止的一刻就好。
事實上，程序本身並不能判斷某一程序是否可以在有限時間內結束運行
所以停機問題也是 不可解問題 之一。
這一章是對之前8章的回顧和總結。
前幾章作者分別對 0的意義、邏輯、余數、數學歸納、排列組合、遞歸、指數爆炸、不可解問題 進行了簡單的介紹和探討。其實所有的章節最後都是在引領讀者產生如何解決問題的思考。
1.認清模式，進行抽象化
2.由不擅長催生出的智慧
3.幻想法則
本書比較適合作為第一本接觸演算法的書籍。目前開始在上 Khan的Algorithms ，9月份跟上 coursera的Algorithms Part I 的開課。
前方的路註定不好走，但是要慢慢嘗試和堅持。