中研院資訊所

計算理論與演算法實驗室
Principal Investigators:
王大為 Da-Wei Wang (Chair) 呂及人 Chi-Jen Lu 李德財 Der-Tsai Lee
徐讚昇 Tsan-sheng Hsu 高明達 Ming-Tat Ko 楊柏因 Bo-Yin Yang
廖純中 Churn-Jung Liau 劉進興 Jing-Sin Liu 鐘楷閔 Kai-Min Chung

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

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

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


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

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

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


排版插圖排版插圖


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

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

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