學位論文

Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912

Browse

Filter results by typing the first few letters
Now showing 1 - 20 of 949
  • No Thumbnail Available
    Item
    2×n踩地雷一致性問題之研究
    (2006) 胡淑琼; Hu Shu-chiung
    踩地雷是微軟作業系統上非常流行的一套單人電腦遊戲，自從Richard Kaye在2000年證明了踩地雷問題是NP-complete之後，近年來有許多學者投入這方面的研究。Meredith Kadlac提出了一維的踩地雷遊戲，並証明了一維踩地雷一致性問題(One-dimensional Minesweeper Consistency Problem)是非常容易處理的，且可以用一個決定性的有限狀態機(DFA)來判斷一個一維踩地雷的盤面是否一致。我們將此一致性問題延伸至2×n踩地雷盤面上，2×n踩地雷是二維的，但其中一個維度被限定為2。我們發現這個問題也是可克服的，我們成功的設計了一個有限狀態機，其可在線性時間內解出2n踩地雷一致性問題，因此，我們證明了2×n踩地雷一致性問題的複雜度亦為P。
  • No Thumbnail Available
    Item
  • No Thumbnail Available
    Item
    5五將棋程式Wonders的設計與實作
    (2014) 張懷文
    利用人工智慧與人對弈的這個概念，可以追溯自1769年。但直到了1950年，人工智慧這個領域出現了一位Shannon教授致力於如何發展能夠與人對弈的西洋棋程式，這領域的研究才逐漸有穩定發展的方向。許多後來從事電腦對局領域的相關研究人員，也都跟隨Shannon教授的觀念發展而來。直至現今，無論是西方的跳棋、西洋棋、五子棋、撲克牌，抑或是東方的象棋、暗棋、孔明棋、將棋等等，許多的對弈遊戲皆成為電腦對局領域裡面研究的項目。 其中日本的mini-shogi(5五將棋)，為日本將棋於1970年左右發展的其一分支。並於2007年開始，發展國際電腦對局的相關賽事。由日本的電氣通信大學所舉辦的UEC Cup到ICGA的Computer Olympiad，5五將棋已經成為在國際賽事中被熱烈參與的項目之一。在台灣近幾年也被TCGA(Taiwan Computer Games Association)和TAAI(Technologies and Applications of Artificial Intelligence)列為固定的競賽項目之一了。 本研究論文中實作之程式Wonders，利用alpha-beta搜尋來幫助我們找到最佳走步。並且利用嶄新的審局函數快速的減少搜尋分支，以減少執行時間。另外我們也使用暫存表以及Zobrist hashing 和 bitboard的技術來提升程式的計算效能。從2011年研發至今，Wonders於2013年的TAAI 電腦對局競賽當中獲得5五將棋的金牌，期望在未來能夠有更穩定且具有突破性的研究發展。
  • No Thumbnail Available
    Item
    A Multi-level Hierarchical Index Structure for Supporting Efficient Similarity Search of Tagsets
    (2011) 熊薇; Nonhlanhla Shongwe
    In this thesis, we propose a multi-level hierarchical index structure to support efficient similarity search for tagsets. The proposed method is designed based on a previous method which supports similarity search in transaction databases with a two-level bounding mechanism. Similar to the previous method, the tagsets are incrementally grouped into clusters. However, a cluster may have sub-clusters in our approach. The tagsets in a leaf-cluster are grouped into batches. Three different thresholds are used to control the degree of similarity at each level of the index structure. Furthermore, we require the tagsets in the same cluster containing at least one common tag to prevent from grouping unrelated tagsets into a cluster. The experimental results show that the proposed multi-level hierarchical index structure provides better performance on execution time of searching than both the proposed method and the naïve method significantly. Besides, with the assistant of an inverted list of clusters, the execution time of the proposed method for deletion and updating is also much better than the other two methods.
  • No Thumbnail Available
    Item
    Accessible Web Page of Indian Tourist Spots
    (2016) 帕格蒂; Muley, Pragati
    抽象 在現今的社會中，網路科技變得不可或缺，網路與其相關服務在我們的生活中隨處可見，政府與企業間也透過網路互相交流連結。讓網站對大眾開放且容易取得是無障礙網站未來科技發展創新的關鍵。因此，本研究利用Hypertext Markup Language 5 (HTML5) 及其他工具，建立了一個更有親和力且具革命性創新的無障礙網站，以改善日常生活的不便。單有美觀卻不具親和力的網站是無法展現網站完整潛能的。 本研究提出了數個與現代網頁相關的技術及種類，包括HTML5、 CSS3、jQuery 及 JavaScript。此網頁包含了很多張圖片、一支影片以及15個印度熱門觀光景點的介紹資訊。此無障礙網站包含了數個高親和力的新特點，例如影像切換功能、影片、配合音效的CSS3與拍立得影像畫廊。本網站依照網頁內容親和力方針2.0 (WCAG 2.0) 來設計，使用者可以輕易地在任何瀏覽器上使用，包括電腦及智慧型手機。 Keywords: WWW, HTML5, CSS3, jQuery, JavaScript, AJAX and WCAG 2.0.
  • No Thumbnail Available
    Item
    AIR Tester: 針對腳本語言與網頁應用程式之侵入式回歸測試工具
    (2011) 陳羿勳; Yi-Hsin Chen
    在各種網頁應用程式與服務(以下簡稱網路服務)普及化的同時，網路服務的安全與穩定成為新的議題。網路服務經常被新增或修改功能，在這些修改過程中，可能會更動到之前的程式碼，造成新的安全性問題而未發覺。為了避免此類問題，在開發過程中導入回歸測試(Regression Testing)是常見的解決方案。 然而傳統式的網路服務回歸測試只會模擬使用者輸入，並檢查網頁上輸出的資訊；對於許多網路服務而言，僅檢查輸出資訊將可能遺漏許多有用的資訊，包括：SESSION、COOKIE記錄、POST信息，或其他不會輸出在網頁上的資訊。若在這些資訊中發生錯誤，將很可能被忽略，這對於網路服務的安全性將無法達到有效的改善。 為了解決上述網路服務安全性的問題，本研究開發了一套針對網路服務的回歸測試工具，利用自動化分析的方式來進行程式嵌入(Program Instrumentation)，減輕開發人員或測試人員的負擔。
  • No Thumbnail Available
    Item
    Alghalith 美式選擇權定價公式評估
    (2024) 黃湘庭; Huang, Hsiang-Ting
    選擇權定價利用數學模型來評估在未來某個時間點或期間內買賣標的資產的權利的合理市場價值。Black-Scholes模型為歐式選擇權提供了一個簡單、計算高效的封閉解公式。對較為複雜的美式選擇權，在2020年Alghalith為美式選擇權導出了一個簡單的公式解。本文將分析、檢驗該公式解於理論上的定價效果，並加以微幅修正。
  • No Thumbnail Available
    Item
    AlphaZero演算法結合快贏策略或迫著空間實現於五子棋
    (2020) 劉浩萱; Liu, Hao-Hsuan
    AlphaZero是一個通用的強化式學習之演算法，除了遊戲規則外毫無人類知識，經過訓練後會有極佳的結果。為了要讓此架構在訓練初期，就能夠成功學習到五子棋所需的獲勝資訊，本研究展示了快贏策略(Quick Win)與迫著空間。 快贏策略旨在讓類神經網路學習到快贏的價值，並且在各走步勝率相同時，能更傾向選擇可以快速獲得勝利的走步；迫著空間則是針對盤面的迫著做搜索，讓能產生迫著走步的資訊被類神經網路學習，以縮短訓練時間。 本研究以四種不同的實驗方式，包含線性距離權重、指數距離權重、結合迫著搜尋於距離權重，以及結合迫著搜尋於蒙地卡羅樹搜索法的方式，觀察AlphaZero為設計基礎的人工智慧模型，在對弈時是否因為選擇了更快獲勝的棋局走步或學會形成迫著，而有效增強棋力。
  • No Thumbnail Available
    Item
    ArCats局部性模型分析安全性質和活化性質
    (2006) 徐志文; Zhi-Wen Hsu
    近年來，局部性模型分析在自動化軟體驗證領域中佔有一席角色。局部性模型分析能夠成功的關鍵在於檢驗的系統模型具有良好的階層架構，同時盡量利用最小化的技術減化子系統的內部行為，達到減緩組態爆炸的發生。透過模型架構重構可以解決不良的模型架構，這增強局部性分析的效能。當利用局部性分析檢驗系統性質時，因為保留過多的系統性質到全域系統中，造成子系統無法最小化的結果，這將大幅消減局部性分析在模型驗證中的效能。 在本篇論文中，我們根據ArCats和其在局部性分析中所提供的良好功能，開發出能夠檢測系統安全性質(safety)和活化性質(liveness)的功能，同時並能夠維持局部性分析的減緩狀態爆炸的優勢。在檢驗安全性質時，我們利用一種類似死結狀態的π狀態，讓違反安全性的系統行為能夠被偵測出來。而在檢驗活化性質時我們使用一種特殊的接受轉移（accept transition）來代表系統符合檢驗性質。這兩種在局部性分析中檢測性質，主要參考Cheung[28][29][30]的研究。但是由於ArCats是以CCS為基礎來提供模型架構重構的功能而Cheung的研究採用的是CSP，本篇論文將針對如何利用以CSP為基礎的驗證技術實做到以CCS為基礎的驗證工具中，同時探討與解決所面臨的困難。
  • No Thumbnail Available
    Item
    ATP: 用於無電池物聯網裝置的自適應傳輸策略
    (2022) 彭成聖; Peng, Cheng-Sheng
    能量收集技術 (Energy harvesting) 實現了物聯網 (IoT) 系統中自我維持的願景。開發人員可以利用此項技術從環境中收集能量，以補充裝置在運行過程中消耗的能量。為了支持長時間或耗電的任務執行，多數的無線感測器節點選擇電池作為其電源。然而，電池對環境是有害的，需要定期地人力維護以保持電池的清潔和無腐蝕。近年來，使用電容代替電池的無電池物聯網系統在降低成本和提高安全性方面帶來了好處。這些系統在任務執行後將感測器節點設置於睡眠模式以幫助電容充電，並調整佔空比 (duty cycle) 以實現長期運行。與電池相比，電容的能量儲存空間很小，裝置很容易因為能量不足而出現斷電的情形。因此，更有效率地利用有限的能源並確保任務能夠成功執行是很重要的。對於無電池的感測應用，維持感測速率有助於評估環境中事件發生的前因後果與隨時間的變化。若能根據環境條件調整節點的傳輸間隔，有助於平衡能量供需。本論文分析了無電池的物聯網感測裝置任務執行所需的電容電壓，並提出了自適應傳輸策略 (稱為 ATP) 及應用批處理 (batch processing) 來保持電容的能量水平。ATP 的目標是保持感測速率，並儘可能地提高有效吞吐量 (goodput)。ATP 有三種實作方法：基於閾值 ATP、數學預測 ATP 與改良的基於閾值 ATP。實驗證明，當所需的環境條件得到滿足時，所提出的方法有助於感測器節點維持其感測速率。模擬結果表明，ATP 有足夠的穩定性來適應環境的變化; 就傳輸性能（即傳輸時間間隔）而言，數學預測 ATP 有比相關研究與 ATP 的其他兩種方法更好的結果。
  • No Thumbnail Available
    Item
    Blockchain-based Reward for Data Delivery Service with Zero-Knowledge Proof
    (2022) 董郡麟; Tung, Chun-Lin
    隨著資訊化時代的來臨，網路上的資訊量有著爆炸性的成長，使得人們對於通訊相關軟體的使用需求愈趨增加，經過了逐年行動網際網路技術的蓬勃發展、進步，如智慧型手機、個人電腦等電子產品徹底成為了電子市場的主流硬體，已經與現今人們的生活有著密不可分的關係，不管是在學生時期又或是出社會工作每天幾乎都會接觸到電子產品，然而隨著手機上的應用程序與功能愈來愈多，為了確保使用者之資訊安全考量，各大公司通常會藉由OTA來發佈新的韌體版本以保障其客戶之資訊安全，因此OTA的需求也愈趨重要。儘管目前已有許多大公司致力於發展OTA技術，也已經有了相當成熟的功能以提供客戶使用，但現今尚有許多小公司無法支援如此大量的雲端更新系統，因此通常會委託一些大公司幫忙對其客戶做OTA服務並予以報酬，但不能保證每一次OTA委託皆有確實完成，所以要達到公平公正的論件計酬是非常困難的。我們希望藉由加入近年來熱門的主題「零知識證明技術」結合了以太坊區塊鏈中的智能合約，實現出一個由Vendor建構的OTA服務系統，並藉由零知識證明的技術將IoT device的一些私密資訊隱藏起來，同時由代理商證明他已完成相關的委託任務，並生成一組特定的有效證明交由區塊鏈系統上的智能合約進行此proof之驗證，讓合約自動判斷此代理商是否有達到領取報酬之條件，一旦判斷條件皆符合Vendor所制定的條件，合約會將報酬自動轉入代理商的以太坊錢包位址，同樣的若是合約判斷代理商不符合領取報酬之條件，則合約會直接結束程式的執行，並由給出錯誤proof的代理商支付本次呼叫合約的手續費給礦工．以達成一個公平公正的OTA服務系統。
  • No Thumbnail Available
    Item
  • No Thumbnail Available
    Item
    Design and Implementation of a Gesture Recognition Library for Touch-Based Devices
    (2011) 胡晉豪; Hu, Chin-Hao
    觸控裝置（touch-based devices）已經深入日常生活中的每一個角落，越來越多人使用具備觸控裝置的手機與平板電腦。但是在開發使用觸控的手勢做為操作輸入介面的軟體目前使用的方法仍然是針對每一個SDK（software development kit）來開發，例如Apple iOS SDK是使用Cocoa Touch framework來處理多點觸控（multi-touch）的事件。 觸控技術最常見的一個應用是手勢的辨識，但是這些開發工具與裝置中還沒有一個完整的手勢辨識的函式庫提供給開發人員使用。程式設計師必須要使用event handlers或delegate的方式擷取使用者的每支手指在平面上的座標位置。以軟體工程的角度來看，即使只拿來辨識一支手指的手勢，也必需搭配額外的機制或加入辨識的演算法等方式來實作。 本論文提出一個手勢辨識函式庫在觸控裝置的實作方法。我們以client與server的架構來建置本研究的實驗環境。Client端為多點觸控裝置，重點在於能夠傳送手在觸控板上的位置或所辨識出的手勢給server端。Server端在收到訊息後會針對與之連結的應用程式做出相對應的動作。手勢辨識的部分重點在於實作$1與$N gesture recognizer演算法。前端擷取特徵的部分搭配SVM（Support Vector Machine）進行學習與分類以辨識出是何種手勢，除此之外也能夠讓使用者自行定義手勢並透過反覆的訓練（training）相同的手勢達到準確度提升的效果。
  • No Thumbnail Available
    Item
  • No Thumbnail Available
    Item
    Diversity and Quality: Comparing Decoding Methods with PEGASUS for Text Summarization
    (2021) 唐科南; Thompson, Keenan Nathaniel
    none
  • No Thumbnail Available
    Item
    DTS演算法效能改良之研究
    (2007) 白聖秋
    電腦西洋棋在近年來已經大量使用平行搜尋演算法，目前表現最好的是使用DTS（Dynamic Tree Splitting）搜尋演算法，該演算法的作者Robert M. Hyatt所設計出來的電腦西洋棋程式Crafty也在2004年第12屆World Computer Speed Chess Championship比賽獲得第二名。 本篇論文主要研究DTS（Dynamic Tree Splitting）搜尋演算法，發現使用一些改良技巧，如改良方法一的控制CPU分配量與改良方法二的控制允許使用DTS搜尋演算法的最低層數，能將DTS（Dynamic Tree Splitting）搜尋演算法在電腦西洋棋程式中獲得更好的效能。我們也使用開放程式碼的Crafty20.14版做實驗，目前研究結果發現改良方法一能提升20％左右的效能，而改良方法二能提升35％左右的效能。
  • No Thumbnail Available
    Item
    Dynamic Generation of a Facet Hierarchy for Web Search Result
    (2014) 張崴; Wei, Chang
    In this thesis, we propose a method to construct a facet hierarchy to organize the web search results dynamically. The proposed method is designed by two steps. First, we extract candidate facet terms according to a knowledge base. Second, we construct a facet hierarchy according to the candidate facet terms. We design an objective function to simulate the browsing cost when a user accesses the search results by a facet hierarchy. Accordingly, two algorithms are proposed to construct a facet hierarchy to optimize the objective function. The first one is a bottom-up approaches which select the best facet terms from the lowest level iteratively. The second one is a top-down approach, which uses an entropy function to estimate the expected browsing cost to select facet terms from the top level. Both algorithms are greedy algorithms which find optimal solutions. We evaluate the proposed methods on different distributions of access probability. The experiment results show that the facet hierarchies construct by the proposed methods achieves better performance on saving 30 to 50 percent of expected browsing cost than the one of the existing method.
  • No Thumbnail Available
    Item
    EPUB電子書編輯系統
    (2014) 吳念學; Nian-Xue Wu
    近年來隨著科技產品的推出，人們獲得資訊的方式也跟著改變，原本紙本的資訊，也漸漸轉移到電腦、手機及平板等閱讀工具，進而帶動了電子書的發展。然而不同的閱讀工具，產生了許多不同的電子書格式，因此，國際數位出版論壇（IDPF）制定了EPUB格式的正式標準，以取代舊的開放Open eBook電子書標準。經濟部工業局為了幫助國內業者能快速瞭解EPUB3.0規範內容，與國際同步發展，亦積極推廣使用EPUB格式。 本研究提出了一個在PC或者平板上，結合EPUB電子書的群組編輯系統，因EPUB可以「自動重新編排」內容，也就是文字內容會根據閱讀設備的特性，以最適當的閱讀方式來顯示，所以我們選用EPUB格式的電子書來做研究探討，其使用的技術為XHTML、HTML、PHP、JavaScript等。 本編輯平台的設計可在網頁或者平板上進行操作，能隨時透過線上編輯的方式，多人進行共同編輯，分享資訊及教材內容，並以電子書的瀏覽方式來呈現。本編輯系統可配合校園內師生透過行動載具編輯教材與學習報告，如此一來便可提供一種新的學習管道，讓學習更加有趣。
  • No Thumbnail Available
    Item
    Event Extraction for Gene Regulation Network Using Statistical and Semantic Approaches
    (2014) 班法; Bamfa Ceesay
    Genic regulation networks are the primary study object in systems biology. They allow better understanding of the relationship between molecular mechanisms and cellular behavior. However, one of the bottlenecks in systems biology is the acquisition of an accurate genetic regulation network. In the recent years, the BioNLP community has produced systems for extracting genic interactions and Protein-Protein Interaction (PPI) from the literature. The sporulation network of the bacteria model for bacillus subtilis is very well studied. The automatic design of the gene regulation network is one of the main challenges in biology, because it is a crucial step forward in understanding the cellular regulation system. In this study, we present a description of a system on Gene Regulation Network (GRN) in bacteria and we use the data from the BioNLP’13 shared task (BIONLP-ST) on Event Extraction. For this work, we first propose a procedure to do biological event extraction combining a dependency graph-based method and a method using semantic analysis in Natural Language Processing (NLP). Then a second design, a statistical approach using Hidden Markov Model (HMM), is experimented. Dependency parsing is a significant and commonly used approach to finding out the dependency relationship between tokens in, for example, a sentence. We use dependency features to identify and classify our event trigger tokens using multi–class Support Vector Machine (SVMLight multiclass). However, the dependency features are not sufficient to give the semantic relationship between tokens with a sentence. Therefore, we develop a semantic analysis approach based on NLP techniques to capture more detail information and improve our result on event extraction. In our second design approach, we use a general statistical method via Markov’s logic instead of developing certain inferences and learning algorithms. Markov’s Model has achieved significant recognition in Natural Language Processing especially in the field of speech recognition. Our result shows that the graph-based approach obtains a better result on event extraction and produces a much better regulation network than the semantic analysis method. The combination of the two approaches has yet a much slightly better result than that with the individual approach. Moreover, the proposed statistical approach achieves a much better result than the combined and individual results of our graph-based and semantic analysis approaches.
  • No Thumbnail Available
    Item
    Explainable Anomaly Detection in Surveillance Videos: Autoencoder-based Reconstruction and Error Map Visualization
    (2024) Littek, Alina Raffaella Giulia; Littek, Alina Raffaella Giulia
    none