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

[研究群介紹]

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

網路設計與分析:網路設計問題探討的是如何將許多不同 位置的站點,經由適當的網路架構連結以滿足特定的需 求。這類問題涵括了許多不同領域內的核心議題,例如超 大型積體電路設計、無線傳感器網路、生物資訊學及通訊 網路等。在不同的應用領域,這些問題透過各式各樣的效 能評估方式及限制條件,以不同的形式出現,而其間又存 在著微妙的共通性。
二、幾何計算
Voronoi圖形有非常廣泛的用途,是幾何計算領域學者長期 研究的重要幾何結構。此結構所具有的性質及複雜度,還 有如何計算而得等等都是幾何計算演算法的基本問題。當 引進不同的「距離」概念時,例如「時間距離」,Voronoi 圖形也會跟著變化。而其特性與所選定的「距離」如何互 動改變,如何利用「距離」的某些性質,設計更有效率的 演算法是我們所欲探討的問題。
三、機器人相關系統
發展機器人相關的系統設計、感測、規畫、控制的基礎理 論和整合技術、情感與認知計算,讓人能安全舒適的與機 器人進行必要的互動,使機器人能成為人類生活(包含食、 衣、住、行、育、樂)的好夥伴與好幫手,是當前及未來機 器人研發的重要課題。我們正進行機器人的模擬與實驗研 究為:基於地圖重建的自主導航與控制,平滑路徑規劃的 軟性計算方法,以及整合感測網路與機器人的研究。
排版插圖四、資料密集計算
巨量資料之邏輯與知識表達:巨量資料之中隱藏許多有用 的資訊與知識,我們將以形式邏輯的方法來探討相關的知 識表徵與推理問題。

巨量資料相關之高速演算法設計:近年來大量資訊很容易 在線上取得。我們研究如何利用這些巨量資料進行快速計 算。研究題目包含資料隱私保護、多方私密計算、電腦對 局理論和實作及大型社群網路的動態模擬。
五、複雜度理論
亂數在計算上,已成為一個有用的資源,因為隨機演算法 對許多重要計算問題提供了目前最有效率的解決方法。然 而一般隨機演算法的設計,均假設有完美的亂數供其使 用。然而電腦或自然界能否存產生完美的亂數,也是一個 值得爭議的問題。解決此困境的第一種方法,乃是研究如 何將隨機式演算法有效率的轉化成確定式演算法。我們研 究如何在合理的假設下達成這個目的,我們也研究這種方 法的可能極限。解決困境的第二種方法,乃是設計所謂的 亂度淬取程序,來由稍具亂度的弱亂數源中,淬取近乎完美的亂數,以 供隨機演算法使用。我們建構出目前最有效率的亂度淬取程序,而我們 也發現亂度淬取程序於密碼學的應用。
六、密碼學
特殊硬體密碼學:包括微控制器晶片 (microcontroller, 即智慧卡的主 要組件),可即時重新程式化的電路陣列 (Field Programmable Gate Array, FPGA) 上面的密碼學演算法。利用計算機的顯示晶片來做橢圓曲 線的計算,可在破密上獲得破紀錄的速度。我們也做出低電流低耗能可 以在 RFID 上執行的數位簽章演算法。最近也進行使用智慧型手機或其 他類似的裝置來協助進行認證的資訊交換,或其他實用上的資訊安全研 究。

後量子密碼學:研究一種以處理多個小有限體中的變數,來取代大代數 結構中的元素的多變量的公鑰密碼系統(MPKC),它被認為是在量子電腦 發明之後可能存續的公鑰密碼系統 (Post-Quantum Public-Key Cryptosystem) 的一個重要分類,該類系統一般也有高效能的名聲,適合用 在小或嵌入式系統上。

代數攻擊:XL 演算法為一種解方程式的技巧,幫助終結了線性回饋平移 暫存器 (Linear Feedback Shift Register) 作為加密技術的時代,我們對 它首度作了完整的分析,並推廣到一些其他的應用。
排版插圖

相關資訊

Academia Sinica 資訊科學研究所 Academia Sinica