代數復雜性理論

代數復雜性理論

图书基本信息
出版时间:2007-1
出版社:科學
作者:比爾吉斯爾
页数:618
字数:760000
书名:代數復雜性理論
封面图片
代數復雜性理論
内容概要
從出版方面來講,除了較好較快地出版我們自己的成果外,引進國外的先進出版物無疑也是十分重要與必不可少的。從數學來說,施普林格(Springer)出版社至今仍然是世界上最具權威的出版社。科學出版社影印一批他們出版的好的新書,使我國廣大數學家能以較低的價格購買,特別是在邊遠地區工作的數學家能普遍見到這些書,無疑是對推動我國數學的科研與教學十分有益的事。    這次科學出版社購買了版權,一次影印了23本施普林格出版社出版的數學書,就是一件好事,也是值得繼續做下去的事情。大體上分一下,這28本書中,包括基礎數學書5本,應用數學書6本與計算數學書12本,其中有些書也具有交叉性質。這些書都是很新的,2000年以後出版的佔絕大部分,共計16本,其余的也是1990年以後出版的。這些書可以使讀者較快地了解數學某方面的前沿,例如基礎數學中的數論、代數與拓撲三本,都是由該領域大數學家編著的“數學百科全書”的分冊。對從事這方面研究的數學家了解該領域的前沿與全貌很有幫助。按照學科的特點,基礎數學類的書以“經典”為主,應用和計算數學類的書“前沿”為主。這些書的作者多數是國際知名的大數學家,例如《拓撲學》一書的作者諾維科夫是俄羅斯科學院的院士,曾獲“菲爾茲獎”和“沃爾夫數學獎”。這些大數學家的著作無疑將會對我國的科研人員起到非常好的指導作用。    當然,23本書只能涵蓋數學的一部分,所以,這項工作還應該繼續做下去。更進一步,有些讀者面較廣的好書還應該翻譯成中文出版,使之有更大的讀者群。
作者简介
作者︰(瑞士)Peter Burgisser (瑞士)Michael Clausen (瑞士)M.Amin Shokrollahi
书籍目录
Chapter 1.Introduction 1.1 Exercises 1.2 Open Problems 1.3 NotesPartⅠ.Fundamental Algorithms Chapter 2. Efficient Polynomial Arithmetic  2.1 Multiplication of Polynomials I  2.2* Multiplication of Polynomials II  2.3* Multiplication of Several Polynomials  2.4 Multiplication and Inversion of Power Series  2.5* Composition of Power Series  2.6 Exercises  2.7 Open Problems  2.8 Notes Chapter 3. Efficient Algorithms with Branching  3.1 Polynomial Greatest Common Divisors  3.2* Local Analysis of the Knuth-Schonhage Algorithm    3.3 Evaluation and Interpolation    3.4* Fast Point Location in Arrangements of Hyperplanes    3.5* Vapnik-Chervonenkis Dimension and Epsilon-Nets  3.6 Exercises  3.7 Open Problems  3.8 NotesPartⅡ.Elementary Lower Bounds Chapter 4. Models of Computation  4.1 Straight-Line Programs and Complexity  4.2 Computation Sequences  4.3* Autarky  4.4* Computation Trees  4.5* Computation Trees and Straight-line Programs  4.6 Exercises  4.7 Notes Chapter 5. Preconditioning and Transcendence Degree  5.1 Preconditioning  5.2 Transcendence Degree  5.3* Extension to Linearly Disjoint Fields  5.4 Exercises  5.5 Open Problems  5.6 Notes Chapter 6. The Substitution Method  6.1 Discussion of Ideas  6.2 Lower Bounds by the Degree of Linearization  6.3* Continued Fractions, Quotients, and Composition  6.4 Exercises  6.5 Open Problems  6.6 Notes Chapter 7. Differential Methods  7.1 Complexity of Truncated Taylor Series  7.2 Complexity of Partial Derivatives  7.3 Exercises  7.4 Open Problems  7.5 NotesPart Ⅲ.High Degree Chapter 8. The Degree Bound  8.1 A Field Theoretic Version of the Degree Bound  8.2 Geometric Degree and a Bezout Inequality  8.3 The Degree Bound  8.4 Applications  8.5* Estimates for the Degree  8.6* The Case of a Finite Field  8.7 Exercises  8.8 Open Problems  8.9 Notes Chapter 9. Specific Polynomials which Are Hard to Compute  9.1 A Genetic Computation  9.2 Polynomials with Algebraic Coefficients  9.3 Applications  9.4* Polynomials with Rapidly Growing Integer Coefficients  9.5* Extension to other Complexity Measures  9.6 Exercises  9.7 Open Problems  9.8 Notes Chapter 10. Branching and Degree  10.1 Computation Trees and the Degree Bound  10.2 Complexity of the Euclidean Representation  10.3* Degree Pattern of the Euclidean Representation  10.4 Exercises  10.5 Open Problems  10.6 Notes Chapter 11. Branching and Connectivity  11.1 Estimation of the Number of Connected Component   11.2 Lower Bounds by the Number of Connected Components  11.3 Knapsack and Applications to Computational Geometry  11.4 Exercises  11.5 Open Problems  11.6 Notes Chapter 12. Additive Complexity  12.1 Introduction  12.2* Real Roots of Sparse Systems of Equations  12.3 A Bound on the Additive Complexity  12.4 Exercises  12.5 Open Problems  12.6 NotesPart Ⅳ.Low Degree Chapter 13. Linear Complexity  13.1 The Linear Computational Model  13.2 First Upper and Lower Bounds  13.3* A Graph Theoretical Approach  13.4* Lower Bounds via Graph Theoretical Methods  13.5* Generalized Fourier Transforms  13.6 Exercises  13.7 Open Problems  13.8 Notes Chapter 14. Multiplicative and Bilinear Complexity  14.1 Multiplicative Complexity of Quadratic Maps  14.2 The Tensorial Notation  14.3 Restriction and Conciseness  14.4 Other Characterizations of Rank  14.5 Rank of the Polynomial Multiplication  14.6 The Semiring T  14.7 Exercises  14.8 Open Problems  14.9 Notes Chapter 15. Asymptotic Complexity of Matrix Multiplication  Chapter 16. Problems Related to Matrix Multiplication  Chapter 17. Lower Bounds for the Complexity of Algebras  Chapter 18. Rank over Finite Fields and Codes  Chapter 19. Rank of 2-Slice and 3-Slice Tensors  Chapter 20. Typical Tensorial RankPart Ⅴ.Complete Problems Chapter 21. P Versus NP︰A Nonuniform Algebraic AnalogueBibliographyList of NotationIndex
下载链接

代數復雜性理論下載

评论与打分
  •     內容翔實,理論經典,很有收獲!