Showing posts with label project. Show all posts
Showing posts with label project. Show all posts

Wednesday, February 03, 2016

Embedded Systems 中的 Resource 管理

開發 Embedded Systems 常常會碰到 f/w 要用到圖、字型、甚至音樂等 resource 的情況。實務上一種處理方式是將這些 resource 轉換後串成一個大的 C array 。然後再用 resource ID 去讀取它們。一些書上稱這種轉換的工具叫 Resource Maker 。不過我不會採取這種作法,雖然還是透過 resource ID 讀取,但不把 resource 轉成 C array ,而是直接轉成 binary 格式,要用時才去 storage 裡 load 進來,因為這樣比較節省記憶體空間。

多年前我就用 Python 寫了類似的工具,那時我把這支程式稱作 weave 。後來慢慢精練,演變成今天要介紹的 ResourceLink

同樣地,這裡我主要也是著重在 ResourceLink 裡用到的領域專用語言,來看看我怎麼描述這些 resource files ,以下是個 res.lst 的例子:

:0x00       # start offset (default is 0x00)

:kind=A     # kind A for the enumeration
bat.png     # file size: 2877 bytes

:kind=B     # kind B for the enumeration
:4096       # offset to address: 4096
broom.png   # file size: 3083 bytes
candle.png  # file size: 2771 bytes
  • 這個文字檔列出了 bat.png, broom.png, candle.png 等三張圖檔檔名,當作 resource
  • # 一直到行尾代表註解。
  • : 接數字代表接下來的檔案要放的位置,單位為 bytes
  • :kind=name 用來對產生的 enumerator 作分類。
    • 除了用來區分 resource 的 type 外,我還常利用這個機制來處理多國語言。

把這個 res.lst ,餵給 ResourceLink 後,可以產生 ResID.h, ResMap.i, 跟 res.bin 。

res.bin 就是這些 resource 檔案(三張圖檔)連結成的單一檔案。

ResID.h 為每一個 resource 都指定一個 enumerator ID:

// Generated by the Resource Link v1.14
//    !author: Jiang Yu-Kuan 
//    !trail: reslnk.py id -oResID.h res.lst
#ifndef _RES_ID_H
#define _RES_ID_H


/** IDs of Resources */
typedef enum {
    RES_A_BEGIN,
    RES_PNG_bat = RES_A_BEGIN,
    RES_A_END,

    RES_B_BEGIN = RES_A_END,
    RES_PNG_broom = RES_B_BEGIN,
    RES_PNG_candle,
    RES_B_END,

    RES_End = RES_B_END,
    RES_Total = RES_End
} ResID;


#endif // _RES_ID_H

ResMap.i 是用來描述每個資源檔的偏移植跟大小的:

// Generated by the Resource Link v1.14
//    !author: Jiang Yu-Kuan 
//    !trail: reslnk.py map -dres -oResMap.i -a4 res.lst

//   offset,       size     (in bytes)
{         0,       2877},   // RES_PNG_bat (bat.png)
{      4096,       3083},   // RES_PNG_broom (broom.png)
{      7180,       2771},   // RES_PNG_candle (candle.png)

Friday, January 29, 2016

利用 LangConvert 工具處理多國語言

dic.xls

開發 Embedded Systems 相關應用時,常得處理多國語言。而系統資源受限的的場合,就算掛了 OS,往往也沒內建多國語言。這時候只能捲起袖子自己處理了。自幹的過程,很直覺地,多數人都會想到要有個類似右圖這樣的 Excel 字典檔當作翻譯表。

有了翻譯表後,我們還要有個字庫(font)。為了存取字庫裡的字,我們要先決定字序(character order)。有了字序後,我們就能根據字序,把翻譯表裡面的多國語言訊息,一一轉換成字序的串列(a sequence of character orders)。要秀某個訊息時,就根據這個字序列,回過頭把字庫裡的字形(glyph)抽取出來顯示。

