Comments on Z Value

寫好了！這篇不是獨立的文章，算是課後討論，所以沒上課的人應該看不太懂 XD。其中證明 L(i) <= L'(i) 時，我不小心又證一次 L(i) >= L'(i)，變成為同一個敘述造兩個不同的證明，最後整段刪掉有種心血流失的感覺 XD。

--
寫論文很辛苦 XD。

---

我寫這篇之前，只從 Amazon.com 看了 Gusfield 的字串定義。剛剛找到 Z value 演算法的全文，發現我把 R(i - 1) 和 L(i - 1) 的 notation 記為 r 和 l，還有 case 的分法，都和 Gusfield 寫的一樣 XD。不過像隨機客先把 R 和 L 函數明確寫出來，再把 notation 簡化成 r 和 l，我覺得最好 XD。然後 L 函數兩個定義等價的證明、用不同的編號方式及 notation 更乾淨地描述演算法，這些應該都是 original XD。

假象

經驗法則：考試的時候再怎麼十拿九穩，總是有辦法出紕漏。

例證：演算法期中考大概兩小時寫完，剩下一小時就慢慢坐慢慢檢查，果然在倒數十五分鐘前發現巨大的 bug XD。然後最後一題，我直接把例圖視為輸入格式，吃晚餐的時候才想到輸入可能是 general form。雖然我初步一想，應該可以用 linear time 把 general form 化成例圖那種特定輸入格式，可是來不及寫在答案卷上了 XD。

然後記一句 cyy 講的笑話：今天上 Y 老師的課，有人向老師說「莊永裕有提到你耶」（現在發現竟然什麼敬語也沒有 XD（「代號」另當別論，語系不一樣 XD）），接下來我憑想像重建 cyy 的話：「別人都說楊佳玲老師講話很快，可是我不這麼覺得啊。」（這句話三秒內要講完 XD。）

--
其實這也可能是 Murphy's law XD。

Turns Out...

Algorithm midterm turns out to be not so bad XD. 第一題陳述 Master method，連考第三次，我早就特別複習過定理第三段的 regularity condition，也看了簡單版的證明，可惜這次隨機客好心地只叫我們寫前兩段 XD。然後第四題我一看到就笑了，就是這個 bug 嘛 XD！

--
猜題成功？XD 能拿到這題的分數還得謝謝 Yen3 XD。

有料老師

經驗法則：真正有料的老師，期考絕不放水。

最佳例證：金次，只出習題都可以出成這樣 XD。

--
隨機客也符合這條，現在可以放棄抵抗、挫著等了 XD。

Z-Value 備忘

首先要提出的一點：若採用 STL 的左閉右開慣例並讓字元編號從 0 開始，那麼整個演算法（包括右護法 R、左護法 L）的表述都會變得相當乾淨。我的定義依照 C/C++ 字串的慣例（字元編號從 0 開始，區間採用左閉右開），而且 L(i) 的定義可能比較符合原意（我還沒去思考隨機客投影片的定義、隨機客口頭的定義（所謂原意）、和我的定義三者是否等價）：

其中 L(i) 取 min 應該只是為了讓它是 well-defined，實作上不取應該無妨。我上 Amazon.com 看 Gusfield《Algorithms on Strings, Trees, and Sequences》字串的定義，s[i..j] = s[i] s[i + 1] ... s[j]，i 和 j 之間是兩個點，而我的 notation 是三個點，這和 Ruby 的語法完全一致。不過隨機客的 notation 是 s[i...j] = s[i] s[i + 1] ... s[j] XD。

從 i 之前所有的 Z-values 和 r = R(i - 1)、l = L(i - 1) 算出 i 位置的三個函數值時，分為三種狀況。第一種是 r <= i，此時完全無法從已知推斷未知，所以只能用 naïve 的方法比對計算 Z(i)。第二大類是 r > i，以 i 為中心，將 s[l...r] 分為 s[l...i] 和 s[i...r] 兩段，此時我們有以下的已知條件：

這個狀況下的第一個 subcase 可如下推演：

第二個 subcase：

總之可以「代數地」處理此事，而且因為左閉右開，所以完全不需處理 offset-by-one 的問題，很乾淨。詳細狀況連同實作我以後再補，今日不宜花太多時間 XD。

--
只是先記下來備忘 XD。

連哄帶騙

無聊歸無聊，作業還是得做。於是連哄帶騙，穿插勇者動畫放映，最後今天晚上的工作效率不錯，可終於把系統程式作業二寫完了 XD。Effective programming time 應該不多，但是 total programming time（也就是把哄騙的那些時間算在內 XD）應該和一般人差不多 XD。我是用 Xcode IDE 寫的，睡醒再來處理 Makefile 吧 XD。

昨天都沒發文，頁面載入次數竟然和前天四篇文相差不多，很有趣 XD。（但是人次的確減少了 XD。）

--
單純是耐煩的作業 XD。

Correctness of Dijkstra's Shortest Path Algorithm

--
系統程式作業實在是太無聊了 Orz，先看演算法 XD。

Knuth on MMIX

