20101230

生日快樂！

今天早上算了離散題庫班講義第一本的一半
進度停在中國餘數定理

心情真的很複雜...
中午前後又心浮氣躁的坐立難安
本想去睡個覺
後來乾脆把接下來要做的考古題整理出來
算是花了不少時間...
但是心情總算平靜下來了

計畫複習DS
可是這科雖然是我之前考最好的
但是卻是我最不知道怎麼準備的一科
之前是因為演算法的部份寫的還OK
不過資結的部分還是會碰到基本題寫的很抖的情況
寫了幾題分類題庫
但是DS分類題庫錯誤率實在過高
加上題目怎麼做都不是資工所的= =

所以跑去PTT看了一些前輩經驗分享
有人提到DS這科不仿提早做考古題！
所以我就直接印了88年NCTU的考題來做XD
寫的時間不多...
可是花在翻書找答案的時間卻是好幾倍作答時間！

不過也因為這樣
我剛剛鼓起勇氣的開始網NP問題邁進！
非常大的突破
因為這部份一直是我所認為的天書
也沒有勇氣去面對的一個章節
趁睡前來默寫一下好了XD

P：P集合內所包含的每一個問題均可以在多項式時間的複雜度被解決。
      即：均存在一個O(n^k)的演算法可以解決
NP：集合內所包含的每一個問題是可以在多項式時間的複雜度內被驗證(Verifiable)
         此類問題再給定一個"可能的解"情況下
         可以在多項式時間內驗證是否為"真正的解"



NP-Complete：

20101229

哈哈
今晚很神奇的接到的強生的電話
更神奇的是這段強生老師開講
又讓我聽到了另一種思維
雖然有些部分我還是無法認同
不過倒是那個人生衝刺的公式很值得思考
G=(K+S)^A
那個A算是我目前僅有的優勢
但是K+S則是我最欠缺的
也是強生老師認為我"錯"的地方
要有更高的G是要靠A來做加乘
但是要有驚人的加乘卻還是要回歸基本面
K+S要往上提升

關於我錯的地方我也認同
畢竟這是分手的點
加油！剩沒幾天了！

今天開始了DS的second round
目標將提庫班講義做完
離散的部份也開始的97年度第一本

廢話不多說了
衝衝衝
多念一點
榜單上一定有我！

20101228

今天過完就是M49了

線性代數終於結束了
可以開始狂作之前題庫班的講義了

計組的memory也結束了
快點把後面IO的觀念念完
就要排課了
大約14堂左右
至少要到台中十趟
交通時間還真是不小的浪費呀

今天最大的收穫
就是弄懂了householder&&householder like的題型
藉由householder like幾合意義
再延伸至無幾何意義之householder like題型
這可是NTU近兩年的大熱門呀

整合了兩大特殊矩陣
關於求eigencalue、determine的方法

剛剛練球的時候
穿了桌球鞋
也做了適度的暖身
昨晚不只沒熱身還穿了DIESEL的休閒鞋打球= =
害我膝蓋怪怪的
舊傷似乎又復發了

不過今天唸書精神卻不是很好
真的很奇怪...
為什麼昨晚又夢到關於你的事情
三點多、五點多各嚇醒一次
其中一次就讓我睡不著了
因為我夢到你交新對象了..

為什麼會這樣呢= =
明明就一直告訴自己不要再去想
因為不管怎麼樣
真的就是結束了
也沒必要難過了

因為我確實一直很用心的付出
甚至我可以很自豪的講
再看了一段時間PTT的B&G版
裡面不論是進行式或是過去式的文章
我自己為戀愛所花費的心思
跟人家甜蜜蜜的經驗比較起來
我可是一點都不吝嗇在感情上的付出

也是因為我確實用心過了
卻依舊無法一直走下去
這就不是我值得懊惱的了
但是我確實非常後悔我為了這個人如此用心...
而且時間還不短...


