星期三, 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

變壓器

建議買AirPort時,把變壓器納入考量,機器都很小,變壓器都很大一顆是怎麼回事...Orz

星期日, 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, 2005MV06/08/05
Where'd you goFort MinorThe Rising Tied, 2006MV06/12/05
勇敢王婧我要的未來MV 06/12/31
海洋音樂記歐噴愛純愛物語, 2006Film07/01/03
並不張懸N/AFilm07/01/27
What ifLene MarlinLost In Moment, 2005MV07/02/01
SorryLene MarlinAnother Day, 2003MV07/02/03
表面的和平陳綺貞華麗的冒險, 2005MV07/02/06
But I do love youLeAnn RimesI need you, 2001MV07/02/14
Free LoopDaniel PowterDaniel Powter, 2005MV07/03/03
How would it beLene MarlinLost In Moment, 2005MV07/04/03
輕功五月天時光機, 2003MV07/04/16
Breaking The HabitLinkin ParkMeteora, 2003MV07/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

有一個還不錯的朋友跑去暑假補習了...老師說過大學要訂一個目標來做,我想我的好好念書目標太general了,但是要做什麼呢?老實說,我也不知道,只能確定,暑假不會那麼早回家,我想在外面流浪一陣子

星期二, 4月 24, 2007

連續崩壞之後...

在連續崩壞之後,到底我們還剩下什麼?

可能一點不剩的流走,也可能是持續崩壞,生活,本來就如此簡單,不為任何複雜的目的存在,當看見這個世界時,進行著。

關係,簡化,信念,堅持,追求想要的,遠離喧鬧的世界,隱居,只是下一個開始

---
紀念gb014388生日

星期一, 4月 23, 2007

The Legend of Rainer

據說,只要某人興起去台大上課的念頭,那天就會有程度不一的雨,而在某人唯一一次沒去時,該次陰天XD

---
我可以不要當那某人嗎XD

星期日, 4月 22, 2007

精采可期


接下來的日子,用行事曆就可以解釋XD

---
著實精采可期XD

星期三, 4月 18, 2007

無所事事

相對而言,無所事事也是一種事...躺在床上,累到睡不著...著實看來,這幾天太操了,有種放空的感覺,眼睛只要一看到書又會不自覺的高度認真,這也是一個有趣的現象

---
啦啦啦~XD

星期二, 4月 17, 2007

SIC/ XE document

SIC/XE document 第一部完成,這算是我最近會比較讓人高興的事,但是呢,寫完才發現,很像在翻譯課本而己,算了,完成高興就好:)

看這

星期一, 4月 16, 2007

五月天

五月天一直是我在觀察的一個團體,等有空的時候來寫些東西吧


五月天 - 輕功
詞曲:阿信

最近 很需要愛情 讓我這一生混亂 能平靜

人在江湖 心不由己 這世界 又煩又黏膩
你在哪裡 你在哪裡 一雙鞋 踏破了天地

多想要 找到你 多想要 能飛簷走壁
找到你 擁抱你 恨自己 不能飛(到)天上去

多想要 找到你 多想要 地心沒引力
找到你 擁抱你 再一步 愛恨都在我腳底

常常 打你的手機 常常 像打到火星 沒回應

雖然科技 始於人性 可是我 要真實的你
摸到了雲 離開了地 長出了 蚱蜢的後勁

慘痛

現在的我認為照我的學習能力,只要能搞懂理論,實作再克服一些問題即可,於是我拋下很多實作的時間拿去學理論,事實證明我錯了

在大二下接二連三的實作,真的給我慘痛的感覺,道理都懂,但是在實作不約而同的出現小問題,所以我想說的是,我對這些東西還是不夠了解,這讓我覺得,原來我也才不過這樣子而己。

人有時會看不到自己的盲點,但是更可貴的是要看到自己的慘痛,這會讓人心情不好,不過應該要努力的克服,實踐。

---
今天沒去台大上課覺得很可惜,都是很有趣的東西

星期六, 4月 14, 2007


從早上畫到現在才發現,我只喝了兩杯牛奶XD 裡面的compoment各是一個subprogram,呃,花了很多心思在把圖縮小,成果令人滿意

乘法器

早起開始用VHDL寫乘法器,成效不錯,只剩兩個compoment,也可稱之為subprogram(共8個compoment),寫完之後就是把compoment連起來,故事就結束了

---
事實上乘法器也不難寫XD

星期二, 4月 10, 2007

購書清單

Concrete Mathematics: A Foundation for Computer Science, 2/e
by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik 連結
買回來看的,總覺得對現在的我也許會有幫助

The Art of Computer Programming vol 1. fundamental algorithms 3/e by Donald E. Knuth連結
單純想買回來拜,相對於此書,CLRS真的是 introduction XD

發現

學校所教的shortest path 完全聽不懂...是我的錯覺嗎,總覺得我只能抓到關鍵字,然後我就神遊於外了

---
二十分鐘抵兩個禮拜XD

星期日, 4月 08, 2007

有趣

學習任何一個專業學門有的趣之處,只要有人夠智慧與開創性,隨時都可以從後面超越你,提出一個想法讓你大叫,我怎麼沒有想到,然後就知道原來這個世界很有趣

---
後生可畏XD

星期六, 4月 07, 2007