如果要通吃幾乎各國的語言,一個奢侈的做法是直接用 Unicode 當字序,建立完整的字庫。不過這不適合用在資源受限的場合。

多年前,我遇到決定字序的問題時,想了一種簡單又好用的表示法。以 ASCII code 有對應字形的部分為例子,可以利用這個表示法描述如下:

# Printable characters of ASCII code

:0x20
 !"#$%&'()*+,-./0123456789:;<=>?
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_
`abcdefghijklmnopqrstuvwxyz{|}~
  • # 開頭的行表示該行是註解。
  • :0x20這行,代表接下來的字元從 0x20 (有可以寫成十進位的 32)開始編號。
  • 行尾的空白字元會被忽略掉。
  • 這整段看起來很直覺,就是列出了 ASCII code 32 到 127 間的字元。

因為英文太常用了,所以 32 到 127 這段通常會保留給 ASCII code 用。其他國家的語言,我們可以只列出有用到的,以節省字庫佔的儲存空間,以下是實際的例子:

# A sample character list file

:0x20
 !"#$%&'()*+,-./0123456789:;<=>?
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_
`abcdefghijklmnopqrstuvwxyz{|}~

:0xA0
áíñóúąćęśП
РУЭабвдежз
ийклмнопрс
туфщыьэюя中
件像册删单图子定客影
文时显检此电相示置菜
言设访语间除验간겠국
까뉴니메문미방범삭설
스습시앨어언영을이인
일자전정제지틸파표하
한화확?

有了翻譯表(dic.xls)跟字序表(char.lst)後,就可以利用 LangConvert 產生下述的幾個 C 原始程式:

  • LangID.h: Language ID 的 enum 。
  • MsgID.h: Message ID 的 enum。
  • mlang.i: 將每個訊息的多個語言版本,一一列出對應的字序串列

接下來還缺個從字序表轉出字形(glyph)的工具,這個大家可以自己練習看看。我這裡著重在介紹領域專用語言來表達字序表。

LangConvert 還有個新增的 command 可以透過 Google Translate 來對空的字典檔實施自動翻譯,有興趣的可以直接執行 demo_trans.bat 觀察看看。它會吃進還沒翻譯好的 dic_empty.xls ,然後吐出翻譯好的 dic_trans.xls 。

Sunday, January 24, 2016

利用 PicCrop 工具來切圖

iPod Touch 5g

記得小學製作海報時,會用剪貼的方式分工,快速拼湊出一張教室海報。時代進步了,現在大家都用電腦,我好幾次觀察到現在美術人員幫忙設計 UI 時,也常常會先把整體畫出來,然後再一塊塊的剪下來。這些剪下來的圖,還有個貼切的稱呼,叫「切圖」

現在有很多現成的切圖工具,幾乎都搭配 Photoshop 使用,甚至 Phothoshop 本身對這道工序也提供一定的支援。不過我沒打算在這介紹這些搭配 Photoshop 的圖形化工具,而是想設計一個專用的語言,來執行這個切圖的動作。

這個語言要告知原始圖檔,然後再列出每張被切下來的圖的位置、大小、甚至名字等。舉個例子,假設我要把圖中八個紅線匡起來的部分,一一切下來存檔。


最簡單的描述方式,大概就長這樣子:

# source picture
#---------------
ipod-touch-5th-black.png

# x,   y,  w,  h, target picture
#------------------------------------
117, 139, 62, 62, ico_FaceTime.png
190, 139, 62, 62, ico_Calendar.png
263, 139, 62, 62, ico_Photos.png
336, 139, 62, 62, ico_Camera.png
117, 223, 62, 62, ico_Weather.png
190, 223, 62, 62, ico_Clock.png
263, 223, 62, 62, ico_Maps.png
336, 223, 62, 62, ico_Videos.png
依照慣例, # 開頭的代表該行是註解。

下面八張小圖就是剪下來的切圖:



這個工具可以一次對多張的原始圖寫好要怎麼切的描述,切之前還可以反覆用紅線匡起來確認大小跟位置沒錯,然後只要 "One Touch" 就一口氣全切出來了。

