中央研究院 資訊科學研究所

研究群

友善列印

計算理論與演算法實驗室

研究人員

研究群介紹

本組的研究目標在探討計算問題本身的極限和效用,並為資訊科學其他領域建立穩固的理論基礎。以下簡述幾個我們進行的研究主題。

(1) 量子密碼學

量子密碼學的目標是了解量子計算在密碼學中扮演的角色。對密碼學來說量子可說是一把雙面刃:一方面量子密鑰分配協定使無條件安全的通信成為可能,而另一方面秀爾量子演算法(Shor’s quantum algorithm) 可被用來破解許多我們日常生活中使用的密碼學系統。我們對量子在密碼學的不同角色有廣泛的興趣,探索數個不同的研究方向,其中有些方向是我們提出的。研究的主題包含設備無關量子密碼學、安全的量子計算、處理量子邊信息的後量子密碼學( 如防量子洩漏密碼學) 與探索新的量子密碼學假設與任務。

(2) 幾何計算

Voronoi 圖形有非常廣泛之用途,此幾何結構所具有的性質及複雜度,其建構所需要的時間等,是幾何計算領域的核心問題。當引進「抽象距離」的概念,Voronoi 圖形也會因而產生變化。諸如其特性與所選定的「距離」如何相依改變,如何利用「距離」的某些性質設計高效率的演算法,是我們欲探討的基本問題,而相關的應用問題,包括以時間距離為基礎的最短路徑規劃、相同功能的競爭型設施配置問題、或是不同功能的合作型設施配置問題等,這類問題亦是交通網路、無線感測網路、或超大型積體電路設計等領域裡,同時具有理論重要性與實際應用價值的研究課題。

(3) 組合最佳化與近似演算法

我們考慮一系列與傳統最小支配集問題以及節能排程相關的組合最佳化問題、以及相對應的近似演算法研究。前者包括了將節點容量以及節點的需求納入資源分配的考量、以及更進一步考慮設施配置的成本問題。這問題在近似演算法領域已有廣泛的研究,近幾年來更有相當程度的進展。而後者則是以演算法設計與分析的角度,透過改善傳統的排程方法,搭配系統硬體的節能機制,如低耗電待機模式、與電壓頻率微調,來達到節能的目的。在演算法的基礎研究過程,我們不僅要設計高效率的演算法或最佳的近似解,而且要發展具根本的分析技巧與工具,來解決更具廣泛應用的相關問題。

(4) 巨量資料

巨量資料之邏輯與知識表達:
巨量資料之中隱藏許多有用的資訊與知識,我們將以形式邏輯的方法來探討相關的知識表徵與推理問題。

巨量資料相關之高速演算法設計:
近年來大量資訊很容易在線上取得。我們研究如何利用這些巨量資料進行快速計算。研究題目包含傳染性疾病散播模型之快速動態計算理論與演算法組實驗室模擬、疾病網路之建構和視覺化呈現、電腦對局理論和實作。

排版插圖

排版插圖

(5) 基礎圖論

圖論可以解決許多實際應用問題,而且也是很多理論研究的工具。我們通常先由基礎圖論性質的研究著手,然後藉由新性質的發現,設計高效率演算法,再進一步探討理論之突破,以及可能的應用價值。我們探討於實際應用產生的圖論演算法問題。目前的研究重點之一為河流模式(streaming model) 下之演算法設計。

(6) 機器學習理論

在日常生活中,我們時常必須不斷在未知的環境中作決定,並為此付出代價。這可被抽象化為所謂的線上決策問題,而我們希望能為此問題設計出好的線上演算法,可以從過去的歷史中學習,而能在未來做出好的決定。對此問題,我們刻畫出一些自然而常見的環境條件,並在這些條件下設計出更有效率的線上演算法。此外,我們也為此問題在機器學習、賽局理論、複雜度理論等研究領域中找到新的應用。

(7) 機器人

我們的工作專注在有環境拘束( 例如避障) 與動態拘束( 例如曲率、速度、加速度限制) 的輪型機器人的路徑 / 軌跡規劃及導航,以及擴充到三維的環境 ,例如無人機的路徑/ 軌跡規劃及導航、輪型機器人在非平面路面運動的的路徑/ 軌跡規劃及導航問題方面。我們基於拉普拉斯偏微分方程的邊界值問題數值解法,發展一個使用流線的避障系統,經由輪型機器人導航實驗與有限差分法數值模擬,驗證這個系統的即時性、隨時性。