奇怪的Rate

This site is certified 19% EVIL by the Gematriculator This site is certified 19% EVIL by the Gematriculator

老實說我也不知道這是根據什麼來排的,只是覺得這個分析的圖很有趣就放上來了XD

願望

有時候,最微小的願望,反而很難以達成

---
這就是生活

最近

生活平順的跟鬼一樣,或許就是那麼平順,才覺得這是一個很好的生活吧,每天自由的念書,自由聊天,自由睡覺,自由翹課(這是不好的行為XD)

念書是越來越順了,在此感謝兩位女性朋友,一位為了我在班上的評語而生氣,一位跟我說,你人真的很好,不要理他們說的這些話,老實說,當我自己看到的時候我是置之一笑的,但是我為了這些人而感謝,不過有時候會陷入一種想法,什麼意見是自我該接受的,而什麼是該置之一笑的,如果全盤不接受只聽好話,這就很像綠色只看自由時報是一樣的有趣。

不過目前的我只想做好一件事,把我該學的學好...相信知道我的人都是那個字,有人說blog的Computer 味變的非常重...呃,可能最近無意在blog上搞笑吧,就盡量啦,連寫個孫燕姿都會寫成評論文...回憶成評論啊,我是不是對生活太過於認真了些?或許吧XD

在此提醒Josh,快去買張懸吧,呵,難得他會有肯聽的中文歌手(Josh如此要求,我看中文他肯聽的真的很少XD),雖然他稱張懸是"基本教義派"的歌手(這聽起來像某激進教派,還好張懸唱歌不怎麼激進XD) 這算是一件令人高興的事,有時候也會想起常常傳歌給他的情形XD

---
雜記XD

隱藏

好耶~只是偶爾會無意間跳出來...Orz

ex:寫個信就被人查到了

---
盡量不要留真名在網路上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)

  • 那麼今天真正的主題就是,要把Naïve algorithm speeding up(yen3註:上禮拜是一個怪好笑的舌頭,這禮拜為一個戰鬥機代表speeding up XD)

  • 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)



---
下次寫作時間不要拖那麼長了..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

睡覺

昨日與朋友聊的非常高興,半夜三點才睡....早上醒來已經十二點....連翹四堂課,資料結構與演算法無妨,我一直靠著線上課程和隨機客在學習,現代小說,有點對不起老師。

室友相當的神奇,用手機設了五個鬧鐘,皆在我還沒有聽到時就按掉了,所以今天睡到十二點不是偶然XD

星期一, 4月 02, 2007

下雨

去旁聽隨機客的課,共去了5次,4次下雨,難得的高紀錄,我在上禮拜說,該不會下禮拜會下雨吧,果真成真了,獲得一個"雨男"的稱號,Josh 身體不適,我偷偷錄了音,具有單聲道立體環繞的效果,下次不會再做了,因為隨機客不是一個能接受學生上課的錄音,但是為了Josh著想,就偷偷錄一次吧XD

星期日, 4月 01, 2007

感想

三天看完海賊王50集,我的感想是什麼?

在現實生活中,我的朋友都好厲害(厲害用日文發音)

---
看海賊王是很熱血的一件事XD

星期六, 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

才能?

才能能當飯吃之外還能做什麼?

當水喝XD

---
為什麼我早起就要那麼冷Orz

星期一, 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.)


  • 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)為
        If d[v] > d[u]+w(u,v) then
    let d[v] = d[u] + w(u,v)
    那何謂A phase of improvement
        For each edge(u, v) of G do
    relax edge(u, v)
    問題又來了,試問phase of improvement 要跑幾次才能確保答案的正確呢?
    如果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呢? 方法如下
    • 先對該DAG做topological sort
    • 根據topological sort 的順序,由小到大(slight 上寫由for 1 to n)做relaxing動作
    其Running Time 是 O(m+n)

  • 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

XD

家樂福的XD
家福福的XD2

---
是男人就該逛家樂福

星期六, 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給人活下去的力量

記錄

記錄一:已經校稿的成果拖了三天,我對不起Josh..Orz
記錄二:為了VHDL從九點畫到四點
記錄三:7個人去家樂福買了約4300元

星期二, 3月 20, 2007

balance

從昨天馬不停蹄的念書(假設寫隨機客的上課筆記blog也算),昨天晚餐沒吃,今天早餐只喝牛奶,午餐麵包,由於課相當的輕鬆,還是一樣保持高度的念書熱誠,只是到下午,胃莫名奇妙的痛起來,痛到食慾不佳,這會讓我想起我在高中寫程式寫到胃痛的日子(也是一樣整天不吃),似乎我想做事,就會比Josh還糟,連飯都不吃了XD

念書念到沒時間吃飯,好像不是理由XD

---
睡了一覺之後,只剩些微了

I2A

老酒新調,了無新意,目前自修,準備搭配OOPs上的Instruction to Algorithm Fall, 2005課程來自修,現在用Leture 1學習,效果比直接讀書來的好的多。

看到老師上課的簡報...嗯...不予置評

星期一, 3月 19, 2007

噁心?

efang說"資料結構與演算法0x by 隨機客" 看起來有很噁心的感覺,我看起來覺得還好啊....可能最近傾向寫這些東西吧。本來想寫有關"浮華"的文章,總覺得怎麼寫都不怎麼順手,Josh Ko 已用魔術師的禮帽述說的非常完備,所以我也不多做廢話。