照慣例,程式是用 Python 寫的,細部的安裝跟使用說明可以參考PicCrop 的 Overview

Sunday, January 17, 2016

以 EnumLookup 查詢 C enumerator

前陣子我把 AWK 撿回來練習,順便研究一下 Windows 下怎麼跑 GAWK 跟 AWKA 之類的工具。這期間,我想了幾個簡單的題目來練習。其中有個我稱作 EnumLookup 的工具,一些慣 C 的人應該會用到,所以在這裡做個分享。

顧名思義,這個工具的目的是針對 enum ,它可以在多個 C enumerations 上查詢 enumerator 或它們對應的值。這裡是安裝跟執行說明文件,大家可以根據上面的指引,直接下載內含執行檔的下載包來試用。

這個工具有個搭配的 enum.bat ,執行後可以雙向查詢:可反覆敲進數字來查對應的名字(enumerator),或者敲入名字(enumerator)來查對應的索引數字。

需要注意的是,這個工具沒有真的去實作完整的 C enum parser ,只是認「通常」情況下的 enum 特徵。下面這種寫成一行的寫法,無法正確執行:

typedef enum {SPRING, SUMMER, AUTUMN, WINTER} Season;

因為這工具不認得寫成一行的寫法,只認得下面這種,比較正規的,分行寫法:

typedef enum {
    SEASON_BEGIN,
    SPRING = SEASON_BEGIN, 
    SUMMER, 
    AUTUMN, 
    WINTER,
    SEASON_END,
    SEASON_TOTALS = SEASON_END // the total number of seasons
} Season;


Friday, January 07, 2005

久違了 XTinux

前陣子到 Study Area 閒逛時,發現了之前為公司弄的一些 PDA 軟體,同事把它 Screen Shot 起來,在那展示著:

第一幅圖是主畫面九宮格,為啥要設計成 3 by 3 的九宮格?只知道是客戶聯想集團的要求。

第二幅是 Email ;第三幅是 Browser 。

Tags: [] [] [] []

Saturday, July 10, 2004

The Neuron Farm

基於興趣,碩士論文我是作 Bio-machine modeling 方面的題目,在歸類上屬於人造生命(Artificial Life, ALife)的範疇,選擇的 target 是神經細胞的生長、發育。以下就先簡述一下整個概念:
這裡並不是要詳盡地模擬腦部的發育和功能執行,而是提出經過大幅簡化的模型,以利電腦模擬,及供我們驗證假設之用。經過長期考量過各種可能方案後,我決定以 Cellular Automata 來模擬神經細胞生長的環境。
考慮在一個由 CA 舖成的空間中,我們在一些選定的位置,滴上特定的化學物質,於是這些化學物質就會由滴定的點,向四周擴散。再考慮到真正的腦,對個別神經細胞而言,並非完全開放的空間,所以我們也在 CA 舖成的空間中設置各種障礙,來對空間作某種區隔。於是我們的神經細胞除了有化學的土壤外,現在也有了障礙的地形。整個生長環境豐富了許多。
有了生長環境之後,該是時候讓細胞在環境中過活了,於是我們就隨手一灑,這些神經幹細胞就被灑到 CA 構成的空間中了。既然有了前面土壤的比喻,就讓我們稱這個“灑”的動作為“播種”吧! ^__^
神經幹細胞的生長也遵循 automata 的模式。完全因應環境中的化學梯度而長出軸突(axon)和樹突(dendrite)……環境中的化學物質有其自然的損耗率、神經細胞的成長也會消耗掉 大量的化學物質……我們可以在其中模擬神經細胞的成長、競爭與凋亡。並觀察最後長成的神經網路拓僕。
~~
為了完成這個模擬,我當然要先 survey 一下現成的東西,決定一下要以哪些工具來達成想要的效果。雖然在大規模的模擬時,在效率的考量下,比較傾向於使用 C++ ;最後我還是決定用 Java 來實作,因為要縮短開發時程下,執行效率的考量就顯得比較次要了。
在決定用 Java 實作後,我 survey 了許多 Java 下的 agent software toolkits 。在它們當中, Swarm 雖是該領域的元老,它的接繼者 Repast 卻比較合我胃口。但由於 Repast 的架構還是顯得龐雜,且我要的許多效果它也沒提供,索性就 參考一下 Repast 的作法後,自己重新開發一套合用的 toolkit 。
為了確認每一步都沒出錯,也為了好玩,在開發過程中我同時利用自己的 toolkit 撰寫了許多測試用的小程式:

左邊那個是用來 Demo 在物理上有名的布朗運動(Brownian Movement)。程式一開始會把固定數量的化學分子置於中央,分子們很快就會以 Random Walk 的方式擴散開來,其中的色溫提示我們每個位置的分子數量的多寡。
右邊那個我管它叫做 Diffusion Sun 。化學分子一開始也是置於中央,隨著每個 time tick 的推進,這個 Demo 程式會繼續滴上給定數量的分子作為補充。在給定的自然分子損耗(lose)及不斷地添加分子間會有個動態平衡,造成一個形狀像抖動的太陽般的圖像,故稱之。
接下來,我們就繼續觀摩一下這個 toolkit 還提供了甚麼:

很明顯地,右邊那兩個綠底、裡面畫有 sine 波的東東,就是示波器(socillograph)的 scope 。比較特別的是這裡的示波器原則上是無限量供應的,只要點選 toolbar 上面代表探針(probe)的 icon 即可。值得一提的還有,這裡的探針量測的不是單純的點的訊號,而是一個指定的範圍。我們可以在左圖的 Imaging 畫布上看到一個虛線框住的範圍,它對應到右上那個 scope ,以這個例子來說,scope 顯示的是整個框框內所有點的平均訊號,實際上我們可以在上面顯示其他更有用的統計。
最後,我這裡也附上 SineSun 的 jar 檔,有興趣的話,諸位看官也可以自行玩玩看 :)

Monday, February 02, 2004

The cocktail party problem

在一個雞尾酒會場上,假設有人事先在三個不同的位置分別安置了三支麥克風,意圖監聽大家的談話。由於酒會是在開放的場所舉行,麥克風錄到相互混雜的嗡鬧聲,很難好好地監聽出想要的情報。

想像你是當事人,面對好不容易錄下來的東西竟然無法派上用場,該如何是好呢?

為了解決這個難題,我們必須由各個麥克風錄到的資料中,把想要的聲音解析出來,這就是所謂的 Blind Source Separation, BSS 。

本學期生醫訊號處理(Biomedical Signal Processing)課程的 term project ,就是要利用獨立分量分析(independent component analysis, ICA)來達到 BSS 的效果。老師雖然沒限定大家實作的工具,但面對如此紛雜的矩陣及行列運算,不用 Matlab 這種好用的工具,那真是自找麻煩。以下是我完成專案的 Screen Shot:

程式一開始先在左上角的選單決定要載入的 Blind Sources ,其波形會在左邊的畫布顯示。決定好參數,並按下 Analysis 扭,我們要的訊號波形會出現在右邊的畫布。除了可以選取個別的波形來觀察外,我們還可以聽聽分解前的混音,及分解後的清音。

以這次拿來測試的聲音訊號來說,原始訊號混雜著男高音演奏、交響樂曲、搖滾歌唱、新聞撥報等四種聲音。分解出來後果然是原音重現,乾乾淨淨的,一點混雜都沒有,效果好到令我大吃一驚。

在 Pattern Recognition 課堂上,蔡文祥老師一再地提醒我們,資訊系的學生所受的訓練中,會傾向於利用合成(synthesis)的方式來解決問題,以後在解題時要是遇到瓶頸,不要忘了還有個很有用的方式,那就是利用分析(analysis)手段來處理問題。雖然當時他的目的是要強調他上課所教授的東西不只是抽象的數學式子,而是很實用的工具,還是無礙於此時此刻,在我內心響起共鳴。