PS：
今晚和俊傑都通了電話
恭喜他要升上士了
他確實是少見的善良志願役呀
但是阿湯的電話就沒接到了
真是有點不好意思

聖誕節祝福的簡訊我也都沒有回
小熊、阿湯、力王
記錄一下有空要賠罪一下XD

20101227

天阿！
又到睡前的時刻了
今天花了太多時間在二項式求極值中的Reyleigh Principle
雖然小黃一直說第八章不用念的太強XD

定義在Hermitian Matrix所以eigenvalue皆為實數
所以可以排大小
Rayleigh Quotient
分子擺二項式
分母擺長度的平方

最大值就是利用主軸定理所假設出的矩陣所求出的最大eigenvalue
同理最小的就是最小eigenvalue

有一個要注意的地方：
Rayleigh Quotient中的x假若取的是eigenvector
則Rayleigh Quotient就會是eigenvalue

其中：此eigenvector必須要做單位化！！！

由於利用主軸定理所令出的Matrix幾乎都很接近對角矩陣
只差在對角項不一定而已
所以要求這種矩陣的eigenvalue變的非常困難
列運算很久也不一定可以找到一個零行或零列可以降階
就是因為這個原因讓我今天花如此大量時間的主因
後來我發現搞不好直接硬幹3*3矩陣會比較快XD
反正了不起就是3*3而已...

另外有一道題要消除cross term(95中正)
因為我的eigenvector擺的順序跟小黃不一樣
我花了非常多的時間在驗算是否兩者相同= =

其中還有一個小小關鍵點也是要注意的：
Rayleigh Quotient的分母假若=1時該怎麼辦@@
也就是Rayleigh Quotient只有分子的情況(只有二次式)
這時候必須將(X^H)AX的範圍縮小至單位圓(球)
才可以直接由最小eigenvalue求最小值

關於矩陣的長度：norm
有四個要記住的
F norm：(A^T)A的trace開根號、或由矩陣內的各element平方相加之後開根號
1 norm：由每行的元素取絕對值相加找最大的那行。(注意：不是相加取絕對值)
無限 norm：由每列的元素取絕對值相加找最大的那行。(注意：不是相加取絕對值)
2 norm：因為A(A^H)必為正半定得知eigenvalue>=0的實數，所以可以比大小找MAX
               作法：求出A(A^H)之eigenvalue再開根號即為所求

condition number：在可逆矩陣的情況下
定義：條件數：||A||*||A^-1||。看題目要求是何種norm

問題來了
假若求的是2-norm
難道要球兩次的eigenvalue外加一次inverse！
天啊！這麼浩大的工程！
解法：
因為A為可逆只能保證eigenvalue不為0
但是不保證為實數
所以無法比較大小
這時候就直接求(A^T)A的eigenvalue並由小排到大
//(A^T)A：同理，因為正半定，所以eigenvalue為實數所以可以排大小
再由最大( eigenvalue / 最小eigenvalue )開根號即為所求



剛剛洗澡前花了大概30分中練球
並且搭配腳步
哈哈
希望趁這段時間唸書搭配適量運動(練球)
桌球球技可以在提升~
不過才拉了大概30分鐘
心臟就快要跳出來的感覺= =
又讓我想起了大四時有位醫生所講的一句話
"會引發心臟衰竭"

呼呼~真恐怖！

20101226

聖誕節過去了
依舊是個唸書日

下午跟VIC約在豐原碰面
趁他等火車的一個多小時的空檔
在MOS聊了一下
哈哈
之前都沒注意過
原來VIC有娃娃臉= =
怎麼看起來還像一個小朋友
怎麼都沒辦法聯想他已經在郭董旗下賣肝了XD

今天主要還是在念計組的memory部分
雖然有在念書
不過心服氣燥的唸的進度實在有點少
也有一部分是在仔細算書上的題目

但是有一部分我實在覺得很奇怪
當使用multileve cache時
L1的data cache通常都使用direct-mapped
目的在降低hit time來縮短clock cycle