事實上寫了那麼多,只會感覺到自己的基礎深深的不足,遇到證明無從著力,真的要再加油

下期預告:SIC (Simplified Instructional Comptuer), SIC/XE (extra equipment)簡介

資料結構與演算法04 by 隨機客

非正題:嗯,今天是騎車去上課有史以來最塞的一次,也是我有史以來上課最認真聽的一次(拿著筆電狂打)事實上還有很多不懂的地方,寫到這裡就要很感謝,哈密瓜的討論,Josh Ko的支持與校正,隨機客上課的精采,這些都是我邊碎碎念騎車邊快樂上課的動力:)



2007/03/19 資料結構與演算法(下) 呂學一 投影片

今天上課的主題是Minimum Spanning Tree MST 和 Epilogue(時間來不及所以省略)
  • Minimum Spanning Tree - Boruvka' s algorithm
    此問題主在描述,在一圖形G中,每個edge都有不同的權重,找出連結所有node的最輕解(edge 的權重和相加為最小)用比較正式的描述則變成
    • 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被波蘭政府委託在Bohemia這塊土地上牽電線,而讓每個城市都有線,而要怎麼樣牽電線會讓所耗費的成本為最小,就成為Minimum Spanning Tree的原始問題(yen3註:也蠻經典的XD)

    但是先假設一個狀況,才能使用Boruvka' s algorithm
    We may assume that all edge weights are distinct(yen3註:假設每一個邊的權重(重量)是不一樣的,而這樣子的假設不失一般性(JK註:不失一般性的原因,如果遇到這樣的狀況,也可以加以修改而符合假設。),原因是,在真實世界上,也很難找到一樣權重的路)
    (JK註:假設並不會得問題的範圍變狹隘。)(相同權重的邊,稍微加一個數字造成些微的不同,雖然相同權重的邊有些許的不同,但是所算出的結果仍然一樣。)

    那麼解法呢,Boruvka' s algorithm 方法如下(s.9)
    1. 尋找每個node對外連接node的lightest incident edge加以連接
    2. 將已連接的connected component視為一點,尋找connected component 的 lightest incident edge再加以連接
    3. 集合每一個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

  • 事實上為換湯不換藥的方法,採用的是disjoint-set方法資料結構,方法比較簡單(JK註:Disjoint set的實作比較簡單)(s.14)
    1. 每個node自為成一個集合
    2. For each edge (u,v), taken in non-decreasing order by weights
      if Find-set(u) ≠Find-set(v) then
      Output edge (u,v)
      Union(u,v)
      (從權重最輕的邊依序處理,若兩集合不相等,則此兩邊必為相連的MST,所以印出edge(u, v),把u, v兩個集合做一個結合成新集合)
    至於正確性的證明是和Boruvka' s algorithm 一模一樣的。但是效率會好一點,會等於O(m log m) = O(m log n)

  • 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需要再做處理)


臨時趕完有品質很差的感覺(雖然品質從來沒好過),不過換來的是,有一個禮拜的時間可以修正和擴充


Josh Ko 於 2007/03/20 校稿
---
寫到後面有一種很累的感覺

問題

有人跟我反應上課筆記看不懂,我是沒有差啦,反正我還錯誤很多需要訂正:) 現在的確是分段寫(04已經累積至1200字左右,尚未寫完),但是正在想會不會一篇文章太長,所以要分開po(我絕對沒有要賺篇數),這個問題...就再說吧,目前會為了完整性一次po。

下雨

這似乎對要前往台大的我不太妙,不過已經告訴自己風雨無阻了

補記:從7:30騎車至08:50,一路塞車到台大,還好沒有下大雨:)
補記2:回來從1:30至2:10,頗為順利,公里表為7050(三個禮拜前到校為6450)
---
筆電+筆記本 = 全身行囊

資料結構與演算法03 by 隨機客

老師帶領學生去東京比賽,停課一次XD

星期日, 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,方法是,每一個節點建立一個sorted list(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)

  • 解法,則使用(JK註:因為disjoint sets無法在linear time解決,所以才使用DFS)了disjoint sets的概念(s.18),而pseudo code在s.23,至於使用DFS是否為linear time? 見我們需見到subroutine visit中的for loop,此處證明為O(m+n)(yen3註:太晚寫筆記,我忘了怎麼證了Orz)。中間插話,上帝有一本美麗的數學證明本(s.25)XD

  • 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)

    演算法的方法也很簡單,步驟如下
    1. Topological sortDFS讓每個node有一順序
    2. 將圖上的directed edge全部反向
    3. 再跑一次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

  • 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) 是成立的(隨機客將中間證明省略)

  • Randomized maximum cut

  • 掃黑的藝術(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 (列入Hilbert's 23 open questions)

亂數沒有那麼好產生,也早就有人證明出依照現在所存的方法,所產生的亂數都是假隨機亂數(也就是有跡可循的亂數),要能夠產生真正夠亂的亂數依舊是一個難題,世界上沒有一個公平的硬幣,所以就有了一個題外話的數學小證明,號稱20世紀最聰明的人von Neumann,提出了丟硬幣的方法(見投影片p.38)。用了簡單的機率,即得證。


有錯誤請盡量指正,謝謝:)

---
寫的好長好亂,下次我是不是該改成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

更新

如果在做資料性網頁時,盡量保持一個原則,不要翻頁,盡量在一頁顯示重要資訊,所以這一次的更新中,採用隱藏table,左邊為課表,右邊為課程資訊,事實上可以更為簡化,可能會再做更改吧。

星期四, 3月 08, 2007

efang

親愛的宜芳

生日快樂

---

早睡

這學期受到cll老師影響(這名字有仿Josh對於cyy的命名XD),每天過著十二點睡七點起床的生活,剛開始不甚習慣,有很累的感覺,後來越來越習慣,也不太需要鬧鐘,自己就會比鬧鐘早醒來,人跟機器的競賽,似乎有一點有趣:) 身體好很多了,生活也很普通,過著專業念書的生活,有朋友嫌我一個禮拜生了14篇blog有點多,呃,我個人是沒有想那麼多,想寫就寫,有點像散記,沒有那麼專業,所以就將就點吧。好玩的一點是,我和我室友被cll老師在課堂上對學弟妹說,你們的學長很認真的早睡啊,上課都不會打嗑睡,但是有點抱歉的是,我下課會一直睡啊。

