• 學位論文

終端路徑覆蓋問題之研究

令G = (V,E)為一有頂點集 V 與邊集 E 的圖，而 T 為 V 之一個子 集，一 G 對於 T 的端點路徑覆蓋PC 是 G 一兩兩頂點互斥路徑的集，此集合覆蓋G 之頂點，使得 T 所有的頂點都是PC中路徑的端點，端點路徑覆蓋問題即是要尋找G 之一具有對於T 最少元素數(minimum cardinality)的端點路徑覆蓋，路徑覆蓋問題乃是端點路徑覆蓋問題在T 為空集合時的一個特殊狀況，而該終端的路徑覆蓋問題是要找到一個終端路徑覆蓋 G 的最小基數。而如果 T 是空的，所描述的問題相吻合於傳統路徑覆蓋問題，在本論文中，我們首先利用一些圖形類別來說明路徑覆蓋問題可以在線性時間上解決路徑覆蓋上的問題，區塊圖則是其中之一，因此，終端路徑覆蓋的問題，可以簡化成路徑覆蓋問題;另一方面，我們給予樹形分解型態(tree-like decomposition structure)，來表示區塊圖(block graph)，要顯示所提出樹形結構的效率，我們用它來設計一個動態規化線性演算法以直接解決終端路徑覆蓋問題，而不使用簡化的技巧，本文亦要證明樹狀圖上的端點路徑覆蓋問題能於線性時間解之。

• 學位論文

以概念查詢評估查詢擴展方法與線上搜尋引擎之資訊檢索效能

當資訊檢索的使用者不知道精確的關鍵字(keyword)時，可能會使用不精確的查詢關鍵字來描述其所需的訊息，嘗試著尋找正確的資訊。我們稱這些不精確的查詢關鍵字為概念查詢(concept query)。我們希望能夠評估線上搜尋引擎與資訊檢索研究者所研發的檢索系統的檢索效能。現有的資訊檢索測試集不適合用於評估概念查詢，因為目前標準的資訊檢索大型測試集，如TREC、CLEF、NTCIR，這些測試集所使用的典型的查詢主題(topic set)都包含了精確的查詢詞以及其主題說明，並不包含概念查詢。而且要提供線上搜尋引擎與一般資訊檢索系統一個一致性的評比環境是很困難的，因為面對的文件集不相同。 在本篇論文中，我們提出一個新的想法，利用公開的線上百科全書-維基百科(Wikipedia)的釋出資料(dump data)，與線上搜尋引擎的指定網域搜尋的功能，讓線上搜尋引擎與一般非線上的資訊檢索系統有一個一致性的評比環境。並依據TREC、NTCIR等建置資訊檢索測試集的標準流程，來建構一個可以評估線上搜尋引擎與資訊檢索演算法的測試集，藉由蒐集真實世界使用者的概念查詢與精確的關鍵字，來作為測試集中的查詢主題。 在我們的檢索系統中，我們利用此測試集的鏈結結構特性，提出了兩種新的查詢擴展方法。第一種為使用維基百科來作為查詢擴展方法的同義辭典，並與虛擬關聯回饋的查詢擴展方法結合，我們稱此方法為維基百科查詢擴展。第二種為利用鏈結結構的特性，將鏈結分析演算法的概念加入查詢擴展演算法中，利用鏈出鏈結(Outward Link)與鏈入鏈結(Inward Link)找出查詢詞與文件間的關聯性，來幫助提升檢索效能，我們稱此方法為經由鏈結分析之查詢擴展方法。 實驗結果表明，本篇論文所建構的基於概念查詢的資訊檢索測試集，能夠合理的評估線上搜尋引擎，並且在概念查詢與精確的關鍵字檢索效能的比較，可以明顯的觀察到，概念查詢的檢索效能的確較差，並且我們發現，在使用概念查詢下，虛擬關聯回饋的檢索系統會優於主流的線上搜尋引擎，如:Google, Alta Vista。而在查詢擴展方法的部分，適當的使用維基百科查詢擴展方法的確是可以提升檢索效能，而且只使用維基百科查詢擴展與只使用虛擬關聯回饋查詢擴展間效能的比較，顯示利用維基百科作為查詢擴展的同義辭典是很好的資源。而經由鏈結分析的查詢擴展方法，其表現的效能並不如預期的佳，經由我們實驗的分析，認為經由統計為基礎的檢索方法其效能已經很好，而我們使用基礎的鏈結分析方法，並不足以提供更好的資源來提升檢索效能。

• 學位論文

應用可變增益電路之氫氣偵測器之研究