Tags: [] [] [] [] [] []

Sunday, February 01, 2004

The Prolog Interpreter

這學期加入 AI 助教群,我打算讓學弟妹從實作中瞭解 Unification Algorithm ,但又不想為他們帶來太大的負擔。從眾多 Prolog language 的 open source 中,我選出了 Peter Bouthoorn 所開發的版本,它原本就是被用於教學,可惜其程式架構實在稱不上漂亮。在無法坐視不理下,我一次一小步地 refactor 它,改了幾百個回合,並將其中好幾個關鍵的地方整個重寫,才有一個適用的 Prolog Interpreter 。這真是個不錯的練習。

接下來是將這個動過手術的 Prolog Interpreter 版本當中的 Unify, OccrCheck, and UnifyVar 等 functions 挖空,要學弟妹參照 AI 課本的 Unification Algorithm 後,為這些挖空的 functions 補上血肉。

考慮到修課的人數眾多,為了讓自己在批改作業時不會哭出來,必定得把這個作業批改的流程盡量自動化。

於是我就為學弟妹準備了一對 .txt 檔: input.txt 及對應的 output.txt 。為了怕有些學弟妹過份聰明地以 printf 將 desired output 直接印出,在批改作業時另外準備其他 input 及 desired output是一定要的。這部分我以 Unit Test 的工具來自動比對,只有在比對出錯才要告訴我出錯的地方在哪,否則它只要簡單打個點代表程式還活著,並在通過所有測試後吐出 OK 就好了。

為了更省事,我在 Windows XP 下裝了 MinGW with MSYS 來模擬 Linux 的 terminal ,並寫了一個 BASH 的 script 來將這一百餘份程式作業自動作執行、比對及歸類的動作。

Unit Test tool 在 Java 下有 JUnit 可以用,無奈這裡用於開發的程式語言是 C++ ,所以勢必要另外找一套對應的工具。我最先注意到的是其中最有名的,移植自 JUnit 的 CppUnit ,進一步瞭解後,發現它 Java 味太重了,感覺很不純,而顯得有點礙手礙腳(唉呀,我是不是太偏執了),於是我最後選擇使用專為 C++ 打造的 Unit++ 。嗯,這次用起來果然很順手 ^___^

Tuesday, June 17, 2003

Session Initiation Protocol

就 VoIP 網路而言, SIP是一個非常有彈性而且功能強大的通訊協定, SIP 能夠更有力的支援許多智慧型的電話網路服務及各種使用者平台,並且能夠快速而有效的發展許多先進的功能。

這次是要實作 SIP protocol 的 redirect server 。我決定讓它能夠支援 multi-user ,每次由 user end 那 send 出的 request 都會在 server 上由個別的 Thread 處理。

我將整個架構切割成 SipStack, SipProvider, SipListener 等三個 class 或 interface 。

  • SipStack 將底層 network protocol 封裝起來,供 SipProvider 使用。
  • SipProvider 則提供基本的 SIP message 傳遞及分送。並將收到訊息後的對應動作委託給SipListener 處理。
  • SipListener 是一個 interface ,用來傾聽 SipProvider 送來的 event ,並處理。

此外, SipHeader 被設計來剖析 SIP message 的 header。

最後, RedirectServer 則 implements 了 SipListener 這個介面。 RedirectServer 也處理了所有關於 SIP redirect server 的高階協定。

由於要支援 multi-thread ,且軟體以 OO設計,再加上此 SIP 是 application layer 的 protocol ,所以決定以 Java 語言實作。

若只滿足於達到作業的功能要求,程式部分還滿單純的。唯之前並未真正接觸過網路程式設計,所以費了一翻功夫在相關程式寫法的摸索。

此外,我還為本程式立下 reusable 和 extendable 的目標。所以在分析及設計上費了一番功夫。

這個 SIP AP 的底層是採用 UDP 協定。原則上,在目前設計的架構下我們可以很容易地切換到 TCP 。也可以很容易地改寫成其他 SIP AP 。