筆電對於我這學期上課的影響度達到前所未有的高,每天都要擔心用電問題,卻真的沒有一天把電用完過(螢幕調最暗,CPU速度調最低)。感覺上,這樣子的生活也不錯

最後我想說的,有看我blog的十多個人(假設StatCounter可信),有沒有人要響應我的早睡運動,響應的送台客照一張XD。

---
不過也不得不說,五天中三天八點有課XD

來一點不專業的

早上心生無聊,用LaTeX生了一篇作業題目出來(有需要),看到的人大為驚豔,我卻甚為漸愧...因為我並沒有做很細步的調整。

今日上計算機組織上了一個很簡單卻很重要的語言,事實上我們可以做成如下論述

  • RTL Register Transfer Language 針對整個Computer Organization 的 microoperation做描述

  • VHDL VHSIC Hardware Describe Language 針對boolearn function 抑或是整個電路圖描述
看起來很像,事實上一點都不像RTL相較之下還算高階一些,register 可是由flip flop做出來的,但是VHDL卻要實作整個flip flop(當然,好一點的軟體都會內建寫好的function),兩者的語法我不多做描述,google一下都有。我想說的是。
在撰寫VHDL時,你是在對電路做描述,而不是在寫高階語言,在寫作時,應對電路存有一個大局觀

這是一個很簡單的概念,也不難,問題出在那?VHDL有for, if, case switch, while, 甚至連bit vector都有了,你寫起來很像一個高階語言,但是不代表他如你所想的

if(K==1) R1 <= R3;
else R1 <= R2;
這樣子的程式碼在C/C++等高階語言中,大部分都是循序執行,看完if再看else,如果if成立,program根本不在乎else發生了什麼事。但是在VHDL中,這個if else乃是同時被執行的,意思即是,K只有0與1,所以我們會在R2和R3 assign 給R1之前,加一個K的2 to 1 multiplexer ,就可以完成選擇動作了,這也是同時被執行的意思。

那麼我們再來看一個在電路中根本不存在的東西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

寫ADT

有時候,寫簡單的ADT真的會感到厭煩...感覺上都在做同一件事,只是把名字換一換而己。

---
但是不寫也不能說你會..XD

星期六, 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....

課程更新

閒來沒事,自己做了一個課程網頁,老實說就只是把sidebar上的schedule複製貼上,再加上一些課程網站資訊,等以後有多一點的資訊就隨時更新吧

---
課程網站上線的竟然只有兩個....

星期五, 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

---
人生吧,就上課,不要想太多

開玩笑

什麼時候我的約會可以跟場務一樣多...

---
禮拜五聽說要去實習足球場務XD

星期三, 2月 28, 2007

228

228對我而言的意義是什麼,呃,早上有早餐聚,晚上有工院盃兩場籃球場務到晚上十點。此外還有更重要的

Josh Ko 生日快樂

發這種生日文好像不符合我的style,但,高興就好:)

星期二, 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

星期日, 2月 25, 2007

清理電腦

花了二個小時把電腦的灰塵清一清,清的時候總有慘不忍睹的感覺,雖然這篇很像記事,但是還是想說,讓電腦盡量沒有灰塵吧,有灰塵會短路的...等會燒起來或過熱總是不好的...

---
電腦灰塵多是因為風扇(3個12cm)太多....

活動

今日因為工院盃做了賽程表...感謝我的mx1000和小白,也感謝我的筆電,更感謝小花,反正,做的蠻順利的,不過用PhotoImpact做賽程表,絕對是一個dirty work。對我而言,每次辦活動似乎都要生一堆讓人覺得麻煩的表,還好不用常常生..XD

到底有多複雜,舉例一張。(看!)

---
以後做這種事,要收雞排

星期六, 2月 24, 2007

到校了


如預期計畫把桌子整理如照片,這樣子會蠻方便的,只是兩台都是windows是唯一的敗筆..XD 只是這桌子出奇的大,照學校其他桌子的放置,肯定會覺得臃擠,這張桌子卻無感覺,非常好

---
筆電上的一堆設定懶的移到桌上型去了...XD

