2011/10/27

4個人顧一隻魚顧到飛走

http://www.youtube.com/watch?v=WmtEeAd2DMU&feature=player_embedded

「畢業」

鳳凰木吐露的豔紅,又是候鳥南飛,莘莘學子畢業的時節,天下沒有不散的宴席,鐵人
賽也是,就用「畢業」兩字,做為第四屆鐵人賽分享的休止符。

本系列文章提及課程數,超過30個,課程之廣涵蓋軟體,硬體,應用及理論四大領域。
無非希望日後資訊科系的學弟妹,或者想要唸資訊系的高中畢業生,在搜尋到相關文章
時,能對科系與課程有一個更深入的了解。

也感謝由ithome的SEO做的相當傑出,讓這「資訊學院的30門課」一系列的原創文章,
能夠讓更多人看到。

人外有人,天外有天,一直是我追求知識的態度,天下無處無導師,每一個人,每一件
事,都有在下面的我可以學習的地方,鐵人賽中,百忙之中,協助我更正錯誤的每一位
邦友,都是我知識上的導師。我的學習態度就是,我不懂沒有關係,我只要知道哪裡錯
誤,把他更正過來,往後就是內化成自己的知識。在每個領域都有存在真正的大內高
手,只要能習得這些高手的千分一,就值得欣慰了。

畢業後,面臨的就是人生大轉折,大致上會有幾個方向!
1. 當兵。
2. 國防役或是替代役。
3. 國內或國外繼續深造。
4. 就業。
5. 嫁為人婦。
6. 家裡蹲。(俗稱失業)
而像我比較特別,我是選項六,在家養病,對於人生也有別的感觸,人生最最最重要的
莫過於一個健康的身體了。在鐵人賽的賽事中,真的有考慮過中途放棄,因為這樣每天
擠出一篇原創文章的辛苦,每一位認真的貼文的參賽大大應該最能體會,帶來身體上的
負荷,也與日俱增,不過也終於完成劣文30篇,畢業了。
我曾經想過,如果我沒有重大傷病,我現在人在哪呢?決對不是現在這個地點,這個位
置。而或許是老天爺覺得我人生過的太過於辛苦,要給我一個喘息的機會吧。

2011/10/26

RE: IPTV涵蓋了哪些大學課程