裡面提到 MMIX T-shirt，當天（1999 年底 XD）參加演講的人可以無條件拿到，除此之外只有 MMIXmasters 可以拿。嘖嘖，其實我不知道我有沒有能力參加這個 project XD。

--
除了 MMIX，連 MIX 和程式實作的演算法都要會，還要寫得漂亮 XD。

演算之美

喔喔，這標題和介紹很吸引我啊！而且天時地利人和，下星期五上完高等微積分吃個中餐剛好到系館免費入場，I see no reason not to go！XD

--
不過 103 會塞爆吧 XD。

泵引理

最近很多人搜尋 "pumping lemma" 到我的 blog，是期中考的關係嗎？XD 我的 blog 出現在第三條，可是主要內容和 pumping lemma 的 technical detail 沒什麼關係呀 XD。

不得不說，這次系統程式的作業實在相當煩 XD。

--
不過 Google 引的那段剛好是強者學長（很嗆）的話，難怪會吸引那麼多人的注意？XD

LU Decomposition

前幾週想到這個 C++ data abstraction 示例，感覺上還不錯，把很多重點都串起來了，描述如下：

1. 造出基本的 SquareMatrix class：這裡涵蓋基本的 class 概念，constructor 與 (member) function 的撰寫，arithmetic operator overloading，以及 const correctness。可能被挑剔的一點是：我習慣把 call operator 寫成矩陣元素存取，這在 C++ 其實是 unconventional usage。
2. 寫出回返 L 和 U 兩個矩陣的函式：演算法本身當然需要稍加描繪（嚴謹證明部份可暫且省略），記得闡明這個函式為 const。
3. 實作 cached LU 分解：算出 L 和 U 之後暫存起來，只要矩陣內容不變，下次索取 L, U 時可直接回傳。「矩陣值變」的判準暫先採用「non-const call operator 被呼叫」。儲存 L 和 U 的記憶體採用動態配置，所以 copy-control 三成員要補上，其中 copy assignment operator 使用 copy-n-swap idiom，所以也涉及一點 exception safety。分解函式為 const，但可能修改指向 L, U 的 pointer，所以比較罕見一點的 mutable members 也自然進入視野。
4. 用 proxy objects 更精確掌控矩陣的修改時機：上一步驟的矩陣值變判準顯然不夠精確，所以此步令 non-const call operator 傳回一個 proxy object，精確判定矩陣元素是否被修改。撰寫 proxy object 也會用到 conversion operator。

感覺上值得寫成文章 XD。可是前一篇 ACM #476 ~ 478 都還沒寫完，從大一寫到現在 XD。（後者是從 476 ~ 478 引出多型，然後進一步模仿《Modern C++ Design》實作簡單、特化的 object factory（which is a Singleton），是 OOP 的例子。）

--
寫成文章的話，大概得寫 LU 'P' 分解 XD。

形上觀

前天高中同學問我一題 C++，題目出得糊裡糊塗，那門課叫做資料結構。然後我就聯想到一切教砸的例子，電機系的 C++ 編程、資訊系的各門數學課、醫學系的醫學資訊學…，於是我就有感而發了。形而上者謂之道，形而下者謂之器。能把 C++ 視為器，前提是此人已然得道，則持此觀點無妨。但初學者心中無道，若師者以器的形式傳授 C++，那將只是散亂片段、無法收納歸一的零碎知識。當然學生應該自己做歸納，往形上邁進，但如果要求學生獨立完成這個工作，師者便不需存在了。以器載道，用具象形體作為載具，傳達蘊含於內的形上觀，才是師者最重要的工作 ─ 傳道。因此，擁有對於一個學門的形上觀，是教授此學門的必要條件。（我想這個條件一定馬上排除掉大多數的家教。）相較之下，師者對於形下的具體實作倒可以不用太精深，但如果這方面也能講得有聲有色，將大大提升教學的信服力。

其實系上的數學課可以模仿物理系，直接商請數學系的老師來教啊，或是直接讓學生去上數學系開的課就好了 XD。

--
真的是有感而發 XD。

襲來

真正的期中考浪潮撲來了。本來還好，可是今天高微一敲定第二次期中考時間，感覺整個份量立時變成兩倍，心理壓力變三倍 XD。

--
要從現在就進入備戰狀態 XD。

信任

鄭卜壬老師上課讓人有信任感。我相信老師自己的任脈應該相當順暢了 XD。基本上我聽起來速度剛剛好，不過我也相信，如果對全局沒有什麼掌握的學生聽鄭老師上課會是負擔，因為鄭老師預設學生之前學過的東西都已經通透了。這其實不是過分的要求，像我今天聽到 stack frame 就在心中快按「下一頁」，因為重複講那些很基礎的東西實在沒有意義 XD。

我覺得我現在講課，風格大概和鄭老師很像 XD。講 data abstraction 還會扯到 metric space 去 XD。

感覺上助教授（assistant professor）的實力都相當堅強，正教授反而不一定 XD。

然後那個什麼課程研討會好像真的要辦了，該如何是好呢？XD

--
不過金次還是教得更好，薑是老的辣 XD。