星期五, 2月 23, 2007

想換mac

目前自己有兩台電腦 (一桌機+一筆電),倒是很想把筆電換成ibook之類的,呃,換成MacBook是不太可能的,筆電配備如下,約為05年10月購入(所以已過保固...XD)


  • Pentium M 730(1.73Ghz,Dothen)
  • DDR2 1GB SDRAM(我自己買了512MB加上去)
  • 14.1 吋WXGA(1280*800)
  • Intel GMA 900(換言之就是內建)
  • 60gb HardDisk
  • DVD-ROM/ CD-RW combo
  • 無線網路(802.11g), bluetooth

當然,桌上型我想還是保持原樣,筆電,想換台ibook,不過呢,好像機率不大,我應該要來列個WishList,不過在這邊做一個如下的建議,如果口袋麥克麥克的人,可以買PowerBook G4,C/P值頗高。但是對我而言,就算要拿這台筆電換的話,我也會把筆電大修(蓋子嚴重損傷+鍵盤磨損,我打字太大力...Orz),當然,如果有機會換機的話(我的筆電換成ibook G4),我會把我的電腦大修再換...當然,也希望有人有看到的可以幫我注意一下,謝謝:)。

---
說那麼多,終究是幻想...XD

sidebar

新增label block,事實上只是超連結連一連而己,哈哈,但是由於label是blogger新版才有的功能,新發的文章當然會有label,但是以前所發表的文章就不一定了(懶的整理,哈..XD),事實上應該再新增一個Recent comment的block,只是我不會寫JavaScript(應該是說,對blogger不熟),暫時擺著,或許是等有現成的..XD

有aocwind的幫忙,用了一個Recent Comment,但是相較之下是一個非常慢的方法(先把資訊抓完再轉成一般格式),剛剛閒閒無事,看著Joshsoft源碼發呆,發現,他的sidebar關於文章資訊和回應統計的部分,我猜,在每篇文章產生的同時,就會把該有的資訊,assign 給自行定義的array,之後就會相當好寫,只是我不太能理解,每篇文章怎麼自動產生這些資訊去assign的...看來我學的JavaScript根本就簡單的跟什麼一樣...XD

雖然現在sidebar有Recent Comment,大概幾天過後就會移除,因為我覺得效率不彰是一個原因,另外一個原因,我沒有自己寫也是一個原因就是。
---
移到上面來之後,似乎有排擠效應。

轉換

只會C++而盲然的寫Java是一件很危險的事,至少就我今天簡單的寫作中體會到非常多。

以我自己寫的而例。

class UnitBlock{/*.....*/};
UnitBlock[][] u =new UnitBlock[BombSolution.X+2][BombSolution.Y+2];

這樣子,還是不能使用的,因為根據說法,這樣子充其量只是array of array of reference,根本沒有物件被產生。如果使用會有Exception產生(只學過C++的我第一次就卡在這裡),所以得加入

for(int i=0;i<u.length;i++){
for(int j=0;j<u[i].length;j++) u[i][j] = new UnitBlock();
}

讓每個reference完成指向new所創造的物件上,我不甚聰明,今天就卡在這個問題上。

另外的想法,Java 的class method 本身的傳值方式為 pass by value ,所謂的pass by reference,是因為Java本身的object在利用new做分配時,就是reference,所以做為傳遞時,也是傳遞reference(也就是說reference本身就是該object的value)。這點跟我原本預先Java為pass by reference 相差甚遠。

當然,自己第一次寫的時候,也發現一個有趣技法,宣告一個class,class method皆為static, 那麼這些class static method,在還沒有任何object被建立時,就已經實作之,這樣子很像C++ 的namespace 的技法(當然C++ class要這樣子做也是可以的)。只是和Josh一討論,發現這不是什麼了不起的技法,Java 的整個Math都是只有class static method,討論之後才得知,事實可以。

class BombSolution{
private BombSolution(){};
}
把defaule constructor為private,使得任何物件無法為之產生,我不得不說,好方法,而且把我思考的這個技法發揮到一種美麗的境界。

事實上還有很多白癡錯誤,但是從C++ 跳Java 還是一個很有趣的過程

---
感謝今天容忍我的聊天一直lag

星期四, 2月 22, 2007

Java

感覺好麻煩,很直覺的東西會有exception,慢慢來處理吧...XD

星期二, 2月 20, 2007

制約

原本以為什麼人事物都不會有綁住我的可能,第一次有被制約的感覺,呵。

---
以前的我還真自大XD

星期一, 2月 19, 2007

踩地雷完成

小程式,180行完工command line,頂多只是在尋找空白的時候用了簡單的bfs,但是不可否認的,我還是對interface的設計實在是沒什麼興趣。

---
實施計畫下一階段

星期日, 2月 18, 2007

新年到哩

大家新年快樂,身體健康,萬事如意,豬年行大運^^

星期六, 2月 17, 2007

節目

我對於三台的新春特別節目,稱之為新春特別難看節目,重點是,你得陪家人一起看

---
或許再過幾年就習慣了XD

星期五, 2月 16, 2007

11

是個普通的數字,但是卻是我下學期要修課的門數...我要怎麼念書...老實說連我自己都不知道。就試著去念吧。船到橋頭自然直,不要沉了就沒事。

