看看台湾的计算机概论是怎麽写的

习惯单恋

http://www.csie.ntu.edu.tw/~kmchao/books/bcc/index.htm

計算機概論　

台灣大學資訊工程系 趙坤茂教授
海洋大學資訊工程系 張雅惠教授
台灣大學資訊工程系 黃寶萱助教

全華科技圖書公司出版

(本書第一版於2004年7月29日出版；修訂版於2005年暑假問世。)


摘录：

2004年仲夏 摘自《全華計算機概論》

趙老五四三


--------------------------------------------------------------------------------

台北101大樓在2004年落成，號稱是當時世界第一大樓。本書作者趙老從上個世紀起，就住在1011樓了，什麼？1011？那不是超高樓層嗎？啊哈！其實是二進位的1011，也就是1 x 23 + 0 x 22 + 1 x 21 + 1 = 11，是十進位的11樓啦！


--------------------------------------------------------------------------------

「二八年華」常被用來形容含苞待放的青春歲月，指的是「二乘以八」等於十六歲左右的年輕朋友們，本書作者趙老已是百戰沙場的歐吉桑，居然號稱剛度過二八年華，這到底是怎麼一回事呢？原來是十六進位的二十八，也就是x28 = 2 x 161 + 8 = 40。


--------------------------------------------------------------------------------

高德納（Donald Ervin Knuth)乃史丹福大學的退休教授，公認是當代最偉大的資訊學家，他是計算機方法分析及程式語言實作研究的開路先鋒，約三十年前獲頒有資訊領域「諾貝爾獎」之稱的「杜林獎」。

以前唸書時，老師曾提到高教授所寫的一套書《程式設計的藝術》共三冊（預計完成七冊)，是資訊領域的聖經。下課後我馬上到書局購買，放在書架上虎虎生風；並於當晚邀請好友來寢室聊天，故意掉書袋，大家不禁豎起大拇指說：「有學問！」

最近我一時興起，把這套書帶到班上和同學分享，學生好奇地問：「老師這套書用了二十年，怎麼還那麼新啊？」聞之赧然，蓋書中饒富義理禪趣，靜不下心的話，是翻不了幾頁的。

高教授的書除了極為深奧外，也寫得出奇地嚴謹。他對讀者找出的第一個錯誤都給予2.56美元（十六進位的一百錢)獎金，頗有當年呂不韋的《呂氏春秋》懸賞一字千金之氣勢。雖然全球有百萬讀者認真地找，但能有幸找到錯誤的可說是鳳毛麟角；高教授也會遵守承諾寄上支票，不過絕大多數的人是捨不得兌現那張價值遠超過面額的支票。

高教授自1975年開始使用email，於1990年停用，自喻從此快樂無比。想想我們芸芸眾生每日被垃圾郵件、轉寄郵件、病毒郵件及插花郵件等轟炸得七葷八素，高教授可真有先見之明啊。

那要如何與高教授聯繫呢？每三個月高教授會看一次信件；如果是傳真的話，則大約每六個月才看一次。高教授之所以選擇這種隱士般的生活模式是因為他要在接下來的幾年裡，心無旁鶩地完成約四十年前開始撰寫的《程式設計的藝術》後面幾冊。

為了書的撰寫，他有時也會透過秘書寄出email，前陣子我就收到高教授秘書轉來的一封email，主要是說他打算引用我的論文，希望能知道我中文名字的寫法，以便能將我的中英文名字都放在索引裡（高教授母語正名的做法令人佩服)。想到自己的名字有可能列在本科領域的聖經中，心中雀躍不已！

後來高教授問我知不知道某位林教授的中文名字寫法，我在答覆時順便做點文化交流，說明「林」（wood)這個字來自兩個象形字「木」（tree)的組合，而且可以延伸到「森」（forest)。高教授回說他有位朋友叫林甡，因為父親是個數學家，取的名和他的姓都是左右對稱的。高教授對中文字的認識太讓人驚艷了。

你也許會懷疑這位老先覺還寫得動嗎？其實高教授出道甚早，現在仍退而不休，火力可旺得很呢！而他孜孜不倦及筆耕不輟的精神，已為後生晚輩樹立了永恆的典範。

-- 趙老