MMIX Register Stack

為啥怎麼看都看不懂…真可惡 XD。

--
今天計算機結構助教講 Verilog，一團混亂 XD。

MMIXmasters

想認真玩 MMIX 的話，大概不能略過 MMIXmasters 這個計畫 XD。MMIXmasters 的偉大目標就是把 TAOCP 前三集所有 MIX programs 都轉換為 MMIX，雖然這工作其實沒有很大創意 ─ 程式邏輯當然要和原本的 MIX 程式一樣、風格要盡量模仿 Knuth、寫完要經過 peer review、最後當然要 Knuth 本人點頭認可。最好暑假能夠開始，不過現在好像有約一半的程式被人認領了，到時候不知道還剩下幾個（或許都剩下特別難的）XD。

--
Fascicle 1（連同《Hacker's Delight》）已經入手了 XD。

與原文對照

以下是未經刪改的原文，並附上對「報刊版本修改之處」的評論 XD：

出於好意作的事情就是對的嗎？
從道德哲學的角度論「立委突擊台大事件」

台灣大學生命科學系 謝廷松
台灣大學資訊工程系 柯向上

民進黨籍立委李鎮楠與林國慶兩人，昨日下午無預警地帶著教育部與警政署的官員到本校（台灣大學）突擊測試校園安全應變機制，臨時模擬同學遭歹徒持槍挾持事件。由於本校正值期中考週，加上前幾天美國維吉尼亞理工學院才發生槍擊案，所以大批警力無預警地進入校園，讓許多正在準備考試或是考試中的不知情學生受到影響。這樣的行為，無論是在社會上或是朝野政壇都引發討論與檢討的聲音。李立委於今日召開記者會時強調他的動機是出於「好意」，而非作秀，並稱騷擾到學生是校警隊處理不當所致而非他的錯，堅持不道歉。

立委突擊檢查的動機是個爭議點，但人心隔肚皮，是好意或是作秀，只有本人知道。旁人只能從各種跡象揣測一人的真正動機，邏輯上卻難以鐵口直斷其動機為何。相對之下，行為具客觀性質，能夠評斷，（JK 注：上兩句乃用以論證「非當事人難以評斷動機，只能考慮行為正誤」，被刪 XD）因此我們擱置關於動機的爭議，聚焦於這次突擊行為的正誤。

一般人常稱「我出於好心，不應受到指責」為自己的行為辯護，卻不知「心存善意」無法證明所作所為合乎道德。仔細考量「無預警突擊測試校園安全應變機制」這個行為在合理可預見的範圍內所帶來的一切正反價值，我們傾向認為這個行為是錯誤的，（JK 注：上句的確可刪，算補述性質，只是怕下面那句直接蹦出來對一般人太突兀 XD）一個在道德上錯誤的行為，並不因選擇這個行為的人具善意而變成正確的。相對之下，會選擇這個錯誤行為的人是否出於好意，倒值得商榷。如果只想到「突擊檢查能檢驗校方和警方的機動程度」，卻沒想到自己的所作所為可能給師生員警造成巨大困擾，這樣的狹隘視野就足以讓我們質疑其行為是否出於善意，因為一個具善意的人會相當關心自己的作為究竟是對的還是錯的。

再者，李委員聲稱騷擾到學生是校警隊處理不當所致，所以錯不在他。訴諸直覺，（JK 注：這四個字被刪掉了，對於一般人也的確不需強調是「直覺」XD）相信大部分的人都會認為這樣的說法有推託的嫌疑。從道德哲學的角度來看，也是如此。（JK 注：因為「直覺」被拿掉了，所以這句 "theoretical perspective follows" 也被拿掉了 XD）如前所述，我們在衡量一個行為在道德上的對錯時，會細細思量它直接或間接地可能帶來的後果。因為校警隊所採取的一切演習舉止，都是「無預警突擊測試校園安全應變機制」這個行為的後果的一部份，所以假若委員在考慮是否突擊學校時，有設想過這樣的結果但仍執意去做，就該負起道德責任。（JK 注：結果上面這段論證全部被拿掉了，此段第一句變成沒有處理 XD。）

「無預警突擊檢查會引起校內師生不必要的恐慌」顯然是合理可預見的結果，應該避免。以這次演習為例，預先知會師生不但能避免負面效應，也不會減弱演習效果，因為師生在這次演習中沒有什麼需要扮演的角色。委員實施突擊檢查之前，更該看看學校是否有重大事項正在進行，就這次事件而言，期考和演習兩相權衡，考試中的學生精神處於緊繃狀態，不宜受無謂干擾，而演習稍延一陣並無多大壞處。最後，突襲檢查除了警示作用以外，其實沒有太大的實質幫助。若要真正提升校園安全，可能的措施包括加派警力巡邏、強化校園的安全設施、設立相關安全單位、向師生宣導生命受脅時的應變方式等等，假若李委員真正為學生好，有心於校園安全的提升，這些才是該要努力去做的事！

聯合報編輯下的標題不錯 XD。

--
Hennessy & Patterson 的 Computer Architecture 新版變得好薄 XD。

史料

