Mastering Algorithms with Perl. Practical Programming Through Computer Science Jarkko Hietaniemi, John Macdonald, Jon Orwant

Kup polskie wydanie:

Spis treści książki

• 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

pokaż cały spis treści

ukryj recenzje