計算機演算法專家

Ⅰ 計算幾何:演算法設計與分析作者簡介

周培德，1941年出生於湖北省武穴市，1965年畢業於武漢大學數學系。現任北京理工大學計算機系教授。

在學術領域，周培德教授做出了顯著貢獻。他個人獨立發明的計算機演算法多達160多個，這些創新為計算機科學領域注入了新活力。此外，他發表了超過60篇學術論文，涉及的領域廣泛，展示了他在計算科學領域的深厚研究功底。

周教授的學術成果不僅限於論文，他還出版了3部學術專著，深入探討了計算科學的理論與實踐。此外，他編寫了兩部研究生教材，為培養計算機科學的未來人才做出了貢獻。

周培德教授以其嚴謹的科研態度和卓越的創新能力，成為了中國計算科學界的傑出代表。他的研究成果不僅推動了計算機科學的發展，也為後輩學者樹立了榜樣。

總體而言，周培德教授在計算幾何演算法設計與分析方面做出了重要貢獻，不僅在學術界贏得了高度認可，也為培養新一代計算機科學家做出了巨大貢獻。

本書系統地介紹了計算幾何中的基本概念、求解諸多問題的演算法及復雜性分析，概括了求解幾何問題所特有的許多思想方法、幾何結構與數據結構。

Ⅱ 量子計算機的演算法理論

量子計算機在1980年代多處於理論推導狀態。1994年彼得·秀爾（Peter Shor）提出量子質因子分解演算法後，因其對於通行於銀行及網路等處的RSA加密演算法可以破解而構成威脅之後，量子計算機變成了熱門的話題，除了理論之外，也有不少學者著力於利用各種量子系統來實現量子計算機。
半導體靠控制集成電路來記錄及運算信息，量子計算機則希望控制原子或小分子的狀態，記錄和運算信息。 1994年，貝爾實驗室的專家彼得·秀爾（Peter Shor）證明量子計算機能做出離散對數運算[11]，而且速度遠勝傳統計算機。因為量子不像半導體只能記錄0與1，可以同時表示多種狀態。如果把半導體比成單一樂器，量子計算機就像交響樂團，一次運算可以處理多種不同狀況，因此，一個40比特的量子計算機，就能在很短時間內解開1024位計算機花上數十年解決的問題。 量子計算機，顧名思義，就是實現量子計算的機器。是一種使用量子邏輯進行通用計算的設備。不同於電子計算機（或稱傳統電腦），量子計算用來存儲數據的對象是量子比特，它使用量子演算法來進行數據操作。
要說清楚量子計算，首先看經典計算機。經典計算機從物理上可以被描述為對輸入信號序列按一定演算法進行變換的機器，其演算法由計算機的內部邏輯電路來實現。
1.其輸入態和輸出態都是經典信號，用量子力學的語言來描述，也即是：其輸入態和輸出態都是某一力學量的本徵態。如輸入二進制序列0110110，用量子記號，即|0110110>。所有的輸入態均相互正交。對經典計算機不可能輸入如下疊加態：C1|0110110 >+ C2|1001001>。
2.經典計算機內部的每一步變換都演化為正交態，而一般的量子變換沒有這個性質，因此，經典計算機中的變換（或計算）只對應一類特殊集。
相應於經典計算機的以上兩個限制，量子計算機分別作了推廣。量子計算機的輸入用一個具有有限能級的量子系統來描述，如二能級系統（稱為量子比特（qubits）），量子計算機的變換（即量子計算）包括所有可能的幺正變換。
1.量子計算機的輸入態和輸出態為一般的疊加態，其相互之間通常不正交；
2量子計算機中的變換為所有可能的幺正變換。得出輸出態之後，量子計算機對輸出態進行一定的測量，給出計算結果。
由此可見，量子計算對經典計算作了極大的擴充，經典計算是一類特殊的量子計算。量子計算最本質的特徵為量子疊加性和量子相乾性。量子計算機對每一個疊加分量實現的變換相當於一種經典計算，所有這些經典計算同時完成，量子並行計算。
無論是量子並行計算還是量子模擬計算，本質上都是利用了量子相乾性。遺憾的是，在實際系統中量子相乾性很難保持。在量子計算機中，量子比特不是一個孤立的系統，它會與外部環境發生相互作用，導致量子相乾性的衰減，即消相干（也稱「退相干」）。因此，要使量子計算成為現實，一個核心問題就是克服消相干。而量子編碼是迄今發現的克服消相干最有效的方法。主要的幾種量子編碼方案是：量子糾錯碼、量子避錯碼和量子防錯碼。量子糾錯碼是經典糾錯碼的類比，是目前研究的最多的一類編碼，其優點為適用范圍廣，缺點是效率不高。
正如大多數人所了解的，量子計算機在密碼破解上有著巨大潛力。當今主流的非對稱（公鑰）加密演算法，如RSA加密演算法，大多數都是基於於大整數的因式分解或者有限域上的離散指數的計算這兩個數學難題。他們的破解難度也就依賴於解決這些問題的效率。傳統計算機上，要求解這兩個數學難題，花費時間為指數時間（即破解時間隨著公鑰長度的增長以指數級增長），這在實際應用中是無法接受的。而為量子計算機量身定做的秀爾演算法可以在多項式時間內（即破解時間隨著公鑰長度的增長以k次方的速度增長，其中k為與公鑰長度無關的常數）進行整數因式分解或者離散對數計算，從而為RSA、離散對數加密演算法的破解提供可能。但其它不是基於這兩個數學問題的公鑰加密演算法，比如橢圓曲線加密演算法，量子計算機還無法進行有效破解 。
針對對稱（私鑰）加密，如AES加密演算法，只能進行暴力破解，而傳統計算機的破解時間為指數時間，更准確地說，是 ，其中 為密鑰的長度。而量子計算機可以利用Grover演算法進行更優化的暴力破解，其效率為 ，也就是說，量子計算機暴力破解AES-256加密的效率跟傳統計算機暴力破解AES-128是一樣的。
更廣泛而言，Grover演算法是一種量子資料庫搜索演算法，相比傳統的演算法，達到同樣的效果，它的請求次數要少得多。對稱加密演算法的暴力破解僅僅是Grover演算法的其中一個應用。
在利用EPR對進行量子通訊的實驗中科學家發現，只有擁有EPR對的雙方才可能完成量子信息的傳遞，任何第三方的竊聽者都不能獲得完全的量子信息，正所謂解鈴還需系鈴人，這樣實現的量子通訊才是真正不會被破解的保密通訊。
此外量子計算機還可以用來做量子系統的模擬，人們一旦有了量子模擬計算機，就無需求解薛定諤方程或者採用蒙特卡羅方法在經典計算機上做數值計算，便可精確地研究量子體系的特徵。