Page 39 - profile2012.indd
P. 39

Research Laboratories  研究群



                                       計算理論與演算法實驗室


 Computation Theory




 and Algorithms  Laboratory




 研究人員


 王大為 Da-Wei Wang  呂及人 Chi-Jen Lu  李德財 Der-Tsai Lee  高明達 Ming-Tat Ko  徐讚昇 Tsan-sheng Hsu  楊柏因 Bo-Yin Yang  廖純中 Churn-Jung Liau  劉進興 Jing-Sin Liu
 Research Fellow  Research Fellow  Distinguished Research Fellow  Research Fellow  Research Fellow  Associate Research Fellow  Research Fellow  Associate Research Fellow



 研究群介紹


 一、圖論與圖論演算法  亂度淬取程序，來由稍具亂度的弱亂數源中，淬取近乎完美的亂數，以
           供隨機演算法使用。我們建構出目前最有效率的亂度淬取程序，而我們
 基礎圖論：圖論可以解決許多實際應用問題，而且也是很  也發現亂度淬取程序於密碼學的應用。
 多理論研究的工具。我們通常先由基礎圖論性質的研究著
 手，然後藉由新性質的發現，設計高效率演算法，再進一  六、密碼學                                              計算理論和演算法研究在
 步探討理論之突破，以及可能的應用價值。我們探討於實
 際應用產生的圖論演算法問題。  特殊硬體密碼學：包括微控制器晶片 (microcontroller,  即智慧卡的主                    探討計算問題本身的極限
           要組件)，可即時重新程式化的電路陣列 (Field Programmable Gate                         和效用，為電腦科學之基
 網路設計與分析：網路設計問題探討的是如何將許多不同  Array, FPGA)  上面的密碼學演算法。利用計算機的顯示晶片來做橢圓曲
 位置的站點，經由適當的網路架構連結以滿足特定的需  線的計算，可在破密上獲得破紀錄的速度。我們也做出低電流低耗能可                     石。
 求。這類問題涵括了許多不同領域內的核心議題，例如超  以在 RFID  上執行的數位簽章演算法。最近也進行使用智慧型手機或其
 大型積體電路設計、無線傳感器網路、生物資訊學及通訊  他類似的裝置來協助進行認證的資訊交換，或其他實用上的資訊安全研
 網路等。在不同的應用領域，這些問題透過各式各樣的效  究。
 能評估方式及限制條件，以不同的形式出現，而其間又存
 在著微妙的共通性。  後量子密碼學：研究一種以處理多個小有限體中的變數，來取代大代數
           結構中的元素的多變量的公鑰密碼系統(MPKC)，它被認為是在量子電腦
 二、幾何計算  四、資料密集計算  發明之後可能存續的公鑰密碼系統 (Post-Quantum Public-Key Cryp-
           tosystem)  的一個重要分類，該類系統一般也有高效能的名聲，適合用
 Voronoi圖形有非常廣泛的用途，是幾何計算領域學者長期  巨量資料之邏輯與知識表達：巨量資料之中隱藏許多有用  在小或嵌入式系統上。
 研究的重要幾何結構。此結構所具有的性質及複雜度，還  的資訊與知識，我們將以形式邏輯的方法來探討相關的知
 有如何計算而得等等都是幾何計算演算法的基本問題。當  識表徵與推理問題。  代數攻擊：XL 演算法為一種解方程式的技巧，幫助終結了線性回饋平移
 引進不同的「距離」概念時，例如「時間距離」，Voronoi   暫存器 (Linear Feedback Shift Register) 作為加密技術的時代，我們對
 圖形也會跟著變化。而其特性與所選定的「距離」如何互  巨量資料相關之高速演算法設計：近年來大量資訊很容易  它首度作了完整的分析，並推廣到一些其他的應用。
 動改變，如何利用「距離」的某些性質，設計更有效率的  在線上取得。我們研究如何利用這些巨量資料進行快速計
 演算法是我們所欲探討的問題。  算。研究題目包含資料隱私保護、多方私密計算、電腦對
 局理論和實作及大型社群網路的動態模擬。
 三、機器人相關系統
 五、複雜度理論
 發展機器人相關的系統設計、感測、規畫、控制的基礎理
 論和整合技術、情感與認知計算，讓人能安全舒適的與機  亂數在計算上，已成為一個有用的資源，因為隨機演算法
 器人進行必要的互動，使機器人能成為人類生活(包含食、  對許多重要計算問題提供了目前最有效率的解決方法。然
 衣、住、行、育、樂)的好夥伴與好幫手，是當前及未來機  而一般隨機演算法的設計，均假設有完美的亂數供其使
 器人研發的重要課題。我們正進行機器人的模擬與實驗研  用。然而電腦或自然界能否存產生完美的亂數，也是一個
 究為：基於地圖重建的自主導航與控制，平滑路徑規劃的  值得爭議的問題。解決此困境的第一種方法，乃是研究如
 軟性計算方法，以及整合感測網路與機器人的研究。  何將隨機式演算法有效率的轉化成確定式演算法。我們研
 究如何在合理的假設下達成這個目的，我們也研究這種方
 法的可能極限。解決困境的第二種方法，乃是設計所謂的




 研究群
 38  Research Laboratories
                                                                                                                 39
   34   35   36   37   38   39   40   41   42   43   44