本文提出由MEMS技術，結合標準CMOS技術製作之3乘3陣列式氣體感測器，藉由陣列式的多重輸入，能同時偵測不同製程之氫氣感測器。本感測晶片在製程上有兩大優點：1.元件陣列結構為懸橋式，當加熱器加熱時，懸橋結構能有效隔絕熱效應所造成之影響。2.採用Poly 2為微加熱器及感測電極材料，在製程上有良好相容性。元件結合可變增益放大電路，透過電路將元件感測之信號放大，以利量測及分析。以往的氫氣感測電路，大都將感測器及處理電路分開製作，此種做法往往造成訊號在介面處失真。本研究以晶片設計搭配微機電技術，透過佈局將感測器及信號前置放大電路整合一起，可減少晶片面積與達到整合效果，整個晶片分微感測器與感測電路兩部分，感測器部分，材料選用與氫氣有較大反應之觸媒金屬Pd；感測電路部分，因不同濃度之氫氣會有不同感測值，因此本電路設計了可變增益放大功能，在以往的放大電路中，常使用電阻比例做為放大信號的比例，此方法易受製程偏移影響，因此在本電路中將使用電容比例做為信號放大的倍率，透過這種作法將有效的改善DC offset所造成的輸出準位偏移影響以及配合交換式運算技術，搭配不重疊時脈信號對放大電路改善取樣時所產生的功率消耗，透過本電路之實現可有效整合感測電路、降低成本以及功率消耗。

• 學位論文

一個有效率的三方金鑰交換協定

網際網路時代的來臨，電腦系統與網路連結造就病毒與駭客在安全性上威脅。三方通訊中，最大優點就是能夠降低一個會議中，所有使用者所需儲存的金鑰數。 近年來，在三方通訊研究方面，都是針對使用者雙方利用驗證伺服器公鑰加密，加以保護資訊安全，作為後續接收與驗證伺服器所傳送訊息，然而這樣作法，容易遭受到假冒與密碼猜測攻擊。因此，接著陸續有學者提出不需要使用到驗證伺服器公鑰交換協定，來改善上述問題。架構設計上，主要是讓使用者雙方透過可信賴第三方協助金鑰交換動作，在通訊過程中，驗證伺服器可驗證使用者雙方身分與密碼，並且產生暫時金鑰分送給使用者雙方，讓使用者雙方產生出事後所要協商交談金鑰，而且此協定必需具備防止各類攻擊與提高整體效率，才能符合現今網路中的使用。 在本篇論文中，我們將設計一個有效率的三方認證金鑰交換協定，在我們設計的協定中，通訊雙方必須事先與憑證中心註冊，並且分享個人自選密碼。待雙方通訊時，在雙方公鑰計算中，分別加入另一方身分，讓使用者雙方能夠知道另一方是否為真實通訊對象，防止所謂中間者攻擊。 計算量方面，驗證伺服器分別傳送給雙方不同的暫時金鑰中，去除使用者雙方密碼，不只降低計算量，且仍然保有協定安全性，防止所謂辭典猜測攻擊。與其他學者協定相較下，我們的協定不只降低計算量，同時也達到相同安全性需求，能夠在現今網際網路環境內使用。

• 學位論文

使用EPCglobal GEN-2RFID的產權轉移協定

無線射頻認證(RFID)是一項新興的技術。近年，在許多應用層面上是便利且可行的。然而，也提出了許多值得去討論的安全議題,由於RFID使用無線傳輸環境，有些惡意人士想藉由這個環境取得RFID標籤內的資訊並且侵犯使用者的隱私，即使已經有許多關於RFID安全性的保護方式被提出，許多研究還是經常遭受各式各樣的攻擊。在本篇論文中，我們提出一種可證明安全暨符合EPCglobal 第二代標準的無線射頻產權轉移協定，透過謹慎及仔細的證明，這個方法可以抵抗各種攻擊及確保安全交的易

• 學位論文

命名實體的中英文音譯

在現今網路上，不管是資訊檢索或是機器翻譯等應用上，使用者常常需要使用命名實體(named entity)的音譯詞，音譯詞可以幫助使用者可以找到需要的資訊，許多外國命名實體的翻譯是在字眼中找不到的，這就是一般所稱的out-of-vocabulary(OOV) problem，然而音譯常常會因為發音方式的不同或是地方字詞彙的不同而會有不一樣的結果，在真實世界中一個命名實體常常會有一名多譯的狀況發生，例如"Bush"會被音譯為"布希"或是"布什"等。 在本篇論文中，我們主要是針對英文對中文跨語言資訊檢索所遇到音譯以及命名實體消歧義兩個問題進行探討，我們利用機器學習演算法，對於音譯的一名多譯以及OOV的問題進行學習，提供使用者多個恰當的音譯候選詞，並且協助使用者適應網路上一名多譯的狀況，我們的系統會提供恰當的音譯詞組提供給使用者使用。 我們主要是使用Named Entity Workshop Shared task 2009(NEWS 2009)以及維基百科(Wikipedia)的資料進行實驗，NEWS主要提供一個由新華社音譯的語料庫，新華社針對音譯詞進行音譯會遵循較嚴謹的規則以及中文字，在訓練資料中會有一個英文名稱對應一個中文音譯，維基百科是網路上一個開放式的百科全書，可以讓所有使用者進行編輯，維基百科擁有266種語言版本，由於是線上由全球的使用者進行編輯，因此並沒有遵循翻譯規則，針對發音以及使用的字詞也會有所不同，因此我們擷取維基百科中擁有中英文雙語條目的音譯詞進行實驗，比較正規式音譯所訓練出來的模型測試非正規音譯詞的狀況。由實驗結果發現，利用正規音譯所訓練出來的音譯模型在測試正規音譯與非正規音譯的效果差距很大。

