詢問區間 K 小，額外支持插入一個元素到序列中。
|
|
|
|
直接修改可持久化塊狀鏈表的那一題 Zerojudge b411 記憶中的序列 2，把可持久化的記憶體拔掉，這樣就免得記憶體需求過大。出題者是想用替罪羊樹掛另一個平衡樹下去做。應該沒設想到塊狀鏈表在此題的速度也不算差。時限 60 秒大概跑了 30 秒，還不比樹套樹來得慢。
因為有插入操作，不管是主席樹還是函數式線段樹 (這兩個應該是同一個傢伙)，都無法辦到，只能靠可插入的平衡樹。
|
|
維護一個並查集的操作，並且支持版本回溯。
|
|
|
|
持久化概念，相當於維護 parent[] 陣列的版本，這一點可以利用可持久化線段樹來維護。
並查集的查詢功能不修改 parent[] 陣列，合併操作卻有可能修改數個 parent[]，為了降低記憶體用量，盡可能少用路徑壓縮這個技巧，雖然在一般並查集都會使用這個來加速，否則很容易變很慢，是因為持久化是會拉低速度，因為持久化需要 $O(\log N)$ 的時間去更改 parent[]，單筆路徑壓縮長度為 $M$ 個點，需要 $O(M \log N)$ 的調整，$M$ 在並查集中是常數類。
詢問不多時用啟發式合併就好，將小堆的元素合併到大堆中。效能會比較好。
|
|
動態區間 K 小，有四種操作
|
|
|
|
每次操作最多增加 $O(\sqrt{n})$ 記憶體，需要針對節點作抽象化，修改節點時再進行實體化，如此一來不用針對搜索路徑上的每一節點都進行複製，一般持久化平衡樹進行時，會直接複製整個節點，但塊狀鏈表若是複製下去會退化成時間、空間都是 $O(n)$ 的情況。
詢問時仍然需要二分搜索答案，看答案是否符合 K 小元素，也就是說要得到某個元素在區間中的排名。
塊狀鏈表代碼很醜，看看就好。如果需要支持修改、增加元素的區間 K 小，雖然複雜度高，但常數小、記憶體快取優勢，速度不比二元樹類型的資料結構來得慢，不管需不需要持久化塊狀鏈表都是這類型不錯的選擇。
假設詢問為 $Q$ 個，聽說可以用區間 $[1, 2NQ]$ 的線段樹之類的超大區間線段樹，必要的探訪時進行開花 (將子節點打開)，利用標記計算相對位置來進行查詢。相對位置計算大概會在邊緣情況崩潰。
至於柳柳州提到的替罪羊樹是樹套樹下去持久化，每一個節點表示一個區間，接著在節點中建造一個平衡樹來查找區間 K 小元素。這樣的做法一樣需要二分搜索答案。但塊狀鏈表在速度跟記憶體都贏了，因為樹套樹的常數比較大，增加的記憶體也多。
|
|
幾乎是密碼學基礎數論，看來也走到這了。
隨便寫寫，上課不專心真是抱歉。
Given an integer $x$, what is the requirement to let the multiplcative inverse $x^{-1}$ exist when modulo $p$? if $x^{-1} \mod p$ exists, please write down the equation (based on Fermat’s theorem) used to compute $x^{-1} \mod p$. (5%)
What is the Euler totient function $\phi(n)$? Please answer $\phi(77) = ?$
$\phi(n)$ 表示 1 到 n 之內的整數，有多少與 n 互質的個數。
$\phi(77) = 77 \times (1 - 1 / 7) \times (1 - 1 / 11) = 60$
Whais the discrete logarithm problem? (5%)
對於等式 $y = x^a \mod p$，已知三整數 y, x, p，解出 a 的問題。詳見小步大步算法 baby-step-giant-step，複雜度 $O(\sqrt p)$
What is a hybrid cryptography? (5%)
$$\text{hybrid cryptosystem } = \text{ public-key cryptosystem } + \text{ symmetric-key cryptosystem}$$
What are the two primary reasons of using a cryptographic hash before signing a signature? (5%)
cryptographic hash 密碼雜湊函數，通常會計算 $hash(M)$
Please write down the RSA public key encryption and decryption process (including public key and private key generation process). (10%)
Please develop a left-to-right binary exponentiation algorithm without “conditional jump” which is usually dangerous to some engineering attack. (10%)
Montgomery Ladder
|
|
Below is the DSA signature scheme in which $p$ is a large prime, $q$ is a 160-bit prime factor of (p - 1), $g$ is an integer of order $q$ modulo $p$. Let $x$ be the signer’s private key and $y = g^x \mod p$ be the public key.
Please complete the following nissing steps of the scheme. (10%)
Please describe a trick for speeding up DSA’s on-line signing process. (5%)
_______________________________________________________________________
Signing algorithm Verification algorithm
_______________________________________________________________________
r = (g^k mod p) mod q w = s^-1 mod q
k is a random integer u1 = (SHA(m) * w) mod q
s = ________________ u2 = (r * w) mod q
m is the messgae v = _________________
the signature is (s,r) if v = r then the signature is correct
$g = h^{(p-1)/q} \mod p $ ，其中隨機亂數 $h$，滿足 $g > 1$ 即可。
從費馬小定理中，有一個比較特別的計算來得到 order $q$，所謂的 order $q$ 就是在前 $q$ 個 $g^i \mod p$ 下不會出現重複 (循環長度至少為 $q$)，從觀察中得知循環長度 $L$ 滿足 $L | p-1$，也就是說 $L$ 是 $p-1$ 的因數，$q$ 則是要找到一個大循環，讓攻擊者更難找到 $x$，又因為 $L$ 是其因數，由於 $q$ 是 $p-1$ 的其中一個質因數，則保證是一個最小循環節的要求。
$s = k(SHA(m) + x \times r)$
$v = g^{u1} y^{u2}$
可以 offline 去預處理隨機亂數 $k$，事先計算一堆的 $r$、$z = k^{-1}x \times r$，那麼計算 $s$ 可以非常的快速，$s = k^{-1} SHA(M) + z \mod p$，假設 hash 計算快速，只動用到一次乘法和加法，相較於 RSA 的簽章方法，少了指數次方運算。
Under the following certificate hierarchy, please provide all the details of how end user A checking the correctness of end user C’s public key by verifying a sequence of certificates. Note: User A only knows X’s public key, but does NOT have the root Z’s public key directly. (10%)
若 A 要確認 C 給的 public key 是否正確，則依循以下步驟來確認
Y<<C>>，拿 Y 的 public key 進行確認 C 的 public key。Z<<Y>>，拿 Z 的 public key 進行確認 Y 的 public key。X<<Z>>，拿 X 的 public key 進行確認 Z 的 public key。 Z
／ ＼ Notation used
X Y X<<A>>:
／ ＼ ＼ A's certificate issued by X
A B C
Pleasewrite down the Diffie-Hellman key exchange protocol (including the public key and private key generation process). (10%) What is the man-in-middle (or the middle person) attack? (5%)
假設有兩個人 A, B 要通訊，則把自己的 public key 交給對方，共同產生出一把暫時的 key $K_{AB}$ 進行通訊加密。
假若現在要進行中間人 C 的攻擊，則會在一開始交換 $K_{AB}$ 的時候插入到其中通訊。
如何防止中間人攻擊，大約有幾種方法，但牽涉到可信任第三方、計算速度。
owner_id 不是通訊對象 A。如果 CA 不可信任，則可以讓 C 簽一個 $Sign_{CA}(\text{public key C || owner_A || expiration date || ...})$ 來欺騙 A 和 B，也就是說 CA 和 C 偷偷在私底下做了黑心勾當，那麼中間人攻擊仍是存在的。Both message authentication code (MAC) and digital signature can be used to provide the functionality of message origin and integrity check. Please briefly describe these two techniwues and compare percisely the difference between these two techniques. (10%)
message authentication code (文件訊息鑑別) 顧名思義就是針對 message 進行驗證，確認發送者身分和資料完整性，相較於 digital signature (數位簽章) 也是做相同的事情，訊息量不同且產生出來的結果也大不相同。通常文件訊息鑑別會破壞儲存資訊，藉由雙方共享的 key 來進行身分認證，可用暫時性的 key，若採用非對稱式則需要額外的數位簽章來輔助驗證發送者。而數位簽章則是提供有效期限內的使用，這把驗證的 public key 必須存在比較長的時間。
數位簽章簽定時不知道對方怎麼簽，但能驗證是他簽的並且只有他簽得出來，文件訊息鑑別通常知道對方用什麼流程輸出一樣的數值。
| 類型\性質 | 加密類型 | 輸出訊息 | 碰撞情況 | 重複使用 |
|---|---|---|---|---|
| 文件訊息鑑別 | 普遍上對稱式 | 不管多長都固定長度 | 存在 | 相同輸入 - 相同輸出 |
| 數位簽章 | 非對稱式 | 視情況而定 | 視情況而定 | 相同輸入 - 可能不同輸出 |
現在學校活動也告一段落，即將要進入淡季，因此對於活動時數認證會變得更加麻煩。學校活動大多都是剩下營隊，當然也只有工作人員才能參與來替換時數，只能參與一半的半吊子可是無法融入進去的。於是被催著去參加校外活動來補這一個門檻問題。
來到中壢，基本上也就只有在校園、火車站及租房地點三角範圍內行動，對於其他地點一概不知，在中壢的學校有中原、元智以及我們中央，之前有被學長帶去中原夜市，若要自行出發還算個挑戰，曾考慮騎車去參加活動，但在前幾天去演練騎車過去時，卻不知不覺繞回學校，中壢的環狀分布、高架橋之路線讓我卻步，看來還是搭公車較為妥當。
去過中原夜市，卻沒進過中原大學，去過元智大學參加程式競賽，卻不知道怎麼自行前往。早上聽完一場演講後，趕緊搭公車轉兩次過去，在一個小時內就抵達中原，比預期中還來得順暢。在提早到達後，走在不同的校園觀望，看看不同地方的感覺，也許是股錯覺，由於騎腳踏車的人少，顯得人群非常的多，而且相較於中央更容易在路上見到女生，想到畢業學長回來學校的時候說一句「怎麼一眼望過去幾乎都男生」突然有點感觸，即使每三個人就有一個人女生，只比中原少一點，在戶外的大椅上不少學生坐在哪裡，顯得更加地活絡。也許只是太少出門，對中央不慎了解吧。
在講座開始前就明顯地感受到不同的風氣，開幕前來個留外的音樂表演，同時也請學校校長來說本校的希望不要拿通識的營養學分，正是舉辦這一系列全人教育講座的目的，講座規模不大，卻有不少校外人士和同學入場，相信仍有不少同學是來混時數的，包括我自己。
「人之何以為人：一個 20 萬年的故事」這演講標題不外乎就是在描述人類演化的過程，這 20 萬年間的不斷地挖考出來的化石，訴說人類的起源，為什麼要知道自己的起源與文明發展？能在人類文明習慣中了解不少疑惑，如為什麼總是成對科學人雜誌 - 「 演化路上夫妻同心 」、科學人雜誌 - 「 天天上網的靈長類 」 … 等。
不少相似的化石指出，智人與其他類似的族群之間的相似程度，雖然基因只有一點點不同，造就體能、合作、學習、腦容量 … 等都有所差異，為了度過險惡的環境，單純體能良好的人種消失，會合作延續文明的種族存活下來，靠的只是一點點變異。這讓我想到動畫《攻殼機動隊》對於文明的看法，人類之所以能成長到這一個地步都是靠一個 外部記憶體 - 文明，那我們真的是擁有自我嗎？還是順著文明的發展？但我想當人們不缺物質時，才能去想這些無關緊要的事情。
到底該不該去怪罪努力、後天學習？還是去怪罪刻印在 DNA 上的排序？曾經為了存活繁衍導致的基因，而基因養成習慣。從計算機科學的廣義算法中的基因算法可以裡也到，人類之間的基因變異不算少，這有沒有影響呢？就如電影《蠢蛋進化論》中的基因變化，不見得聰明靈敏，只要適合生存即可。很多行為是沒有道理的，有些演化也是沒有道理的，在用現代的眼光去看待過去的演化價值時，本身就是件很奇怪的事情。
回過頭來看看講者提到的科學人雜誌，人耐不住寂寞也是因為曾經有段長久的日子需要彼此扶持，度過那段艱辛的冰河時期。現今環境還算充裕下，人可以不見到其他人，藉由上網交流資訊，雖然這可以交流資訊，但卻難以得到實質的幫助。從現在觀點來看，人其實也很單純，藉由學習外部遺留的文明來成長，所以才看起來聰明，大家也都知道若沒有傳承，人類根本走不到今日。
中原講座的發問其實還挺有趣的，發問相當踴躍，原來在別校是這種情況，即使是一些課本上的內容、電視影集的科幻劇情都拿出來問，講者當然只能回答這不確定，至少不能斷言去否定。講者大部分的內容都可從國高中學的歷史中理解到，藉由後續學習的資訊也可以明白這些小道理，大部分都是在描述科學人雜誌上的資訊，有興趣可以去讀讀。
講者的描述有點囧，也許是狀態不好吧，可能尚未習得說話術，對於分享感覺是難以用文字去描述。儘管如此，藉由之前學到的文明與族群的通識課程，大概能猜到她想描述些什麼，就由我來說說吧！
首先，講者在大學混了四年不感興趣的專業，在四年存夠了錢，前往泰緬邊境的難民營中去當國際志工，泰緬邊境難民營是因為兩個民族之間的糾紛導致。國際志工是什麼？國際志工能做什麼？到底是誰需要誰？還是在別人艱困的環境下，只是想要藉由別人的艱困來充實富足自己的知識？
我對於國際志工不甚了解，但對於文明與文明之間的隔閡有點認識，很多人就會用體驗、參觀的方式去遊走各地，因為旅行是跳脫環境最簡單的方法！想要跳脫環境就去存個錢吧，去別的環境了解自己有多麼無知且高傲，看著別人過著自認為窮困的生活，不了解當地的文化，卻又想幫忙他們的窘境。
對於這件事情，我的看法如下，常說「人只能自救」，國際志工去幫忙不少只是「 偽善 」瞧不起別人的文化、可憐他們的處境，去了那裏，只能觀察別人的生活，有時還需要當地人照顧生活。去那兒 體驗 ，就跟別人來家裡 觀光 的感覺一樣，尤其是在戰亂複雜的關係下，志工除了送物質協助無關戰爭的人外，請思考有沒有可能把他們牽涉進去，因為提供給對方敵人協助，那志工算不算敵人？這要特別小心，當我們在台灣成長，沒有那種經驗是很正常的，懵懂無知的情況下，被用另外一種方式教導「 幫助別人 」是件好事，因此就把這套邏輯用到另一個國情上。
請跟沒有計畫性的幫助說再見！
之前在網路上看到一篇文章《本滿懷熱血的教山區孩童，學生竟對志工老師說：「叔叔阿姨，請你們不要再來我們這義教了…」 》link，開頭第一句「我們沾沾自喜著自己的偉大、奉獻。但是，我們到底為他們做了什麼？」正是描述志工的心境，也正是講者有提及到不少跟著一起去當志工的同學在那裏覺得自己的心很空虛，的確若沒有對自己夠了解時，突然用自己所謂的理解去理解別人時，回饋得到的那種失落感正是那股空虛。
學校教育是活在這個社會的學習過程，但不就是人類太多、過於群聚，相依彼此產生不少抽象式的職位，並非對物而是對人、對制度的職位，把偏鄉小孩帶來教育城市的生活技巧，對於他們能學到什麼實質內容？跟著大家一起進入城市搶那一鍋粥嗎？原始心中那股純樸到哪去了？講者描述到學校因為有一位長者去世而停課，學生們都跑去為那位長者送行，這是學校教育做到的嗎？還是生活教育體驗到的？
書本的內容可以協助他們理解這個世界，但並不是替他們指引出路的方法。教育這一舉動大多是為了未來生存技能存在，身為一個教育者是否又想過「教育是否又抹殺掉另外一種全然不同的世界觀」這是兩難的取捨，並不是往哪個目標走就是對的，而是要把這概念在教學的背後告訴學生吧。
講者描述上還有趣的，想必是出國體驗後的衝擊巨大，有些事情無法用言語來描述吧。
並不是所有講者都能闡述有多成功的一面，或者是自己體驗多麼豐富的內容，這場演講充分地從講者身上看出那種衝擊，說話言之有物、做事持之以恆，君子不多話、默默做事，人的一生充滿困惑，很多事實無法二分化、二值化，去累積吧！也許有一天就能化作一生最美妙的道理。
想到不久前高中教我資訊的啟蒙老師打電話回來，問我要不要回去去當資訊老師，如果要當老師，必須先修完 32 學分以上的教育學程才行，就以當前的狀況是沒辦法完成，因為牽涉到實習，延畢去完成也至少需要一年半的時間。
接到老師打電話來是還不錯的驚喜，在這可能延畢與困惑的季節上來說，來了點與眾不同的聲響，雖然學校成績還算不錯，但要是當個老師可能還有點缺陷，之所以可能會延畢都是要求全人教育吧，不曉得到底要怎麼當一個普通的大學生呢。
現在還差許多參加活動的時數，這一場講座是教導 教師 為主，對於老師上課的好壞，其一專業知識，其二教學方法，針對如何說話、上台解說給學生聽是一門功夫，不外乎地從一般說話就能知道有些人上台說話不行，即使是枯燥乏味、或者是非常簡單的課程內容，如何在台上持續講一兩個小時？又要如何講得不讓學生覺得費力？
上台長篇大論一番，對於內容感到好奇的學生，講者用什麼語調影響不大，那對於其他學生肯定是很重要的，上台教學有如演戲歌唱，若不是這樣，大概就像是一個古老的自動播放機吧，如何把一句話說得長、不造成聽者的負擔。
此課程由台師大音樂系老師來講課，一開始活動就請各位老師用平常的方式來介紹自己的名字、職位、專業，「大家好，我叫XXX，目前是中央大學資工系學生」在這一群教師中，混有一個學生的自我介紹是很緊張的，輪到自己真想找個洞鑽。唯一沒想到這場活動也是互動式，就之前參與教師研習的打工，明白許多研習活動都是互動式的，馬上就會請老師設計課程之類的，這一點應該早點想到。
如果教師四肢受傷，那嗓音的影響力就非常大。上台說話就像演歌，那麼從說話技巧開始，從一般的生理性的平直對談、口技、口哨、喉音、泛音 … 等，看來要從合唱團開始練起，如何避免氣音、粗啞，練習圓滑發音，將音調拉高 …。把一句話盡量往上揚，讓整個說話具有和氣、輕鬆的對談，這會對聽者更為舒服，把講話方式弄得輕鬆，這樣也可以講得長，聲帶比較不會受傷。
在授課前二、三十分鐘前就要喝好足夠的水，並且在授課時是實地補充水分，若是在授課一半才進行補水，很容易造成聲帶受傷。對於一名教師，說話是生命，聽到不少老師都是靠喉糖 … 等方式作為後續應急的方案，看來授課真是場戰爭。這也讓我想到光是上台講個二、三十分鐘，喉嚨隔天就有點不行，也許只是平時沒有磨練說話的緣故。
此外還有特別談論到千萬要避免「滔滔不絕」一旦需要趕課，總是來個加快說話速度版本來授課，想必要好好演一齣戲都辦不到，在這裏看起來是沒有辦法解決的課題。
要講好一場課，先去卡拉 OK 練唱吧！
別像許多講者，久久碰一次麥克風，人轉、麥克風不轉的有趣情景就能少見。如果沒有麥克風要講一整天課是很累人的，但麥克風有時會沒電，在沒有麥克風的狀態，也必須練練如何把話傳得遠，藉由拉高音量，用較沉的方式比較合適，說話需要氣量、聲帶健康，講師建議少喝冰品刺激食道肺部，作為一個以說話的職業多喝溫水吧，為了講話的氣量多多運動吧。
問卷設計跟面試方法一樣，如何了解使用者的需求與能力，如何發問、如何誘導都是相當有趣的。對於每一種人格特質，在面對不同問題的問法時，作答的難易度是有影響的，這對面試官也是相當重要的課題，因此需要了解到問題設計的方法。
問卷通常會分成兩種
當不知道問題的答案分布，既不是好與壞兩者，那麼定量分析就不能作為評估，採用開放式作答的定性分析，讓使用者回答它們所理解的，通常開放式有一個缺點，會導致過於雜亂的回答，很難得到期望的答案。想必很多人在不理解 問題描述 就會答非所問。定量分析的面向去設計，會得不到意想不到的答案，兩種方法各有優缺。
按照上述的兩種情況分成 選項 跟 申論 兩種。申論題就不必說，留給使用者提出自己的看法，欄位設計就是文字欄位而非選項欄位。
特別介紹一下選項部分，通常會有 是 / 否 、 喜歡 / 不喜歡 ，再複雜一點就是 非常喜歡 - 喜歡 - 沒意見 - 不喜歡 - 非常不喜歡 。如果在量表中只有偶數選項，通常是不存在中立立場，希望每個應答者都給予一個立場去回答，反之在奇數選項中，給予中立立場的應答機會，通常會得到非常多的 沒意見 此時有效問卷的數量相對少。
面談通常會分成三種
通常第三者的非結構面談相當輕鬆，如果變化問題不特別刁難，面談者也會根據應答者的能力詢問相關問題。然而在結構化問題中，相當一板一眼，容易對應答者感到緊張，當問題卡住的時候，接下來的問題就會影響到應答者的狀態。半結構化則介於兩者之間。
特別小心主持人不應該讓面談者們 達到共識 ，而是讓他們分享所知。誤導或誘答的情況應該避免，否則有可能會造成馬拉松領先者帶著一群人走錯方向的感覺。感覺不少情況會設下陷阱去讓面談者誤答，在問題描述上不給予明確的規範，在算法問題上也常常會這樣，至於算不算誤答就不曉得，當一個人對問題的背景認知不同時，問題本身就不一樣，能不能 取悅 面試官呢？
回收問卷後，利用定性方式去得到的答案是最難分析，只能靠觀察去理解，對於定量方式去設計的，將要看採用的數學模型來決策，例如消頭去尾後得到的平均數、眾數、中位數 … 等。不管哪一種方案，要看應答者的文化習慣，是否會造成不願意表態，極端情況是否正常 … 等因素，適時地消去一些實驗數據進行統計。
問卷介面也要有所區別，通常會有數個相似領域的問題，整合在一起，並且給予一個問題大綱有助於對問題的理解，特別注意到問題設計時要確定題目是否能二極化。
最奇葩的要來了，針對認知風格進行問卷調查，針對先前設計的遊戲，不同認知風格對遊戲介面的觀感。，各組提出的問卷問題如下：
我們組所提出的七個問題如下
本課程教學極為詭異，應該請全班人一起填，總共才七組來卻只要求自己去找 課程班上 十個人來填問卷，互填對方設計的遊戲問卷難道這麼困難嗎？老師應該要直接請全班來填寫吧，用鼓勵的方式，居然在畢業前一周要大家填問卷，一星期統計好並且報告，明顯地大家都在忙畢業典禮的拍照，問卷也很晚統計回來。
當然十個人的樣本數只能自我安慰，下什麼結論都是不具有信用的，只好按照老師的調調亂扯一通。就算遊戲做得再差，問卷回饋不如預期的對答，也許按照自己的預測方式去報告就行，問卷感覺就是裝飾用的。自己的教授自己靠北？
分別對於兩個版本，非常非常少的實驗數據。
遊戲難度 Holist 認為難度簡單，對遊戲進行不算困難，對於 Serialist 比較有新事物認知上的起手問題。
在遊戲偏好上，大部份的 Holist 看到了整體的光影效果對此深感好奇，而 Serialist 不少指出遊戲說明上的困惑與扣除血量的細節。
在遊戲內介面上，Holist 對於道具切換、使用狀態有強烈的要求，太過簡潔的界面是介意的地方，而在 Serialist 對於顏色要求較為強烈，對於簡介的介面設計滿意。
在遊戲介面動畫上，Holist 比較偏向回答遊戲內部的元素動畫，而 Serislist 則比較在意流血效果和字體閱讀。在這一部分的回答可以說是有點誤導，預期是想要讓他們回應遊戲介面動畫，而非遊戲內的元素動畫。
在遊戲目標上，一致都朝著遊戲通關目標為基準，而非劇情走向，估計是劇情走向對遊戲進行流程不影響，所以沒有必要去注意遊戲劇情內容。
在人工智慧 AI 上，Holist 比較偏向滿意，對有一些與現實邏輯不合的反應介意，對於 Serialist 對於 AI 的反應比較兩極，有好有壞。
對於預測遊戲進行上，Holist 比較想要的是局部性改變，例如效果與道具使用上、遊戲進行邏輯、新的功能利於闖關。而 Serialist 比較喜歡全局性的擴充，如新增關卡、不同類型的通過條件、關卡成就感、角色成長的需求。
請不要一堂課的結尾就喊出成績來決定一個學生的價值，若要從認知風格中挑選一種分類，老師的認知風格屬於一種衝動型，部分是需要不斷反思來接受新的資訊。不強求這門課的走向，但從做遊戲方面，可說是此次教學的創舉，既然要我們寫程式，麻煩就以資工系的方式引導，時間跟計劃不是一兩個星期前講就了事，牽涉到設計與構思，不給一個明確的方向，導致各組面向不同種遊戲，類型不同的遊戲設計出來就不能隨意說好與壞，若是要符合你們口味的網路學習，那直接說做益智遊戲即可，有些探討問題也因遊戲類型扯不上關係。
若要用小組程式作業、設計作為不上課的理由實在說不過去，導致這一學期很多次沒上課，起碼可以一個小時上課，後兩個小時討論的方式。而在論文上台報告卻有報告老師的同一篇論文，導致報告內容重複且冗長。上課投影片請不要用講稿模式 (兩攔筆記式，另一半的筆記欄位不知道給誰看的)，可以請助教弄全螢幕的投影片。
給一個序列，支持插入元素、刪除元素、反轉區間、區間極值、區間總和、區間修改以及最重要的 版本回溯 。
題目輸入會拿上一個答案進行 XOR 的加密，
|
|
decrypt input
|
|
|
|
持久化 treap，區間反轉，區間最大值，區間最小值，區間總和，插入元素，刪除元素，操作回溯。
這坑爹的題目描述擺明就是拖人下水，只好含淚地寫下去。持久化類型的題目應該是告一段落，就差一個 LCP + HASH 的維護了吧。麻煩的地方在於持久化的懶操作標記傳遞時都要新增加一個節點，這項舉動導致記憶體量非常多，1 秒處理的資訊吃掉 512 MB。二分記憶體上限，終於找到內存池的最多元素個數，中間不小心把多項資訊的 int 型態宣告成 long long，導致內存池一直不夠大。
如果不考慮回溯操作，速度上沒有比暴力算法來得快上很多，treap 基於隨機數的調整，而且每一次修改元素都要增加很多記憶體來補，導致速度上無法領先太多。但如果用暴力法，會造成版本回溯問題，空間會到 $O(
n^2)$，不允許的狀態，持久化造就的平均空間使用 $O(Q log N \times sizeof(Node))$，看起來仍然是很巨大的。
|
|
暴力法驗證用，不支持加密的輸入運行，用一個 vector 完成。
|
|
小測資檢驗用
|
|
由於在選讀論文時，和上課都遇到相關問題，但一直對這 SVD 的實際感觸沒很深，了解數學計算，卻不知道特性一直很困惑我。在這裡收集一下曾經學過的內容，當初在線性代數時沒有學到這一塊，至於 $LU$ 分解有沒有上到過，我自己也深感困惑，不過看一下網路資源勉強還能理解。
至於 SVD 則在線性代數非常重要，在許多領域時常會遇到，如巨量資料 (massive data)？機器學習？影像處理？就我所知理解看看吧！
定義從一般式
$$ A_{m, n} = U_{m, m} \Sigma_{m, r} V_{n, r}^T$$得到縮減過後的相似矩陣
$$ A_{m, n} \cong U_{m, r} \Sigma_{r, r} V_{n, r}^T$$給定 $A$ 矩陣，要變成三個矩陣相乘，可以壓縮儲存空間，一般來說都是拿來得到近似的 $A$ 矩陣，藉由刪除過小的 eigenvalue 來完成，eigenvalue 就是所謂的矩陣特徵值。
在學線性代數時，沒有仔細想過 eigenvalue 的意義所在，每一個 eigenvalue 也會對應一個 eigenvector，這些 eigenvalue 大小對應的分佈的相關性大小，而 eigenvector 則表示新的轉換軸的方向。類似最小平方法得到的結果。
但在巨量資料課程中我們可以知道一件事情，若是稀疏矩陣 $A$，經過 SVD 運作後，得到 $U, V$ 矩陣都是稠密的，因此空間儲存反而划不來，因此會有另外一種解法 CUR，可以上網搜尋 massive data mining coursera 在 這裏 可以知道關於 CUR 的資訊。
從課程中的例子來看，假設在電影評論系統中，則 A 矩陣表示電影對人的喜好度，則 SVD 相當於如下描述 (假想，單純的矩陣概念)
也就是說有一些電影屬性不是很重要，可以移除掉，這樣的表示法得到一個近似的矩陣 $A$。
在巨量資料中一個有趣的運用，可以用在購物推薦系統中，來達到預測相關性，跟某人對其他產品的喜好程度或者是需求性，但是在處理之前會遇到矩陣過大，但又非常稀疏，為了解決紀錄問題，就有奇奇怪怪的 Dimensionality Reduction 來完成，SVD 就是其中一種方法。
其他應用部分，將不重要的特徵值消除，來求得哪些元素是需要的，看到有一篇 文章 在做 PCA 主成份分析。
$$ \begin{align} & A_{m, n} V_{n, r} = U_{m, r} \Sigma_{r, r} V_{n, r}^T V_{n, r} \\ & \because V_{n, r}^T V_{n, r} = I \\ & \therefore A_{m, n} V_{n, r} = U_{m, r} \Sigma_{r, r} \\ \end{align}$$如此一來就可以知道要保留哪幾個主要資訊。
在虛擬實境論文中也是有這樣的處理，做的是 CT 建模，將模型的每個頂點，要計算 QEM (最小二次誤差) 的重要性，可以將其表示成一個矩陣，利用 SVD 方式得到，來決策要保留前 k 個重要性的節點，再將其他節點移除，來讓新得到節點盡可能地可以貼近真實模型。
之所以會這麼做，是要利用內插法來強迫得到邊緣偵測，但這樣會造成很多新頂點，為了要把過多頂點消除，使用 QEM 作為評價方法，利用 SVD 來完成大規模刪除的操作。
都明白 SVD 是一個很繁複的做法，有一個 $O(N^3)$ 的算法來求得所有 eigenvalue，若要用一般電腦跑，光是得到一個大矩陣所有 eigenvalue 複雜度相當高，其複雜程度沒有細讀過。有一種迭代的方法，類似馬可夫過程，每一次迭代可以逼近一個 eigenvalue，為了得到 n 個 eigenvalue，想必要迭代非常多次。運用 Map-Reduce 分散到很多台群落電腦加快矩陣乘法，這種方法的複雜度是可以期待的。
詳細操作 請參考
eigenvalue $\lambda$ 滿足
$$Av = \lambda v$$現在開始迭代 $v$ 讓其等式趨近於穩定
$$A x_{i} = \lambda x_{i+1}$$初始化 $x_{i} = (1, 1, ..., 1, 1)$ ，其中 $| x_{i}| = 1$ 藉由長度為 1 的向量，來求得 $\lambda$，之所以要對 $x$ 進行正規化，其一就是要求出 $\lambda$，另一個原因是要看何時穩定，當 $| x_{i} - x_{i+1}|$ 差距夠小時，則表示進入穩定狀態。
那就可以得到矩陣 $A$ 的其中一個 eigenvalue，為了求得另外一組解，得到新的 $A^* = A - \lambda x x^T$，再對 $A^*$ 找到 eigenvalue，不斷地迭代下去。
在這個畢業季節，考量著那做不到服務小時的畢業門檻，近乎危急之下，學校邀請 閱讀 社群創辦人來講這個社群的心路歷程與目標，被家裡人催著參加活動，剛好參加了這個講座。
在進入這場講座之前，用很久的 Facebook 都不曉得有『閱讀』社群的存在，活動標榜 「百萬人都愛上的華人最大臉書閱讀社群」的確有朋友也喜歡這個粉絲頁，從未見過演算法會讓我知道這個訊息，稍微看了一下內容，也許就跟長輩們常常分享的心靈雞湯差不多吧？既然參加活動，事前準備按個讚也不為過，但一個星期中也從來都沒見過相關訊息跳出來。
好吧！參加活動就能開始理解到底是賣什麼。
在這炙熱的畢業季，走到學校後門的白色貨櫃屋，比起以往只從租屋處到學校的田中小徑，這一天走了一條不尋常的道路，不習慣的環境，停個車也擔憂打擾到其他住在附近的人。曾經聽同學說這是個茶鋪，對我來說是高檔了點，只要有網路電腦的地方，在哪都無所謂，這種高檔店一年去的次數一隻手就能數出來。
吱吱悟悟走向協辦單位拿取資料填寫、簽名報到，很久沒聽到認識人以外的聲音，聽不懂活動人員給予我的下一個指令是什麼，傻里傻氣地按照當初在網路上看的活動訊息行事，心想找知道就找個朋友跟我一起來，但又想到朋友常回應的那一句話「我時數滿了，為什麼要去？」看來是沒望了。
也許在別人眼中舉止是多麼笨拙，選擇一杯飲料作為低銷入場、再找個位子坐下，久違的一步，對我來說可是比寫代碼還辛苦。為了防止看起來突兀，盡可能地選擇一個可以躲藏的位子，所思又想「到底哪個位子才適合我，這一切好困難」在這小茶鋪，擺著如電視劇一樣的一堆小椅子、小投影幕及少數的桌子，既不是可以躲藏自我的專業講廳，也不是階梯式的椅子擺放，彼此跟彼此之間的距離少了點隔閡，心中的畏懼又增添一層。
活動一開始，從主持人 鄭俊德 口中開始道出自己的經驗、家庭背景，與其款款地道出自己有多成功、怎麼成功的，那些不具有說服別人跟著一起做的舉動，介紹自己的一些小事開始，來龍去脈講的是自己怎麼從家庭圈圈中跳出來，又說著自己如何從學歷下走出自己。
中間有個小插曲活動「 如何說出自己的故事？ 」先別急著講長篇大論，能不能用一分鐘介紹給旁邊的人認識，現在的我們越來越少用文字對談，資訊相當多導致大部分的時間都在聽別人怎麼做，如何說給別人聽變得相當困難。
要我們介紹自己給自己旁邊的人，「等等，我身旁坐得是 … ？」此時心中不斷地迴盪，既然都走出門總得再跨一步『我是 …』我想已經在別人眼中死了吧，自覺說出來會被當作活在平行世界似的。跟妹子聊天什麼的，不是奇蹟可以形容的，但想到自身的負面情緒會影響他人，說話又更加的怯步。
「我叫翔雲，資工系，來這邊的機緣只是單純畢業門檻，平常是個碼農。中興轉學來到這裡，在別人眼中只是離家鄉花蓮更近一點 …」
話語就此打斷，對方是個法文系女生，跟我仇視的 英文 有點血緣關係，大一生不刷 Facebook，覺得在上面會消耗時間太多，大一生活多采多姿又忙碌，這一點我是很清楚的，曾經也過著自以為忙碌的代碼生活。原來她來這裡的原因是因為主持人是位 專欄作家 ，看來是一位社會中現實真正的生活者，看著雜誌、與朋友交談、或者在圖書館中靜靜讀書度過一日的生活的吧，在我心中假想的形象不斷地浮現。不知道能不能說個一分鐘，更多情況無法進行即時的對談，想說的話很多，很想讓別人記住我，但又怕這一段成為 黑歷史 ，躊躇之際又選擇放棄說話。
主持人講到，對於父母給予的環境到底要怎麼跨出圈圈，圈圈中的 熱情、專業、經濟 如何永恆運作？在圈圈中發現世界，還是在圈圈中活在自我 (用他的弟弟來講例子，弟弟好像被出賣了！)，如何將圈圈放大？理解的越多，圈圈越大就會越複雜。用熱情推向專業再來獲得金錢，空有熱情造就不出專業，將自己的熱情變成專業，但更多的是沒有熱情，先用專業帶來的經濟，將獲得的金錢培養出熱情，再利用熱情跳到另一個新的圈圈。
從某些人身上的確發現這一點，不少人在大學習得專業卻沒有熱情，偶爾會罵著他們「到底是不是來學習，還是來玩的？」在知道自己讀的專業也不過是生活的一小塊時，那種想法也隨之消去，在大學累積人脈才是重要的，學業只要維持在最低限度之上就好。
一個問題被創造出來通常是有解法的，即便那解法不夠快速，講者一講到這個部分，身為計算機專業可說是反對再三，有些問題連解法都沒有，這裡的沒有可以說是人一生的時間也算不出答案的問題。這裡笑笑就好，畢竟現實生活中這種問題鮮少。
既然自己無法解決，肯定要問問朋友，朋友也可以問問朋友，相互幫忙是不錯的選擇。「 世界那麼大，理解得卻很少。 」腦袋記憶的時間有限，學習專研也是有所限制，什麼都要理解是不可能的。既然現在流行分散式系統架構，單機運作什麼的，隨著學習曲線不斷地陡增，越來越明白這困境。「 教練，我想會一個交朋友的技能啊！ 」
關於 習得性無助 可以參考維基百科。
講者用實際實驗的例子告訴我們，實驗中把一條狗 彼得 關進一個地板接有電擊房間中，當狗尋找躲避電擊的方法，若發生找不到解決方案，彼得會進入放棄狀態，直接接受地板上的電擊，毫無抵抗地趴下。
接著把彼得帶到另一個房間與其他兩隻狗放在一起，這個房間與剛才只差了一點，跨過某一個衡桿後，另一邊是沒有電擊的，另外兩隻狗開始掙扎逃脫，其中一隻狗恰好跨過衡桿躲避電擊，另一隻狗也就跟著那隻狗一起在衡桿的另一側，特別的是彼得 選擇放棄 ，仍然在電擊區承受電擊，這就是所謂的 習得性無助 。
講者描述到很多人接觸數學是多麼地恐懼，也許我面對的是對 英文的恐懼 ，因為聽不懂發音，好像也沒有努力的必要，於是我選擇放棄，一般人認為理所當然的事情，做不到那不是更容易放棄嗎？其實一開始英文成績都還算不錯，國中基測還是英文滿分，隨著聽力成績的壓迫，近乎猜測期望值的分數，讓我越來越不行。
於是我走向另一邊，每天窩著打程序爬到現在，解題數上千、文章篇數上千、累積點閱次數一百多萬。現在的我相當無助，畢不了業，英文不好甚至沒有工作、未來，即便從他人口中道出「Morris 很強」，對我來說不具有一絲的鼓勵，更明白前面有更多無法理解的內容， 世界都用英文封藏起來 。
這社群有一點很有趣，關於文章分享的部分，提供不只有大眾愛看的內容，原以為只是喜愛讚數的社群，對於負面情緒的文章從來不在意，講者口中道出「 用正向文章鼓勵負面情緒的人們是辦不到的 」因此他們仍然會放一些讚數不高的文章，不總是討好大眾愛看的內容，比起以往粉絲頁的經營方式這一點令我相當訝異。
這一點我很喜歡，也許正是處於負面那一群的人們。
甚至會因為有人看了那些正面文章，向他們哭訴要 自殺 了呢，要是我頂多到憎恨的地步罷了，「你們口口說聲簡單、正向的事物，這些我都沒有，是不是該結束人生呢？」被這樣的話語絆住雙腳。
講者描述「他們想要自殺，目標不是結束生命，而是解決問題」聽到 解決問題 四個字耳目一亮，在平常用程序解決算法問題正是解決問題，對於解決問題的熱情，自殺真是不錯的方法，時間複雜度低、速度快速、實作方法簡單，不外乎是這世界快好的 $O(1)$ 作法。
