神奇
今早起來收gmail，忽見新信是自己的老媽寄的
大驚!!!
---
讓我會心一笑了XD
星期五, 6月 08, 2007
星期四, 6月 07, 2007
Creative
今日又沒念書了，不過不甚可惜，我基礎英文重修很神奇的被assign到一個影片剪輯的事(我根本就不會XD)，硬著頭皮上，使用Windows Movie Maker工作，我再度體驗到M$軟體的難用，檔案移動性非常的低，從筆記型電腦移動至桌上型電腦，發現路徑使用的是絕對路徑，難以解決。
不過非常高興的是，遇到了一群富有創造力的人群，這正好是我所欠缺的，跟這群人合作是一個愉快的經驗，雖然我最後並沒有做什麼，好像只是做到非常簡單的技術支援還有把比較無聊的字幕插入一半，最主要的影片和配樂都是他們自己拍好提供，這個我做不到，蠻佩服的，富有創造力的一群。
我的專長是什麼呢？找到最好的技術？不，我負責創造這些技術，這也是我以後要走的路，呵
---
好廢話XD
星期二, 6月 05, 2007
星期一, 6月 04, 2007
質變
突然之前，發現自己有一個最大的質變了，以前是系上的活動不想參加...現在的我發現，我不屬於那喧鬧的世界，也就是說，不論是誰辦...我好像都不那麼在意，相對而言我可以打很久很久的籃球，念很久很久的書，這對我而言都很平靜
---
那份想玩的心遠我而去嘍，是件好事:)
星期日, 6月 03, 2007
星期二, 5月 29, 2007
pass1完成
SIC/XE assembler pass1大抵上完成了...該有的資訊都有了，接下來的pass2會比較輕鬆
有遺憾的是，未能善用STL，但是我打算一口氣做完，然後再把程式碼做最佳化，或許會是一個比較好的方法
---
三個小時XD
星期日, 5月 27, 2007
星期五, 5月 25, 2007
第二張專輯
很少有專輯在預購前就可以讓我期待吧，雖然我手上仍未購入Linkin Park - What I've done，但是我得抽空講一下為什麼張懸的第二張專輯仍然讓我如此保有高期待度，因為我用emule所找到的歌遠超過她的第一張專輯，My Life Will，她以前在海洋音樂祭所組成的芒果跑時所唱的"並不"(因為這首歌不能參加金曲獎最佳新人獎)，她戲稱為兒歌的"氣球"，聽起來不是愛情但是卻很愛情的歌詞"無與倫比的美麗"，她寫給自己妹妹"親愛的"，還有相當讓我期待的"嫁媧進行式"(歌詞有一段是，嫁媧的藝術是其實誰不這樣呢)
還有那麼多讓人高期待度的歌，以我的見識度，想必還有我還沒聽過的歌，雖然不能首首都精彩，但是我想，這還是讓人有高期待度的
螢幕歸來
從上禮拜日我的 Benq FP71G+s 螢幕壞掉(開關部分的線路損壞)，電源按下去三秒內就熄滅了，上網查benq的網站，結果網站一起掛點(網站倒是隔天就好了XD)，利用google的庫存頁面找到電話通知之後，禮拜三方得收件(住宿不怎麼方便)，今天就回來了，非常快。
還好還有筆電可以用，不然這個禮拜就掛點了，不過深深感受到不方便處就是XD
---
維修處也是桃園龜山XD
星期日, 5月 20, 2007
預購
同志們，是時候衝一個了~
作者 sodaeric (我們都期望飛翔) 看板 Deserts
標題 [模樣] 新專輯的消息
時間 Fri May 18 22:41:17 2007
───────────────────────────────────────
剛剛看一下g-music的網站
裡面的最新專輯發行日期
2007/07/10 張懸 最新專輯 專輯 SONYBMG 日期暫訂，6/8開始官方預購
大家開始倒數吧!!!!!
預購預購預購~~~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.208.211
---
某人不預購我就鎖喉他...嘿嘿XD
星期三, 5月 16, 2007
星期二, 5月 15, 2007
星期一, 5月 14, 2007
星期日, 5月 13, 2007
星期六, 5月 12, 2007
星期四, 5月 10, 2007
七段顯示器
由於實驗需要，我寫了一個不怎強的加強版七段顯示器，A~F表示成 A b C d e F
還蠻好用的
LIBRARY ieee;
USE ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
ENTITY dis47 IS
PORT(in_d: in std_logic_vector(3 downto 0);
out_d: out std_logic_vector(0 to 6));
END dis47;
ARCHITECTURE beheavor OF dis47 IS
BEGIN
process(in_d)
begin
case in_d is
when "0000" => out_d <= "1111110";
when "0001" => out_d <= "0110000";
when "0010" => out_d <= "1101101";
when "0011" => out_d <= "1111001";
when "0100" => out_d <= "0110011";
when "0101" => out_d <= "1011011";
when "0110" => out_d <= "1011111";
when "0111" => out_d <= "1110010";
when "1000" => out_d <= "1111111";
when "1001" => out_d <= "1111011";
when "1010" => out_d <= "1110111";
when "1011" => out_d <= "0011111";
when "1100" => out_d <= "1001110";
when "1101" => out_d <= "0111101";
when "1110" => out_d <= "1101111";
when "1111" => out_d <= "1000111";
when others=> out_d <="0000000";
end case;
end process;
END beheavor;
星期三, 5月 09, 2007
65536 與 32
一個是2^16一個是2^5，就這樣，但是在一個很簡單的SRAM程式碼(實作非常非常簡單的記憶體)與MAX PLUS II卻有不同的結果
LIBRARY ieee;
USE ieee.std_logic_1164.all;
use ieee.std_logic_unsigned.all;
use ieee.std_logic_arith.all;
ENTITY SRAM IS
generic(S_size: integer:= 65536;
S_address: integer:= 16;
S_length: integer:= 16);
PORT(enable: in std_logic;
M_rw: in std_logic;
address: in std_logic_vector(S_address-1 downto 0);
in_data: in std_logic_vector(S_length-1 downto 0);
out_data: out std_logic_vector(S_length-1 downto 0));
END SRAM;
ARCHITECTURE beheavor OF SRAM IS
type memory_array is array(0 to S_size-1) of std_logic_vector(S_length-1 downto 0);
signal sram_unit: memory_array;
BEGIN
process(enable)
begin
if(enable = '1') then
if(M_rw = '1') then
out_data <= sram_unit(conv_integer(address));
else
sram_unit(conv_integer(address)) <= in_data;
end if;
end if;
end process;
END beheavor;
其中
generic(S_size: integer:= 65536;
S_address: integer:= 16;
S_length: integer:= 16);
這個在MAX PLUS II我放了將近兩個小時complier還是沒跑完，後來將S_size改成32，S_address改成5，才能夠有點lag的complie過。
---
實驗講義寫的2^16 * 16bit 是怎麼回事XD
星期二, 5月 08, 2007
掃描器
SCX 4200 漸漸發揮功用了，目前先以考古題掃完為主，再用Adobe Acrobat做合併動作，感覺甚為完美，只是檔案大了些，目前進度不錯。
雖然這學期自己寫的重點不多，但是整理老師的上課簡報，課程的一半，竟然高達170Mb，人類真偉大，大概一個學期可以燒一張光碟吧:)
---
難道這就是所謂的知識管理XDXD
星期一, 5月 07, 2007
星期日, 5月 06, 2007
專題
最近有老師開始詢問我專題，也有老師開始詢問我是否要當TA，當然，我很遺憾的是兩個我都得說對不起，我可能不能做。
專題還是得做的，自從我開始寫VHDL開始，我蠻熱情投入這塊領域的，跟著老師課學習真的很高興，別人說的Computer Organization and Design: The Hardware and Software Interface 3/e這本一開始我試著自己看完全看不懂，到現在隨意翻翻大概猜的出來在做什麼，也大概猜的到MIPS是一個架構，裡面以描述他為主，我雖然還沒看，但是我很希望我可以在暑假實作出一台簡單的MIPS(希望VHDL可以承受這樣子的複雜度，還沒看不知道，呵)，我也很高興我能學數學，在系上有好老師真的很高興(當然也不乏讓我提不起興趣的老師:) )
於是我開始問自己，我想要學什麼，以及我以後想要做什麼？我曾對別人講過，資工人強在Computer Organization, Operating System, Complier這條Computer Science督脈，並不是別的系說轉進來說插入就插入的。
Computer Science由Josh和我討論的結果(不如說是他傳述給我的XD)，一條是由Data Structure, Algorithm, high programming language 甚而到software enigeering 一條純理論路線(這脈的描述似乎有所欠缺)謂之Computer Science 之任脈，而督脈指的是由數位電路而上(電子學而上也行)，到Computer Organization & Aritchture 進而到Operating System 進而到Application Software，中間還穿插了Complier。而這兩脈各自獨立卻又緊緊交錯，形成了Computer Science這個學門(當然，把Computer 變成Computer Science，Knuth 的TAOCP是很重要很重要的關鍵)。
那麼我開始問我自己，我到底在這些年學了什麼東西，答案是我什麼都沒有學好，都有學過但是不夠紮實，為什麼我現在熱衷學習督脈這一條而專題不走這一條呢。
我不想放棄我學到一半的東西，我在programming這條路我已經快學到OOP了(當然，我希望可以的話我想學OOA, OOD)。
我在C++ programming這條路走的甚久，甚而可以追溯到我高中時代，我現在的想法很簡單，我連design patterns 都大概知道是什麼意思(離應用還差的遠)，為什麼我現在要半路放棄我學到這樣子的東西呢，我決定先學完，我要把這條路走到告一段落，但是我不否認這些東西的重要，所以我到暑假我要先把我認為的計組學到告一段落，大三繼續把這條我還沒走完的路走完。我書架上的書也是以programming，現在不消化完豈不太可惜，我想把這條路完成，我不想放棄。計組呢，我想留到研究所會再做進一步深入的，如果可以，我想為資訊基礎教育盡一份心力。如果我有那個能力念到博士，我想學兩條脈的交錯與整合，或許我的想法是錯的，我想我會努力下去。
研究所想去那...？我想去台大，這願望是蠻狂妄的，我不否認，但是我不認為不能實行，為什麼要去台大？ 台大對我而言並不是那麼具有吸引力，但是我覺得與Josh討論是個不錯的決定，Josh對我的吸引力可能比台大還大，他如果在那處我就去那處，就這樣子而己。
所以我的暑假計畫很簡單，照我自己列的書單與目標，每天在學校念書，一一擊破，開學繼續走向軟體這條路，計組聖經本也在我的範圍之內，至於具體計畫，我想我過一陣子才會想出來，或許不會，我的生活不是那麼具有計畫。
---
好像寫太長XD
積極
我不是一個很積極的人，尤其是我遇到我想都想不出來的問題時，但是我沒有想過放棄，因為問題還是在那裡。
這次我遇到的VHDL問題是我聞所未聞，見所未見，我真的一度問自己，是不是自己功力不足(這答案很肯定)，一度把自己的檔案重寫，重看，結構重來，後來聽從老師的建議，裝了怪獸級的軟體(Quartus II，web edition 要540mb)，找到問題，重新compile 終於看到不同的error messenge，看了之後，也發現到自己的問題，尚未解決，但是已燃燒重新快速解決問題的心
我學程式語言，好像一開始都是盡量靠自己亂學亂寫，等遇到真正的問題時，我會鎮定思痛重新好好看一本書(C++就是C++ Primer)，重新學那一套學理，但是很有用助於自己理性思考的好想法。
---
現在VHDL也是這個時候了
星期三, 5月 02, 2007
scx 4200
花了不小的一筆錢買了三星SCX 4200，最主要是看中整合雷射和掃描的功能，可以把自己的手寫筆記掃描起來，平常也可以掃一些只有紙張的資料，算是方便許多
不過別人看到看到我的掃描器是如這張圖的用途XD 我得承認，我沒啥美術細胞，這掃描器可能會哭一下XD
---
我朋友是高手耶~好厲害~
星期一, 4月 30, 2007
星期六, 4月 28, 2007
music 整理
過了很久很久以後到現在，我才發現，對吼，有youtube可以抓mv放個歌讓大家聽一下，單純貼歌詞似乎是一件還算無聊的事，所以我又更無聊做了如下整理，到現在都還記得第一次是因為生日，後來就因為單純的聽某首歌或是想介紹某位表演者而貼的，總而言之，都是個不錯的回憶，有時候相較之下，台灣的mv，如果不想做的話，就千萬不要拿演唱會的錄影來做mv，這會讓人覺得很沒誠意，我那時候滿心期待張懸的寶貝mv，結果...Orz
| 無狀態 | 張懸 | My life Will, 2005 | MV | 06/08/05 |
| Where'd you go | Fort Minor | The Rising Tied, 2006 | MV | 06/12/05 |
| 勇敢 | 王婧 | 我要的未來 | MV | 06/12/31 |
| 海洋音樂記 | 歐噴愛 | 純愛物語, 2006 | Film | 07/01/03 |
| 並不 | 張懸 | N/A | Film | 07/01/27 |
| What if | Lene Marlin | Lost In Moment, 2005 | MV | 07/02/01 |
| Sorry | Lene Marlin | Another Day, 2003 | MV | 07/02/03 |
| 表面的和平 | 陳綺貞 | 華麗的冒險, 2005 | MV | 07/02/06 |
| But I do love you | LeAnn Rimes | I need you, 2001 | MV | 07/02/14 |
| Free Loop | Daniel Powter | Daniel Powter, 2005 | MV | 07/03/03 |
| How would it be | Lene Marlin | Lost In Moment, 2005 | MV | 07/04/03 |
| 輕功 | 五月天 | 時光機, 2003 | MV | 07/04/16 |
| Breaking The Habit | Linkin Park | Meteora, 2003 | MV | 07/04/28 |
Linkin Park - Breaking The Habit
最近蠻喜歡聽Linkin Park - Meteora，我聽歌的方向似乎不怎麼多元的多元，我原本一直以為我不會喜歡那麼吵的音樂，後來漸漸的發現，似乎聽這種，吵不是他的元素，融入之後，發現，Listening to Meteora in dark feel quiet. 看到此首的MV，有一種墜落的感覺。
Breaking The Habit (Linkin Park, Meteora, 2003) MV
Memories concern
Like opening the wound
I'm picking me apart again
You all assume
I'm safer in my room
Unless I try to start again
I don't want to be the one
Who battles always choose
Cuz inside I realize
That I'm the one confused
I don't know what's worth fighting for
Or why I have to scream
I don't know why I instigate
And say what I don't mean
I don't know how I got this way
I know it's not alright
So I'm breaking the habit
I'm breaking the habit tonight
Cultured my cure
I tightly lock the door
I try to catch my breath again
I hurt much more
Than anytime before
I have no options left again
I dont want to be the one
Who battles always choose
Cuz inside I realize
That I'm the one confused
I don't know what's worth fighting for
Or why I have to scream
I don't know why I instigate
And say what I don't mean
I don't know how I got this way
I'll never be alright
So, I'm breaking the habit
I'm breaking the habit tonight
I'll paint it on the walls
Cuz I'm the one that falls
I'll never fight again
and this is how it ends
I don't know what's worth fighting for
Or why I have to scream
But now I have some clarity
to show you what I mean
I don't know how I got this way
I'll never be alright
So, I'm breaking the habit
I'm breaking the habit
Breaking the habit tonight
---
聽說五月份要發行新專輯
補充
感謝bluegmn提及南方公園的影片連結
在此
劇情大概就是，主角四個人呢很快樂的玩著魔獸，結果被一個人打爆了，blizzard開會時，說到，此人是真正的宅男(yen3註：聽到的英文是no life，我笑了XD)，接著這四個人就躲在森林裡練功，殺著一隻經驗值只有2的野豬？到最後靠著blizzard的工程師寫的千真之劍把宅男中的宅男做掉了，於是大家恢復正常的魔獸生活。
事實上裡面蠻多笑點的，整篇故事我覺得比起一般提醒大家不要玩魔獸的苦心規勸文來的有用，no matter 值得推薦
沒有照著裡面翻譯也是一個必要的事，South Park本身就是照著美國文化去發展的，如果直接翻譯，大概會少了很多笑點(因為並不是每個人都知道且融入美國文化)，所以翻譯時做本土化是必要的，no life 翻成沒有生活和宅男，我相信後者比較具有說服力，這個跟專業文章的翻譯又大異其趣了(在Computer的領域中，專有名詞應保持一致性，這很重要)
星期五, 4月 27, 2007
有關儲存媒體的兩三事
在很久很久以前，我和我室友一起使用VHDL做乘法器時(聽說最近好像要做一個非常Simple CPU XD)，做完，檔案竟然有7mb之多，存入隨身碟，這一切都是那麼的合理。朋友與我共用一個隨身碟，存完之後他說
我們的價值都在這小小的隨身碟裡了XD
這或許對於現代人都存在普遍的狀況，對於最常使用電腦的我更有很大的感觸，當然，今天我不講資料備份的重要性，我更不想屢次提醒，硬碟是電腦主要硬體中唯一的機械性媒體(如你所見，CPU, memory, motherboard, display card etc...上面的風扇去掉，都是電子性媒體)，更有太多人因為硬碟掛掉而痛哭一整夜XD
那麼我想從另外一個角度來看看儲存媒體(泛指HardDisk, FlashMemory, CD ...etc)，這會讓我想到兩個曾經在電視演過的故事，一個日劇"輪舞曲"(yen3註：呃，不是那麼喜歡)，裡面的美女駭客發明了一種可以入侵全日本銀行的program(yen3註：真神奇)，不過此程式還沒完成，日劇後面幾集就繞著存著program的隨身硬碟在走，女主角被綁去完成最後的程式，到最後，硬碟終於搶回來，由警察開槍把隨身硬碟掛掉。我看完這個故事存在一個感想...以現在硬碟的精密程度，只要不小心"啊，手滑"就可以破壞硬碟了，抑或是說拿著硬碟跳hithop，我相信也具有同樣效果，重點是，沒有那麼長的故事，沒有那麼帥的結束，這故事就演不下去了。
另外一個故事是，南方四賤客中，某一個人在網路上魔獸被打爆了，於是展開尋虛寶之旅，到最後找到一個小姐，他就要最強的武器，小姐不急不徐的把一個隨身碟給他，主角就說了"x，這就是那傳說中的寶物？"(這故事由別人轉述，所以我只能敘述較短)
上面兩個故事述說了知識的重要性，我想說的是，人類的知識價值以另外一個形式存在時，或許會變的脆弱不堪，存在的形式也會讓人莞爾一笑，不過這一切無損於知識價值，只要存在能夠改變世界，那我們就不應該在意那麼多
記得好好保護好你的知識XD
---
難得寫那麼輕鬆的文章
星期三, 4月 25, 2007
星期二, 4月 24, 2007
連續崩壞之後...
在連續崩壞之後，到底我們還剩下什麼？
可能一點不剩的流走，也可能是持續崩壞，生活，本來就如此簡單，不為任何複雜的目的存在，當看見這個世界時，進行著。
關係，簡化，信念，堅持，追求想要的，遠離喧鬧的世界，隱居，只是下一個開始
---
紀念gb014388生日
星期一, 4月 23, 2007
星期日, 4月 22, 2007
星期三, 4月 18, 2007
星期二, 4月 17, 2007
星期一, 4月 16, 2007
五月天
五月天一直是我在觀察的一個團體，等有空的時候來寫些東西吧
五月天 - 輕功
詞曲:阿信
最近 很需要愛情 讓我這一生混亂 能平靜
人在江湖 心不由己 這世界 又煩又黏膩
你在哪裡 你在哪裡 一雙鞋 踏破了天地
多想要 找到你 多想要 能飛簷走壁
找到你 擁抱你 恨自己 不能飛(到)天上去
多想要 找到你 多想要 地心沒引力
找到你 擁抱你 再一步 愛恨都在我腳底
常常 打你的手機 常常 像打到火星 沒回應
雖然科技 始於人性 可是我 要真實的你
摸到了雲 離開了地 長出了 蚱蜢的後勁
慘痛
現在的我認為照我的學習能力，只要能搞懂理論，實作再克服一些問題即可，於是我拋下很多實作的時間拿去學理論，事實證明我錯了
在大二下接二連三的實作，真的給我慘痛的感覺，道理都懂，但是在實作不約而同的出現小問題，所以我想說的是，我對這些東西還是不夠了解，這讓我覺得，原來我也才不過這樣子而己。
人有時會看不到自己的盲點，但是更可貴的是要看到自己的慘痛，這會讓人心情不好，不過應該要努力的克服，實踐。
---
今天沒去台大上課覺得很可惜，都是很有趣的東西
星期六, 4月 14, 2007
乘法器
早起開始用VHDL寫乘法器，成效不錯，只剩兩個compoment，也可稱之為subprogram(共8個compoment)，寫完之後就是把compoment連起來，故事就結束了
---
事實上乘法器也不難寫XD
星期二, 4月 10, 2007
星期日, 4月 08, 2007
星期六, 4月 07, 2007
最近
生活平順的跟鬼一樣，或許就是那麼平順，才覺得這是一個很好的生活吧，每天自由的念書，自由聊天，自由睡覺，自由翹課(這是不好的行為XD)
念書是越來越順了，在此感謝兩位女性朋友，一位為了我在班上的評語而生氣，一位跟我說，你人真的很好，不要理他們說的這些話，老實說，當我自己看到的時候我是置之一笑的，但是我為了這些人而感謝，不過有時候會陷入一種想法，什麼意見是自我該接受的，而什麼是該置之一笑的，如果全盤不接受只聽好話，這就很像綠色只看自由時報是一樣的有趣。
不過目前的我只想做好一件事，把我該學的學好...相信知道我的人都是那個字，有人說blog的Computer 味變的非常重...呃，可能最近無意在blog上搞笑吧，就盡量啦，連寫個孫燕姿都會寫成評論文...回憶成評論啊，我是不是對生活太過於認真了些?或許吧XD
在此提醒Josh，快去買張懸吧，呵，難得他會有肯聽的中文歌手(Josh如此要求，我看中文他肯聽的真的很少XD)，雖然他稱張懸是"基本教義派"的歌手(這聽起來像某激進教派，還好張懸唱歌不怎麼激進XD) 這算是一件令人高興的事，有時候也會想起常常傳歌給他的情形XD
---
雜記XD
星期五, 4月 06, 2007
TeX4PPT
TeX4PPT 是一個讓Microsoft PowerPoint 可以順利show出數學方程式的一個轉換軟體，只要寫出TeX code就可以在文字方塊中按右鍵的"TeXify"即可順利轉換，是一個相當方便的工具，但是需裝LaTeX的complier為前置轉換，官方說明中，MikTeX為佳
前置軟體(只要是LaTeX即可)
MikTex 2.5 (2.6 beta試過，不能用)
TeX4PPT
官方網站
資料結構與演算法(下)06 by 隨機客
非正題：這一次是有史以來上課最緊張的一天(雖然課程內容不怎麼緊張)，Josh 身體不適，嗯，有點緊張，但上課越來越進入狀況，只是對沒學過圖論的我還是一個很大的問題，早上六點起來騎車也是一個不錯的經驗，只是一直下雨XD
2007/04/02 資料結構與演算法(下) 06 呂學一 投影片
今天的主題為算出all-pairs shorest paths tree(yen3註：相當於把Graph上所有的node都建shortest path tree)，而今日的主題有三，Naïve algorithms和改善其效率的dynamic programming和Reweighting(yen3註：若能把edge weight 都變正，則可用Dijkstra's Algorithm)。在進入正題之前，先討論。
- The setting
對於問題的setting仍與上禮拜相同，有一Graph G=(V, E)，而每個edge有weight，而edge weight允許為negative
- The Problem
- Input: Edge weight matrix w, where w(i, j) stands for the length of edge (i, j).
- Output:The distance matrix d, where d(i, j) stands for the length of a shortest path from node i to node j.
今天的問題仍然在討論shortest path trees和distance是否等價- 從all-pair shortest path tree求得distance table
這相當的直覺，有n個node，而每一次皆跑n-1個node，總次數為n*(n-1)，所以為O(N^2) - 從distance table 算出 all-pair shotest path trees
這看起來不怎麼直覺，但是就上禮拜的從distance找回shortest path tree的方法，是一樣的若是shortest distance呢？從r到v的點，我們從v點找起，把指向v點的edge weight掃描一次，若剛好等於，則是shortest path 的一個解，若小於此weight，則扣掉該重量，進行recursion，由於只有m個邊，我們可以保證在linear time 找到
而每個row至多把所有edge走完為m次，而有n個node，所以為O(nm)(yen3註：懶的寫XD)
所以今天重點仍舊是在shortest distance上
- Naïve algorithm - all-pairs distance
根據上禮拜所教的演算法(Bellman-Ford, Lawler, Dijkstra)，Naïve algorithm - general edge weight上(可以有negative edge, negative cycle)，方法如下。
- 先Run Bellman-Ford 確定G中有沒有negative cycle，如果有negative cycle則停止，可在O(mn)時間內完成(yen3註：怪怪的，因為只跑一次真的能保證能找到negative cycle?)
- for each node in Graph G Run Bellman-Ford Algorithm，每一個點都是O(mn)，所以Time complexity 為 O(mn^2)，最多是任意兩點都有edge，則為C(n,2)*O(mn^2) 則worest case 為O(mn^4)
若確定為each edge weight is nonegative edge weight則可使用Dijkstra Algorithm，for each node in Graph G run Dijkstra Algorithm，由於是nonegative edge weight，所以不用擔心negative cycle，每一個node為O(m+n^2)，所以為O(mn+n^3)，而使用Fibonacci heap的話，Time complexity 為O(mn+ n^2 log n) - Dynamic Programming
(JK註：以下的DP皆建立在Graph無negative cycle 上)(一種聰明的填表法，想辦法讓走過的都留下痕跡，recursive definition很重要)，首先，建立一個matrix w(i,j)，而w_k(i,j)指的是所有i to j 的path中，所使用的edges <= k中，挑選min edge weight sum為其value，定義如下
- w_1(i, j) = w(i,j)
- w_{n-1}(i, j) = d(i, j)
而Recurrence Relation為- w_1 = w(i,j)
- w_{2k}(i, j)= \min_{1<=t<=n}(w_k(i,t)+w_k(t,j))
算出一個的(i,j)為O(n^2)*O(n)，而我們可用O(log n) 求完所有的點，所以總花費時間為O(n^3 log n) - Dynamic Programming - Floyd-Warshall algorithm
定義一個matrix, 而d_k(i,j)的定義為，把每個node編號，而從i到j的中繼點編號不能超過k，所以對於每個d_k(i,j)我們都有如下定義- d_0(i,j) = w(i,j) (it's clear)
- d_n(i,j) = d(i,j) (d_n 是所有的點都可以經過或不經過，所以path distance就是shortest path)
而它的 Recurrence Relation如下- d_0(i,j) = w(i,j)
- d_{k+1}(i,j) = min{d_k(i,j), d_k(i,k+1) + d_k(k+1, j)} (把整個路徑分成i to k, k+1 to j而分別求)(yen3註：寫到這邊有一點後繼無力的感覺XD)
- Reweighting
用意是把有negative weight edge 變成正的，如此一來可使用Dijkstra's Algorithm 做一個speeding up的動作。但是方法不是直接對每一個edge weight 加上一個constant value，這樣子會造成shortest path 改變(例如說，本來繞了很多圈在經過negative weight edge，可能因為加了一個constant value而造成不經過。)，在此，Johnson提出了一個方法- Assign a weight h(i) to each node i in G.(給每個node一個weight)
- for any path P from node i to node j, we have
\hat{w}(P) = w(P) + h(i) - h(j)
(New edge weight = old edge weight + 起點的 node weight – 終點的 node weight)(前一個edge 的 end node weight會和下一start node weight做抵消動作，故不影響shortest path，而知道shortest path 之後，利用原圖G，即可在O(n^2)求出原圖的distance) - 此方法成立嗎？假設戴帽子的P為最短的，而沒有戴帽子P卻不是最短的，那麼，我們必然能找到一個Q比沒有戴帽子的P還要短，然後根據reweighting的方法，我們得到帶帽子的Q竟然比帶帽子的P還要來的短，矛盾，故沒有帶帽子的P一定是shortest path
問題又來了，這樣子做reweighting的動作，並不保證edge weight為nonegative，所以Johnson提出的方法如下- 多設立一個為0的node，使其node連接到每一個node上，而edge weight 為 0
- 如果G沒有negative cycle，則戴帽子的G也不會有negatvie cycle
- 對於每個node的h(i)設為0 至每一個node 的weight sum
可利用s.29的圖來說明，用三角不等式即可得證，d(0,j) <= d(0,i) + d(i, j)，d(0, j) 為shortest path，則d(0,i) + d(i, j) 至多有可能為d(0,j) 的其中一個解。
使用了Johnson's Reweighting的方法之後由於edge weight為nonegative，所以可使用Dijkstra's algorithm，running time可達到O(mn+n^2 log n)
那麼今天真正的主題就是，要把Naïve algorithm speeding up(yen3註：上禮拜是一個怪好笑的舌頭，這禮拜為一個戰鬥機代表speeding up XD)
---
下次寫作時間不要拖那麼長了..Orz
星期二, 4月 03, 2007
How Would It Be
聽起來讓人心情不錯的歌，最近一直在聽這首
How Would It Be(Lene Marlin, Lost In A Moment, 2005)
What have I done?
What if it's too late now?
Did I do all I could, did I?
Did I make it good, did I?
Somehow it doesn't feel right
Is it really all over?
Did I think it through, did I?
What if all I want is you?
And now
I won't see you again
The moment was there but we lost it
Time changed it all
And we let it
We let it happen
And now
I wonder how it would be
If things stayed the same and we liked it
The end of a search 'cos we found it
How would it be?
How would it be?
How would it be?
How would it be?
What have we done?
What if it's too late now?
Was it always like this, was it?
Was it something we missed, was it?
Somehow it doesn't feel right
Is it really all over?
Was it all it could be, was it?
Did I give you the best of me?
And now
I won't see you again
The moment was there but we lost it
Time changed it all
And we let it
We let it happen
And now
I wonder how it would be
If things stayed the same and we liked it
The end of a search 'cos we found it
How would it be?
How would it be?
How would it be?
How would it be?
And now
I won't see you again
The moment was there but we lost it
Time changed it all
And we let it
We let it happen
And now
I wonder how it would be
If things stayed the same and we liked it
The end of a search 'cos we found it
How would it be?
How would it be?
How would it be?
How would it be?
睡覺
昨日與朋友聊的非常高興，半夜三點才睡....早上醒來已經十二點....連翹四堂課，資料結構與演算法無妨，我一直靠著線上課程和隨機客在學習，現代小說，有點對不起老師。
室友相當的神奇，用手機設了五個鬧鐘，皆在我還沒有聽到時就按掉了，所以今天睡到十二點不是偶然XD
星期一, 4月 02, 2007
下雨
去旁聽隨機客的課，共去了5次，4次下雨，難得的高紀錄，我在上禮拜說，該不會下禮拜會下雨吧，果真成真了，獲得一個"雨男"的稱號，Josh 身體不適，我偷偷錄了音，具有單聲道立體環繞的效果，下次不會再做了，因為隨機客不是一個能接受學生上課的錄音，但是為了Josh著想，就偷偷錄一次吧XD
星期日, 4月 01, 2007
星期六, 3月 31, 2007
回憶
很多很多天以前，我就想寫一篇有關孫燕姿的文章，但是苦無時間...
對我而言，聽音樂是一個具有很特殊的回憶之事，孫燕姿對我而言就是一個很特殊的高中回憶。我高一的時候，她的第六張專輯"未完成 To be continued"出來了，我聽一聽之後，不知道有什麼動力，我餓了一兩個月，把她前面五張專輯買齊，現在想想，仍屬一件神奇之事。
照慣例，要說話之前，我們先來看看，她出專輯的記錄(破例記錄到月)
- 同名專輯 - 2000.06
- 我要的幸福 - 2000.12
- 風箏 - 2001.07
- Start自選輯 - 2002.01
- Leave - 2002.05
- 未完成 - 2003.01
- The Moment - 2003.08
- Stefanie - 2004.10
- 完美的一天 - 2005.10
- 逆光 - 2007.03
就發片速度來看，早期的速度可謂是迅雷不及掩耳，到後來越來越慢(一方面是合約問題，一方面是她真的唱的很累)。
對她歌的感想是什麼呢？Josh Ko對我說了如下的話
剛出道時耳目一新，但是久了就與一般歌手一樣
對我而言
剛出道時耳目一新，但久了就陷入了複製自己的迴圈
何謂陷入複製自已的迴圈？周杰倫是個很好的例子(我直到現在還是只聽同名專輯和范特西，雖然咬字還是模糊，但是創作原味仍在)一般歌手為什麼不敢跳脫既定印象呢？因為怕失去原有的老聽眾群，更害怕無法開發新的聽眾群，如果仍然走一脈的唱風，孫燕姿的確出的每一張專輯都有固定的支持群眾，但是卻很難再吸引新的群眾了。
"逆光"出來時，我一首都沒有聽過，即以掏錢預購之，聽完不出預料的失望，這張專輯的歌曲鑑別度不高(鑑別度高的？我要的幸福)，聽了十首歌很像聽了同一首，硬是要聽的話...我頂多只能分出其中三首。事實上孫燕姿後面所出來的專輯都有歌曲鑑別度不高的問題，帶來的就是人氣下滑(The moment的"遇見"或許是例外，與電影"向左走，向右走"結合，事實上很多歌都與電視電影行銷)，更別提那奇怪的銷售量數字(或許會有專業的姿迷提出精確的數字反駁，但是我不得不說，歌迷流失是一個事實)，其他有關孫燕姿的想法，我想，與大部分人相同。
我是不是姿迷，或許是，早期我與"18度C的孫燕姿"站長、yahoo家族"愛姿病末期病房"的家長 有過接觸(家長都叫我小藍XD)，那是我一段很快樂的網路生活(少不更事時，曾經過著每天灌水18度的日子XD)，或許是姿迷，我會以較嚴格的標準來看待。
但是就今年而言，"逆光"是不是一張好專輯，是，因為台灣整體的流行音樂界品質也降了不少，不然我不會轉聽外文歌曲和非主流樂團。張惠妹的姊妹不也賣了上百萬張嗎:)
---
看來最近都走懷舊風
星期四, 3月 29, 2007
發現
真的要寫一份說明document的話，用字要嚴謹，這好像不是現在的我所能辦到的，不過願盡力一試，當然，排版要有一定的乾淨程度，這是一必然要求，SIC已經完成，SIC/ XE，我想我會照我自己的意思來寫
星期三, 3月 28, 2007
星期一, 3月 26, 2007
資料結構與演算法(下)05 by 隨機客
非正題：今天上課算是比較輕鬆的一次(是進入狀況還是課比較好懂呢?我也不知道XD)，上課還被隨機客詢問(當然，我答不出來XD)，興起了換位子的念頭XD
2007/03/26 資料結構與演算法(下) 呂學一 投影片
今天上課的主題是Shortest-Path Tree Algorithm, 主要分有Bellman-Ford, Dijkstra Algorithm
在進入Algorithm前，先行討論此問題的背景
- The setting
- The graph G = (V, E) is directed with edge length w. (此圖必需是個有權重的有向圖)
- The length of each edge could be negative. (允許圖上的edge 為 negative)
- The problem
- Input: A directed Graph G=(V, E) with weight edge w.
A node r of G - Output: A tree T rooted at r such that the path of T from r to each node u of T is a shortest path from r to u in G.(yen3註：一個root 為r 的shortest path tree.)
- Input: A directed Graph G=(V, E) with weight edge w.
- We may assume that each node in the graph is reachable from r.(yen3註：假設r 可以到達每個node)
那麼在Graph中，有unreachable node，則一開始則remove掉，而不失一般性(Without loss of generality)，為什麼呢？
尋找對r所有的unreachable node只需要花linear time，用DFS(depth First Search)從r開始，把所經過的點編號，而沒有被編號到的node就是unreachable node，而執行DFS只需要linear time，故此假設不失一般性 - Can a shortest path between node u and v contain a cycle? (是否會有cycle在shortest path tree上呢?)
答案是否，我們把cycle weight sum分成三種狀況- cycle weight sum is positive: 此狀況不可能發生，因為這一定不是shortest path，因為一定不會通過，因為把此cycle 拿掉則path會更短
- cycle weight sum is negative: u到v根本沒有shortest path，繞了n圈為最短，則繞了n+1圈會更短，則繞不完，所以有negative cycle weight的Graph, 則shortest path 不存在(這是一個if and only if)
- cycle weight sum is 0: 則不會通過，就沒有cycle，這樣子可把cycle做一個remove的動作，使其cycle不在shortest path上
- Single-source shortest-path problem
在此問題上為single path，但是與一般的path定義不同，一般的path定義為該node通過後則不能再通過，但是在此，我們比較確切關心edge weight sum - Such a shortest-path tree always exists? 不一定，原因如上
若r至任何一點u，都是reachable，就找所有可以走到的方法，事實上有可能是無限條，但是限制在G has no negative edge 和remove unreachable node 和 only think about single path ，則shortest path 則會變成有限條 - The shortest-path tree problem is equivalent to finding the distance from r to each node u in graph G. (尋找shortest distance和shortest path 是等價的問題)
何謂等價的問題，若A和B是等價的問題，則找到A的答案之後，我們可以在linear time 找到B的答案，且找到B的答案之後，也可以在linear time 找到A的答案
那麼為什麼shortest distance 和 shortest path是等價的問題？若已知shortest path，則把edge weight求其和即為distance，可在linear time 找到，若是shortest distance呢？從r到v的點，我們從v點找起，把指向v點的edge weight掃描一次，若剛好等於，則是shortest path 的一個解，若小於此weight，則扣掉該重量，進行recursion，由於只有m個邊，我們可以保證在linear time 找到 - 補充說明：在演算法上所定義的linear time並不是指O(n)，而是指執行效率相對於input size，若input size 為O(n^2)，而RunTime也是O(n^2)，則我們說該演算法是linear time
終於可以描述演算法嘍XD
- Bellman-Ford Algorithm
此演算法的方式如下
- 設一個array d[u]為從r 到u的距離
- 對其array做初始化的動作
- Let d[u] = infinty for each node u of G
- let d[r]=0(自己到自己距離為0)
- Repeat improve對於d[u] for d(u)的估算
而Relaxing edge(u,v)為
那何謂A phase of improvementIf d[v] > d[u]+w(u,v) then
let d[v] = d[u] + w(u,v)
問題又來了，試問phase of improvement 要跑幾次才能確保答案的正確呢？For each edge(u, v) of G do
relax edge(u, v)
如果node為n個，則跑n-1次就可確保答案正確性，每當我們跑了phase of improvement，則會有一點被改善(yen3註：竟然不會證Orz)
那麼效率呢，由於有n個node，m個edge，每個點皆跑m個edge，所以Time Complexity = O(mn)
第二個問題是，若圖中有negative cycle，則我們要怎麼得知？
問題也很簡單，已知演算跑n-1次已經得解，若跑了第n個phase 而仍然有d[u]被改變的情形，則知道與原先預想的不合，此圖有negative cycle
為什麼？在s.31說明(yen3註：證明竟然忘了...真神Orz)
若該Graph 為一個 Directed Acyclic Graph DAG呢? 方法如下
其Running Time 是 O(m+n)- 先對該DAG做topological sort
- 根據topological sort 的順序，由小到大(slight 上寫由for 1 to n)做relaxing動作
- Dijkstra Algorithm
(題外話：Edsger W. Dijkstra 是提出“Goto is considered harmful.”的人)(yen3註：此話真的是powerful，對於現在學assembly language的我而言更是一個有趣的問題。)
此演算法是一個極具powerful的演算法，此演算法求shortest path是建立在無non-negative weight edge, non-negative-cycle的DAG上，方法如下(此方法不用依靠topological sort做前置作業)- 做與Bellman-Ford Algorithm同樣的初始化動作(與對其array做初始化的動作相同)
- 每一個iteration中，尋找unprocessed node中，尋找到目前為止smallest path做relaxing，直到每一點都做完為止(換句話說，在所有未處理的點找到該點花費最少的來做處理)
此方法的正確性呢?由s.50得知。假設u是unprocessed minimal node，而在處理到u node時出錯了，而y node 與processed node 的範圍只用一條edge連結，所以我們確信d[y] = d(y)，但是我們又說u是unprocessed minimal node，而用y連過去則會讓d[u] > d(u) >=d(y) = d[y] 矛盾(yen3註：證的真爛Orz)
則Running Time用 Naïve implementation: O(n2 + m).
With Fibonacci heap: O(n log n + m).
---
聽Josh Ko說明才得知簡報上的數學式是用TeX4PPT做的，來找找做個介紹
塞車
騎摩拖車遇到塞車算是很大的難題之一，雖然演算法學的是圖論，但是關係不大XD 唯一的關係，你得避開車潮，今日六點半起床(上大學以來最早)，七點出發...還是躲不了塞車的惡夢，下禮拜決定六點起來好了
---
再塞我前天就睡台大(會不會有兩個人做惡夢XD)
星期日, 3月 25, 2007
星期六, 3月 24, 2007
星期五, 3月 23, 2007
所學為何？
有一天我的室友和我聊天時(我幾乎天天和我室友聊天)，我室友問起我，為什麼我肯為了念書(大部分是CLRS)而那麼衝，我不會累嗎？
Absolutely yes.
我並沒有和Josh Ko 一樣，能夠在高三到現在還是保持大概相同的想法與目標，我說過，我高三曾經念書念到壓力極大，剛好又被人發卡XD，每天一直念書一直念書，靠的就是每天聽三十分鐘的音樂(內容一定固定為F.I.R. - Fly away為開頭，中間一定有DAI - 樂園, for the future)，似乎就只是為了這些歌中的信念活下去。
到大學了，念書，有時候真的會覺得，原文書難念的跟鬼一樣，我到底是為了什麼而活下去？不為了什麼很複雜的目標，就只是想要活下去而己。
在我高一時代，我曾經花了一個晚上看完吉川英治所寫的 宮本武藏，雖然吉川英治的文筆很美麗(這當然跟譯者也有關係)，如同他所著的三國英雄傳，渲染了小說的每一個角色，把個性強化了，回到本文，宮本武藏一生的信念只有如下八個字
一切即劍，萬里一空
一直到了很多很多年以後，我才漸漸了解這兩句話的涵意，這可不是高中的時候以為這很帥，然後就一直放在msn狀態上，這對我而言是一個有趣的回憶。
宮本武藏本身對於生活的態度就是"一切即劍"，意思也很簡單，每件事物的存在都有它一定的道理，而劍道就可以從此中體會，每件事物，都有劍道的意涵(我的文化水平不高，只能做到如此解釋)，相較於佐佐木小次郎的"劍即一切"，他是用劍道來解釋一切的東西，是極為霸道的，可以得到一定的道理，但是否違背了大自然的運行？
兩個人的決鬥說明了一切。
今天的我，就是以"一切即劍"的觀點在看待Computer Science，每件事物存在都有它一定的道理，而我的基礎遠遠的不足以讓我觀察這個世界，所以我選擇繼續努力，這是我思考層面的觀點。就現實層面而言，我有很多支持我的親人與好友，這更是我要活下去的動力。
那麼為什麼我選擇了Computer Science？ 這答案或許就跟宮本武藏選擇劍道一樣，沒有太多花俏的理由，只是為了實現生活的一種方式
---
我不懂日文，但是我真的覺得DAI給人活下去的力量
星期二, 3月 20, 2007
balance
從昨天馬不停蹄的念書(假設寫隨機客的上課筆記blog也算)，昨天晚餐沒吃，今天早餐只喝牛奶，午餐麵包，由於課相當的輕鬆，還是一樣保持高度的念書熱誠，只是到下午，胃莫名奇妙的痛起來，痛到食慾不佳，這會讓我想起我在高中寫程式寫到胃痛的日子(也是一樣整天不吃)，似乎我想做事，就會比Josh還糟，連飯都不吃了XD
念書念到沒時間吃飯，好像不是理由XD
---
睡了一覺之後，只剩些微了
I2A
老酒新調，了無新意，目前自修，準備搭配OOPs上的Instruction to Algorithm Fall, 2005課程來自修，現在用Leture 1學習，效果比直接讀書來的好的多。
看到老師上課的簡報...嗯...不予置評
星期一, 3月 19, 2007
資料結構與演算法04 by 隨機客
非正題：嗯，今天是騎車去上課有史以來最塞的一次，也是我有史以來上課最認真聽的一次(拿著筆電狂打)事實上還有很多不懂的地方，寫到這裡就要很感謝，哈密瓜的討論，Josh Ko的支持與校正，隨機客上課的精采，這些都是我邊碎碎念騎車邊快樂上課的動力:)
2007/03/19 資料結構與演算法(下) 呂學一 投影片
今天上課的主題是Minimum Spanning Tree MST 和 Epilogue(時間來不及所以省略)
- Minimum Spanning Tree - Boruvka' s algorithm
此問題主在描述，在一圖形G中，每個edge都有不同的權重，找出連結所有node的最輕解(edge 的權重和相加為最小)用比較正式的描述則變成
這個問題的主要起源是Boruvka被波蘭政府委託在Bohemia這塊土地上牽電線，而讓每個城市都有線，而要怎麼樣牽電線會讓所耗費的成本為最小，就成為Minimum Spanning Tree的原始問題(yen3註：也蠻經典的XD)- Input: A connected n-node m-edge graph G with edge weight w.
- Output: A spanning tree T of G with minimum w(T).
但是先假設一個狀況，才能使用Boruvka' s algorithmWe may assume that all edge weights are distinct(yen3註：假設每一個邊的權重(重量)是不一樣的，而這樣子的假設不失一般性(JK註：不失一般性的原因，如果遇到這樣的狀況，也可以加以修改而符合假設。)
，原因是，在真實世界上，也很難找到一樣權重的路)
(JK註：假設並不會得問題的範圍變狹隘。)(相同權重的邊，稍微加一個數字造成些微的不同，雖然相同權重的邊有些許的不同，但是所算出的結果仍然一樣。)
那麼解法呢，Boruvka' s algorithm 方法如下(s.9)- 尋找每個node對外連接node的lightest incident edge加以連接
- 將已連接的connected component視為一點，尋找connected component 的 lightest incident edge再加以連接
- 集合每一個maximal subtree of F 成為一個single node(yen3註：我解釋的不好，所以照簡報)
連接每個maximal subtree為單一集合，即為答案
那麼簡單而言，讓每一個city伸出一隻手出去，往鄰邊伸出一隻手，從重量最輕的邊伸出去，如果每個ctiy都伸出最輕的手，則是Minimum spanning tree, 若無如此，，each city 都伸出lightest edge尋找spanning tree，則將connecting component縮成一個點再將已形成的spannign tree視同為一個node，再尋找每個node's lightest edge，直到連結全部node為止。
那麼演算法的效率呢，是一個expected linear time從O(m log n)一直至O(m, a(m, n))甚至optimal time(比任何已知的演算法都來的快)，但是不是真正的linear time，無人知道，在s.7中有提到基於兩種基礎所發展出來的演算法。- Unit-cost RAM Model
每一個數字用log n的數字來表示，允許任何連續O(log n) bit做加減乘除，皆可在linear time 上做到。 - Deterministic comparison based algorithms
需要把資料兩兩做比較的演算法，所以最多為O(n logn)
當然，眼尖的人會發現此slight的論文發表時間有所問題，但是不是那麼的重要，所以我們略過:)
那麼演算法的正確性呢？對於任何一點，連接此node的lightest edge
此點為週圍鄰邊最輕的，此edge必得在MST上在s.12上，紅色代表為最輕的邊，n-1個點皆在右邊，假設Red edge 不在MST上，那麼右邊為一個connected ，變成第二個點在MST上，但是權重卻比red edge重，矛盾(JK註：證明) - Minimum Spanning Tree - Kruskal' s algorithm
- 每個node自為成一個集合
- For each edge (u,v), taken in non-decreasing order by weights
if Find-set(u) ≠Find-set(v) then
(從權重最輕的邊依序處理，若兩集合不相等，則此兩邊必為相連的MST，所以印出edge(u, v)，把u, v兩個集合做一個結合成新集合)
Output edge (u,v)
Union(u,v) - Minimum Spanning Tree - Prim's algorithm
前面的方法稍微散亂，這個演算法的方法的方法蠻簡單的(JK註：要先實作priority queue，本質上和Dijkstra最短路徑演算法相同)從任一點開始，尋找權重最輕的邊，每連一個點，就視為一個connected component，縮為一個點，再尋找權重最輕的點，相連，直至連接G 上所有node為止
至於正確性呢，證法也同Boruvka' s algorithm - Advanced Topic - Expected O(m)-time comparison-base algorithm for MST [Karger-Klein-Tarjan, JACM 1995](yen3註：此處目前無人校稿，)
呃，事實上要了解並不難，但是要先了解三個特性- Cut Property - 給一個MST，任意選一edge把所有node分成兩半，任意的crossing edges，一定比剛剛切掉的edge權重來的重
- Cycle Property - 任一cycle in graph G，此cycle一定有一權重最重的edge，而此edge一定不在MST上
- Uniqueness Property - 若任一edge權重都不一樣，那麼MST只有唯一解
證明呢，我打算在下一篇blog說明，因為我認為我的思考還不夠完備，那時候寫也是不夠的XD
此外還要再說明T-heavy edges(s.40)定義為在任一spanning tree of G，必然有一邊權重為最重的edge(u, v)，那麼根據cycle property ，此edge必不在MST上所有不在MST的edge必為T heavy edge(if and only if)。
給一個spanning tree，把所有的T heave edge 丟掉，則此spanning tree必為Minimum Spanning Tree.
也因為有了這個性質，要證明一個spanning tree是不是MST是非常簡單的，在linear time即可做到(s. 44. 45)
那麼方法為The strategy: Using random sampling to further delete at least a constant factor of edges on average after each phase of edge contraction.(yen3註：這這裡不是那麼了解，課堂上的大意為random 取node，然後把T heave node刪掉，約取三次，最後會最多只剩n/3 nodes需要再做處理)
事實上為換湯不換藥的方法，採用的是disjoint-set
至於正確性的證明是和Boruvka' s algorithm 一模一樣的。但是效率會好一點，會等於O(m log m) = O(m log n)
臨時趕完有品質很差的感覺(雖然品質從來沒好過)，不過換來的是，有一個禮拜的時間可以修正和擴充
Josh Ko 於 2007/03/20 校稿
---
寫到後面有一種很累的感覺
問題
有人跟我反應上課筆記看不懂，我是沒有差啦，反正我還錯誤很多需要訂正:) 現在的確是分段寫(04已經累積至1200字左右，尚未寫完)，但是正在想會不會一篇文章太長，所以要分開po(我絕對沒有要賺篇數)，這個問題...就再說吧，目前會為了完整性一次po。
下雨
這似乎對要前往台大的我不太妙，不過已經告訴自己風雨無阻了
補記：從7:30騎車至08:50，一路塞車到台大，還好沒有下大雨:)
補記2：回來從1:30至2:10，頗為順利，公里表為7050(三個禮拜前到校為6450)
---
筆電+筆記本 = 全身行囊
星期日, 3月 18, 2007
資料結構與演算法02 by 隨機客
非正題
工院盃快結束了，我所能做的事也暫告一段落，所以我決定在下次上課前趕快把上課隨筆寫出來，不然lag到就麻煩了，也很久沒有寫blog了。
2007/03/05 資料結構與演算法(下)02 呂學一 投影片
這堂課最主要講的是Graph 圖論(The adjancency among a set of nodes)，重點落在Depth First Search DFS而今天主要著重在三個問題上，但是在進入這三個問題前，什麼是Graph?
G = (V,E) to denote that G is a graph, where V consists of the nodes of G and E consists of the nodes of G and E consists of the edges of G. (yen3註：簡而言之，一張圖G由節點V，和連接邊E所組成)，通常使用(n,m) 元素個數來代表(V,E)的集合。
而要怎麼表示一個Graph呢，最常見的有兩種方法
- adjacency matrix
一個很直覺的方法，使用一個space為O(n^2)來儲存(yen3註：很直覺存法就是使用二維陣列)，若(1,2)有所連結，則在table的(1,2)(2,1)標示為1，代表有其連結，其優點是速度快，在Insertion, Deletion, Query 都是O(1) ，缺點是，若是連接邊集中於某些點JK：若是matrix 很稀疏，意指邊很少的狀況下，則會浪費很多空間。- Adjacency list
很直覺的方法，為絕大部分Graph Algorithm所使用的Data Structure，方法是，每一個節點建立一個sortedlist(JK註，不一定為sorted，為sorted也沒什麼好處)，若和此邊有所連接，則插入(見s.8)(yen3註：在C++中，可用link list或者是STL中的vector儲存節點)，優點是節省空間，缺點是速度較慢，Insertion, Deletion 為O(1) (yen3註：O(n) 也是有可能的，端看如何設計) ，Query 為O(deg) (deg 為資料深度)， Space 為O(m) (m 為edge數)- Adjacency list with balanced search tree
方法與第二種相同，只是儲存資料時改用BST來儲存，如此在Query則會降成O(log deg)。
那麼三個問題又是什麼呢，分別如下
- Connected components
什麼是Connected components呢，定義如下Each connected component of graph G=(V,E) is maximan subset U of V such that any tow nodes in U are connected in G.(yen3註：簡而言之，在一圖型G中，尋找subgraph G 包含最多節點n)
解法，則 - Topological sort(拓撲排序)
首先，Topological sort是使用在directed graph上，這時候又會牽扯到DAG(directed acyclic graph - a directed graph that does not contain any cycle.(yen3註：簡而言之，不會有任任何成為cycle的node，就是不能從A node出發再回到A node))，其example在s.30，其pesudo code在綠色字處，加入計算每個節點被拜訪到的先後順序(yen3註：上課時沒有證明，不過用實例跑過一次，確實相同)，而，在把答案output時，將t從大到小輸出，原因也蠻直觀的，因為排序最後的節點，是會最先被參觀到的，而排序最前的節點，由於並無人指向，所以是最後被參觀到的，所以一個圖G，並不一定只有一組解，可能會有好幾組解(yen3註：原因，我好難解釋Orz)。證明從s.35開始 - Strongly Connected components
定義如下Each strongly connetced component of graph G= (V,E) is a max imal subset U of V such that any two nodes in U are reachable(through directed paths) from each ohter in G.(yen3註：在directed graph中，尋找max cycle的subgraph)
演算法的方法也很簡單，步驟如下- 用
Topological sortDFS讓每個node有一順序 - 將圖上的directed edge全部反向
- 再跑一次
Topological sortDFS(根據第一次跑出來的Topological sort list來執行)，每一個list代表一個答案
那麼為什麼這樣子的演算法可以成立，隨機客使用了非常直觀的證明方法而避免掉課本一拖拉庫的證明(s.49, 50)(yen3註：時間太久，我竟然忘了XD)。 - 用
請盡量指教，謝謝:)
(Josh Ko：正確性的證明需提一下，至少命題要寫)
(yen3：下次把一篇拆成好幾天寫就有機會，感謝指正)
---
下次要早點寫，而且分好幾天寫....好累
星期六, 3月 17, 2007
BST
Basic Binary Search Tree 大致上已經建構完成(basic的原因，不具備balanced的功能XD)，花了很長的時間在寫ctor, dtor, copy ctor, operator=，不過整個class的效率不佳(基本上都以recursion建成，以後可以思考拆掉)，程式碼目前只有330行，算很小，就算在insert node的這個功能上加入balanced，我相信也不會大到那裡去~
---
AVL Tree建完回頭建link list..XD
星期二, 3月 13, 2007
沒時間
第一次覺得沒時間可以用，利用自身的筆電優勢，大概把BinarySearchTree寫完了，327行，尚未整理，一整個很有dirty work的感覺，晚上要當工院盃場務，回到宿舍已無體力繼續，印出來之後，完成一個AVL Tree or RB Tree指日可待
事實上沒時間最可惜的是，要寫"資料結構與演算法02" 一直找不到時間XD
---
沒時間(Sun yanzi, Start自選輯)
星期一, 3月 12, 2007
最近
發現要念書時間不夠用，對於利用電腦整理重點更有心得，但是總覺得有一種被制約的感覺。有人問我"一把鍵盤改變全世界"(msn狀態)是什麼意思，我很高興的說的，因為資工人就利用鍵盤所輸入的文字在改變世界，但是轉眼一想，我們不就受限於簡單的鍵盤上嘍，但是相較而言，用簡單的鍵盤創造無限可能，這或許就跟用鋼琴，就幾十個黑鍵白鍵，譜出全世界最美麗的樂章，有一樣的感覺
---
但是我想要成為資工人，而不能成為鋼琴家XD
資料結構與演算法(下)01 by 隨機客
非正題
當初一時高興之下決定每個禮拜前往台大旁聽的決定，現在已經是第三個禮拜，想想也是覺得複雜了些(早上七點起來+來回60km機車)，但是現在想想，上這堂課是蠻值得的，一直都很想為這堂課寫一些blog note，但是，呃，苦無時間，原因很多，所以且戰且走吧:)，這還是我蠻常說的一句話。
2007/02/26 資料結構與演算法(下) 呂學一 投影片
這堂課主要講述的是隨機演算法(yen3註：跟隨機客有異曲同工之妙XD)，主要著重於兩個重點
- Randomized quick sort
- Randomized maximum cut
sorting 乃萬古常青的演算法問題，quick sort更是在1960年代時被提出，在投影片的一開始複習quick sort的特性(標準的divide and conquer)與algorithm的運作方式(yen3補註：這中間有非常的漂亮動畫說明，考據指出，只用了powerpoint的內建功能)。
quick sort的時間最佳為O(n logn)，最糟為O(n^2)，這中間的效率在於pivot的選取，重點來了，怎麼選？當然，一般化的想法，選中位數，中位數的選取幾乎可以獨立成為一個演算法的課題(在簡報中提到許多paper都在選中位數，而這篇關鍵性的paper author幾乎都得了Turing Award XD)，證明出選中位數是linear time，於是隨機客在這邊丟出一個問題，是否在做quick sort的選取pivot時，一定要用到如此複雜的選中位數呢？
當然有其他解法，Randomized 選取pivot是一個解，隨機演算法本身的撰寫無難度可言，難的是，如何得知效率(time and space complexity)？亂數是否真的夠亂(yen3註：C library 下的rand() 是個眾所皆知的假隨機亂數)，經過證明，經過隨機選取的亂數當pivot，有一半的機率會達到最佳效率，也可以證明出O(n logn) 是成立的(隨機客將中間證明省略)
掃黑的藝術(yen3註：XD)
給一個圖G，找出從A node 至B node能夠將最多edge切掉，但是也有一個問題，each node no more than 3 neighbors. 問題規定如題，求出最大切割的time complexity 也是O(c^n) c為constant ，n 為節點數...如果n 非常大，此題接近無解
Approximation Algorithms(近似演算法)現身啦，噹噹噹(近似演算法的哲學：放下對完全的堅持，往往就可以找到新的出路。知所進退，則近道矣。)在此問題上，使用隨機演算法選取node進行切割，則有機率是最佳解的一半(但是時間就是生出亂數的時間XD)，隨機近似演算法就變成一個很好的解法(yen3註：後面看不太懂，要再念書。)
對隨機演算法不要有一個誤解，無論input data為何，都不影響其效率，也就是說，對於best case和wroest case，隨機演算法皆保有同一個效率，並不因input改變，因此，沒有必要對所有可能的input 算出每一個時間複雜度，若是這樣子，此隨機演算法不成立。當然，隨機演算法也有其罩門，這世界上是否真的有亂數產生器？(Pseudo-random generator exists if and only if one-way function exists.)到目前為止沒有人知道有沒有，因為事實上證明出現有的亂數產生器都是有跡可循的，若是用C library 上的rand() ，照著一定公式所產生的亂數，也有演算法可以很大的機率猜出下一個會出現的數字是什麼(以bit的觀點)。在這也提到了P vs NP problem
有錯誤請盡量指正，謝謝:)
---
寫的好長好亂，下次我是不是該改成wiki..XD
星期六, 3月 10, 2007
換環境
試著在Dev C++寫稍大一點的程式是一件很恐怖的事，終於在昨天體會到了，不用專案即可單檔編譯一向是Dev C++顯著的優點，這對初學者而言非常的方便(我到現在還是初學者XD)，但是昨天試著建構一個屬於自己的Data Structure Library時(完全不用STL)，多檔連結可謂是dev c++的災難，用筆電字小，長期寫下來著實勞累，不得已，暫時換至桌上型+Visual C++ 2005 Express Edition，老實說我也不是那麼喜歡Microsoft的東西，但是僅我所認識的 Editor + Compiler 只剩CodeBlock，呃，好是好了，但是其語法顏色好像七彩霓虹燈一般，不甚習慣(我一般只有keyword 和string不同顏色)，暫時且戰且走吧。
此library也只建構了Stack和Binary Search Tree，連一個能操控的Iterator Class都沒寫，看來可以盡情的發揮寫程式的心情了XD
---
小白+大螢幕 = 好的寫程式環境
星期五, 3月 09, 2007
星期四, 3月 08, 2007
早睡
這學期受到cll老師影響(這名字有仿Josh對於cyy的命名XD)，每天過著十二點睡七點起床的生活，剛開始不甚習慣，有很累的感覺，後來越來越習慣，也不太需要鬧鐘，自己就會比鬧鐘早醒來，人跟機器的競賽，似乎有一點有趣:) 身體好很多了，生活也很普通，過著專業念書的生活，有朋友嫌我一個禮拜生了14篇blog有點多，呃，我個人是沒有想那麼多，想寫就寫，有點像散記，沒有那麼專業，所以就將就點吧。好玩的一點是，我和我室友被cll老師在課堂上對學弟妹說，你們的學長很認真的早睡啊，上課都不會打嗑睡，但是有點抱歉的是，我下課會一直睡啊。
筆電對於我這學期上課的影響度達到前所未有的高，每天都要擔心用電問題，卻真的沒有一天把電用完過(螢幕調最暗，CPU速度調最低)。感覺上，這樣子的生活也不錯
最後我想說的，有看我blog的十多個人(假設StatCounter可信)，有沒有人要響應我的早睡運動，響應的送台客照一張XD。
---
不過也不得不說，五天中三天八點有課XD
來一點不專業的
早上心生無聊，用LaTeX生了一篇作業題目出來(有需要)，看到的人大為驚豔，我卻甚為漸愧...因為我並沒有做很細步的調整。
今日上計算機組織上了一個很簡單卻很重要的語言，事實上我們可以做成如下論述
看起來很像，事實上一點都不像RTL相較之下還算高階一些，register 可是由flip flop做出來的，但是VHDL卻要實作整個flip flop(當然，好一點的軟體都會內建寫好的function)，兩者的語法我不多做描述，google一下都有。我想說的是。
- RTL Register Transfer Language 針對整個Computer Organization 的 microoperation做描述
- VHDL VHSIC Hardware Describe Language 針對boolearn function 抑或是整個電路圖描述
在撰寫VHDL時，你是在對電路做描述，而不是在寫高階語言，在寫作時，應對電路存有一個大局觀
這是一個很簡單的概念，也不難，問題出在那?VHDL有for, if, case switch, while, 甚至連bit vector都有了，你寫起來很像一個高階語言，但是不代表他如你所想的
這樣子的程式碼在C/C++等高階語言中，大部分都是循序執行，看完if再看else，如果if成立，program根本不在乎else發生了什麼事。但是在VHDL中，這個if else乃是同時被執行的，意思即是，K只有0與1，所以我們會在R2和R3 assign 給R1之前，加一個K的2 to 1 multiplexer ，就可以完成選擇動作了，這也是同時被執行的意思。
if(K==1) R1 <= R3;
else R1 <= R2;
那麼我們再來看一個在電路中根本不存在的東西for，那麼這樣子的東西到底怎麼樣被實作的？答案也很簡單，原地把程式碼展開，使得一個for是一個一個依序執行的變成平行執行(實際上當然沒有那麼簡單，可能還要加一個clock)，簡單而言for如果跑了10次，那麼assembler就轉成十行程式碼，這或許是最快的解法，如果真的要學會VHDL，我還是得對背後的運作原理多多下功夫才行。
---
聽完今天的課有頓悟的感覺。
星期二, 3月 06, 2007
學習
從隨機客的課堂上，我想可以學習到很精采的演算法與資料結構，這是無庸置疑的，但是他更想教給我們的是做學問的態度，原因無他，我上課只有半年，但是做學問可能要做一輩子，顯然，他所述說的，與我從Josh看到的金次述說強調重點不同。
不要做一個verifier，而做一個prover或presenter，此乃知易行難的事，以我的聰明才智，我還要學很多很多才看會不會用嚴謹的數學語言證明某些事的存在。我從高二開始教別人寫程式語法，到大二教人學習寫C++(以程式語言的角度)，有時候在準備時，真的深深的覺得，懂了並不代表你可以很嚴謹的說明出他是什麼，以前我總是討厭嚴謹的東西，現在回頭想想，嚴謹的東西才能讓自己的思考趨近於完備。以教授一個"物件"的概念，我還是翻了"世紀末軟體革命"的chapter 2，我才照本的宣科的解釋(再加上自己的見解與舉例)。現在想想，我的學習和教授兩件事都有很大的進步空間。
---
昨天當場務太累，連複習都沒了...
星期一, 3月 05, 2007
有關"序號"這回事
每個人都有過重灌繽紛的精采時代:)。
blueforest /* 淋雨是另外一種知道自己想法的方式 */ 說:
WIN98 ME的序號裝到都會背了
blueforest /* 淋雨是另外一種知道自己想法的方式 */ 說:
只要是會重灌的，我相信都經歷過這種時代
blueforest /* 淋雨是另外一種知道自己想法的方式 */ 說:
我背的是Windows 2000序號
Josh Ko 說:
XD
Josh Ko 說:
XXXXX-XXXXX-XXXXX-XXXXX-XXXXX
blueforest /* 淋雨是另外一種知道自己想法的方式 */ 說:
哇考~
Josh Ko 說:
Office 2000 的樣子 XD
星期日, 3月 04, 2007
星期六, 3月 03, 2007
論重灌
前幾天剛好重灌到一個讓我覺得慘不忍賭的電腦，事實上頗有感觸
當然，如果能跟Mac OS一樣，長期不重灌而依然保持一種穩定，這當然是我們這種只會基本修電腦人員所最為樂見的，只是很可惜的是，大部分的人，還是在使用在不甚穩定的Windows 系列。依我現在的使用習慣，就算是使用Windows仍然可以撐到一年不重灌而保持一定的速度(當然，沒有突發的狀況)，以前的我呢，一天重灌三次都不當一回事...只是經過這些年，我還是追求一個穩定的工作環境吧。
有些人看我重灌速度就是那麼穩定，就是還不錯的狀態，很多人問我怎麼灌的，事實上，我灌電腦也沒有用什麼很特別的技巧，大家都會的重灌方法，老子有言，順其自然，我一般都使用原版，以及最常使用的軟體版本(當然，會挑過，最好軟體小速度快)，若要說我跟大部分的人有什麼不一樣，就是，我大概會挑一下軟體，但是這些軟體，對於電腦稍有程度的人是很常見的，我從來不覺得使用foobar Firefox有什麼特殊的，該使用的就灌一灌，電腦的調校軟體就不要灌了，就我的經驗中，灌了調了，就不穩定了，依現在電腦本身的體質，應該是不需要做很特殊的調校就足以應付一般所需，若有特殊需求的話，就盡能力的把電腦配好一點。
Windows XP 我堅持使用原版而不使用任何調校版(最有名的就是我高中時代的SuperXP)，更新一定要裝，怕WGA要不破解，要不找正版序號(幸好我們現在是學生，還有校方授權)，軟體要用才灌，不要灌一堆有的沒有的，尤其是調校，就算再會用，我還是逃不掉一年要重灌一次的命運，這生命週期太短了。
怎麼樣讓自己使用電腦變快，不是在電腦重灌上下功夫，而是在自己的使用習慣上下功夫，不要亂灌，不要讓自己做一些奇奇怪怪的事(如果有不得不的原因要做，防火牆, adwarew灌一下，這是治標不治本的方法)，防火牆，基本的有就好了，根據google原則中，大部分的人都是善意的，也不會有人真的閒到每天入侵你的電腦。
灌電腦就一句話，順其自然
現在的電腦的配備不至於太慢，所以，不要再花心思讓自己的電腦變的快而不穩了，變的又快又穩是可能的，但是我不會，因為這不是我的本業，我的本業是寫寫程式，打打電腦，而不是操出一台電腦的效能極限。
Free Loop
忽然聽到這首歌，甚有感觸，是一首可以讓我repeat again and again的歌
Free Loop (Daniel Powter, Daniel Powter, 2005)
I'm a little used to calling outside your name
I won't see you tonight so I can keep from going insane
But I don't know enough
I get some kinda lazy day
Hey... yeah
I've been fabulous through to fight my town a name
I'll be stooped tomorrow if I don't leave as them both the same
But I don't know enough
I get some kinda lazy day
Hey... yeah
(Chorus)
Cos it's hard for me to lose,
in my life I've found only time will tell how to figure out
How we can, baby, we can do a one night stand, yeah...
And it's hard for me to lose in my life,
I've found outside your skin right near the fire
How we can, baby, we can change and feel alright
I'm a little used to wondering outside the rain
You can leave me tomorrow if it suits you just the same
But I don't know enough
I need someone who leaves the day
Hey.... yeah
REPEAT CHORUS
REPEAT CHORUS....
星期五, 3月 02, 2007
基礎英文
沒錯，這是一門重修課，誰叫我大一下如此帥氣，上到期中考之後就都不去上課了XD，選了是高佩倫老師的課，我在大一的"基礎英文寫作"給予她的教導，那對我而言是少數會讓我認真上的英文課之一(所以我英文從來沒好過XD)，雖然她提及很多可能會發生的問題，但是我覺得一切都還好，會慢慢克服的。跟大一上課，而且是這種互動高的課，還是有一點不習慣，原因，我早己脫離這種搶著發言的時間很久很久了XD
此外老師還跟我說了很多事，還包括了朋友...慢慢來處理吧。
星期四, 3月 01, 2007
資料庫系統
database system,老師為上學期就已認識的老師，所以期待度平平，上課用書為 Fundamentals of Database Systems, 5/e by Ramez Elmasri, Shamkant B. Navathe，我對資料庫完全沒有比較好一點的概念，所以也是一門蠻值得上的課，上課分成兩節使用SQL Server 2000實作(這好像是M$的東西)，一節講述概念，我也不知道這樣子的上課方法好不好，只是覺得很有趣罷了XD ，但是我有問題，為什麼不是用MySQL呢..XD
---
人生吧，就上課，不要想太多
星期三, 2月 28, 2007
星期二, 2月 27, 2007
今日上課
"資料結構與演算法"(教科書為CLRS)嗯，這學期比上學期有趣的多(就課程提鋼而言)，且與隨機客接下來要上的東西有驚人的相似性...不過...第一個作業是，建一個binary search tree，然後假設unbalanced，試做方法讓它平衡之，我沒寫過，不過應該不會太難寫，反正，也是頂有趣的。
這學期似乎越來越有趣了XD
踩地雷
又完成，這次是在Java 上的console mode進行測試，由於只是單純的程式碼轉換，大約208行，所以還算順利，也有用到Java的Generic中的container(只是簡單的運用)，只是由於沒有operator overloading，所以要取得ArrayList中的元素，得用ArrayList.get(i)，操作上不是那麼直覺，而且，並不能回轉reference(雖然這某程度的破壞data abstraction)，也不能剛ArrayList.get(i).length(再此假設每一個元素都是一個fixed sized array)，是較不適應的一點，不過，除了此之外，利用Ecilpse寫作愉快，是一個相當強大的editor，我還不會用裡面一些較好用的功能(程式碼自動格式化，選段註解，這些都自己做習慣了)，唯一比較需要的是刪除整行為Ctrl + D，不錯用，但是跟ConTEXT, Dev C++, PCMan 三者皆為Ctrl + Y，大異其趣，不過Ecilpse可以調，也不是那麼麻煩就是。
---
進行計畫最後一步XD
星期一, 2月 26, 2007
連續一個禮拜
工院盃很神奇的被人拖去當場務了，主要是籃球，但是我是一個連籃球規則都不懂的傢伙，還好室友是一個很聰明的人，一學即通，但是這個禮拜還是一樣的忙。
今日上"組合語言與系統程式"，上課用書為System Software: An Introduction to Systems Programming, 3th Edition,. Person Education, Inc. 老師說可以用中文版(系統軟體：系統規畫導引)，呃，我對中文版沒有什麼興趣，期末報告為一人一組交一個assembler ，似乎是一個還不錯有趣的作業(或許也有可能簡化至字串轉換)。課程很擠，雖然有一點點小失望，但是期待還是一堂不錯的課。
筆電今天下午修好，acer打電話來，外殼錢照算，我有說明螢幕訊號不穩定，他換了一個新螢幕給我，不用錢，但是他說，我的螢幕傷痕累累，下次要換可能就無法算保固了(如果再這樣子搞下去的話XD)，建議貼個保護貼，呃...我那時候怕燈照會反光才沒有貼保護貼的，所以這次電腦回來，大概借人機會極少，也要更為小心愛護了。
筆電
因為許久之前的外殼刮傷(借人時造成的)，螢幕訊號不穩，今日送光華附近的直營店，外殼收1.5k，稍嫌貴了些，不過是與人分擔，所以就最好不要有下次了。
用筆電用習慣了，看桌上型的螢幕竟然覺得好大好大...XD
第一次
今天早上趕去台大聽隨機客上的演算法，精彩可期!!那自己系上的演算法呢？不予置評，稍微算一下，這堂課會會花很多時間和精力於其上，但值得，今天主要上的是隨機演算法，聽起來不算吃力，不過以後沒有良好的基礎，就不知道了，就且戰且走吧:)
---
聊個天，一小時XD
訂閱：
文章 (Atom)