資訊工程學系
Permanent URI for this communityhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/60
本系前身「資訊教育學系」成立於民國七十四年，首先招收大學部學生，民國九十年成立資訊工程研究所碩士班，而後於民國九十五年進行系、所調整合併為「資訊工程學系」；並於九十六年成立博士班。本系目前每年約招收大學部四十餘人，碩士班六十餘人，博士班約五人，截至民國一百零四年十一月止，總計現有大學部一百九十多人，碩士班一百二十多人，博士班二十三人，合計學生人數約為三百三十多位。
News
Browse
2 results
Search Results
Item 較高維度演繹競局問題最佳演算法之設計與分析(2009) 黃立德; Li-Te Huang隨著眾多領域中最佳化問題的逐步探索，發現許多重要的問題都能被轉換成演繹競局問題(deductive game)的模型，例如編碼理論(coding theory)、電路測試(circuit testing)、密碼系統破解(differential cryptanalysis)、附加條件搜尋(additive search problem)等問題。換言之，在演繹競局問題上的研究將使其他相關領域問題的求解露出希望曙光，因此發展有效解決演繹競局問題的方法變得不容遲緩。 在過去數十年間，有許多針對演繹競局問題的研究產生。Mastermind與AB game(或稱為Bulls and Cow)是最有名的兩種演繹競局問題，知名的電腦科學家Donald E. Knuth在1976年於論文中介紹此二者並針對Mastermind做相關研究。在本論文中，我們提出一系列理論剪裁(theoretical-pruning)的最佳化方法與數學證明來解決這兩種問題。 在運用這些新方法到欲解決的問題後，我們得到下列新的成果： (1)我們提出一個適用於各種演繹競局問題的admissible heuristic。同時，我們根據此admissible heuristic，提出一個更有效率的演算法來解決Mastermind，最後亦得到Mastermind在平均狀況下的最佳策略。 (2)針對AB game，我們提出一個更精緻的剪裁演算法(pruning algorithm)來處理它。很幸運地，最後我們得到AB game在平均狀況下的最佳策略且其平均猜測次數為5.213。 (3)我們針對在最差狀況下3×n AB games的最佳策略做理論性的分析。最後我們成功地導出一個計算最差狀況下的最佳猜測次數之公式。 (4)我們研究一個AB game的變型，稱為容許一次錯誤回應之AB game。最終我們求得其最佳猜測次數為8。Item 容許多次錯誤回應之演繹競局問題之研究(2005) 黃立德; Li-Te Huang今日的資訊科學領域日新月異、發展迅速，許多相關應用領域的重要關鍵技術，如：容錯通信（fault-tolerant communication）、電路測試（circuit testing）、附加條件搜尋（additive search problem胝）以及密碼學中的差分密碼分析(differential cryptanalysis)等組合計算最佳化問題皆與演繹競局最佳化問題相關。 在本論文中，我們提出嶄新且有系統的演算法解決著名的Mastermind和AB game等兩個演繹競局問題之變形“容許e次錯誤回應的Mastermind演繹競局問題”與“容許e次錯誤回應的AB game演繹競局問題”。首先我們使用k分支演算法（KWB）針對不同的e值求得此類問題所需猜測次數的上限。藉由分群技巧，KWB演算法能有效且有效率的求得接近最佳的結果。另一方面，我們根據鴿籠原理的觀念，發展出一個以鴿籠原理為基礎的快速式回溯驗證演算法（PPBFB）來求出所需猜測次數的下限。這是一種電腦輔助驗證演算法，在搜尋過程中它能估計競局樹的高度，且當高度超過我們欲驗證的值時，就回溯並繼續驗證其他分支。此外我們更進一步提出「容量更新」和「預先處理」二種創新的技術，能更有效的提升下限估計的準確度和搜尋的速度。 我們提出的KWB演算法與PPBFB演算法可推廣到任意次數錯誤回應之演繹競局問題，而且若使用KWB演算法時，在空間與時間允許的情況下，我們可以增加k值，以求出更好的策略。目前我們使用KWB演算法和PPBFB演算法得到以下的成果： (1) 對容許一次錯誤回應的Mastermind，我們求得此問題所需的猜測次數之上限和下限皆為7。因此我們完整的解決此問題而且求出在最差情況下最佳的猜測次數為7。 (2) 對容許一次錯誤回應的AB game，我們得到此問題所需的猜測次數之上限為9、下限為8。 (3) 對容許二次錯誤回應的Mastermind，我們求得上限與下限分別為10和7，而對容許二次錯誤回應的AB game，得到的上限與下限分別為15和8。 此外，針對容許一次錯誤回應的Mastermind與容許一次錯誤回應的AB game，我們將找到的競局策略表示成遞迴表示法，並實作成線上對局系統，供作後續驗證及研究之用。