• 學位論文

時間派翠網路的工作流程分析

工作流程管理已經被認為是一個企業成功的重要因素。基於合作夥伴 所提議的工作流程方案，公司是否能夠在截止日期或訂單時程內完成交付 而做出正確的決策，這對公司而言是很重要問題。本研究的目的是建立一 個有效的計算方法來分析時間的工作流程。許多研究指出派翠網路（Petri Nets）能夠充分表達工作流程的問題和解決複雜的時序分析問題。我們提出 一個時間性工作流程網路問題，而這個網路模型屬於工作流程網路中的特 殊問題。我們提出一個演算法來計算最早完成的時間，以及開發一個支援 已標準化派翠網路標記語言（Petri Net Markup Language, PNML）格式的工 具，來幫助工作流程管理中的決策工作。

• 學位論文

利用模糊克伯經驗學習理論於學習策略之資訊分群工具

教育部「九年一貫」課程特色使課程保持相當彈性，並將國中課程內容連貫起來，希望教師能騰出更多心力安排彈性教學時間，進行適性化的教學。但一個老師必須面對三、四十位學習風格迥異的學生，許多老師都深感到困惑，如何提供適合的學習策略幫助學生學習，也讓老師能夠適時掌握學生的學習風格，達到因材施教的適性化教學目的。 在許多適性化教學的相關研究中，通常僅加上資訊技術提供個人化之服務，而忽略了學生的學習風格也是影響學習的重要因素。而且在這些研究的結論都已經證實了學習風格的考量可以大幅提升學生的學習效率。因此，如何在學習策略中加入學生個人的學習風格因素，已成為未來可以更深入探討的主題。 本研究主要探討國中生學習英語適性化的學習策略，利用灰關聯分析法找出結合Kolb的學習風格與Oxford的學習策略之灰關聯度，並提出結合Fuzzy C-means理論的資訊分群工具。以此工具在分群定位學生學習風格的同時，實現類人性化所作的整體性判斷，使其更合乎邏輯性，也避免了傳統方法論的主觀不確定性。藉此研究可以幫助學生了解自己的學習風格，也可檢視採行的學習策略是否得當；此外老師更可以根據班級學習風格分佈狀態，修正或建議學生的學習策略，以提高教學成效。

• 學位論文

植基於差異演化之類神經網路於臉部辨識應用

臉部辨識已經廣泛的被應用在很多地方，多數的臉部辨識方法是聚焦在二維影像的探討，我們提出一個創新的方法結合二維臉部特徵資訊及三維的臉部深度資訊，接著我們使用賈伯小波強化二維影像的區域特徵向量在不同角度及方向的特徵資訊，然後我們結合二維臉部特徵資訊及三維臉部深度資訊，使用主成份分析法來取得二維臉部及三維臉部深度的特徵向量資訊，在辨識方面，我們提出植基於差異進化之多層類神經網路於臉部辨識應用。經實驗結果證明我們所提出的方法可以有效的辨識不同臉部表情及不同臉部姿勢的人臉。另外，我們也比較不同特徵數量的臉部資訊及測試在不同隱藏層數量，實驗結果證明我們提出的差異演化法擁有較穩定的辨識效果，也證明了結合二維臉部特徵及三維臉部表面特徵向量的方法，可以有效的提升臉部辨識率的效果。

• 學位論文

和弦辨識利用植基於粒子群最佳化之類神經網路

音樂和弦的序列可以幫助音樂家或音樂創作者進行音樂的編曲或旋律的伴奏，為了實現和弦辨識，我們提出了一個使用類神經網路為架構的方法，並且使用粒子群最佳化(PSO)及倒傳遞(BP)兩種不同的演算法，來幫助尋找類神經網路中最適合的權重。所有使用於類神經網路中訓練用與測試用的資料，都是透過人工將旋律錄製成樂器數位介面(MIDI)格式檔，然後再將MIDI檔轉換成實驗用的數字型態資料。此外，為了要增加辨識的效能，本研究還在資料中加入了一個幫助辨識的特徵值─終止式特徵值；終止式不僅呈現了一段樂句的標點頓挫，而且又是和弦辨識的一個重要依據。在實驗結果方面，由實驗的數據可以得知終止式特徵值明顯地提升了和弦辨識率，而使用粒子群最佳化演算法比使用倒傳遞演算法之類神經網路，具有更佳的和弦辨識能力。然而，我們發現在實驗數據中，即使是相同參數的實驗所產生的辨識率，也會不穩定地在某個範圍內變動，所以為了讓辨識率更精確穩定，我們預先挑選了幾組能產生較佳辨識率的類神經網路，應用在本研究所提出的兩階段類神經網路模型中，把不同的辨識結果融合在一起，進而產生更好的辨識率。