Methods in Algorithmic Analysis (Hardcover)

Vladimir A. Dobrushkin

  • 出版商: CRC
  • 出版日期: 2009-11-01
  • 售價: $3,150
  • 貴賓價: 9.5$2,993
  • 語言: 英文
  • 頁數: 824
  • 裝訂: Hardcover
  • ISBN: 1420068296
  • ISBN-13: 9781420068290
  • 相關分類: Algorithms-data-structures
  • 立即出貨 (庫存=1)

買這商品的人也買了...

商品描述

Explores the Impact of the Analysis of Algorithms on Many Areas within and beyond Computer Science
A flexible, interactive teaching format enhanced by a large selection of examples and exercises

Developed from the author’s own graduate-level course, Methods in Algorithmic Analysis presents numerous theories, techniques, and methods used for analyzing algorithms. It exposes students to mathematical techniques and methods that are practical and relevant to theoretical aspects of computer science.

 

After introducing basic mathematical and combinatorial methods, the text focuses on various aspects of probability, including finite sets, random variables, distributions, Bayes’ theorem, and Chebyshev inequality. It explores the role of recurrences in computer science, numerical analysis, engineering, and discrete mathematics applications. The author then describes the powerful tool of generating functions, which is demonstrated in enumeration problems, such as probabilistic algorithms, compositions and partitions of integers, and shuffling. He also discusses the symbolic method, the principle of inclusion and exclusion, and its applications. The book goes on to show how strings can be manipulated and counted, how the finite state machine and Markov chains can help solve probabilistic and combinatorial problems, how to derive asymptotic results, and how convergence and singularities play leading roles in deducing asymptotic information from generating functions. The final chapter presents the definitions and properties of the mathematical infrastructure needed to accommodate generating functions.

 

Accompanied by more than 1,000 examples and exercises, this comprehensive, classroom-tested text develops students’ understanding of the mathematical methodology behind the analysis of algorithms. It emphasizes the important relation between continuous (classical) mathematics and discrete mathematics, which is the basis of computer science.

商品描述(中文翻譯)

探索算法分析對計算機科學內外許多領域的影響
靈活互動的教學形式,配以大量的例子和練習

本書《算法分析方法》是根據作者自己的研究生課程開發的,介紹了許多用於分析算法的理論、技巧和方法。它向學生介紹了實際且與計算機科學理論相關的數學技巧和方法。

在介紹基本的數學和組合方法之後,本書重點介紹了概率的各個方面,包括有限集合、隨機變量、分布、貝葉斯定理和切比雪夫不等式。它探討了遞迴在計算機科學、數值分析、工程和離散數學應用中的作用。然後,作者描述了生成函數這一強大的工具,並在列舉問題中進行了演示,例如概率算法、整數的組合和分割,以及洗牌。他還討論了符號方法、包含與排斥原理及其應用。本書還展示了如何操作和計數字符串,有限狀態機和馬爾可夫鏈如何幫助解決概率和組合問題,如何推導漸進結果,以及收斂和奇異點如何在從生成函數中推斷漸進信息中起主導作用。最後一章介紹了生成函數所需的數學基礎的定義和性質。

本書配有1000多個例子和練習,全面而經過課堂驗證的教材,幫助學生理解算法分析背後的數學方法論。它強調了連續(經典)數學與離散數學之間的重要關係,這是計算機科學的基礎。