從高三下學期開始零星地寫 blog，大一開學後方趨頻繁。至於高中生活，乃至國中生活，主要的記錄留在聯絡簿（國中）和週記（高中）。昨天拿起來翻一翻，國中聯絡簿超過一半的篇幅都是考試，偶爾會有一天考九科或是作業趨近十項的時候，還真的滿恐怖的 XD。基本上國中和高中都滿 naïve XD。

--
看看以後會不會覺得大學時代很 naïve XD。

非罕見書籍

我看今天到台北就順便繞到天瓏去，把那兩本非罕見書籍帶回來好了 XD。

--
然後實質的期中考週也差不多要到了 XD。

Bernstein Polynomial

雖然 Bernstein polynomial 看起來已經是很真實、「可以摸到」的函數了，但是用數學家的方式看 Bernstein polynomial 還是有點飄渺 XD。給一個閉區間上的連續函數和誤差 epsilon，若要造出一個每一點誤差都小於 epsilon 的 Bernstein polynomial，首先要確定 n 的值，而 n 的值取決於 uniform continuous 的 delta 值（among other values），這個 delta 值是用「[a, b] 為 compact」造出 finite subcovering 得到，而促成「[a, b] 為 compact」的 Heine-Borel 定理完全是存在式的定理。這個狀況和 Knuth 在〈Computer Science and its Relation to Mathematics〉（《Selected Papers on Computer Science》，p.8）描述的真實故事如出一轍：

The following true story is perhaps the best way to explain the distinction I have in mind. Some years ago I had just learned a mathematical theorem from which it followed that any two n \times n matrices A and B of integers have a "greatest common right divisor" D. This means that D is a right divisor of A and of B, i.e., A = A' D and B = B' D for some integer matrices A' and B', and that every common right divisor of A and B is a right divisor of D. So I wondered how to calculate the greatest common right divisor of two given matrices. A few days later I happened to be attending a conference where I met the mathematician H. B. Mann, and I felt that he would know how to solve this problem. I asked him and he did indeed know the correct answer; but it was a mathematician's answer, not a computer scientist's answer! He said, "Let R be the ring of of n \times n integer matrices; in this ring, the sum of two principal left ideals is principal, so let D be such that

  RA + RB = RD.

Then D is the greatest common right divisor of A and B." This formula is certainly the simplest possible one; we need only eight symbols to write it down. And it relies on rigorously-proved theorems of mathematical algebra. But from the standpoint of a computer scientist, it is worthless, since it involves constructing the infinite sets RA and RB, taking their sum, then searrching through infinitely many matrices D until finding one for which this sum matches the infinite set RD.

Knuth 後來倒有找到解決這個問題的 "computer scientist's answer"。Bernstein polynomial 在圖學的 Bézier curve 上好像也有一些應用，according to Wikipedia。（然後才突然想到，Bernstein polynomial 的形式的確和 Bézier curve 有點像，都有二項式的痕跡 XD。）

--
其實我之前很多關於 CS 的想法都可以在 Knuth 這本書裡看到類似敘述 XD。

亞馬遜團

想要的「罕見」（定義：難以在台灣本地買到）書單累積到三本了，全都是 Knuth XD：

• Selected Papers on Computer Science
• MMIXware（JK 注：這本相當貴 XD。）
• Surreal Numbers

另外還有非罕見書籍兩本：

• The Art of Computer Programming, Volume 1, Fascicle 1: MMIX -- A RISC Computer for the New Millennium
• Hacker's Delight, by Henry S. Warren Jr.

好一陣子沒買書了，不過其實也不急著買，因為現在手邊的書也有點消不掉，而且最想要的兩本 MMIX 都有電子版可看 XD。只是屆時光顧 Amazon.com 的時候，可能開個團比較省 XD。

--
右邊的 WishList 順便更新一下 XD。

上了！

倫理學這次要求大家投稿聯合報、中國時報或教育部的生命教育網站，於是神和我前天寫了一篇社論，從道德哲學（倫理學的同義詞）的角度檢視立委突擊台大事件。隔一天後，也就是今天刊出來了 XD。最後聲明一點：神才是主筆，我只是副手 XD。

連結在 external link 喔 XD。

--
我以為這麼理性的東西不會上的 XD。

數學底子

Knuth 的數學底子真的很深啊 XD。〈Algorithms in Modern Mathematics and Computer Science〉裡面，他隨便抽九本數學書出來看第 100 頁的第一個結果，要觀察何謂數學思維，並搜尋演算法的影子。第八本是 Pólya & Szegö 的《Aufgaben und Legrsätze》，英譯本書名叫做《Problems and Theorems in Analysis》，第 100 頁是一個 "real challenge"：

看 Knuth 的說法，這題沒提供解答，只有「足夠的提示」。於是 Knuth 熟練地化簡算式、變數代換成無窮的瑕積分、造出 uniformly convergent sequence of functions、證明這個 seq. of functions 是 uniformly bounded、從而能夠把瑕積分外的 limit 放進積分符號內，最後用 Stirling's approximation 得到結果，令人目瞪口呆。其中「uniformly bounded convergence ==> limit 和無窮瑕積分操作順序可掉換」還是金次沒說過的，這個要想辦法自己證一次 XD。