沒力氣再掰下去了,有興趣的話,這裡也附上原始碼。請自行參照。

Tags: [] [] [] [] [] []

Tuesday, February 25, 2003

又遇 N Puzzle

針對 N Puzzle,之前以 CLIPS, C Language Integrated Production System 求解過,那是專家系統的課,所以我也很配合地,以 heuristic 的方式,寫起一條條的 production rules 。

這次研究所的 AI 課則要求分別利用 BFS (Breadth-First Search), DFS (Depth-First Search), Iterative Deepening DFS 及 A* Search 這四種方式來求解,並比較結果。

無論在 AI searh 理論方面,或是 OOA/OOD 上,這都是個有趣的練習,所以我自告奮勇要打頭陣,完成 framework, BFS, DFS, 和最後的整合及 CUI (Character-based User Interface) 等。

設計的目標有:

  1. Correctness
    最起碼要能通老師指定的兩個 case 的試驗。
  2. Clarity
    系統架構設計要清晰、簡單、易理解,以方便對軟體作追蹤、審閱、除錯、細部調整、功能刪減等。
  3. Performance
    在滿足了correctness 及clarity之後,還要考量程式的高階效率和低階效率。舉凡底層資料結構的選擇、和高層抽象表示法連結上的介面設計等,都是考量重點。
  4. Flexibility
    我們在設計時還希望對系統架構能保持一定的彈性。如,不要只針對 8-Puzzle 設計,而更進一步粹取出N-Puzzle的表達方式。

由於分析及設計階段就是採用 OOA/OOD 的方式,所以很自然地要採用支援 OO 的程式語言來實作。經討論,我們決定採用 ANSI C++ 來實作這份設計,並利用 GNU Compiler Collection 來製作可執行檔。

雖然我們只在 Windows 下的 DJGPP 搭配 rhide 的 IDE 及 Linux 下的 g++ 搭配 make 試著編譯過我們的源碼。但理論上應可以適用於任何支援「完整」ANSI C++ 語法的平台。除了 STL 外,還使用了namespace,所以古老的 C++ 編譯環境可能無法順利編出可執行檔。

※請參閱附件:

  1. The Report
  2. Its UML diagram
Tags: [] [] [] [] [] [] [] []

Tuesday, July 04, 2000

The Thread Class Library for Linux

在設計應用程式時,一些需要並行處理(concurrent processing)的功能,已經很少人使用中斷(interrupt)的方法解決,也不必再自行利用一個輪詢迴圈(Round-robin loop)來達到並行的效果──因為現在作業系統的設計,都已經支援執行緒(thread)了。一個程式可以透過許多執行緒達到並行處理的作用。

一個執行緒的產生,是在應用程式開始執行之後,而執行緒所能運用的系統資源是應用程式可用資源的子集;在應用程式結束前,執行緒就要被銷毀。因為執行緒是應用程式執行時的一個子功能,程式結束後,執行緒就沒有存在的必要。

Linux 作業系統核心提供了 clone() 這個 system call 來支援 thread 的功能。此外, Linux 的共用函式庫中,也利用了 clone() 來實作了 POSIX thread, PThread 標準的 C 語言 thread 應用程式介面。不過在現在到處充斥著物件的後 OO 時代裡,一個傳統 functional 的 C Language API 似乎顯得有些礙手。