大二下可能是大學中最多課要修的一個學期。管他的,就這樣子過

sidebar更新

呃,課表還蠻明顯的,但是多了一個music's link,目前暫時不知道要做什麼用,以後希望改成有用一點,現在只能做到這個樣子,不過都有了,我還是介紹一下好了。


  • 張懸 - 我想這就不用介紹了,一個讓人有勇氣活下去的聲音

  • 陳綺貞 - 有人稱之為音樂才女

  • Mai Kuraki 倉木麻衣 - 實力派唱將,唱了非常多的柯南主題曲(事實上我聽不懂日文)

  • Lene Marlin - 在previous blog有介紹過

  • LeAnn Rimes - 在previous blog有說過,但是未詳加說明

  • 歐噴愛 OpenEye - 一個樂團,但是不只是一個樂團。

  • Do As Infinity 大無限樂團 - 一個解散的團體,主唱伴都和美子現在單飛中

  • Every Little Thing 小事樂團 - 一個超過十年的團體,正在習慣中

  • The Corrs 可兒家族合唱團 - 暫時不知道怎麼介紹的樂團..XD

  • Savage Garden 野人花園 - 兩個團體,因理念不合就解散,有許多著名的情歌



---
事實上自己都知道自己有介紹等於沒介紹,但是還是想到就寫吧

課表

96 Spring課表已經排完,大二下的精采程度超乎想像,剛好修滿25學分(重修5學分),禮拜一旁聽臺大資訊隨機客的資料結構與演算法,禮拜二滿堂,禮拜二至四上至第九節,比較輕鬆的就禮拜五,但是有實驗課...看來大二下的睡眠會比大二上更正常(大二上整整比大一整年平均提早了一到二個小時睡覺)。

爆肝,意指催殘自己的身體,但是大二上睡更多,念更多,反而學的比較好,我想,慣性睡嚴會對身體有益,故,努力試試。

---
sidebar增加課表部分(style from:Joshsoft)與pdf

星期四, 2月 15, 2007

失敗

拿了Mac OS 10.4.7 無論怎麼灌都會產問題,當然,我沒有試著去排除,因為每次都卡在怪異的驅動程式上,拿了家裡的三台電腦測試,自己的筆電無法開機,家中電腦一台無法開機,一台灌好後無法開啟圖形介面(開機就卡在這樣子的訊息上),暫時宣告失敗,待抓完10.4.8再測試一次吧。

---
離Mac OS要用在PC上還很遠很遠

星期三, 2月 14, 2007

情人節

從我有記憶以來,情人節似乎從來沒忘記過,但是也從來沒有去過這個節日,今年的情人節,老實說,還是一樣平靜吧,常常思考,在一個商人操作下的節日產物,還剩下什麼意義?但是我的胡思亂想說,這給情侶是有勇氣在這一天做什麼事,那麼我今天做了什麼呢?不斷的重灌電腦,在Windows 和 Mac OS 中徘徊,似乎在逃避些什麼。


But I do love you (LeAnn Rimes, I need you, 2001)

I dont like to be alone in the night
And I dont like to hear Im wrong when Im right
And I dont like to have the rain on my shoe
But I do love you, but I do love you
I dont like to see the sky painted gray
And I dont like when nothings going my way
And I dont like to be the one with the blues
But I do love you, but I do love you
Love everything about the way youre loving me
The way you lay your head
Upon my shoulder when you sleep
And I love to kiss you in the rain
I love everything you do, oh I do
I dont like to turn the radio on
Just to find I missed my favorite song
And I dont like to be the last with the news
But I do love you, but I do love you
Love everything about the way youre loving me
The way you lay your head
Upon my shoulder when you sleep
And I love to kiss you in the rain
I love everything you do, oh I do
And I dont like to be alone in the night
And I dont like to hear Im wrong when Im right
And I dont like to have the rain on my shoes
But I do love you but I do love you
But I do love you but I do love you



情人節快樂

試灌Mac OSX


用VMware灌Mac OSX 10.4.7,目前還算順利中,速度不會很慢,用虛擬的好處是,省很多麻煩,壞處是,慢了些。等我真的裝上去再來說吧...先試著灌灌看,畢竟這是我完全陌生的系統。

星期二, 2月 13, 2007

Vista


以前身為一個愛測試的人,最近終於入手,在筆電的記憶體變成1GB之後,終於有硬體可以做一個測單的測試了,不過這硬體也沒有好到可以開Aero glass介面,就只是很普通的試用。什麼時候會正式使用呢?大概等學校有授權,常用的軟體不相容的再少點,或者是出個Service Pack1,等穩定點再說。

就驅動程式而言,我一灌會抓不到音效卡和讀卡機驅動程式,其他都抓完了(筆電約為前年九月時所購買),經過更新,就全部抓到驅動程式了,相當方便,就常用程式而言,我最常使用的Foobar 0.94 BlackIce 版無法使用,另外一版從Ptt的Ezsoft找到版本依然無法使用,後來使用foobar 0.942原版(對,就是長的最簡單的),還有0.83繁體中文美化版,算是可以順利使用了。嘸蝦米部分,偽蝦米可以輸出文字,但是backspace鍵失去作用,我放棄,使用官網出的for Vista 測試版暫時用一下吧,Alchohol 120%我的手上版面過舊,一灌就當掉,連安全模式都進不去,我只好再重灌一次Vista,所以目前沒勇氣再灌第二次(我還想試用久一點XD),Kaspersky AntiVirus 手上只有5.0版,所以並沒有灌下去做測試,原因,官方for Vista beta版剛釋出,我想我這版也沒有必要測試了。不過就我愛用的bbs閱讀軟體而言,PCman2004 Combo 在Vista上跑起來有一點頓的感覺,尚無解決之道,此外還有一堆軟體沒有試,就讓我偷懶的略過吧。