然後下一本書 Bishop 的《Constructive Analysis》第 100 頁赫然就是 Stone-Weierstrass 定理，真是讓我震撼 XD。剛好正在學，所以對心理的衝擊特別大 XD。

--
大概可以了解 Knuth 說「近來的 CS 學生都不太讀數學」的意思了 XD。

MST Uniqueness Property 另證

這是強者同學當天上課提出來的，不需要直接使用 cut property，看起來比隨機客的版本簡短一點點 XD。

然後金次今天證明上次那個 Bernstein polynomial 均勻收斂的 lemma，用的純粹是 generating function 的手法。唔，這個 lemma 的證明上，我認為我的版本大勝 XD。

--
而且金次沒講那個式子在機率上的意義 XD。

MST 基本性質

以下三個性質全部要有不失一般性的假設「所有邊的權重皆相異」。剛剛和同學看隨機客投影片，在 cycle property 卡了好久（我記得隨機客也是說他很容易在 cycle property 卡住 XD），趕快記下來比較安全 XD。

---

Figure 1: Illustration of the Cut Property

---

---

Figure 2: Illustration of the Proof of the Uniqueness Property

---

示意圖取自隨機客的精美投影片 XD。嚴謹說來，必須要有 uniqueness property，才能用 MST 基本定理證明 Boruvka、Kruskal、Prim 三個演算法的正確性，所以上述三個性質不能忽略 XD。

--
其實 cut property 的證明可以寫 "Proof. Trivial." XD。

S-B T

D.E. Knuth，〈Computer Science and its Relation to Mathematics〉，《Selected Papers on Computer Science》p.7：

Certainly there are diverse phenomena about computers that are now being actively studied by computer scientists, phenomena that are hardly mathematical.（JK 注：如何定義 "mathematical"？）But if we restrict our attention to the study of algorithms, isn't this merely a branch of mathematics? After all, algorithms were studied primarily by matematicians, if by anyone, before the days of computing machines. Therefore one could argue that this central aspect of computer science is really part of mathematics.

However, I believe that a similar argument can be made for the proposition that mathematics is a part of computer science! Thus by the definition of set equality,the subjects would be proved equal; or at least, by the Shröder-Bernstein theorem, they would be equipotent. My own feeling is that neither of these set inclusions is valid. ...

隨便引一段 XD。才看七頁就熱血沸騰，好看啊，Knuth 寫得真是太棒了！XD

--
連 Shröder-Bernstein 定理都出來了！XD

全套 Knuth

其實可以考慮把 Knuth 的書都收集起來 XD。不過還是先從圖書館借好了 XD。

--
《The TeX Book》竟然收在總圖 2F 人社資料區 XD。

---

坐而言不如起而行！初步鎖定《Selected Papers on Computer Science》、《Selected Papers on Computer Languages》、《Things a Computer Scientist Rarely Talks About》，不過第二本圖書館沒有，第三本被借走了，所以只能預約第三本，待會吃完晚餐借第一本。不過我忘了「到期 06-08-07」到底是「2006 年 8 月 7 日到期」（這是被偷走很久的意思 XD）還是「2007 年 6 月 8 日到期」（為啥可以借這麼久？哪位老師借的嗎？）XD。

--
沒有期中考的期中考週 XD。

---

謎底揭曉：是「2007 年 6 月 8 日到期」XD。看來借的人不是大學部學生 XD。

交叉測試

星期三「AP 突然正常」看來其實是迴光返照，因為接下來幾天斷斷續續的狀況更嚴重了。剛剛趁計算機結構停課，用室友的網路做了交叉測試，幾乎可以確定是 AP 的問題了。其實還有可能是台大（或宿舍）的網路系統和這台 AP 相沖，這樣子嚴格講就不是 AP 出錯 XD。反正最近要調查一下如何送修 XD。

沒有 AP 的話，因為宿舍網路會認網卡卡號，所以 PB 和 PC 同時只能有一台上網，而且切換手續麻煩。剛剛拿 USB 無線網卡想讓 PC 接收 PB Airport 的無線網路廣播，可是 Vista 不認它，也找不到驅動程式，所以現在 PC 處於與世隔絕的狀態 XD。

--
至於 PB 的藍芽真的自體修復了 XD。

核爆

高微下學期第一次期中考宣告慘爆！猶如惡夢成真，整張考卷看下來，能夠讓我一看「啊，trivial」的題目少之又少，大多數都是「我的天啊」、「連這個都出了」、「不會吧」XD。只能說，我完全低估下學期的難度，然後很多心魔還沒突破 XD。這樣的結果或許會對下次期中考有點振奮作用 XD。

--
心魔其實是最可怕的 XD。

Expectation