--------------------------------------------------------------------------------

Ctrl-Alt-Del鍵的發明者David Bradley於2004年退休，這個組合鍵是每個電腦使用戶幾乎都會用到救命鍵，它可使得當掉的電腦重新回過神來，極為好用。Bradley曾說：「我是發明了這個組合鍵，但微軟的比爾蓋茲才是讓它成名的人！」（因為有要命的危險時，救命的東西才會顯得更寶貴。就如同高速路旁的輪胎行生意特別好，老闆可能要感謝在路上灑鐵釘的肇事者！)

有時候，電腦當機當得太嚴重了，連Ctrl-Alt-Del鍵都失效，這時候該怎麼辦呢？可試著把電源開關鍵按久一點（至少超過兩秒)，如果連這招都不管用，那就只好把電源線拔掉囉。若是筆記型電腦，不幸的時候，有時還得將電池也拔走才行！


--------------------------------------------------------------------------------

Bill Gates在哈佛大學休學前，雖然只是一個大學生，但已和老師Christos Papadimitriou寫了一篇很不錯的論文〈薄煎餅翻整問題〉：給定一疊大小不一的薄煎餅，廚師如何用鏟子做最少次的翻轉，使得薄煎餅依序由小排到大。這是個很難的問題，但聰慧的Bill Gates給了一個很優的解法。

後來Christos Papadimitriou成了計算複雜理論的大師，據說有人就向Papadimitriou提到：「Bill Gates一定很後悔沒繼續跟你做研究，不然也一定能在計算理論領域佔有很重要的一席之地。」Papadimitriou回答說：「唉呀！該後悔的是我！如果我跟他一起去開公司，我早就列名全美十大富豪了！」


--------------------------------------------------------------------------------

缺錢的請看這裡！

我們小學時都學過：如果一個比1大的整數，只能被1和本身整除，稱之為質數。例如：2、3、5、7、11、13…等都是質數。

判斷一個給定數是否為質數，最簡單的方法就是將所有不大於給定數開根號的那些數拿來除除看，但這種方法一旦給定數很大時，計算量就非常驚人。西元2002年8月，三位年輕的印度學者因為發表了這個問題的第一個有效率解法，而上了紐約時報的重要科學新聞，蜚聲國際。但分解一個極大數，目前仍無有效快速的解法。

給你兩個質數，我們很容易就可以算出它們的乘積，但若給你乘積，要你算出它是由哪兩個質數相乘所得，這問題就困難許多。例如：13和17都是質數，它們的乘積是221，我若問你221是由哪兩個質數相乘，這問題就比13乘以17難一些。

RSA公開金鑰加密法之所以能單向加密，是基於一個由兩個大質數相乘所得的數，很難被現有的技術所分解。因此，RSA分解挑戰（RSA factorization challenges）是給定一個數，解出它是由哪兩個質數相乘所得，例如：給定143，你要回答這是由11乘以13所得的數。但如果是大數，問題就沒那麼簡單！下面這個數，稱為RSA-576（化成二進位有576位數，我們後面章節會介紹二進位）：

1881988129206079638386972394616504398071635633794138270076335642298885971523466548531906060650474304531738801130339671619969232120573403187955065699621305168759307650257059

請用力看看這個數，如果你靈機一動，找到它是由哪兩個質數的乘積，有一萬美元的獎金等著你喲。

在http://www.rsasecurity.com/rsalabs/challenges/這個網站裡，列了八個類似這樣的數，有的位數更大，獎金也更多，算一算大約有兩千萬台幣左右的獎金。


--------------------------------------------------------------------------------

馮紐曼（John Louis von Neumann，1903-1957)是不是第一個提出「儲存程式」概念的人，仍有待商榷，但他毫無疑問地是大家公認絕頂聰明的偉大數學家。

在一次在宴會上，女主人向馮紐曼提出一個算題：有兩輛火車面對面行駛，相對速度為每小時三十哩，假設兩火車在一分鐘後相撞，此時有個時速六十哩的超快蒼蠅從一輛火車的車頭往另一輛飛，等它抵達另一輛火車車頭時往回飛，就這樣來回不停地飛，直到最後被壓扁為止，請問蒼蠅一共飛多遠？

