Page 40 - 2017 Brochure

究群
計算理論與演算法組實驗室
本組的研究目標在探討計算問題本身的極限和效用，並為
資訊科學其他領域建立穩固的理論基礎。以下簡述幾個我
們進行的研究主題。
(1) 量子密碼學
量子密碼學的目標是了解量子計算在密碼學中扮演的角色。
對密碼學來說量子可說是一把雙面刃：一方面量子密鑰分
配協定使無條件安全的通信成為可能，而另一方面秀爾量
子演算法 (Shor’s quantum algorithm) 可被用來破解許多我 以及更進一步考慮設施配置的成本問題。這問題在近似演
們日常生活中使用的密碼學系統。我們對量子在密碼學的
不同角色有廣泛的興趣，探索數個不同的研究方向，其中
有些方向是我們提出的。研究的主題包含設備無關量子密
碼學、安全的量子計算、處理量子邊信息的後量子密碼學
( 如防量子洩漏密碼學 ) 與探索新的量子密碼學假設與任務。
(2) 幾何計算
Voronoi 圖形有非常廣泛之用途，此幾何結構所具有的性質
及複雜度，其建構所需要的時間等，是幾何計算領域的核
心問題。當引進「抽象距離」的概念，Voronoi 圖形也會因
而產生變化。諸如其特性與所選定的「距離」如何相依改
變，如何利用「距離」的某些性質設計高效率的演算法，
是我們欲探討的基本問題，而相關的應用問題，包括以時
間距離為基礎的最短路徑規劃、相同功能的競爭型設施配
置問題、或是不同功能的合作型設施配置問題等，這類問
38 研究群 Research Laboratories
題亦是交通網路、無線感測網路、或超大型積體電路設計
等領域裡，同時具有理論重要性與實際應用價值的研究課
題。
(3) 組合最佳化與近似演算法
我們考慮一系列與傳統最小支配集問題以及節能排程相關
的組合最佳化問題、以及相對應的近似演算法研究。前者
包括了將節點容量以及節點的需求納入資源分配的考量、
算法領域已有廣泛的研究，近幾年來更有相當程度的進展。
而後者則是以演算法設計與分析的角度，透過改善傳統的
排程方法，搭配系統硬體的節能機制，如低耗電待機模式、
與電壓頻率微調，來達到節能的目的。在演算法的基礎研
究過程，我們不僅要設計高效率的演算法或最佳的近似解，
而且要發展具根本的分析技巧與工具，來解決更具廣泛應
用的相關問題。
(4) 巨量資料
• 巨量資料之邏輯與知識表達：巨量資料之中隱藏許多有
用的資訊與知識，我們將以形式邏輯的方法來探討相關
的知識表徵與推理問題。
• 巨量資料相關之高速演算法設計：近年來大量資訊很容
易在線上取得。我們研究如何利用這些巨量資料進行快
速計算。研究題目包含傳染性疾病散播模型之快速動態