昨天找為晋時看到 Cauchy distribution 的平均值（也就是 E[X]） 不存在（無定義？），然後發現 continuous random variables 的期望值要求絕對收斂，以避免不定型出來搗亂。這很自然讓我聯想到 discrete random variables 的期望值，我們的那本課本（就是那種不太理論的課本 XD）也曾提過級數需要絕對收斂，但沒解釋原因。今天上高微前想到原因，也 Google 到相同論調。這在高微講過：條件收斂的級數若次序重排，其和變矣。（很驚人的一個事實是，對於任意「條件收斂的級數」，給定任何實數，你都可以找到一個重排使得級數收斂至那個實數！）相對之下，絕對收斂的級數若次序重排，其和不變。顯然要求絕對收斂是要避免加總之次序影響期望值。

--
高微要爆了高微要爆了！XD

名不符實

下週是校定的期中考週，不過我下週卻沒有任何一科要考試 XD。寬鬆講的話，計算機結構是在下週考啦（仍僅一科 XD），可是我又不用考，難不成要亂入嗎？XD 其實不用怎麼讀就可以去考了 XD。

--
天啊，明天要考高微了！XD

場

昨天突然 PB 的藍芽和 AP 都正常了 XD。

--
自體修復？未知氣場作祟？XD

Arzela-Ascoli 定理證明

這是上數位電子學的時候邊寫的 XD。因為直接用「在 C[a, b] 中有收歛子序列」的敘述，所以相對於金次昨天上課的完整證明，我造出 g_k 後直接證明 uniform convergence（從而在 C[a, b] 中收歛），還用上好久不見的 1/2 covering 手法 XD。

--
這個定理和其證明算是分析學裡面相當經典的吧 XD。

---

勘誤：定理的結論應該是在 C[a, b] 中收歛，不是 C[0, 1] XD。

mimeTeX

太好了！終於有「把 LaTeX 數學式內嵌於 blog」的簡便方案 XD。其實並不非常簡便，效果也不完美（尺寸、位置等等現在都先睜隻眼閉隻眼，以後慢慢想辦法調 XD），但如果遇到大量符號，相較於自己製作圖片上傳應該快很多 XD。不過倘若式子只有一兩個，那大概還是用 LaTeXiT 吧，視覺效果好很多 XD。

--
Bernstein polynomial: .

不要口出狂言

以下是金次在 3/23 的有感而發，先聽寫下來備查 XD。

我聽一個朋友說，有同學在網路上留言，說：「陳金次老師說，數學的真理不因時空而轉變，我對你的愛也不因時空而轉變」。（全班大笑 XD）古人說路遙知馬力，世間很難看到有這種不因時空而轉變的愛，男女之間的愛。不要口出狂言，這很難的事情啊。那是要有條件：在你年輕貌美的情況下，我對你的愛「存在」。（全班大笑 XD）他年老了、醜了，你還愛他嗎？難啊難，真難啊。不要說年老，有一天他生病了、憔悴了，你愛他嗎？愛不因時空而轉變，那個已經是超凡入聖，平常人做不到，很難，很難。我也做不到。你能夠像我那個師母一樣，憂慮她先生退休之後人生怎麼過，能夠憂慮到掉下兩顆眼淚，那已經是世間很美好的愛，那種愛才可能昇華，不因時空而轉變。平常的愛都談不上愛，都是一種慾。平常世間這種愛，只不過是荷爾蒙的分泌而已（全班大笑 XD），談不上昇華。

最後兩句單刀直入 XD。

--
等高微考完再把印象裡可找到的金次有感橋段全部弄出來 XD。

遲鈍

今天高等微積分證明 Bernstein polynomial 的均勻收斂性，從而證明 Weierstrass Approximation Theorem。金次寫了一個 lemma，說下次證明：

這我一看就覺得很親切 XD。不只是玩過一點水泥數學的緣故（這不用玩過水泥數學就會算 XD），更重要的是，這一副就是二項分佈（binomial distribution）的某種期望值的長相，還能不會算嗎？明天要期中考了耶！XD 於是興沖沖地用力計算如下：

愈算愈覺得眼熟，最後一看，呃，我在重造輪子 XD。x 就是 Bernoulli trial 成功的機率嘛，那期望值 E(X) / 平均值 μ 當然是 nx，然後以平均值為軸的二次矩（second moment）就是變異數（variance）σ² 啊。所以那個式子根本是顯然，就只是二項分佈的變異數而已 XD。

--
實在是太遲鈍了 XD。

大喜！

孫效智老師要結婚啦！而且是段動人的感情，孫老師傳授的生命之學又添一個最具說服力的實例！

--
祝福老師！

閉區間上連續函數之個數

定義於一個閉曲間上所有的連續函數共有多少呢？答案：和實數一樣多。證明這個事實需要以下定理：

以 [a, b] --> R 的連續函數來講，只要在 [a, b] 間有理點的值都確定，整個連續函數就確定。這個結果看似無聊（trivial），其實很有趣，因為有理點和無理點的數量差距不可以道里計，前者之於後者，比一粒沙子的質量之於整個地球（不然說整個銀河系也可以 XD）還要稀少。（沙粒雖小，終究還有質量，所以比值不為零。）可見連續函數是多麼好的一類函數，即使只知道少得可憐的資訊，只要確實抓到要害（滿足 dense 的條件），就能掌握整個函數的行為。