這個類別庫(classes' library)主要目的是利用一個 C++ Thread Classes Library ,來提供一個容易使用的物件式介面(object interface),以方便日後在 Linux 系統下開發多執行緒的程式。

“一個具體的問題描述是與一千個尚未運用的抽象觀念等值的”,所以接下來,就先描述一下我們要的 Thread 是長成怎麼樣的:

一個多執行緒類別庫要考量的功能最基本的當然就是要能做好執行緒的內部管理,舉凡執行緒的識別、出生、狀態、行為和死亡等都要照料妥當。

如果執行緒之間要作通訊(communication),當然也要提供一個通訊的管道(channel);此外,還要考慮到執行緒共用資源時所可能引發的同步(synchronization)問題和避免因互相等待而產生的死鎖(dead-lock)問題。

為了方便多個執行緒的管理,還可以提供執行緒分組的功能,分成一個個的 Thread Group,以方便整組一起操作。

當然,在更完備的功能設計下,每個執行緒和執行緒群組還可以設定個別的執行優先權(priority)。並納入凍結(blocked)後的執行排班(scheduling)設計。

※完整的說明請參閱:

  1. Linux 系統 MultiThread 類別庫設計
  2. Linux 系統 MultiThread MMS 類別庫設計
Tags: [] [] [] [] [] []

Monday, July 03, 2000

Ant Simulation

大學(1997)的程式設計課要求學生在網路上找一個 JAVA Applet 的程式,研究後寫一篇報告上來。我在網路上找到 Mark Miller 所撰寫的“Manna Mouse”JAVA Applet,檢閱了原始碼後,覺得它的程式架構太雜亂了。於是決定自己利用物件導向分析與設計的方法,將整個程式重新設計過。

如此,一方面可以加深自己對物件導向分析與設計方法的熟練程度;另一方面我對於這個Applet 所使用的遺傳演算法也有很大的興趣,想藉此有更深的探究…

Grady Booch 一向在物件導向(Object Oriented, OO)的方法論上執領導的地位,他在1986年率先提出OO開發方法,開啟物件導向分析與設計的研究。

Booch方法在進行分析時,不只是針對問題本身作分析,也針對問題的領域進行分析。因為在同一領域的問題,有很多非常類似。實在不需要對這些類似的問題,每次都一一地重新作類似的分析。

對於問題的整個領域作一徹底的分析,雖然在一開始的時候需要耗費相當的心力,可是隨著分析的進行,我們對於整個領域就會有更深入的瞭解,最後不但累積了領域相關的知識,也完成了富彈性、高度可重複使用的軟體元件,對於將來開發新的系統將帶來非常大的助益。

Booch 的開發方法非常強調領域內的可重用性(Reuseability),其將軟體開發分成以下三個階段:

  1. 需求分析(Requirement Analysis)
  2. 領域分析(Domain Analysis)
  3. 系統設計(System Design)

上面三個步驟並不是像傳統瀑布式的分析設計方法般僵硬地要求一定要一步步地執行;而是允許在步驟間回溯(backtrack),進行反覆地修改與調整,直到系統符合需求為止。

根據生物學的說法,曾經在地球上出現過或現存的所有生物都是由構造簡單的、原始的生物,經由長期的演化而逐漸產生的。

生物演化的理論,在早期可分成:相信後天獲得的性狀可遺傳給後代的拉馬克(Lamarck)學說,及相信後天性狀不可遺傳給後代的達爾文(Darwin)學說兩大派。

由於後來新證據不斷地出現,及這幾十年來分子生物學的快速發展,生物學上已經知道自然界生物的演化機制是採用達爾文式的。雖然有學者提出人類文化的演進可以看成是採用拉馬克式的演進方式,不過這不是這裡所要討論的重點。

達爾文的生物演化論可分成以下幾個步驟:

  1. 遺傳變異(genetic diversify):個體間因遺傳基因型(genotype)的差異而顯現出各式多樣的表現型態(phenotype)。
  2. 自然選擇(natural selection):自然界對於不能夠於所在環境中適應良好的個體發生淘汰的現象。
  3. 繁殖複製(reproduction):未被淘汰的個體經由繁殖,產生許許多多的後代。這其實是一種選擇放大(selection amplify)的情形。

新產生的後代間又稍有不同而產生了遺傳變異,因此不斷地變異-選擇-複製,變異-選擇-複製,變異-選擇-複製......一直反覆循環下去即發生了生物的演化。

遺傳演算法在電腦科學上屬於演化式計算(Evolutionary Computation)的一環。遺傳演算法其實是以電腦來模擬生物演化的過程。通常用來解一些對問題解法沒有很充分瞭解的例子,或在用傳統的解法成本過高的時候使用。

※請進一步參閱《模擬螞蟻──以物件導向分析遺傳演算法

Tags: [] [] [] [] []

Sunday, July 02, 2000

The Puzzle Game

大學時(1996)選修的“專家系統”課,任課老師要我們以 CLIPS 實作智慧拼盤程式。當初對這的專家系統的 CLIPS 感到滿新鮮的,所以就把這個問題的核心往自己身上攬,而將使用者介面讓其他組員去發揮。CLIPS 是 C Language Integrated Production System 的縮寫,由美國 NASA 太空中心的一個人工智慧部門所發展,就發展專家系統而言,是個很有用的工具。

“智慧拼盤”(puzzle),是一個n×n的格狀棋盤(grid board)遊戲。棋盤上的每一格都有一個正方形的積木(block),每個積木都有自己正確順序(order)的位置,為了區別,依序編上1到n×n的 編號。遊戲啟始時先將其中一格積木取走,造成的空缺(blank),使相鄰的積木可以移動至空缺上,並編上“0”。如此,利用這個空缺,可以將棋盤上原先 就定位的積木之順序打散(disorder)。玩遊戲的一方(player)所要完成的目標(goal)就是要將積木利用空格 (編號為0),排回(reorder)原先的位置。

這個題目的目的是要設計一個會玩智慧拼盤的專家系統,所以一開始由人將積木的順序 打散,再要求電腦將其排回正確的位置。為了達成更好的展示效果,於是選定了圖形化的使用者介面。又為了簡化問題,於是先從3個階層著手,也就是3×3的智 慧拼盤遊戲,作為測試規則的用途。不過,為了將來能夠將系統套用於任何階層,所以規則制定時都很一般化,原則上這些規則要能在任何階層的智慧拼盤下運轉, 至於能否在任何階層都求出解答,不是目前所要求的。

這個軟體的開發平台是在 MS-DOS 下的 CLIPS v6.0 上建立 puzzle 規則,並利用 MS Windows 3.1 下的 MS Visual Basic 設計使用者介面。

※請參閱《智慧拼盤

Saturday, July 01, 2000

Graphing for the Pattern of Antenna Field

專四下學期至專五上學期延續一年(1994-1995)的專題課。我選了任教工程數學及電磁學的柯盟卿老師開授的“天線場型電腦繪圖”作為畢業專題。
原先的動機是想藉此磨練自己程式設計能力,又可藉由專題對電腦繪圖有一定的探究,再加上柯教授對於學生的要求:只要學生照規定行事、得到成果,其餘的細節絕不過問;當然啦!有任何疑問時,也可以隨時得到他耐心的解說。

當時我選擇了 Borland C++ v3.1 作為軟體開發的整合發展環境,並將內定的語法語意檢查功能全開,以期保障軟體最基本的強固性。此外,於程式撰寫的過程也力求完全利用 C++ 對物件導向程式設計的擴充功能,以達到最佳的學習效果。
這個專題最主要的內涵是要將天線電磁場強度的空間樣式(pattern)以電腦繪圖的型式呈現出來。
其用途除了可用作電磁學課堂上的教學展示外,還可以對於有心研發天線產品的人員建立方便的觀測模型,以減少反覆試作成品而造成不必要的浪費。
最基本的功能要能在給定了軟體關於天線的參數後,把天線四周的電磁波強度顯示出來。
經由分析,在工程實務上,只注重天線電磁場的場型(field pattern)。所以在圖形繪出前要先經過正規化(normalization)的處理。
又天線場型強度,其電場和磁場僅相差一個常數,故我們只選定了電場的部分著手。
最後,也決定了讓程式的執行平台最基本的要求在當時最普遍的 286AT 配合 DOS v3.3 的作業系統版本。不過為了繪圖的效果,程式被設計成必須在 640*480 VGA 模式下執行。
※請參閱《天線場型電腦繪圖