星期四, 6月 23, 2005

Sudokus

最近網路上似乎很流行一種遊戲:Sudokus



中文介紹參考:21世紀數字拼圖益智遊戲Sudoku

這不就是魔術方陣(magic square)嗎?

剛好最近代數學上到這哩,就來談一下好了。(蔡炎盛老師該不會是因為最近流行這個才上魔術方陣吧?)

所謂的魔術方陣,是從拉丁方陣(Latin Square)而來。拉丁方陣是指 N x N 的方陣中,用 N 個元素去填,每一行或者每一列的元素都不可以重複。EX.
1-2-3
2-3-1
3-1-2
就算一個拉丁方陣。

而更進一步,限制使用 N x N 個元素填值且每一行每一列的和都相同,就稱為魔術方陣。

魔術方陣怎麼找?可以用程式來算,參考Gea-Suan Lin’s BLOG:Sudokus

不過只是這樣嗎?當然不是。

其實魔術方陣和代數學有關。先回頭看看拉丁方陣,這樣的形式是不是很像是 group 的 operation table?

Definition:

若兩個 N x N 的拉丁方陣 L, K 重疊合成為 G,則 G 的元素可表示為 g_ij = (l_ij, k_ij) for 0<=i<=(N-1), 0<=j<=(N-1)。若 G 之任兩元素不相等,則稱 L, K 為正交。


Lemma:

|GF(p,m)| = n 的群,最多可以組成 n-1 個兩兩正交的 n x n 的拉丁方陣集合。p 是質數,m 是任意正整數,n=p^m。

因此,以 3x3 為例,只有兩個兩兩正交的拉丁方陣:
A-B-C
B-C-A = L
C-A-B

A-B-C
C-A-B = K
B-C-A

G = L x K, let g_ij = n x l_ij + k_ij, G' = g_ij + 1
接下來只要決定,A,B,C對應什麼值({A,B,C} --> {0,1,2})就可以創出一個魔術方陣了。(L and K 的 A,B,C 可以不用同一組 map。)

至於對於玩 Sudoku 遊戲有沒有幫助?我沒有抓這個遊戲來玩,所以也不清楚。

我之所以打這篇,是覺得真的很神奇,這些數學家的大腦是怎麼想的啊?感覺一點關係都沒有的東西,用這麼曲折的方式連在一起。真是太神奇了。


Tag: [], []

星期二, 6月 21, 2005

The Art of Unix Programming 4. Modularity

The Art of Unix Programming by Eric Steven Raymond


4. Modularity
早期軟硬體限制,所以比較偏向硬上,直到後來才開始注重結構化和模組化。裡面的一段引言很有意思,也很好笑。

Dennis Ritchie encouraged modularity by telling all and sundry that function calls were really, really cheap in C. Everybody started writing small functions and modularizing. Years later we found out that function calls were still expensive on the PDP-11, and VAX code was often spending 50% of its time in the CALLS instruction. Dennis had lied to us! But it was too late; we were all hooked...
-- Steve Johnson



Encapsulation and Optimal Module Size

The first and most important quality of modular code is encapsulation. Well-encapsulated modules don't expose their internals to each other.


The APIs between modules have a dual role. On the implementation level, they function as choke points between the modules, preventing the internals of each from leaking into its neighbors. On the design level, it is the APIs (not the bits of implementation between them) that really define your architecture.

我想這一段話的意思,大概就跟 ISA 的意思一樣吧。

One good test for whether an API is well designed is this one: if you try to write a description of it in purely human language (with no source-code extracts allowed), does it make sense? It is a very good idea to get into the habit of writing informal descriptions of your APIs before you code them.

不過有意思的是,書上說根據 Hatton 的研究,從經驗上來看,最佳的模組大小是 200~400 logical lines。比想像中小得多。


Compactness and Orthogonality

Accordingly, Unix programmers have learned to think very hard about two other properties when designing APIs, command sets, protocols, and other ways to make computers do tricks: compactness and orthogonality.

Compactness is the property that a design can fit inside a human being's head. A good practical test for compactness is this: Does an experienced user normally need a manual? If not, then the design (or at least the subset of it that covers normal use) is compact.

The purpose of emphasizing compactness as a virtue is not to condition you to treat compactness as an absolute requirement, but to teach you to do what Unix programmers do: value compactness properly, design for it whenever possible, and not throw it away casually.