--
其實是 Arzela-Ascoli 定理證明的最後一步，以前在連續那裡沒處理好，趕快補起來 XD。

---

勘誤：關於 f 的那個條件應該改為 "f: K --> (Y, \rho) continuous" XD。

---

再勘誤：上述證明有瑕！我找任意一個點列趨近 x，並任取收斂子點列，這樣還必須證明任意點列和收斂子點列所產生的極限值都相同才行。暫時不去補這個洞 XD。

---

如下修補應該就可以了 XD。

座談會

今天上計算機結構之前聽到內線消息，原來陳俊良老師是課程委員會召集人之類的？！總之好像有意願辦座談會之類的東西，所以之前那個「敢不敢講」的問題可能得認真考慮了 XD。

cyy 真是太威猛 XD。下星期計算機結構期中考，範圍裡面只有 datapath for multi-cycle instructions 超出 cyy 處理過的部份，而且這是這次上課才講到的！XD 以後 architecture 真的可以考慮直接接在 organization & assembly 之後，馬上省半學期 XD。

--
高微期中考倒數開始了 XD。

CiFM

Computation is formal manipulation.

Form 與 semantics 之間看似有道不可跨越的鴻溝。這對於相信心智只是「某種複雜計算」的唯物論者是個重擊，但堅持這道鴻溝不可跨越的人也得設法說明這道鴻溝為何（如何）存在。

很快就找到一篇持反論的文章：〈Computation Is Just Interpretable Symbol Manipulation: Cognition Isn't〉。才剛看完 abstract，看完有立刻的感想再說 XD。

--
然後我的數位電子學現在都只能支離破碎地從形式上去操作 Orz。

---

簡單看完幾段，Harnad 這篇文章是用哲學的論證方式去寫的，有些地方我覺得還可以再質疑 XD。不過這是快速反應下的感想 XD。Dijkstra 也有一篇〈What Computing Science is about〉，也可以看看。其中有一句 "During its first decade, Computing Science suffered, in fact, from an 'identity crisis' " 還滿貼切的 XD。

0^0

標題不是表情符號 XD。今天又翻到，覺得值得摘錄下來 XD。Knuth 宣稱 0⁰ 應該定義為 1，理由在水泥數學 p.162：

Some textbooks leave the quantity 0⁰ undefined, because the functions x⁰ and 0^x have different limiting values when x decreases to 0. But this is a mistake. We must define

x⁰ = 1, for all x,

if the binomial theorem is to be valid when x = 0, y = 0, and/or x = -y. The theorem is too important to be arbitrarily restricted! By contrast, the function 0^x is quite unimportant. (See [220] for further discussion.)

其中 [220] 是 Knuth 寫的〈Two Notes on Notation〉，可從 Knuth 的網頁下載 .tex 全文。這段敘述很有說服力 XD，同時也揭露所謂「定義」的些許本質。

--
HTML 對程式碼（in particular C++ template code）和數學式實在不友善，尤其是後者！XD

---

看完 [220] 關於 0⁰ 的那一段（然後發現其實我以前看過 XD），就想到聰明引述 Laplace 的這句話：「做數學有一半工作是記號的戰爭。」XD

水泥數學

從離散數學的組合學到機率的二項分佈，只要遇到 binomial coefficients 的計算化簡，翻出水泥數學幾乎都有解，而且只用到水泥數學裡面很簡單的部份 XD。線性代數和機率分別因為倫理學和高等微積分不能修陳文進老師的課，【演算法的數學解析】再沒修到就真的沒天理了 XD。

--
沒真正修過，連最基本的公式都要翻書，很惱人 XD。

Might Gaine

餐廳收包裹的流程不小心出差錯，上個週末就該入手的三部勇者動畫直到今天才拿到。很快把勇者傳說和太陽勇者的結局看完 XD，至於勇者特急的結局之前在 YouTube 上就看過了 XD。

--
一般劇情慢慢看 XD。

名

我的名字出現在隨機客板上了 XD。不過我猜隨機客還認不出我，因為到目前為止還沒有被認出的跡象 XD。

--
其實也很難說 XD。

藍芽毀棄

不過沒人大叫 XD。理論上應該送修，然而 ptt MAC 板上最近剛好貼出幾篇送修血淚文，讓人有點害怕 XD。Bluetooth 對我又沒什麼重要用途，所以會先擺爛一陣 XD。

--
唯一的用途就是那隻藍芽滑鼠，可是那隻滑鼠又十分少用 XD。

有瑕

隨機客的 naïve algorithm for all-pairs shortest path based on Bellman-Ford 有瑕疵！投影片上如是說：

• Run Bellman-Ford to detect negative cycle in O(mn) time. If there are negative cycles, then stop.
• For each node i of the input graph G:
  Run Bellman-Ford in O(mn) time to compute d(i, j) for all nodes j.
• The overall time complexity is O(mn²), which could be Θ(n⁴) in the worst case.

問題在第一個步驟。Bellman-Ford 是 "single-source" shortest path 的演算法，那要如何決定起點呢？任意挑選不可行，反例如下：

