Introduction to Algorithms, 4th edition
برچسب ها:
Algorithms |
The MIT Press
Charles E. Leiserson, Clifford Stein, Ronald L. Rivest, Thomas H. Cormen
9780262046305
2022
1312
English
کتاب Introduction to Algorithms, 4th edition (مقدمه ای بر الگوریتم ها، ویرایش چهارم)، به روز رسانی جامعی برای یکی از پیشرو‌ترین کتاب‌های الگوریتم است که شامل مطالب جدیدی درباره تطابق‌ها در گراف‌های دو بخشی، الگوریتم‌های آنلاین، یادگیری ماشین و موضوعات دیگر است.
برخی از کتاب‌ها در مورد الگوریتم ها، دقیق اما ناقص هستند؛ دیگر کتاب‌ها هم انبوهی از موضوعات را پوشش می‌دهند، اما فاقد دقت هستند. ویرایش چهارم کتاب مقدمه ای بر الگوریتم ها، به طور منحصر به فردی دقت و جامعیت را با هم ترکیب می‌کند. این کتاب، طیف گسترده ای از الگوریتم‌ها را به صورت عمقی پوشش می‌دهد، در حالی که طراحی و تجزیه و تحلیل آنها را با فصل‌ها و الگوریتم‌های مستقل و به صورت شبه کد برای تمام سطوح خوانندگان در دسترس قرار می‌دهد. از زمان انتشار اولین ویرایش کتاب، مقدمه ای بر الگوریتم‌ها به کتابی پیشرو در زمینه الگوریتم‌ها در دانشگاه‌های سراسر جهان و همچنین مرجع استاندارد برای متخصصان تبدیل شده است.
ویژگی‌های جدید ویرایش چهارم کتاب مقدمه ای بر الگوریتم ها
- فصل‌های جدیدی در مورد تطابق در گراف‌های دوبخشی، الگوریتم‌های آنلاین و یادگیری ماشین
- مطالب جدیدی در مورد موضوعاتی از جمله حل معادلات بازگشتی، جداول هش، توابع بالقوه، و آرایه‌های پسوندی
- 140 تمرین جدید و 22 مسئله جدید
- بازخورد خوانندگان به همراه بهبودهای آگاهانه برای مسائل قدیمی
- سبک نوشتاری واضح تر، شخصی‌تر و بی طرف‌تر از جنسیت
- رنگی شدن برای بهبود ارائه بصری
- یادداشت‌ها، تاریخچه و فهرست به‌روزرسانی شدند تا تحولات این حوزه را منعکس کنند
- وب سایت با مطالب تکمیلی جدید
Table of Contents:
- I Foundations
- Introduction
- 1 The Role of Algorithms in Computing
- 1.1 Algorithms
- 1.2 Algorithms as a technology
- 2 Getting Started
- 2.1 Insertion sort
- 2.2 Analyzing algorithms
- 2.3 Designing algorithms
- 3 Characterizing Running Times
- 3.1 O-notation, Ω-notation, and Θ-notation
- 3.2 Asymptotic notation: formal definitions
- 3.3 Standard notations and common functions
- 4 Divide-and-Conquer
- 4.1 Multiplying square matrices
- 4.2 Strassen’s algorithm for matrix multiplication
- 4.3 The substitution method for solving recurrences
- 4.4 The recursion-tree method for solving recurrences
- 4.5 The master method for solving recurrences
- 4.6 Proof of the continuous master theorem
- 4.7 Akra-Bazzi recurrences
- 5 Probabilistic Analysis and Randomized Algorithms
- 5.1 The hiring problem
- 5.2 Indicator random variables
- 5.3 Randomized algorithms
- 5.4 Probabilistic analysis and further uses of indicator random variables
- II Sorting and Order Statistics
- Introduction
- 6 Heapsort
- 6.1 Heaps
- 6.2 Maintaining the heap property
- 6.3 Building a heap
- 6.4 The heapsort algorithm
- 6.5 Priority queues
- 7 Quicksort
- 7.1 Description of quicksort
- 7.2 Performance of quicksort
- 7.3 A randomized version of quicksort
- 7.4 Analysis of quicksort
- 8 Sorting in Linear Time
- 8.1 Lower bounds for sorting
- 8.2 Counting sort
- 8.3 Radix sort
- 8.4 Bucket sort
- 9 Medians and Order Statistics
- 9.1 Minimum and maximum
- 9.2 Selection in expected linear time
- 9.3 Selection in worst-case linear time
- III Data Structures
- Introduction
- 10 Elementary Data Structures
- 10.1 Simple array-based data structures: arrays, matrices, stacks, queues
- 10.2 Linked lists
- 10.3 Representing rooted trees
- 11 Hash Tables
- 11.1 Direct-address tables
- 11.2 Hash tables
- 11.3 Hash functions
- 11.4 Open addressing
- 11.5 Practical considerations
- 12 Binary Search Trees
- 12.1 What is a binary search tree?
- 12.2 Querying a binary search tree
- 12.3 Insertion and deletion
- 13 Red-Black Trees
- 13.1 Properties of red-black trees
- 13.2 Rotations
- 13.3 Insertion
- 13.4 Deletion
- IV Advanced Design and Analysis Techniques
- Introduction
- 14 Dynamic Programming
- 14.1 Rod cutting
- 14.2 Matrix-chain multiplication
- 14.3 Elements of dynamic programming
- 14.4 Longest common subsequence
- 14.5 Optimal binary search trees
- 15 Greedy Algorithms
- 15.1 An activity-selection problem
- 15.2 Elements of the greedy strategy
- 15.3 Huffman codes
- 15.4 Offline caching
- 16 Amortized Analysis
- 16.1 Aggregate analysis
- 16.2 The accounting method
- 16.3 The potential method
- 16.4 Dynamic tables
- V Advanced Data Structures
- Introduction
- 17 Augmenting Data Structures
- 17.1 Dynamic order statistics
- 17.2 How to augment a data structure
- 17.3 Interval trees
- 18 B-Trees
- 18.1 Definition of B-trees
- 18.2 Basic operations on B-trees
- 18.3 Deleting a key from a B-tree
- 19 Data Structures for Disjoint Sets
- 19.1 Disjoint-set operations
- 19.2 Linked-list representation of disjoint sets
- 19.3 Disjoint-set forests
- 19.4 Analysis of union by rank with path compression
- VI Graph Algorithms
- Introduction
- 20 Elementary Graph Algorithms
- 20.1 Representations of graphs
- 20.2 Breadth-first search
- 20.3 Depth-first search
- 20.4 Topological sort
- 20.5 Strongly connected components
- 21 Minimum Spanning Trees
- 21.1 Growing a minimum spanning tree
- 21.2 The algorithms of Kruskal and Prim
- 22 Single-Source Shortest Paths
- 22.1 The Bellman-Ford algorithm
- 22.2 Single-source shortest paths in directed acyclic graphs
- 22.3 Dijkstra’s algorithm
- 22.4 Difference constraints and shortest paths
- 22.5 Proofs of shortest-paths properties
- 23 All-Pairs Shortest Paths
- 23.1 Shortest paths and matrix multiplication
- 23.2 The Floyd-Warshall algorithm
- 23.3 Johnson’s algorithm for sparse graphs
- 24 Maximum Flow
- 24.1 Flow networks
- 24.2 The Ford-Fulkerson method
- 24.3 Maximum bipartite matching
- 25 Matchings in Bipartite Graphs
- 25.1 Maximum bipartite matching (revisited)
- 25.2 The stable-marriage problem
- 25.3 The Hungarian algorithm for the assignment problem
- VII Selected Topics
- Introduction
- 26 Parallel Algorithms
- 26.1 The basics of fork-join parallelism
- 26.2 Parallel matrix multiplication
- 26.3 Parallel merge sort
- 27 Online Algorithms
- 27.1 Waiting for an elevator
- 27.2 Maintaining a search list
- 27.3 Online caching
- 28 Matrix Operations
- 28.1 Solving systems of linear equations
- 28.2 Inverting matrices
- 28.3 Symmetric positive-definite matrices and least-squares approximation
- 29 Linear Programming
- 29.1 Linear programming formulations and algorithms
- 29.2 Formulating problems as linear programs
- 29.3 Duality
- 30 Polynomials and the FFT
- 30.1 Representing polynomials
- 30.2 The DFT and FFT
- 30.3 FFT circuits
- 31 Number-Theoretic Algorithms
- 31.1 Elementary number-theoretic notions
- 31.2 Greatest common divisor
- 31.3 Modular arithmetic
- 31.4 Solving modular linear equations
- 31.5 The Chinese remainder theorem
- 31.6 Powers of an element
- 31.7 The RSA public-key cryptosystem
- 31.8 Primality testing
- 32 String Matching
- 32.1 The naive string-matching algorithm
- 32.2 The Rabin-Karp algorithm
- 32.3 String matching with finite automata
- 32.4 The Knuth-Morris-Pratt algorithm
- 32.5 Suffix arrays
- 33 Machine-Learning Algorithms
- 33.1 Clustering
- 33.2 Multiplicative-weights algorithms
- 33.3 Gradient descent
- 34 NP-Completeness
- 34.1 Polynomial time
- 34.2 Polynomial-time verification
- 34.3 NP-completeness and reducibility
- 34.4 NP-completeness proofs
- 34.5 NP-complete problems
- 35 Approximation Algorithms
- 35.1 The vertex-cover problem
- 35.2 The traveling-salesperson problem
- 35.3 The set-covering problem
- 35.4 Randomization and linear programming
- 35.5 The subset-sum problem
- VIII Appendix: Mathematical Background
- Introduction
- A Summations
- A.1 Summation formulas and properties
- A.2 Bounding summations
- B Sets, Etc.
- B.1 Sets
- B.2 Relations
- B.3 Functions
- B.4 Graphs
- B.5 Trees
- C Counting and Probability
- C.1 Counting
- C.2 Probability
- C.3 Discrete random variables
- C.4 The geometric and binomial distributions
- C.5 The tails of the binomial distribution
- D Matrices
- D.1 Matrices and matrix operations
- D.2 Basic matrix properties
- Bibliography
می پسندم
به درد نمی خوره