但是同樣是cache概念的TLB(translation lookaside buffer)
TLB是page table的cache
為什麼它通常會使用fully-associative

是因為
1.TLB小，且fully-associative有較小的miss rate
   (有最小的page fault ratio所以是virtual memory之必要的選擇)
2.TLB小，且fully-associative有較低的成本
是這樣嗎@@

張凡下冊P225有兩段說明可是我看不懂= =
1.A page size is much larger than a cache line size, there is likely to very
   less spatial locality amongst the virtual address from a single process
   than between successive memory blocks.
2.Different process have their own virtual address space and hence to
   prevent a lot of conflict misses to ensure TLBs don't become a sourse
  of unfairness as far as a process's memory access is concerned.

＊ 當TLB發生miss時，需判斷是TLB miss 還是page fault

＊討論TLB、virtual memory、cache流程
cpu輸出的是virtual address 會分成virtual page number 和page offset兩部份
virtual page number + page table register(紀錄page table起始位置)
至TLB(data entry)查詢對應的physical address number，if exist ,then
此時physical address number + page offset即為phsical address(virtual和physical的page offset相同)
接著將phsical address分成tag、index、offset三部份
比對phsical address內的tag與cache內的tag是否相同，if yes，hit！


呼呼~流程默寫完畢XD
希望可以把觀念記著到考完試！
這樣在解題的時候也不會感覺都在背= =
就可以順順的寫囉~

20101225

Merry Christmas！

計組的MOMORY問題一定要全部守下來！

direct mapped

cache size (in bits)

2^n*(block size + tag size + valid size)

n：代表index的bit數目
      取決於(資料量大小) / (block內的字組數量)
block size：1word= 4byte，1byte=8bits。所以1word=32bits
      block內的字組數量*32
tag size：假設為32bit address
      32-index-(byte offset + block offset)
       其中：index就是n
                   byte offset = 2
                   block offset取決於block內的字組數量
valid size = 1

簡單的題目，觀念弄懂就一定要拿到分數！

剛剛請教了老李關於m-way search tree的觀念
有一部分是在探討最多與最少的node數與key數
我一直搞混的就是為什麼在最多的case中
key數=node數-1
原來key數是代表填滿時內部DATA數目最多的情況
並非我一直在搞笑認為的link數目= =
他媽的真的很蠢
花這麼多時間一直在想錯誤的東西...

20101224

Christmas Eve！

一個以前從未仔細思考過的重要考題！

一樣是線性代數
第五章對角化時：
P^-1AP=D
R(P)=CS(P)=A的eigenvector
D則擺A的相對應之eigenvalue

第八章正交對角化時：
題目可能會給一個矩陣A
求存在一個P為orthogonal
使得P^TAP= D
這邊與第五章不一樣的地方
同樣是求出矩陣A的eigenvalue即其對應之eigenvector
但是P有要求為orthogonal
代表要每個相異的eigenvector為垂直
加上由算子理論的hermitian matrix性質可知
既然是hermitian matrix
所求出之eigenvalue必為實數
且該對應之eigenvector必互相垂直
但是現在問題出在
假若出現eigenvalue的algebric multiplicity(代數重數)>1
所對應之eigenvector數量>1
這些eigenvector並未保證垂直
所以必須將同一個eigenvalue所對應之eigenvector
做Gram-Schmidt process使其垂直
這時候才可填入P矩陣中
但是還有一點要注意的是
因為題目要求P為orthogonal matrix
滿足column為orthonormal
所以必須將剛剛算出之eigenvector做單位化(除以本身長度)
則D矩陣同第五章
依序擺eigenvalue
完畢！

題外話
有時考題會直接給一個大型矩陣
要判斷是否可做對角化
小黃說：千萬不要沒判斷矩陣就開始硬幹！
硬要解eigenvalue並判斷代數重數是否等於幾何重數

判斷是否為實數對稱矩陣(real symmetric matrix)
如果符合此形式矩陣
必可正交對角化
所以也可以對角化
觀念題~四大送分題XD