這個圖中間有個 negative cycle，由三個點構成。如果隨便選卻沒選到那三個點之中的一個，那就找不到 negative cycle。可以想像，那三隻延伸出去的手臂可以相當長，而使選中那三個點的機率要多低有多低。解法很簡單：把第一個步驟拿掉就好了。對每個點召喚 Bellman-Ford 時，都做第 n 個 iteration 確定沒有 negative cycle。這樣對整體演算法的時間複雜度沒有影響，也對原本投影片上第二個步驟的敘述沒有嚴重影響 XD。如果要寫得詳細一點，就是

• For each node i of the input graph G:
  Run Bellman-Ford in O(mn) time to compute d(i, j) for all nodes j. If a negative cycle is detected, then stop.

不過加速部份的 preprocessing 那裡也有同樣問題，我還不知道可不可以省略，因為還沒聽完 XD。

--
難得有問題可以問 XD。

---

以下是針對 dynamic programming 的兩個演算法。首先，那個 negative cycle 的檢查很重要，因為後面的 recurrence relations 都假設 d 存在。（後註：課本講 Floyd-Warshall 演算法的時候直接假設沒有 negative cycles，很滑頭 XD。）不過，或許可以像 Bellman-Ford 一樣多做一次，若又有變動則代表有 negative cycle(s)。（這個想法有待證明或否證。）至於 Johnson 的 reweighting algorithm…還沒到那裡 XD。

--
或許是找助教或老師的時候了 XD。

---

聽完 Johnson 的演算法，或許那一次檢查 negative cycle 的 Bellman-Ford 可以用 0 號節點當起點？！（後註：課本正是這麼做 XD。）如果本來的圖沒有 negative cycle，新的圖也不會有 negative cycle；如果本來的圖有 negative cycle，那個 cycle 一定可以從 0 號節點抵達，那就會被 Bellman-Ford 找到。這樣的時間複雜度是 O((m + n - 1)(n + 1)) = O(mn + n²)，三個加速演算法都可以負擔。

所以隨機客（和課本）有個地方可以寫得更清楚一些：

• The node weight function h can be obtained by Bellman-Ford in O(mn) time.

這裡的 m 和 n 應該是指原圖的邊數和點數，但 Bellman-Ford 是以「加入 0 號點的圖」為輸入，所以時間複雜度挑剔一點的話不只是 O(mn)，而是 O(mn + n²)。不過對於「正常」的圖（m = Ω(n)），後者就可寫成 O(mn)。

--
這樣問題應該差不多解掉了吧 XD。

玄妙

高等微積分已經進入一種很玄妙的境界 XD，不過倒不至於 beyond comprehension，應該只是不習慣 XD。C[0, 1] 上的 compact set…真的是純理性的東西 XD。

--
明天不用上課！好像做夢一樣 XD。

比較

我不喜歡施吉昇老師教的系統程式 XD。一上來，施老師就把 unbuffered I/O 詮釋成「沒有 buffer 的 IO」，即「每次呼叫 read/write 就執行一次 disk I/O」，這剛好和鄭卜壬老師及課本所說的 "the term unbuffered means that each read or write invokes a system call in the kernel" 相衝突，鄭老師並提出一個很有說服力的佐證：「kernel 可能自己有個 buffer cache，我們不能確定 kernel 的處理方式」。然後，施老師喜歡提那種不知道想要什麼答案的問題，然後又花很多時間等答案，與台下互動的功力遠不如隨機客 XD。總之在這門課上面，鄭卜壬老師讓人比較信服 XD。

--
這種題材很容易教到讓人睡著 XD。

置傘於外

昨天下午依照習俗，把傘放在 7-ELEVEN 外面，今早才發現沒帶回來，幸好還在 XD。

路口的紅綠燈似乎到了這個時段都會在顯示「還有 2x 秒」時轉黃，所以很久以前的星期二不是作夢 XD。

--
不過為晋的傘最近被偷了 XD。

不穩

宿舍網路不穩，正好碰上系統程式作業 deadline XD。剛剛接近十一點的那段斷線中間正好留一個縫隙，似乎是刻意騰出來讓我上傳作業用的，因為一傳完就斷線了 XD。

--
關懷倫理和德性倫理的文章有點長 XD。

小題大作

早上醒來，肚子隱隱作痛，不過似乎沒上次嚴重。穿好衣服、收拾背包，情況沒有好轉，甚至有惡化的趨向。掙扎一陣，最後想到上上星期四的慘狀，還是決定休息，傳簡訊請 yen3 幫忙聽課 XD。最後證明沒有上次嚴重，不過趨近正常也是十一點多的事情了 XD。大概要等到星期三才能把 all-pairs shortest paths 補起來 XD。

Y 老師上星期上到最後一節也不舒服，提早讓我們走。然後 cyy 真的很神妙，Y 老師到這一週都還沒跳出 TOY 的範圍 XD。下一週應該就會進入 multi-cycle instructions，那時候才真正離開 cyy 給的基礎 XD。

--
上上星期四的經驗實在太慘烈，至今心有餘悸 XD。