有人問我,Vista去掉Aero galss 似乎並無可看性,為什麼我還要測試,一方面是手上有軟體不試可惜,一方面是,看看賣什麼藥也好,我不否認,Vista是多了很多新東西沒有錯,但是對於我們真正能影響的,似乎越來越少,以一個桌面設定,以前單視窗數個標籤搞定,現在是一個視窗之後,你還要分別按,是很細沒有錯,但是仔細一看是換湯不換藥的東西,其他東西,感覺上都是經過一層包裝吧,對於用熟的人,多了那層包裝反而會覺得麻煩吧,因為也不是那麼直覺。到現在為止,我還是不知道把我的ADSL撥號捷徑放在桌面上,現在我連線都要按好多下...

就專業使用者而言,或許Vista是個好東西,就現在的我而言(單純的寫程式和寫cwTex),XP就很夠用了。

星期一, 2月 12, 2007

聚餐

和高中社團同學聚餐,看到學長學弟,甚為高興,也幫自己的筆電買了512mb的記憶體,把筆電增至現在認為基本的1gb,使用上順暢許多。

這樣子的聚餐,思考的碰撞,而激出許多想法,都算是相當正面的。

星期四, 2月 08, 2007

舊文-絕對 | 衣性戀

這是在我已經沒在用的MSN Space(現在叫Windows Live Space)轉過來的文章,是對於一本書的感想


絕對 | 衣性戀 books
張小虹著,時報文化出版

我還蠻高興我看了這本書的,因為有時候學寫程式還蠻煩的,偶爾看個書,的確能讓自已獲得最大放鬆
哈哈,我的思考還是和以前一樣簡單
這本書我想就書名本來解釋在寫什麼(這就是文學的無限想像兼無限無聊之處),由於作者是台大外文系教授,所以我把絕對翻成absolutly,我想會比較接近作者想要表達的意思,那麼衣性戀呢?
所謂的衣性戀,衣服和性(sex)之戀焦不離孟,孟不離焦的關係,人需要用衣服去表現的sex一面,但是sex也需要衣服來烘托
我想,我的解讀是這樣子
對喔,我忘了對作者做一個簡單的介紹,張小虹教授,我曾經參加聯合文學文藝營聽到她所講的"城市花衣裳書寫",當場我對她留下非常深刻的印象,因為,我的墨水本來就不多,聽到她對張愛玲的解讀,實在是讓我有一番新的體會,而不是課本考試上的解讀錯誤,哈,在台大執教多年,對女性身體的研究,算是一個非常的精準定位
感覺上自已做了介紹,等於沒有做,想要了解,就看看她著作吧
怎麼說?
成英姝說,基本上我不會很喜歡去訪問一個作家,因為如果我想要知道一個答案,我就會從他的著作中來尋找
那麼一般人幹麻還要訪問,因為,笨蛋者如我,並不是會對作者所要表達的有所了解,外加不是每個人都有著作,所以訪問還是有訪問的好處,哈
回到正題,這本書到底在寫什麼? 就是一種身體情慾表現和衣服的關係
她對於每個名牌的解讀,我實在是不懂,因為我平常並沒有穿這些名牌的習慣(學電腦的我,只要求吃的飽穿的暖,偶爾喝個starbucks是我最大的消遣XD),但是我從這些文字中看出一件我認為我想的實在是有夠淺的事
當人穿一個名牌的時候,並不是要注意它的價錢和名牌價值,而是要注意這種剪裁和搭配的背後意義
如果我看到一件衣服能說,好漂亮,而不是說好貴,至少我前進一大步了。
所以一個真正的好設計,在於拿掉他的名牌過後,你仍然會買它,這個才是真正的名牌價值
而不是在於,把名牌拿掉,你完全沒有購買這一項東西的動力
我想,這本書就是提供我的思考,也對我一看到牛仔褲就會慣性看別人屁屁是否有levi's的mark,做了一個非常合理的解釋,但是我還是得說,我不是變態XD
有人跟我說,levi's的價值,在於他非常好穿,嗯,那麼我還相信這個名牌的價值,但是我沒有穿過,所以我不知道了,我身上的牛仔褲一件都是299的XD
完了嗎,當然還沒
to be continued



絕對 | 衣性戀

張小虹著

現在才發現,原來我的前文講了太多廢話…而本書的重點,身體情慾和衣服的關係?
抑或是說,設計師所發展出來的衣服,適時對女性做了情慾的釋放?
我不知道,畢竟我不是一個對衣很有研究的人,如果有研究,我也就不用看這本書了,是吧

這會讓我想到一個很有趣的問題,為什麼現在的女生喜歡穿較小號的衣服
換句話來說,喜歡穿,烘托出自己身體曲線的衣服?

