Mastering Algorithms with Perl - Helion
ebook
Autor: Jarkko Hietaniemi, John Macdonald, Jon OrwantISBN: 978-14-493-0719-6
stron: 706, Format: ebook
Data wydania: 1999-08-18
Księgarnia: Helion
Cena książki: 118,15 zł (poprzednio: 137,38 zł)
Oszczędzasz: 14% (-19,23 zł)
Many programmers would love to use Perl for projects that involve heavy lifting, but miss the many traditional algorithms that textbooks teach for other languages. Computer scientists have identified many techniques that a wide range of programs need, such as:
- Fuzzy pattern matching for text (identify misspellings!)
- Finding correlations in data
- Game-playing algorithms
- Predicting phenomena such as Web traffic
- Polynomial and spline fitting
Osoby które kupowały "Mastering Algorithms with Perl", wybierały także:
- Java 9: Building Robust Modular Applications 332,22 zł, (29,90 zł -91%)
- Practical Machine Learning Cookbook 186,88 zł, (29,90 zł -84%)
- Mastering Spark for Data Science 175,88 zł, (29,90 zł -83%)
- Mastering Functional Programming 157,37 zł, (29,90 zł -81%)
- C# Data Structures and Algorithms 157,37 zł, (29,90 zł -81%)
Spis treści
Mastering Algorithms with Perl. Practical Programming Through Computer Science eBook -- spis treści
- Mastering Algorithms with Perl
- SPECIAL OFFER: Upgrade this ebook with OReilly
- A Note Regarding Supplemental Files
- Preface
- About This Book
- Theory or Practice?
- Organization of This Book
- Conventions Used in This Book
- What You Should Know Before Reading This Book
- What You Should Have Before Reading This Book
- Online Information About This Book
- Acknowledgments
- Comments and Questions
- About This Book
- 1. Introduction
- What Is an Algorithm?
- A Sample Algorithm: Binary Search
- What do all those funny symbols mean?
- References
- Adapting Algorithms
- Generality
- A Sample Algorithm: Binary Search
- Efficiency
- Space Versus Time
- Benchmarking
- Floating-Point Numbers
- Temporary Variables
- Caching
- Evaluating Algorithms: O(N) Notation
- Dont cheat
- Recurrent Themes in Algorithms
- Recursion
- Divide and Conquer
- Dynamic Programming
- Choosing the Right Representation
- What Is an Algorithm?
- 2. Basic Data Structures
- Perls Built-in Data Structures
- Build Your Own Data Structure
- A Simple Example
- Lols and Lohs and Hols and Hohs
- Objects
- Using a Constructed Datatype
- Shortcuts
- Perl Arrays: Many Data Structures in One
- Queues
- Stacks
- Deques
- Still More Perl Arrays
- 3. Advanced Data Structures
- Linked Lists
- Linked List Implementations
- Tracking Both Ends of Linked Lists
- Additional Linked List Operations
- Circular Linked Lists
- Garbage Collection in Perl
- Doubly-Linked Lists
- Infinite Lists
- The Cost of Traversal
- Binary Trees
- Keeping Trees Balanced
- User-visible routines
- Merging
- The actual balancing
- Keeping Trees Balanced
- Heaps
- Binary Heaps
- Janus Heap
- The Heap Modules
- Future CPAN Modules
- Linked Lists
- 4. Sorting
- An Introduction to Sorting
- Perls sort Function
- ASCII Order
- Numeric Order
- Reverse Order: From Highest To Lowest
- Sort::Fields
- Sort::Versions
- Dictionary Order
- Sorting Efficiency
- The Schwartzian Transform
- Long duration caching
- Deficiency: missing internationalization (locales)
- Sort::ArbBiLex
- See for yourself: use the Benchmark module
- Sorting Hashes Is Not What You Might Think
- All Sorts of Sorts
- Quadratic Sorting Algorithms
- Selection sort
- Minima and maxima
- Bubble sort
- Insertion sort
- Shellsort
- Log-Linear Sorting Algorithms
- Mergesort
- Heapsort
- Quicksort
- Removing recursion from quicksort
- Median, quartile, percentile
- Beating O(N log N)
- Radix sorts
- Counting sort
- Hybrid sorts
- Bucket sort
- Quickbubblesort
- External Sorting
- Quadratic Sorting Algorithms
- Sorting Algorithms Summary
- O(N2) Sorts
- Selection sort
- Bubble sort and insertion sort
- Shellsort
- O(N log N) Sorts
- Mergesort
- Quicksort
- How Well Did We Do?
- O(N2) Sorts
- An Introduction to Sorting
- 5. Searching
- Hash Search and Other Non-Searches
- Lookup Searches
- Ransack Search
- Linear Search
- Binary Search in a List
- Proportional Search
- Binary Search in a Tree
- Should You Use a List or a Tree for Binary Searching?
- Bushier Trees
- Lists of Lists
- B-Trees
- Hybrid Searches
- Lookup Search Recommendations
- Generative Searches
- Game Interface
- Exhaustive Search
- Alternatives to Exhaustive Search in Games
- Minimax
- Pruning
- Alpha-beta pruning
- Killer move
- Transpose tables
- Advanced pruning strategies
- Other strategies
- Nongame Dynamic Searches
- Greedy algorithms
- Branch and bound
- The A* algorithm
- Dynamic programming
- 6. Sets
- Venn Diagrams
- Creating Sets
- Creating Sets Using Hashes
- Creating Sets Using Bit Vectors
- Set Union and Intersection
- Union
- Intersection
- Set Universe
- Complement Set
- Null Set
- Set Union and Intersection Using Hashes
- Union and Intersection Using Bit Vectors
- Set Differences
- Set Difference
- Set Symmetric Difference
- Set Differences Using Hashes
- Set Differences Using Bit Vectors
- Counting Set Elements
- Set Relations
- Set Relations Using Hashes
- Set Relations Using Bit Vectors
- The Set Modules of CPAN
- Set::Scalar
- Set::Object
- Set::IntSpan
- Bit::Vector
- Set::IntRange
- Sets of Sets
- Power Sets
- Power Sets Using Hashes
- Multivalued Sets
- Multivalued Logic
- Fuzzy Sets
- Bags
- Sets Summary
- 7. Matrices
- Creating Matrices
- Manipulating Individual Elements
- Finding the Dimensions of a Matrix
- Displaying Matrices
- Adding or Multiplying Constants
- Adding a Constant to a Matrix
- Adding a Matrix to a Matrix
- Transposing a Matrix
- Multiplying Matrices
- Extracting a Submatrix
- Combining Matrices
- Inverting a Matrix
- Computing the Determinant
- Gaussian Elimination
- Eigenvalues and Eigenvectors
- Computing Eigenvalues
- Using PDL to calculate eigenvalues and eigenvectors
- Calculating easy eigenvalues directly
- Computing Eigenvalues
- The Matrix Chain Product
- Delving Deeper
- 8. Graphs
- Vertices and Edges
- Edge Direction
- Vertex Degree and Vertex Classes
- Derived Graphs
- Graph Transpose
- Complete Graph
- Complement Graph
- Density
- Graph Attributes
- Graph Representation in Computers
- Our Graph Representation
- Creating graphs, dealing with vertices
- Testing for and adding edges
- Returning edges
- Density, degrees, and vertex classes
- Deleting edges and vertices
- Graph attributes
- Displaying graphs
- Our Graph Representation
- Graph Traversal
- Depth-First Search
- Topological Sort
- make as a topological sort
- Breadth-First Search
- Implementing Graph Traversal
- Implementing depth-first traversal
- Implementing breadth-first traversal
- Paths and Bridges
- The Seven Bridges of Königsberg
- Graph Biology: Trees, Forests, DAGS, Ancestors, and Descendants
- Parents and Children
- Edge and Graph Classes
- Edge Classes
- Graph Classes: Connectivity
- Biconnectivity
- Strongly Connected Graphs
- Minimum Spanning Trees
- Kruskals minimum spanning tree
- Prims minimum spanning tree
- Shortest Paths
- Single-source shortest paths
- Dijkstras single-source shortest paths
- Bellman-Ford single-source shortest paths
- DAG single-source shortest paths
- All-pairs shortest paths
- Single-source shortest paths
- Transitive Closure
- Flow Networks
- Ford-Fulkerson
- Edmonds-Karp
- Traveling Salesman Problem
- CPAN Graph Modules
- Vertices and Edges
- 9. Strings
- Perl Builtins
- Exact Matching
- Regular Expressions
- Quick tips for regular expressions: readability
- Quick tips for regular expressions: efficiency
- study()
- String-Matching Algorithms
- Nave Matching
- Matching sequences
- Rabin-Karp
- Rabin-Karp is a checksum algorithm
- Handling huge checksums
- Implementing Rabin-Karp
- Further checksum experimentation
- Knuth-Morris-Pratt
- Boyer-Moore
- Shift-Op
- Baeza-Yates-Gonnet Shift-OR Exact Matching
- Approximate Matching
- Baeza-Yates-Gonnet Shift-Add
- Wu-Manber k-differences
- Longest Common Subsequences
- Summary of String Matching Algorithms
- String::Approx
- Nave Matching
- Phonetic Algorithms
- Text::Soundex
- Text::Metaphone
- Stemming and Inflection
- Modules for Stemming and Inflection
- Text::Stem
- Text::German
- Lingua::EN::Inflect
- Lingua::PT::Conjugate
- Modules for Stemming and Inflection
- Parsing
- Finite Automata
- Grammars
- Context-free grammars
- Parsing Up and Down
- Top-down parsing
- Bottom-up parsing
- Interpreters and Compilers
- Modules for Lexing and Parsing
- Parse::Lex
- Parse::RecDescent
- Text::Abbrev
- Text::ParseWords
- Text::DelimMatch
- String::ShellQuote
- Text::Balanced
- Special-purpose parsers
- Compression
- Run-Length Encoding
- Huffman Encoding
- compress, GNU gzip, pkzip
- Perl Builtins
- 10. Geometric Algorithms
- Distance
- Euclidean Distance
- Manhattan Distance
- Maximum Distance
- Spherical Distance
- Area, Perimeter, and Volume
- Triangle
- Polygon Area
- Polygon Perimeter
- Direction
- Intersection
- Line Intersection
- Line intersection: the general case
- Line intersection: the horizontal-vertical case
- Line Intersection
- Inclusion
- Point in Polygon
- Point in Triangle
- Point in Quadrangle
- Boundaries
- Bounding Box
- Convex Hull
- Closest Pair of Points
- Geometric Algorithms Summary
- CPAN Graphics Modules
- 2-D Images
- Perl-Gimp
- GD
- Image::Size
- PerlMagick
- PGPLOT
- Charts a.k.a. Business Graphics
- 3-D Modeling
- OpenGL
- Renderman
- VRML
- Widget/GUI Toolkits
- Perl/Tk
- Other windowing toolkits
- 2-D Images
- Distance
- 11. Number Systems
- Integers and Reals
- Constants
- Pure Integer Arithmetic
- Precision
- Rounding Numbers
- Rounding up or down to an integer
- Rounding to the nearest integer
- Rounding to a particular decimal point
- Very Big, Very Small, and Very Precise Numbers
- Fractions
- Strange Systems
- Bits and Bases
- Bit Vectors
- Complex Numbers
- Polar Coordinates
- Dates and Times
- Roman Numerals
- Trigonometry
- Significant Series
- Arithmetic and Geometric Progressions
- The Fibonacci Sequence
- Harmonic Series
- The Riemann Zeta Function and Bernoulli Numbers
- Integers and Reals
- 12. Number Theory
- Basic Number Theory
- Linear Combination Theorem
- Greatest Common Divisor
- GCD: Linear Combination
- Least Common Multiple
- Prime Numbers
- Caching: Another Example
- Noninfinite Arithmetic
- Modular Arithmetic
- Chinese Remainder Theorem
- Modular Division
- Chinese Remainder Theorem Revisited
- Treating Chinese remainders as integers
- Integer Exponentiation
- Modular Exponentiation
- Miller-Rabin: Prime Generation Revisited
- Unsolved Problems
- Is the Collatz Conjecture False?
- Is There an Odd Perfect Number?
- Is the Goldbach Conjecture False?
- Basic Number Theory
- 13. Cryptography
- Legal Issues
- Authorizing People with Passwords
- Password Hazards
- Authorization of Data: Checksums and More
- Obscuring Data: Encryption
- Perfect Encryption: The One-Time Pad
- Shared-Secret Encryptions
- Analysis of Shared-Secret Encryption
- Encrypting with SSLeay
- Public Key Encryption
- RSA Public Key Encryption
- El Gamal Public Key Encryption
- Choosing Between Public Key and Private Key
- Hiding Data: Steganography
- Winnowing and Chaffing
- Encrypted Perl Code
- Other Issues
- 14. Probability
- Random Numbers
- Dont Forget to Seed Your Generator
- Better Randomness
- Events
- Will the Blue Jays Win, and Will the Stock Market Go Up?
- Will Neither the Blue Jays Win nor the Stock Market Go Up?
- Will the Blue Jays Win or the Stock Market Go Up?
- Permutations and Combinations
- Permutations
- Combinations
- Probability Distributions
- Expected Value
- Rolling Dice: Uniform Distributions
- Measuring Time: Uniform Continuous Distributions
- Choosing an Element from an Array
- Picking Random BigInts
- Rolling Dice Revisited: Combining Events
- Loaded Dice and Candy Colors: Nonuniform Discrete Distributions
- Flipping a Coin: The Binomial Distribution
- The Binomial Distribution in Poker
- If the Blue Jays Score Six Runs: Conditional Probability
- The Vaunted Monty Hall Problem
- Flipping Coins Over and Over: Infinite Discrete Distributions
- How Much Snow? Continuous Distributions
- Many More Distributions
- The Bernoulli Distribution
- The Beta Distribution
- The Binomial Distribution
- The Cauchy Distribution
- The Chi Square Distribution
- The Erlang Distribution
- The Exponential Distribution
- The Gamma Distribution
- The Gaussian (Normal) Distribution
- The Geometric Distribution
- The Hypergeometric Distribution
- The Laplace Distribution
- The Log Normal Distribution
- The Maxwell Distribution
- The Pascal Distribution
- The Poisson Distribution
- The Rayleigh Distribution
- The Uniform Distribution
- Random Numbers
- 15. Statistics
- Statistical Measures
- The Mean
- The Median
- The Mode
- Standard Deviation
- The Standard Score
- The Variance and Standard Deviation of Distributions
- Significance Tests
- How Sure Is Sure?
- The Sign Test
- The z-test
- The t-test
- The Chi-square test
- ANOVA and the F-test
- Correlation
- Computing the Covariance
- Computing the Correlation Coefficient
- Fitting a Line to Your Data
- Statistical Measures
- 16. Numerical Analysis
- Computing Derivatives and Integrals
- Computing the Derivative at a Particular Point
- Computing the Jacobian
- Computing Definite Integrals
- Solving Equations
- Simple Roots: Quadratics and Cubics
- The quadratic formula
- Cubic equations
- Approximating Roots
- Multiple Nonlinear Equations
- Simple Roots: Quadratics and Cubics
- Interpolation, Extrapolation, and Curve Fitting
- Fitting a Polynomial to a Set of Points
- Splines
- Cubic splines
- Data Smoothing
- Computing Derivatives and Integrals
- A. Further Reading
- General References for Algorithms
- Graphs, Graphics, and Geometry
- String Processing and Parsing
- Numerical Methods
- General Mathematics
- Probability and Statistics
- Other References
- B. ASCII Character Set
- Index
- About the Authors
- Colophon
- SPECIAL OFFER: Upgrade this ebook with OReilly