Orthogonality is one of the most important properties that can help make even complex designs compact. In a purely orthogonal design, operations do not have side effects; each action (whether it's an API call, a macro invocation, or a language operation) changes just one thing without affecting others.

The concept of refactoring, which first emerged as an explicit idea from the ‘Extreme Programming’ school, is closely related to orthogonality. To refactor code is to change its structure and organization without changing its observable behavior. Software engineers have been doing this since the birth of the field, of course, but naming the practice and identifying a stock set of refactoring techniques has helped concentrate peoples' thinking in useful ways. Because these fit so well with the central concerns of the Unix design tradition, Unix developers have quickly coopted the terminology and ideas of refactoring.[43]



Software Is a Many-Layered Thing
做多層級的設計時,主要採用由下而上和由下而上的設計方法,雖然沒有哪一種比較好,但是不同設計方法適何哪一種情況卻是問題。Eric Steven Raymond 的建議是:

A very concrete way to think about this difference is to ask whether the design is organized around its main event loop (which tends to have the high-level application logic close to it) or around a service library of all the operations that the main loop can invoke. A designer working from the top down will start by thinking about the program's main event loop, and plug in specific events later. A designer working from the bottom up will start by thinking about encapsulating specific tasks and glue them together into some kind of coherent order later on.

這裡有一節是討論 glue layer,也正好是我一直搞不懂的,為什麼 python 被稱做 glue language,有些網頁稱 script langueage 為 glue language,但這似乎沒說明什麼,他們到底要黏起什麼?

我沒有足夠的編程經驗,所以並不是很了解他在說什麼。(當然也因為我有限的英文能力)

他的意思大概是說,當程式的設計牽涉到不同的模組,尤其是採用不同的設計方法設計出來的模組時,即使個別的模組有良好設計,但是整體來看卻是缺乏 Compactness and Orthogonality (?) 所以需要 Glue Layers 銜接起來。

One of the lessons Unix programmers have learned over decades is that glue is nasty stuff and that it is vitally important to keep glue layers as thin as possible. Glue should stick things together, but should not be used to hide cracks and unevenness in the layers.

The thin-glue principle can be viewed as a refinement of the Rule of Separation. Policy (the application logic) should be cleanly separated from mechanism (the domain primitives), but if there is a lot of code that is neither policy nor mechanism, chances are that it is accomplishing very little besides adding global complexity to the system.




Coding for Modularity
最後 Eric Steven Raymond 提供了一份列表,讓你檢查一下,你的 modularity 是否設計得不好。


Tag: [], []

星期六, 6月 18, 2005

費曼手札摘錄

Ref.:費曼手札

這本書涉及的面向很廣,我這裡的摘要主要是以他給年輕學子的建議為主。而且我也不打算全文抄錄,僅就抄錄我覺得比較發人深省的片段。

戈德是費曼的家鄉老友,他的兒子很有理工的才華,他不曉得要鼓勵他的孩子走工程還是科學。費曼致戈德(page 199)

我給你兒子的建議如下。幸好他喜歡做某些事,而且再做某些事的時候非常開心。你應該盡量鼓勵他去做他喜歡做的事。我不是指將來,而是指現在、每一天。不要預設什麼遠大的計畫。在他現在這個階段,工程與科學的教育內容是大同小異的,而且有好幾年都是這種情況。大學裡多的是畢業後才改唸其他科系的,這沒有太困難,但是不要等到研究所畢業之後,那就嫌太晚了。

因此,讓他很認真的去完他的電腦和想法。當他需要了解電腦的電路時,他的數學能力也會慢慢發展起來。現在,他可以自由自在的去追求自己喜歡的事。當他成為某件事的專家時,他會發現瞭解相關的主題很簡單。

另外,和你信裡描述的情形相反,如果他什麼功課都是中上,並沒有特別喜歡什麼事,或者什麼事都喜歡,經常這事做做,那事搞搞的,那我反而不知道該怎麼建議了。


高中生奚帕寫信詢問費曼,一個數學不好的人是否能掌握高深的物理,成為這行的專家?費曼致康乃狄克州的奚帕(page 200)

我有什麼建議呢?暫時把對數學沒興趣這件事擱在一旁,不要理它,也不必害怕。先做那些你最喜歡的事。你不是做了一個雲霧室嗎?再做一些類似的事情,順應你的才能去發展,不管它們會朝哪個方向走。不必管路上的水雷,全速前進。

那麼,對數學該怎麼辦?(一)或許當你再以後再設計某種裝置而需要用到數學時,才發現它很有趣。(二)你沒有繼續發展現在興趣,設法了解所有的事情,卻發現自己有其他才幹,可以嶄露頭角,例如設計先進太空船的控制系統等等。或者(三)生物學上的問題最後吸引了你的注意和才能,而你決定往實驗生物學發展,利用它來了解大自然等等。


從前的學生真野來信抱怨現在做的題目卑微而末節。費曼至真野光一(page 315)

我們相遇的時候,正式我生涯上的巔峰期。因此在你眼中,我對問題的解決能力,簡直像神一樣,好像什麼都難不倒。但是我當時還帶另一位博士生希布斯,他的博士論文只是研究風如何把海水吹出浪花。我接受他是因為他帶著自己想解決的問題,跑來找我指導。我對你犯一個錯誤,就是我指定的一個題目給你,而不是你自己找的題目。這讓你誤解了題目的意義,認為有些問題是有趣的、令人欣喜的、或者重要而值得的----也就是,你認為有些題目值得妳花功夫去解決,有些則不然。

真抱歉,請原諒我的疏忽。希望這封信能稍微有點補救效果。


費曼至魯勒提(page 544)

因為不管那是什麼事,如果你真的夠高明,如果你真的熱愛他,那你一定會玩出名堂的。那人家就會付錢,請你繼續玩下去。


Page 602 ~ page 610 是本書收錄的最後一段書信往來。凡德海先生寫信給費曼,請他封信給自己的孩子,談談人生之類的事。他的孩子很有天份,卻太過偏重自己喜歡的領域,希望費曼可以給他的孩子一點建議。

這兩封信很有意思,雖然他給凡德海的回信不出上面兩封信的範疇,但是,某個角度上呈現了他對親子關係的觀點。就像費曼的父親影響他很大一樣,他對父子關係也十分重視。


對了,page 497 和 page 571 有提到 wolfram,就是那個搞 Mathematica 和寫《A New Kind of Science》的天才。

Tag: [], [].

費曼手札


費曼手札:不休止的鼓聲
PERFECTLY REASONABLE DEVIATIONS FROM THE BEATEN TRACK:The Letters Of Richard P. Feynman

作者: 理查‧費曼/著,米雪‧費曼/編
譯者: 葉偉文
出版社:天下文化
出版日期:2005 年 05 月 19 日
語言別:繁體中文


這本書還蠻好看的,雖然很厚,但畢竟只是書信集,讀起來沒什麼,我只花了一點時間就讀完三分之一了。這本書值得買嗎?如果你是費曼的瘋狂 fans 當然值得了,如果不是,那我覺得這本書其實到圖書館借來看看就可以了,畢竟可能看第二次的機會不大。如果只讀一次,五百塊大洋也蠻貴的說。

這本書是費曼的養女 Michelle Feynman 編輯整理的(他的養女還蠻正的.....XD),如果你想從中認識費曼不為人知的一面,我想是不太可能的。(絕大多數並未收錄對方的信件,所以大多只會看到費曼片面的說法。別太注重其中的歷史證據的意義,把它當成書信體的費曼散文來讀。)但是如果想更細膩地了解費曼,那麼這本書還蠻值得一讀的。

費曼和阿琳的通信,和母親的通信,和國家科學院的通信,比起描繪式的故事寫法,更是一種細膩的見證。如果你讀過好幾本關於費曼的書,這本書不會給你什麼驚奇,但是我想絶對會讓你有種更貼近一點的感覺,費曼不只是個特立獨行的天才,他也有他現實的一面,也有他溫柔的一面。


Tag: [], [].

Old. Smart. Productive.

Ref.:Business Week Online News, "Old. Smart. Productive.", By Peter Coy, with Diane Brady in New York (Furled)

Old. Smart. Productive. Rather than being an economic deadweight, the next generation of older Americans is likely to make a much bigger contribution to the economy than many of today's forecasts predict. Sure, most people slow down as they get older. But new research suggests that

boomers will have the ability -- and the desire -- to work productively and innovatively well beyond today's normal retirement age. If society can tap their talents, employers will benefit, living standards will be higher, and the financing problems of Social Security and Medicare will be easier to solve. The logic is so powerful that it is likely to sweep aside many of the legal barriers and corporate practices that today keep older workers from achieving their full productive potential.


在彼得杜拉克的書中多次提到,老年化的社會問題和整個經濟體的交互關係,老年人勢必要重回職場。而這篇文章可以說是和彼得杜拉克站在同一邊。

不過回應中則出現不少反對意見,譬如 SJSU Student 說科技業不接受老人;graying at the temples 則指出薪資問題,年資較長的人往往會有較高薪水,但是在整個企業 cost down 時,常常是第一批被裁員的人。

我想,老人重回職場真的有足夠的競爭力嗎?就我的閱讀,彼得杜拉克的觀點,並不是年屆退休的現役勞工,而是已達退休年齡的員工。他們需要工作來找回社會認同,薪資並不是最主要的考量重點。

而且不同的行業也有不的狀況,像是張真誠或者李家同,退休了還是到各個學校去當教授,像我二姑丈,則是以顧問的身分待在企業界。但是以勞力或精密技術為主的職業,年紀卻是很大的關卡。

不過我問我老爸,他退休後想幹什麼,去當義工也不錯。我老爸倒是很爽快的嗤之以鼻:『我又不是瘋了』。

我想在台灣,這樣的概念還要很久才會被接受吧。還有很多人在肖想 40 歲退休....XD (時代不同了好唄)

像我老爸這輩(快六十了),通常生活比較沒有品質,秉持的是『能賺盡量賺』的心態。所以對他們來說,退休就是可以休息的時候了,我想『再出社會』應該不是很能被接受吧?

不過除非很有錢,不然退休還真無聊,沒錢享受旅行等娛樂,又沒有工作.....恩....其實以另外一種方式重新投入社會應該也很不錯。(不過他們的價值觀,大概會說,所以年輕要拼命賺阿。)


Tag: [], [], [].