Introduction to the Design and Analysis of Algorithms: a strategic approach (IE-Paperback)

R.C.T. Lee, S.S. Tseng, R.C. Chang, Y.T.Tsai

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

商品描述

Communication network design, VLSI layout and DNA sequence analysis are important and challenging problems that cannot be solved by naive and straightforward algorithms. Thus, it is critical for a computer scientist to have a good knowledge of algorithm design and analysis.

This book presents algorithm design from the viewpoint of strategies. Each strategy is introduced with many algorithms designed under the strategy. Each algorithm is presented with many examples and each example with many figures.

In recent years, many approximation algorithms have been developed. Introduction to the Design and Analysis of Algorithms presents two important concepts clearly: PTAS and NPO-complete. This book also discusses the concept of NP-completeness before introducing approximation algorithms. Again, this is explained through examples which make sure that the students have a definite idea about this very abstract concept.

In addition, this book also has a chapter on on-line algorithms. Each on-line algorithm is introduced by first describing the basic principle behind it. Amortized analysis is a new field in algorithm research. In this book, detailed descriptions are given to introduce this new and difficult-to-understand concept.

This book can be used as a textbook by senior undergraduate students or master level graduate students in computer science.

商品描述(中文翻譯)

通訊網路設計、VLSI佈局和DNA序列分析是重要且具有挑戰性的問題,無法透過單純和直接的演算法解決。因此,對於一位電腦科學家來說,擁有良好的演算法設計和分析知識至關重要。

本書從策略的角度介紹演算法設計。每個策略都會介紹許多根據該策略設計的演算法。每個演算法都會有許多例子,每個例子都會有許多圖片。

近年來,許多近似演算法已經被開發出來。《演算法設計與分析入門》清楚地介紹了兩個重要的概念:PTAS和NPO-complete。本書在介紹近似演算法之前也討論了NP完全性的概念。同樣地,這些概念都是透過例子來解釋,以確保學生對這些非常抽象的概念有明確的理解。

此外,本書還有一章關於線上演算法。每個線上演算法都會先描述其基本原理。攤銷分析是演算法研究中的一個新領域。本書詳細介紹了這個新且難以理解的概念。

本書可作為資訊科學高年級本科生或碩士研究生的教科書使用。

目錄大綱

1 Introduction
2 The complexity of algorithms and the lower bounds of problems
3 The greedy method
4 The divide-and-conquer strategy
5 Tree searching strategies
6 Prune-and-search
7 Dynamic programming
8 The theory of NP-completeness
9 Approximation algorithms
10 Amortized analysis
11 Randomized algorithms
12 On-line algorithms

目錄大綱(中文翻譯)

1 簡介
2 演算法的複雜度和問題的下界
3 貪婪法
4 分治策略
5 樹搜索策略
6 剪枝和搜索
7 動態規劃
8 NP完全性理論
9 近似算法
10 分攤分析
11 隨機算法
12 在線算法