蒼蠅飛的總距離可以由來回飛的各個小片段加總起來而得，這是一個無窮級數的算法，雖不難，但有些繁瑣。再仔細看這問題，既然火車一分鐘後相撞，而時速六十哩的蒼蠅一分鐘可以飛一哩，所以答案當然就是一哩。

女主人一問完問題，馮紐曼馬上回答：「一哩。」

女主人驚訝地說：「數學家通常用無窮級數花幾分鐘來解，而忽略的速解的竅門。」

馮紐曼說：「什麼竅門？我就是用無窮級數算的啊！」

各位可以體會他的神算功力吧！


--------------------------------------------------------------------------------

幾年前IBM一部很有名的電腦「深藍」，曾打敗過當時世界排名第一的西洋棋大師，讓人不禁要問：電腦是否已有智慧了；要不然就是下棋不需智慧。一下子要接受電腦有智慧，可能很多人會不買賬，至少我們必須承認，擅長下棋的人，還頗需要聰明度的，也許我們可以安心地說：「現代的電腦真的很聰明！」。


--------------------------------------------------------------------------------

演算法常需要好的設計與分析，有時也需要腦筋急轉彎，才能找到好解答。就讓我們從林容任同學提供的幾個例子，先來個腦筋急轉彎吧！



128金幣問題是某一年的資管所口試題目：已知128金幣中有一假金幣（假的較輕），請問用天平最少秤幾次可以得知那一個是假金幣？

最阿達的做法是將兩個金幣分放兩邊秤，若有一個較輕，則其為所求，否則兩個都是標準的金幣，再用這個標準金幣去和其餘的126個金幣一一相秤，直到碰到比較輕的那個為止。最糟情況情況須秤幾次呢？如果假金幣正好是最後一個，我們總共可能要秤127次呢！

稍微不阿達的做法是將金幣兩兩對秤，共有128/2 = 64個配對，這樣最多只要秤64次。

有沒有比較聰明一點的做法呢？讀者也許會想到我們的二進位法，然後提出這樣的做法：將128個金幣平均分成兩堆，每堆64個，分別放在天平的兩邊，比較輕的那一堆一定包含那個假金幣；我們將比較輕的那一堆的64個再平均分成兩堆，每堆32個，分別放在天平的兩邊，比較輕的那一堆一定包含那個假金幣；再將比較輕的那一堆的32個再平均分成兩堆，每堆16個，…。直到只剩兩個金幣的時候，只要再秤一次即可。所以這樣總共要秤幾次呢？128、64、32、16、8、4、2，共7次，也就是log2128 = 7次。

還可以更快嗎？如果每次都儘可能平分成三堆，一定至少有兩堆金幣個數相同，把那相同個數的兩堆拿來秤，如果有一堆比較輕，那一堆一定包含那個假金幣，否則金幣就在沒秤的那一堆，再把包含假金幣的那堆依同樣做法儘可能平分成三堆做下去，…。128金幣平均分成三堆，三堆個數分別為43、43、42，把那43個的兩堆拿來秤，如果一樣重，則假金幣在42個的那堆，否則比較輕的就包含假金幣，此時我們的問題大小已從128降到42或43，比剛剛分兩堆的策略只降到64有效多了，所以這樣總共要秤幾次呢？最遭情況是：128、43、15、5、2，共5次，也就是log3128 = 5次。



地獄與天堂問題：有一路口站著兩個人，其中一位一定會老實回答問題，而另一位則必定說謊，但我們不知道誰是那位老實者。在他們背後有兩條路可走，其中一條通往地嶽，一條通往天堂，請問如何只問其中一人一個問題，就可以確定通往天堂之路呢？

如果我們傻呼呼地問其中一位：「往天堂的路怎麼走？」那注定有一半的機會要下地獄，因為我們不知那位仁兄（或仁妹）是不是老實者啊！

比較技巧的方式是問任何一位：「請問你的另一位伙伴的天堂之路怎麼走」？如果恰好問到說謊者，他會問老實者，老實者回答天堂之路，但說謊者必說慌，故會回答往地嶽之路；若恰問到老實者，他就會問說謊者，說謊者會回答地嶽之路，而老實者會誠\實回答說謊者所指示的地嶽之路。所以在這種問法之下，不管問到誰都會得到往地獄的方向，選擇另一條路即是正確的天堂之路！\\n


