Mastering Algorithms with Perl - Helion

ebook

Autor: Jarkko Hietaniemi, John Macdonald, Jon Orwant
ISBN: 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ł)

Osoby, które kupiły tę książkę, wybierały także »

Tagi: Algorytmy - Programowanie | Perl - Programowanie | Perl/CGI - Programowanie

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

Using algorithms explained in this book, you too can carry out traditional programming tasks in a high-powered, efficient, easy-to-maintain manner with Perl.This book assumes a basic understanding of Perl syntax and functions, but not necessarily any background in computer science. The authors explain in a readable fashion the reasons for using various classic programming techniques, the kind of applications that use them, and -- most important -- how to code these algorithms in Perl.If you are an amateur programmer, this book will fill you in on the essential algorithms you need to solve problems like an expert. If you have already learned algorithms in other languages, you will be surprised at how much different (and often easier) it is to implement them in Perl. And yes, the book even has the obligatory fractal display program.There have been dozens of books on programming algorithms, some of them excellent, but never before has there been one that uses Perl.The authors include the editor of The Perl Journal and master librarian of CPAN; all are contributors to CPAN and have archived much of the code in this book there."This book was so exciting I lost sleep reading it." Tom Christiansen

Osoby które kupowały "Mastering Algorithms with Perl", wybierały także:

Zrozum struktury danych. Algorytmy i praca na danych w Javie 39,67 zł, (11,90 zł -70%)
Projektowanie oprogramowania dla zupełnie początkujących. Owoce programowania. Wydanie V 125,48 zł, (38,90 zł -69%)
Python na maturze. Kurs video. Algorytmy i podstawy j 139,00 zł, (62,55 zł -55%)
Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II 49,00 zł, (26,95 zł -45%)
Tablice informatyczne. Algorytmy 17,00 zł, (9,35 zł -45%)

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
- 1. Introduction
  - What Is an Algorithm?
    - A Sample Algorithm: Binary Search
      - What do all those funny symbols mean?
      - References
    - Adapting Algorithms
    - Generality
  - 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
- 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
  - Heaps
  - Binary Heaps
  - Janus Heap
  - The Heap Modules
  - Future CPAN Modules
- 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
  - 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?
- 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
  - 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
  - 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
    - Transitive Closure
    - Flow Networks
      - Ford-Fulkerson
      - Edmonds-Karp
    - Traveling Salesman Problem
  - CPAN Graph Modules
- 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
  - Phonetic Algorithms
    - Text::Soundex
    - Text::Metaphone
  - Stemming and Inflection
    - Modules for Stemming and Inflection
      - Text::Stem
      - Text::German
      - Lingua::EN::Inflect
      - Lingua::PT::Conjugate
  - 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
- 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
  - 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
- 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
- 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?
- 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
- 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
- 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
  - Interpolation, Extrapolation, and Curve Fitting
    - Fitting a Polynomial to a Set of Points
    - Splines
      - Cubic splines
    - Data Smoothing
- 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