IPTV涵蓋了哪些大學課程,
機上盒 ==> 嵌入式系統 [url= http://ithelp.ithome.com.tw/question/10076053]計
算機組織與結構[/url]
機上盒內AP與遊戲 ==> [url=http://ithelp.ithome.com.tw/question/10074304]計算
機繪圖[/url] [url=http://ithelp.ithome.com.tw/question/10078221]電腦動畫
[/url] 網頁程式設計
機上盒內OS ==> [url=http://ithelp.ithome.com.tw/question/10073965]作業系統
[/url] 系統程式 [url=http://ithelp.ithome.com.tw/question/10073837]編譯器設
計[/url]
媒體撥放器 ==> [url=http://ithelp.ithome.com.tw/question/10074080]數位影像處
理[/url] 視訊壓縮 通訊理論
派送網路 ==> 多媒體通訊
頭端網路 ==> 計算機網路 [url=http://ithelp.ithome.com.tw/question/10074917]
網路與通訊概論[/url]
快取主機 ==> 網際網路技術 作業系統
入口網站 ==> [url=http://ithelp.ithome.com.tw/question/10075109]網際網路技術
[/url]
資料庫主機 ==> [url=http://ithelp.ithome.com.tw/question/10074591]資料庫系統
DBMS [/url]
監控程式 ==> [url=http://ithelp.ithome.com.tw/question/10075384]網路程式設計
[/url] [url=http://ithelp.ithome.com.tw/question/10074591]資料結構
DataStructure[/url]
使用報表分析 ==> 統計學 圖型識別 分群法
[url=http://ithelp.ithome.com.tw/question/10076977]演算法[/url]
VOD主機 ==> 網路程式設計 多媒體通訊
視訊編碼器 ==> [url=http://ithelp.ithome.com.tw/question/10079246]多媒體通訊
[/url] [url=http://ithelp.ithome.com.tw/question/10074080]數位影像處理[/url]
視訊壓縮
上片系統與儲存空間 ==> 網頁程式設計 [url=
http://ithelp.ithome.com.tw/question/10076053]計算機組織與結構[/url]
數位版權管理DRM ==> [url=http://ithelp.ithome.com.tw/question/10078926]密碼
學[/url] 資訊安全
哇咧,一個IPTV幾乎把CS傳統應用課程全用上了!!!!
當然如果拿PS3或XBOX 360來套上去,應該也是差不多。
但是我想要表達的是,真的真的學校這些課程真的用得上。

2011/10/25

多媒體通訊

多媒體通訊包含有多媒體的應用及不同網路的結構 這些包括很多不同媒體的數位表現
形式 還有它們不同的壓縮方法 以及不同媒體應用時它們在通訊上的不同需求 不同類
型通訊網路的操作 以及所需要的通訊規約 還有因應多媒體需求時 這些規約的演化
課程綱要 一 多媒體通訊
二 多媒體訊號表示法
三 多媒體壓縮
四 多媒體通訊的標準
五 公眾電話網路
六 區域網路
七 網際網路
八 無線網路
九 運送規約
http://www.cm.nctu.edu.tw/course/course_cm.php?Sn=33
上面是電機領域的課表,資訊學院的多媒體通訊著重於protocol與系統架構的介紹,以
有別於通訊理論這門較偏重於EE的課程,通訊理論這門課我大學時也有修過,覺得滿有
收獲的。
RTP
VoIP(VoBB)
VOD
IPTV

2011/10/24

密碼學

資訊學院的30堂課-密碼學

發行量超過一千六百萬張、號稱「絕對不可能被破解」的台北悠遊卡,不敗神話破滅!
前一陣子悠遊卡被破解的新聞,大家應該都還有印象吧。crypto1是悠遊卡所使用的加
密演算法則,居然在維基百科就有連結,而且開宗明義說,幾乎是沒有保護狀態。原來
讀取我們的悠遊卡,跟讀取我們數位相機拍出來的照片,保護等級一個是沒有保護狀
態,一個是幾乎是完全沒有保護狀態("the security of this cipher is ... close
to zero")。到底crypto1演算法哪裡錯了?或者我們教的密碼學哪裡錯了?
其實google的PageRank並無法去篩選文章的正確性,常見google把錯誤的文章放在搜尋
的第一位,比如: 你用RSA去咕台灣網頁的第一頁,他是一篇錯誤很多的文章,繁體中
文第一個連結,http://www.mathland.idv.tw/life/rsa576.htm,雖然RSA的演算法難
度基於質因數分解,但跟網站說的完全不同,RSA其中一支public key開宗明義說了由
兩個質數相乘而成,所以不是質數!!!

The RSA algorithm works as follows: take two large primes, p and q, and
compute their product
n = pq; n is called the modulus

不過這個網頁高懸在google search繁體中文第一位超過一年。RSA相關的連結很多,而
且這是屬於數論與演算法的範疇,我就曾經在演算法這門課Implement過RSA的
Project,只是,寫過的人都知道,實作一個基本的RSA加解密並不難,難的是如何使用
長整數,程式語言32位元長的整數或者64位元的整數都不足以提供足夠的保護,我當時
還很笨的去Implement超長整數的四則運算,很顯然的我的程式有bug,而且沒有適當處
理逸位問題,經過時空的演進,現在要在常見的軟體平台找到超超超長整數的函式庫,
已經不是難事,而且效能還不錯。而crypto1演算法的致命錯誤就在於???金鑰太短。

MIFARE Classic是近年來最廣泛被使用的非接觸式智慧卡,應用在門禁、大眾運輸工
具、電子錢包等系統上。MIFARE Classic上密碼保護機制與結構已被發表在許多的論文
上。在本論文中我們提出各式各樣在MIFARE Classic攻擊實作的經驗。我們實作兩類的
攻擊:一是假造讀卡機、二是側錄合法的交易。第一類的攻擊在兩天內利用NVIDIA高速
運算顯示卡上實作密鑰的窮舉搜尋法與隨機數和連認證的漏洞離線的破解卡片上所有的
金鑰。第二類是針對MIFARE Classic加解密器: CRYPTO-1上攻擊方法的改進。經過我們
的改進,攻擊者不僅可以破解自己的卡同時也能破解別人的卡。我們所實作的攻擊徹底
讓MIFARE Classic的密碼保護失去效用,讓未經授權的攻擊者能任意更改卡片上資料,
如同沒有任何保護的記憶卡。更進一步,我們提出有關防止目前已知的攻擊的建議,而
此防禦機制加強對卡片資料的防護並加強後端清算機制的效率。
http://ndltd.ncl.edu.tw/cgi-bin/gs32/gsweb.cgi/login?o=dnclcdr&s=id=%22098NT
U05442107%22.&searchmode=basic


http://www.rsa.com/rsalabs/faq/files/rsalabs_faq41.pdf

2011/10/16

資訊學院的30門課-演算法與google code jam

Google Code Jam 2009我參加過一次,依當時的評分標準,至少要能寫出一題,能夠在限定時間內跑完的code,才能晉級。但是幾乎都是要用dynamic programming的技巧,我用遞迴解一題後,想當然爾,效能不佳,所以我就放棄了。

大家可以上去看看
http://code.google.com/codejam/

既然是軟體,就不能不講到正在全球各地舉行的google code jam 2011,

難度極高,在資格賽的幾個題目中,解出來的難度不高,但是要在極嚴格的執行時間跑出來,

就不能夠亂寫囉,除了要有一台不錯的運算平台之外,挑選的程式語言也很重要,例如很多人用C/C++,

但是最重要的莫過於演算法了。因為這些題目都會讓人無意間進入一種迷思,大部分是divide and conquer的題目,

但是重複計算了一部的運算而不自知。而且某些題型在小範圍的資料中,可以使用遞迴解,但是太多層function call又往往使效能不彰。

演算法教科書提到dynamic programming,當初課本只有兩個範例,所以其實讀的不是很懂,這兩天我又去書局罰站了,翻了一下培養與鍛鍊程式設計的邏輯腦。其實只是用二維或者三維array把之前算過的值儲存起來,碰到一樣的狀況,就直接查表就好,大家都知道查表可以很快,就不用丟到遞迴裡或者loop裡去跑了。不過我相信以mis的programming應用角度而言,不要說dynamic programming,連遞迴我也只用過兩次。

另外瀏覽一下放在他隔壁的Short Coding 寫出簡捷好程式-短碼達人的心得技法
不過這本書是會讓人頭暈的書,很多觀念以前都讀過,
有些小技巧的確在不失可毒性的狀況下,可以讓程式更短,甚至縮短巢狀level,讓程式更好看,有空可以看看啦,但我真的如果如書這樣寫出來,我自己都會頭暈吧。




談到google程式大賽

雖然我不曉得程式怎麼寫效能才高,但可以分享為甚麼我的程式跑的慢,為甚麼大的資料集運算很慢,

一般網頁或視窗是程式設計課程中,都沒有注重在如何讓程式跑的最快,有志參加的coder,一定要記得這些重點才能晉級。

2011我做的是第三題

Problem C. Candy Splitting

http://code.google.com/codejam/contest/dashboard?c=975485#s=p2

提示一下,弟弟的加法就是XOR,哥哥才會進位的加法。這樣題目就容易理解了。

像我這種程式效能上的差異,不是單純使用高級硬體就能cover掉的。

#include
#include
#include
using namespace std;
int main(int argc, char *argv[])
{
int compute(int *candy, int candyNum, int s, int x, int p, int max);
FILE *input;
int i, j, x, sum, ans;
int looptime, candyNum;
int candy[1001];
input = fopen("D:\\Dev-Cpp\\3-test.txt","ro");
fscanf(input,"%d",&looptime);
for(i=0; i
fscanf(input,"%d",&candyNum);
sum = 0;
x = 0;
for(j=0; j
fscanf(input,"%d",&candy[j]);
// sum += candy[j];
}
for(j=0; j
//printf("%d ", candy[j]);
sum += candy[j];
x ^= candy[j];
}
//printf("=%d",sum);
ans = compute(candy, candyNum, sum, x, 0, 0);
printf("Case #%d: ", i+1);
if(ans==0) {
printf("NO\n");
}else{
printf("%d\n", ans);
}
fflush(stdout);
}
system("PAUSE");
return EXIT_SUCCESS;
}
int compute(int *candy, int candyNum, int s, int x, int p, int max) {
int max1,max2;
int a, b;
if( candyNum == 0 ) {
return max;
}
a = x ^ candy[0];
b = p ^ candy[0];
if(a == b) {
max = (max<(s - candy[0]))? (s - candy[0]): max;
}
//printf("[ a=%d, b=%d, x=%d, p=%d, max=%d ]", a, b, x, p, max);
max1 = compute(candy+1, candyNum-1, s-candy[0], a, b, max);
max2 = compute(candy+1, candyNum-1, s, x, p, max);
return (max1>max2)?max1:max2;
}
這邊用到recursive去解,雖然CS教科書上recursive的例子很多,但在google code jam的題目中,
幾乎都是效能殺手。
max1 = compute(candy+1, candyNum-1, s-candy[0], a, b, max);
max2 = compute(candy+1, candyNum-1, s, x, p, max);
因為例如「第三堆到第六堆的XOR」與「第四堆到第七堆的XOR」,其中「第四堆到第六堆的XOR」是不是被重複算了。
資料集越大,被重複算的運算就越多,程式就越慢。
到這邊是不是有大大已經想到,大的資料集要怎麼處理了呢?