十個聰明的囚犯問題是情報局的考試題目：有十個聰明的囚犯關在一起，頭上都戴有紅或白的帽子，他們可以看到別人帽子的顏色，但不知道自己帽子的顏色，而且他們都知道至少有一人以上戴紅帽，但實際情況他們並不清楚。假設實際上是有兩位戴紅帽，八位戴白帽，典嶽長每天都會問這十人自己頭上是戴那一種顏色的帽子，只有確定正確的時候才可以回答，並獲得自由，請問他們最快幾天後可以離開監嶽呢？

答案是：第二天兩位戴紅帽的離開，第三天剩下的八位都離開！為什麼？因為大家都很聰明，若沒把握絕不回答，因此當第一天大家環顧別人所帶帽子的顏色，戴白色帽子的人可看到兩人戴紅帽，七人戴白帽；而戴紅色帽子的人可看到一人戴紅帽，八人為白帽。所以第一天大家都不能確定自己帽子的顏色，但第二天時大家發現彼此都沒離開，戴紅帽的人馬上就警覺到自己頭上應是紅帽，因為如果是白帽的話，他所看到的那位唯一戴紅帽的應會看到全部皆為白色帽子，因此戴紅帽的兩位都聰明地說，我們是戴紅帽的，所以順利出獄了。等到第三天，只剩八個戴白帽的，他們發現戴紅帽的已可正確回答，所以就推斷自己是戴白帽的，因此也順利出獄了。


--------------------------------------------------------------------------------

微軟總裁比爾蓋茲在哈佛大學休學前，曾發表過一篇深度頗好的科學論文。

趙老勉勵某位大三學生：「微軟總裁比爾蓋茲像你這年紀時，就已寫了一篇好論文！」

該學生投桃報李：「微軟總裁比爾蓋茲像您這年紀時，已是世界上最有錢的人了！！」

--------------------------------------------------------------------------------

习惯单恋

对比我们的计算机概论教科书，你觉得这样一本书怎么样？

northzeus

其实我们的计算机理论图书也都是引进的美国的
可能没有这么幽默
不过一些经典的例子也是不会错过的

抚琴煮酒

在刚开始学习的过程中，当然台湾的容易入手；

但到了以后，需要精练查阅回顾的时候，发现大陆不少书籍真是精辟～～

抚琴煮酒

下面是引用northzeus于2005-11-14 19:33发表的:
其实我们的计算机理论图书也都是引进的美国的
可能没有这么幽默
不过一些经典的例子也是不会错过的

湖大计通院的教材选择水平还是不错的；

这点在全国比较算很高的；呵呵，可惜书费因此比别人多了不少

如果比较后会发现，我们使用了许多 机械、电子等出版社的；

有些你工作后都可以继续使用；

northzeus

恩
确实
有点工具书的感觉
不过教学的规划不行

习惯单恋

呵呵 比较深的书就不提了，就这本入门级的图书对于兴趣的培养是大有帮助的。。

我可没说台湾的技术书最好啊，呵呵～～最好当然美国出版社的。

习惯单恋

还有

“Ctrl-Alt-Del鍵的發明者David Bradley於2004年退休，這個組合鍵是每個電腦使用戶幾乎都會用到救命鍵，它可使得當掉的電腦重新回過神來，極為好用。Bradley曾說：「我是發明了這個組合鍵，但微軟的比爾蓋茲才是讓它成名的人！」（因為有要命的危險時，救命的東西才會顯得更寶貴。就如同高速路旁的輪胎行生意特別好，老闆可能要感謝在路上灑鐵釘的肇事者！)“

这段话真是搞笑～

raymond

我觉得还是幽默多一些，人性化一些得好。毕竟教科书也是给人看的

northzeus

在我学的计算机类书里
我觉得John F Wakerly的数字设计 是最幽默的
其中有一段介绍2/8/16进制的计算问题
他推荐使用计算器，
请向德州仪器或者卡西欧公司求助，索要程序算使用的计算器
如果计算器的电池坏了 也可进行心算

当时看了笑死了