所謂的衣服,是對自己情慾的一種釋放
女生穿的有曲線,是愛別人看她? (這裡有可能是男性或是女性)
抑或是說,吸引他人的目光可以建立起自已的自信
還是說,我想太多,現在時下的少女根本就是追求流行,而忘了背後意義
就算衣服小到讓自已覺得不舒服,還是努力的追求下去

我想,有些女生是不會那麼笨的

那麼我又想到另外一件事,為什麼有些女生穿短裙時,抑或是那叫啥....短的褲裙?
啊知,這不是我的專業領域.....
坐下時會拿包包遮住自已的大腿......hmm.....
我不是說為什麼不讓男生看去表現身體情慾
事實上,這想法有著無限可能
有可能是,追求流行盲目過了頭,事實上忘了保護自已身體的重要性?
有可能是,只為了給自已最喜愛的人看(我承認這個假設不怎麼好...XD)
那麼我又思考了一個問題,為什要讓自已處於難以處理的狀態呢?
我不知道......

當然,我自已也不是追求流行的人,我的衣服大概都是黑的,哈,什麼流行服裝也是跟我絕緣XD

所以我可以站在流行外去觀看這社會嗎,也不盡然,因為,我本身也在流行中觀看流行的
難免會有失真吧

老實說,這話題對我而言還是太難,因為我無法把這社會的情慾切入的太深....

就寫到這裡吧...




---
現在看,還真不像是自己會寫的東西,偏偏這東西還是一年前寫的XD

有關寫blog這回事

嗯,自從裝了計數器以來才發現,原來我的blog是有人在看的,而且人不少(驚),十個或許不是很多,但是我的預料就是每天三五個吧,在此感謝每天有來看的人,其中有一個hinet ip,顯示在桃園,2天之中看了15次,老實說我還真的不知道是誰(不是我XD),當然,也有很顯眼的Mac OSX,這一看也知道是誰做的..XD

有很多朋友對我的blog做過感想,非資工的朋友跟我說,這blog火星文真多,呃,我看感覺還好啊,畢竟我很偷懶。也有人說,看的懂的東西比較多了,以後還是寫些大家看的懂的東西吧。我的朋友也有人對我說,blog的右邊(sidebar)比左邊(content)好懂,還有些人欣然同意,這些都是我意想不到的意見。

就一個寫作者的立場,當然會希望越多人看越好,但是就有又如

"沒有必要把每件事搞的跟跨國企業一樣,搞的越大越好,然後搞的很累,事實上不一定會達到你想的要效果(張懸)"
寫作是一件令人快樂的事,這blog的技術文變少是不爭的事實(因為我本身也沒什麼技術可言),有任何的學習心得,我會非常樂意分享,當然,會分享個人的感覺,但是我想我不是一個愛寫風花雪月(即使我當下寫的這篇文章就很像風花雪月(笑)),想寫什麼就寫什麼,頂多我做到
生活和學習keep a balance
寫作也可以很小眾的分享啊,雖然我從不認為我寫的東西會大眾化XD

--
當然,我覺得我會越來越偷懶XD

睡前看到一段

Java垃圾回收器不等於destrotor,它只負責回收記憶體

原來我的理解是完全錯誤的...看完有完整心得再做一個報告XD

星期二, 2月 06, 2007

表面的和平

陳綺貞是一位很有名的非主流歌手,若要提到在台灣的非主流,張懸、陳綺貞、蘇打綠,算是其中較有名的,張懸是我最早接觸的,也是我最喜愛的一位,而陳綺貞我從這個寒假開始聽,我聽了她最近的一張專輯"華麗的冒險(2005)"其他的專輯我大概會陸續聽完。

聽這張專輯的心得啊,聲音雖然讓人覺得很溫柔,但是和張懸所給的平靜是完全不同的,我曾經很懷疑,為什麼會有人把張懸和陳綺貞拿來做比較,這兩個人所表達出來的感覺是完全不一樣的,兩個唯一相同點,就是對音樂都抱持有自己的想法與熱情,聲音聽其起來,溫暖中帶有華麗,和張懸一樣,聽久都不會膩(相較於市面上的流行音樂,很多都過於芭樂),整張專輯都很推薦,但我特愛"表面的和平"


表面的和平 (陳綺貞,華麗的冒險:2005)

我也無所謂
你說什麼都對 當我已經變成你零碎的時間
終於有機會 讓自己再沉澱
讓我回到過去不再為你而
分裂

我竟然如此 執著於星座配對
但是對我們的感覺我比誰都要強烈

我曾經仔細聽 你說的大道理
我曾經認識你 像小孩的任性
我曾經凝視你 你眼睛裡的熱情
小心不跌入你流失的回憶

終於有機會讓自己再沉澱
讓我回到過去毫無恐懼的直言
是你太鬆懈還是我一向太尖銳
當你不止一次脫口而出曾是對別人的稱謂

我曾經仔細聽 你說的大道理
曾經小心翼翼 維持表面的和平
曾經認真的反省 不唱昨日的歌曲
小心不跌入你流失的回憶

為了不讓你傷心 傷了我的心



---
參考連結: wiki:陳綺貞

美麗


事實上排版久了還是會驚豔於LaTeX的美麗,這是會上癮的,看code再看結果,有一種阿匹婆變林志玲的感覺XD